歐陽紅祥，劉炳勝，李 欣

(河海大學 商學院，江蘇 南京210098)

對資源進行優(yōu)化配置是保證資源合理使用的重要手段。資源優(yōu)化有兩類問題，一是資源有限工期最短問題，二是工期固定資源均衡問題。工期固定資源均衡問題理論上屬于組合優(yōu)化問題，目前解決該類問題常用的方法是啟發(fā)式算法，許多學者根據(jù)具體問題提出了多種算法。由于啟發(fā)式算法的優(yōu)化準則、算法都與特定的問題有關，因此算法的可移植性和通用性比較差。遺傳算法是一類可用于復雜系統(tǒng)優(yōu)化計算的魯棒搜索算法，與其他方法相比，具有自行概率搜索、運算并行性，以及搜索效率高等優(yōu)點。文獻［1－8］對遺傳算法在多資源均衡優(yōu)化中的應用作了一些探索，但對交叉算子及變異算子對約束條件的破壞問題沒有涉及或沒能提出較好的方法?；诖?，筆者提出了一種簡易可行的方法，對基本遺傳算法作出了較大改進。

1 多資源均衡優(yōu)化模型

2 遺傳算法

2.1 遺傳算法流程

遺傳算法是模擬生物在自然環(huán)境中的遺傳和進化過程而形成的一種自適應全局優(yōu)化概率搜索算法，它最早由美國密執(zhí)安大學的HOLLAND 教授提出。20 世紀70 年代JONG 基于遺傳算法的思想，在計算機上進行了大量的純數(shù)值函數(shù)優(yōu)化計算實驗。在一系列研究工作的基礎上，20 世紀80 年代由GOLDBERG 進行歸納總結，形成了遺傳算法的基本框架［9－10］，如圖1 所示。

圖1 遺傳算法流程圖

2.2 染色體編碼

迄今為止，人們針對實際應用問題提出了許多種不同的編碼方法，總的說來，這些編碼方法可以分為3 大類:二進制編碼、浮點數(shù)編碼和符號編碼。

2.3 適應度函數(shù)

在遺傳算法中，以個體適應度的大小來確定該個體被遺傳到下一代群體中的概率。個體的適應度越大，其被遺傳到下一代的概率也越大;反之，個體的適應度越小，其被遺傳到下一代的概率也越小。在遺傳算法中，通常采用目標函數(shù)直接作為適應度函數(shù)。

2.4 選擇運算

選擇運算的作用是從當代群體中，選擇出一些比較優(yōu)良的個體，將其復制到新一代群體中。常用的選擇運算包括:①輪盤賭選擇法;②隨機遍歷抽樣法;③局部選擇法;④競標賽選擇法。

2.5 交叉運算

交叉運算指兩個相互配對的染色體按某種方式交換其部分基因，從而形成兩個新的個體。依據(jù)個體編碼方法的不同，有兩類算法:①實值重組，包括離散重組、中間重組和線性重組等;②二進制交叉，包括單點交叉、多點交叉和均勻交叉等。

2.6 變異運算

變異運算指對群體中的每一個個體，以某一概率改變某些基因座上的基因值。依據(jù)個體編碼方法的不同，有兩類算子:①實值變異;②二進制變異。

2.7 群體大小

群體大小即群體所含個體數(shù)量，取20 ～100為宜。

3 資源均衡優(yōu)化遺傳算法及算例

某網(wǎng)絡計劃如圖2 所示，箭線上方數(shù)字為活動所需資源數(shù)量(假設項目中所有活動使用3 種資源)，箭線下方數(shù)字為活動持續(xù)時間(單位為天)，假定3 種資源的權重分別為0.2，0.4，0.4。

圖2 活動所需資源數(shù)量

3.1 計算活動的時間參數(shù)

根據(jù)給定的網(wǎng)絡計劃，采用關鍵線路法(critical path method，CPM)計算各項活動的最早開始時間(ES)和最遲開始時間(LS)?；顒訒r間參數(shù)計算結果如表1 所示。

表1 活動時間參數(shù)

3.2 浮點數(shù)編碼

考慮到資源均衡優(yōu)化目標函數(shù)以及約束條件的復雜性，筆者采用浮點數(shù)編碼方法。以活動的計劃開工時間作為決策變量，個體的編碼長度等于其決策變量的個數(shù)，個體的每個基因值用區(qū)間［ES，LS］內的一個浮點數(shù)來表示，如圖3 所示。

圖3 浮點數(shù)編碼

3.3 產生初始種群

