基于間隔率和遺傳算法的多資源均衡優(yōu)化研究

歐陽紅祥，陳偉偉，李 欣

(1.河海大學(xué) 商學(xué)院，江蘇 南京210098;2.中石化集團(tuán)管道儲(chǔ)運(yùn)分公司 南京輸油處，江蘇 南京210046)

資源優(yōu)化有兩類問題，一類是資源有限工期最短問題，另一類是工期固定資源均衡問題。工期固定資源均衡問題按涉及的資源種類數(shù)，可分為單資源和多資源均衡問題。工期固定資源均衡問題理論上屬于組合優(yōu)化問題，目前解決這類問題常用的方法有解析式法、啟發(fā)式算法及智能優(yōu)化算法［1］。解析式算法只適用于較小規(guī)模、較少資源的優(yōu)化。啟發(fā)式算法可以求解大規(guī)模資源均衡問題，但由于其優(yōu)化準(zhǔn)則、算法都與特定的問題有關(guān)，因此算法的可移植性和通用性較差［2］。智能優(yōu)化算法主要包括遺傳算法、模擬退火算法、螞蟻算法，以及神經(jīng)網(wǎng)絡(luò)等。遺傳算法是一類可用于復(fù)雜系統(tǒng)優(yōu)化計(jì)算的魯棒搜索算法，與其他方法相比，其具有自行概率搜索、運(yùn)算并行性，以及搜索效率高等優(yōu)點(diǎn)［3］，因此許多學(xué)者借助遺傳算法來求解資源均衡問題，并取得了豐富的成果。在以往的許多研究中，學(xué)者們往往基于項(xiàng)目各作業(yè)的開工時(shí)間進(jìn)行編碼，這種編碼方式容易導(dǎo)致在求解過程中產(chǎn)生不滿足作業(yè)間邏輯關(guān)系約束的非可行解。目前解決的辦法有兩種：一是通過修復(fù)算子對(duì)不滿足作業(yè)間邏輯約束的非可行解進(jìn)行修復(fù);二是通過特定的編碼方式來避免求解過程中產(chǎn)生違反作業(yè)間邏輯關(guān)系約束的非可行解［4］。相比較而言，后一種辦法效率更高。基于此，筆者提出了一種基于間隔率的編碼與解碼方法，可以避免在交叉、變異等遺傳操作中出現(xiàn)違反作業(yè)間邏輯關(guān)系的情況，從而大大提高遺傳算法解決該類問題的尋優(yōu)速度。

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

1.1 假設(shè)和定義

假設(shè)1 各項(xiàng)活動(dòng)在優(yōu)化過程中是不可拆分的，其持續(xù)時(shí)間是固定的;各項(xiàng)活動(dòng)所需資源種類數(shù)和數(shù)量在優(yōu)化過程中保持不變。

假設(shè)2 在優(yōu)化過程中，項(xiàng)目的總工期不變，并且在任一時(shí)間段內(nèi)，各種資源的供應(yīng)量足夠多，可滿足需求。

定義1V={1，2，…，N}為網(wǎng)絡(luò)計(jì)劃中所有活動(dòng)的集合，Di和LSi為活動(dòng)i的持續(xù)時(shí)間和最遲開始時(shí)間，Pred(i)為由活動(dòng)i的緊前活動(dòng)組成的集合，Si和Fi分別為活動(dòng)i的計(jì)劃開始時(shí)間和計(jì)劃完成時(shí)間。為滿足既定的邏輯關(guān)系和總工期不變的要求，Si∈［max(Fh)，LSi］，其中，h∈Pred(i)，i∈V?；顒?dòng)i的計(jì)劃開始時(shí)間的取值范圍如圖1 所示。

定義2 稱PFi為間隔率，PFi= (Si-max(Fh))/(LSi-max(Fh))。從圖1 可以看出，0≤PFi≤1。若PFi=0，則表示活動(dòng)i的計(jì)劃開始時(shí)間與緊前活動(dòng)h的計(jì)劃完成時(shí)間相等，也即活動(dòng)h按計(jì)劃完成后，活動(dòng)i立即開始。若PFi=1，則意味著活動(dòng)i的計(jì)劃開始時(shí)間與其最遲開始時(shí)間相等。

