歐陽(yáng)紅祥，劉炳勝，李 欣

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

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

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

2 遺傳算法

2.1 遺傳算法流程

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

圖1 遺傳算法流程圖

2.2 染色體編碼

迄今為止，人們針對(duì)實(shí)際應(yīng)用問題提出了許多種不同的編碼方法，總的說(shuō)來(lái)，這些編碼方法可以分為3 大類:二進(jìn)制編碼、浮點(diǎn)數(shù)編碼和符號(hào)編碼。

2.3 適應(yīng)度函數(shù)

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

2.4 選擇運(yùn)算

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

2.5 交叉運(yùn)算

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

2.6 變異運(yùn)算

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

2.7 群體大小

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

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

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

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

3.1 計(jì)算活動(dòng)的時(shí)間參數(shù)

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

表1 活動(dòng)時(shí)間參數(shù)

3.2 浮點(diǎn)數(shù)編碼

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

圖3 浮點(diǎn)數(shù)編碼

3.3 產(chǎn)生初始種群

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

3.4 適應(yīng)度函數(shù)

遺傳算法中以個(gè)體適應(yīng)度的大小來(lái)評(píng)定各個(gè)個(gè)體的優(yōu)劣程度，從而決定其遺傳機(jī)率的大小。該例中，目標(biāo)函數(shù)σ 總?cè)》秦?fù)值，并且是以求函數(shù)值最小為優(yōu)化目標(biāo)，因此適應(yīng)度函數(shù)直接取為σ。

3.5 選擇運(yùn)算

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

3.6 交叉運(yùn)算

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

圖4 交叉算子改進(jìn)示意圖

3.7 變異運(yùn)算

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

圖5 變異算子改進(jìn)示意圖

3.8 運(yùn)算結(jié)果

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

表2 各項(xiàng)活動(dòng)計(jì)劃開工時(shí)間

4 結(jié)論

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

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

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

［3］ 駱剛，劉爾烈，王健.遺傳算法在網(wǎng)絡(luò)計(jì)劃資源優(yōu)化中的應(yīng)用［J］.天津大學(xué)學(xué)報(bào)，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íng). 建設(shè)項(xiàng)目多資源優(yōu)化的進(jìn)化算法實(shí)現(xiàn)［J］.科技進(jìn)步與對(duì)策，2009(11):88－90.

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

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

［9］ 玄光男，程潤(rùn)偉. 遺傳算法與工程設(shè)計(jì)［M］.北京:科學(xué)出版社，2000:78－102.

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