為滿足約束條件，可按如下規(guī)則產生初始種群:①假如Pred(j)=φ，Pred(j)為活動j 的緊前活動，則在區(qū)間［ESj，LSj］內隨機生成一個計劃開工時間Sj。②若Pred(j)= i，則Sj應在區(qū)間［max{ESj，Si+Di}，LSj］內隨機取值。③依此類推，隨機產生20 個個體形成初始種群，初始種群中的所有個體都滿足兩個約束條件。

3.4 適應度函數(shù)

遺傳算法中以個體適應度的大小來評定各個個體的優(yōu)劣程度，從而決定其遺傳機率的大小。該例中，目標函數(shù)σ 總取非負值，并且是以求函數(shù)值最小為優(yōu)化目標，因此適應度函數(shù)直接取為σ。

3.5 選擇運算

筆者采用輪盤賭選擇法來選擇遺傳個體，其基本思想是:各個個體被選中的概率與其適應度大小成正比。具體過程為:①先計算出群體中所有個體的適應度總和;②計算每個個體的相對適應度大小，即為該個體被遺傳到下一代的概率;③使用模擬賭盤操作(即0 到1 的隨機數(shù))來確定各個個體被選中的次數(shù)。

3.6 交叉運算

筆者采用單點交叉算子。采用交叉算子生成的新個體，其對應活動的計劃開工時間有時會違背第2 個約束條件，因此，需對單點交叉算子進行改進。改進的思路為:從左至右逐一檢查交叉點后的基因值，若對應的計劃開工時間違反活動間的邏輯關系，則在區(qū)間［max(緊前活動計劃完工時間)，該活動最遲開工時間］內隨機抽樣取值對其進行修正，其過程如圖4 所示。

圖4 交叉算子改進示意圖

3.7 變異運算

筆者采用均勻變異算子。同樣，采用變異算子生成的新個體，其對應活動的計劃開工時間有時會違背第2 個約束條件，因此，也需對變異算子進行改進。改進的思路為:若變異點的基因值違反活動間的邏輯關系，則在區(qū)間［max(緊前活動計劃完工時間)，min(緊后活動計劃開工時間－該活動持續(xù)時間)］內隨機抽樣取值代替原來的值，其過程如圖5 所示。

圖5 變異算子改進示意圖

3.8 運算結果

利用Matlab 7.0 提供的遺傳算法工具箱，并結合具體問題編制相應的適應度函數(shù)、選擇函數(shù)、交叉函數(shù)和變異函數(shù)，優(yōu)化運行過程經(jīng)過51 代，其適應度函數(shù)值下降到4.571。優(yōu)化后各項活動的計劃開工時間如表2 所示。

表2 各項活動計劃開工時間

4 結論

遺傳算法是一類具有較好魯棒性的搜索算法，但其交叉算子和變異算子會破壞資源均衡優(yōu)化模型中的約束條件，容易產生無效解，大大降低了遺傳算法的效率，筆者研究提出一種新的方法有效地解決了上述問題。案例表明，改進后的遺傳算法優(yōu)化效果明顯。

［1］ 劉偉軍，袁劍波. 基于遺傳算法的工程項目資源優(yōu)化［J］.計算機工程與應用，2006(21):180－182.

［2］ 謝潔銳，黃忠民，俞守華，等. 一種“工期固定，資源均衡”的神經(jīng)網(wǎng)絡模型設計［J］. 計算機應用與軟件，2005，22(1):66－68.

［3］ 駱剛，劉爾烈，王健.遺傳算法在網(wǎng)絡計劃資源優(yōu)化中的應用［J］.天津大學學報，2004 (2):179－183.

［4］ LEU S S，YANG C H，HUANG J C.Resource level in gin construction by genetic algorithm－based optimization and its decision support system application［J］.Automation in Construction，2000 (10):27－41.

［5］ TAREK H.Optimization of resource allocation and leveling using genetic algorithms［J］.Journal of Construction Engineering and Management，1999(3):167－175.

［6］ 張淑山，張連營. 建設項目多資源優(yōu)化的進化算法實現(xiàn)［J］.科技進步與對策，2009(11):88－90.

［7］ 張連營，張金平，王亮.工程項目資源均衡的遺傳算法及其Matlab 實現(xiàn)［J］. 管理工程學報，2004(1):52－55.

［8］ 王首緒，周學林.遺傳算法優(yōu)化施工網(wǎng)絡計劃的多種資源均衡［J］. 重慶交通學院學報，2001(6):39－45.

［9］ 玄光男，程潤偉. 遺傳算法與工程設計［M］.北京:科學出版社，2000:78－102.

［10］雷英杰.Matlab 遺傳算法工具箱及應用［M］.西安:西安電子科技大學出版社，2005:13－67.