定義3 假如某一項(xiàng)目需要K種資源(如材料、設(shè)備等)，第i項(xiàng)活動(dòng)單位時(shí)間內(nèi)所需第k種資源數(shù)量記為項(xiàng)目總工期記為T，第t時(shí)刻項(xiàng)目所需第k種資源數(shù)量記為

圖1 活動(dòng)i 的計(jì)劃開始時(shí)間的取值范圍

1.2 優(yōu)化模型描述

多資源均衡優(yōu)化的目標(biāo)是尋找各項(xiàng)活動(dòng)的計(jì)劃開始時(shí)間，使得在項(xiàng)目總工期內(nèi)各種資源需要量盡可能均衡。用于評(píng)價(jià)資源均衡效果的指標(biāo)主要有不均衡系數(shù)、方差、最大絕對(duì)離差和極差值這4 種［5-6］。由于方差更能體現(xiàn)項(xiàng)目在各時(shí)刻資源需求的不均衡程度，因此，筆者選擇該指標(biāo)用于評(píng)價(jià)資源需求均衡程度。

假如第k種資源需求的方差用δ(k)表示，則：

對(duì)于多資源均衡問題，由于資源的重要性有所差別，因此可采用不同的權(quán)重系數(shù)來反映其對(duì)目標(biāo)函數(shù)的影響程度。為消除不同資源在數(shù)量等級(jí)、單位等方面的差異，需要對(duì)資源量進(jìn)行標(biāo)準(zhǔn)化處理［7-8］。對(duì)數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化處理的方法有很多，筆者采用極小-極大化方法。設(shè)為第k種資源需要量的最大值，則若用表示第k種資源需要量的最小值，則第t時(shí)刻項(xiàng)目所需第k種資源數(shù)量經(jīng)過極小-極大化變化后變成為可按式(3)進(jìn)行計(jì)算。

第k種資源需要量的平均值ˉR(k)經(jīng)過極小-極大化變化后變成ˉR(k)'，則：

通過上述變換后，各種資源需要量的取值都在區(qū)間［0，1］內(nèi)，并且變成了一個(gè)無量綱的數(shù)，從而消除了資源在數(shù)量級(jí)、單位等方面對(duì)目標(biāo)函數(shù)取值的影響。

綜上所述，多資源均衡的目標(biāo)函數(shù)可定義為：

約束條件為：

式(5)中，ω(k)為選定的一組權(quán)系數(shù)，滿足，其他符號(hào)同前。

2 遺傳算法

遺傳算法是模擬生物在自然環(huán)境中的遺傳和進(jìn)化過程而形成的一種自適應(yīng)全局優(yōu)化概率搜索算法，它最早由美國密執(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é)，形成了遺傳算法的基本框架。遺傳算法的基本運(yùn)算過程如下［9-10］：

(1)初始化。令進(jìn)化代數(shù)計(jì)數(shù)器t=0，最大進(jìn)化代數(shù)為T，隨機(jī)生成M個(gè)個(gè)體作為初始群體P(t);

(2)個(gè)體評(píng)價(jià)。計(jì)算群體P(t)中各個(gè)個(gè)體的適應(yīng)度;

(3)選擇運(yùn)算。通過選擇運(yùn)算選出最優(yōu)的個(gè)體直接遺傳到下一代;

(4)交叉運(yùn)算。通過配對(duì)交叉產(chǎn)生新的個(gè)體;

(5)變異運(yùn)算。將個(gè)體串中某些基因座上的基因值作出變動(dòng);群體P(t)經(jīng)過選擇、交叉和變異運(yùn)算之后得到下一代群體P(t+1)。

(6)終止條件判斷。若t=T，則以進(jìn)化過程中所得到的具有最大適應(yīng)度個(gè)體作為最優(yōu)解輸出，終止計(jì)算。

3 算例

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

圖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)。

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

考慮到資源均衡優(yōu)化目標(biāo)函數(shù)和約束條件的復(fù)雜性，筆者采用浮點(diǎn)數(shù)編碼方法。以各項(xiàng)活動(dòng)的間隔率(PF)作為決策變量，個(gè)體的每個(gè)基因值用區(qū)間［0，1］內(nèi)的一個(gè)浮點(diǎn)數(shù)來表示。各項(xiàng)活動(dòng)的浮點(diǎn)數(shù)編碼如表1 所示。由間隔率的定義可知，可行解集合{PFi}對(duì)應(yīng)唯一的計(jì)劃開始時(shí)間序列S。

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

3.3 染色體解碼

染色體解碼的實(shí)質(zhì)是將各活動(dòng)的間隔率轉(zhuǎn)換成對(duì)應(yīng)的計(jì)劃開始時(shí)間。解碼的規(guī)則如下：

3.4 選擇運(yùn)算

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

3.5 交叉運(yùn)算

筆者采用單點(diǎn)交叉算子，具體執(zhí)行過程如下：①對(duì)群體中的個(gè)體進(jìn)行兩兩隨機(jī)配對(duì);②隨機(jī)設(shè)置交叉點(diǎn)位置;③依預(yù)先設(shè)定的概率(p=0.8)，互換交叉點(diǎn)后的基因值，形成兩個(gè)新的個(gè)體。

3.6 變異運(yùn)算

采用均勻變異算子，具體操作過程如下：①指定個(gè)體編碼串中的某個(gè)基因座為變異點(diǎn);②依預(yù)先設(shè)定的概率(p=0.05)從對(duì)應(yīng)基因的取值范圍［0，1］中隨機(jī)取一數(shù)值代替原數(shù)值。

3.7 運(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ù)值下降到3.201。優(yōu)化后各項(xiàng)活動(dòng)的計(jì)劃開工時(shí)間如表2 所示。各資源需求量優(yōu)化前后的對(duì)比如圖3 和圖4 所示。資源1 的方差由37.7 下降到2.8，資源2 的方差由7.71 下降到4.14。

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

圖3 第1 種資源優(yōu)化前/后需求量對(duì)比

圖4 第2 種資源優(yōu)化前/后需求量對(duì)比

4 結(jié)論

遺傳算法是一類具有較好魯棒性的搜索算法，由于其模型簡單、易于實(shí)現(xiàn)、無需梯度信息和參數(shù)少等特點(diǎn)使其在組合優(yōu)化問題中顯示出良好的求解效果。筆者將遺傳算法引入到資源均衡優(yōu)化問題中，建立了基于間隔率的資源均衡優(yōu)化模型，從而避免了在優(yōu)化過程中容易產(chǎn)生無效解的情況，大大提高了優(yōu)化效率。在此基礎(chǔ)上，敘述了算法流程，并通過算例證明所引入的算法具有一定的可行性和有效性，為工程項(xiàng)目實(shí)施中的資源安排提供了一種新的思路和方法。同時(shí)，研究過程也表明，優(yōu)化結(jié)果與參數(shù)的選擇有很大關(guān)系，因此，如何融合其他算法對(duì)現(xiàn)有模型進(jìn)行改進(jìn)，使其具有更好的全局收斂性，還有待進(jìn)一步研究。

［1］HARRIS R B. Packing method for resource leveling［J］. Journal Construction Engineering and Management，1990，116(2)：331 -350.

［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 leveling in 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］張淑山，張連營. 建設(shè)項(xiàng)目多資源優(yōu)化的進(jìn)化算法實(shí)現(xiàn)［J］.科技進(jìn)步與對(duì)策，2009(11)：88 -90.

［7］張連營，張金平，王亮.工程項(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］玄光男，程潤偉.遺傳算法與工程設(shè)計(jì)［M］. 北京：科學(xué)出版社，2000：43 -98.

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