貪婪算法與遺傳算法結(jié)合的建設(shè)項目合同優(yōu)化選擇

李霄鵬

（齊魯工業(yè)大學(xué)（山東省科學(xué)院）管理學(xué)院，濟南 250300）

0 引言

目前對于工程領(lǐng)域優(yōu)化的研究集中于對建筑工程的項目調(diào)度和資源分配上，并使用傳統(tǒng)的解決資源平衡的方法,如CPM關(guān)鍵路徑法、網(wǎng)絡(luò)計劃法、啟發(fā)式算法等來解決不同情境下的資源均衡問題，使用遺傳算法、蟻群算法來解決復(fù)雜情況下的優(yōu)化平衡問題等。而對合同資源優(yōu)化的研究多集中在供應(yīng)鏈優(yōu)化協(xié)調(diào)領(lǐng)域，如李建斌等[1]、張秀東等[2]采用博弈論等方法研究供應(yīng)鏈柔性合同優(yōu)化問題、徐琪[3]構(gòu)建了合同與供應(yīng)鏈組合優(yōu)化決策模型等。

對前人研究成果[4-8]分析發(fā)現(xiàn)，目前關(guān)于資源優(yōu)化尤其是合同優(yōu)化的研究主要集中于供應(yīng)鏈優(yōu)化協(xié)調(diào)，針對建筑工程項目領(lǐng)域合同優(yōu)化的研究較少。本文在以上研究的基礎(chǔ)上，應(yīng)用背包問題解決合同的優(yōu)化選擇和項目的排序。并在傳統(tǒng)遺傳算法的基礎(chǔ)上進(jìn)行改進(jìn)，引入貪婪算法，使用MATLAB語言進(jìn)行編程仿真，在項目面臨的若干個合同中作出最優(yōu)選擇。

1 復(fù)雜建筑項目合同優(yōu)化模型構(gòu)建

本文采用背包問題原理構(gòu)建建筑項目合同優(yōu)化模型。0-1背包問題即從n個物品的集合中選擇部分物品，使得物品總價值最大，但總重量不超過背包容量c。將其運用在建設(shè)項目合同優(yōu)化問題上，就是在合同所需資源總和不得超過項目的總預(yù)算資源C的前提下，按照計算結(jié)果從眾多待選合同中選擇部分合同，并對其設(shè)定履行順序，進(jìn)行項目資源的合理分配，使得項目發(fā)揮的總效益最高。據(jù)此構(gòu)建目標(biāo)函數(shù)模型如下：

其中pj表示第j個合同帶來的項目效益，wj表示第j個合同所耗費的資源，xj=1表示選擇第j個合同，xj=0表示不選擇第j個合同，C表示項目總預(yù)算資源額度。根據(jù)0-1背包問題原理，用長度為n的二進(jìn)制編碼，如果項目中選擇某個合同，則對應(yīng)的值為1，否則為0。把待選合同所需資源（k為資源的權(quán)重，不同的資源權(quán)重不同，一個合同所需資源總和為wjxj）總和作為個體的適應(yīng)度。據(jù)此把項目待選合同按耗費資源數(shù)量比進(jìn)行排序，先將資源耗費少的合同選出，直至總耗費資源接近項目總資源數(shù)量，從而形成新的合同優(yōu)先級方案。

2 合同優(yōu)化數(shù)學(xué)模型的遺傳算法實現(xiàn)

使用背包問題求解優(yōu)化方案的算法很多。有的算法比較精確，如常用的分支定界法、動態(tài)規(guī)劃法等算法，有的算法則屬于近似算法，如使用蟻群算法、遺傳算法、神經(jīng)網(wǎng)絡(luò)算法來求解背包問題。本文選擇遺傳算法進(jìn)行數(shù)據(jù)處理和仿真。

2.1 遺傳算法及改進(jìn)

遺傳算法簡稱為GA，它是一種模擬方法，使用數(shù)學(xué)模型來模仿生物的一系列進(jìn)化過程。生物進(jìn)化是通過染色體作為遺傳基因的承載體，遺傳算法則用一串?dāng)?shù)組來模擬染色體，并通過對染色體的操作和選取，對問題進(jìn)行優(yōu)化以獲得相對最優(yōu)解。它是基于自然進(jìn)化選擇和基因遺傳的原理來進(jìn)行搜索的優(yōu)化設(shè)置，很適合解決優(yōu)化計算問題，目前已經(jīng)應(yīng)用于人口模型構(gòu)建、工程資源、通訊網(wǎng)絡(luò)優(yōu)化等多種領(lǐng)域[11]，還將在解決人工生命的進(jìn)化模型和復(fù)雜系統(tǒng)的模擬設(shè)計中進(jìn)行廣泛應(yīng)用。

雖然遺傳算法和編碼方法可以方便對背包模型和適應(yīng)度進(jìn)行計算，但是在基本遺傳算法運算過程中有一定的局限性，在使用交叉變異進(jìn)行進(jìn)化得到新的進(jìn)化種群時，容易出現(xiàn)致死染色體，在迭代進(jìn)化過程中其獲取的解會降低多樣性，精確度有限并容易得到局部最優(yōu)解。為了避免這些問題，目前一般采用罰函數(shù)進(jìn)行迭代處理和優(yōu)化。但由于使用規(guī)模的限制，罰函數(shù)不能用于數(shù)量較大的問題求解，故可選用其他算法對遺傳算法進(jìn)行改進(jìn)以求獲得合適的最優(yōu)解。目前對遺傳算法進(jìn)行改進(jìn)的方法主要有以下幾種[12-15]：

（1）將遺傳算法與啟發(fā)式搜索算法貪心算法結(jié)合改良性能。

（2）對遺傳算法通過禁忌搜索進(jìn)行變動擴大了搜索主框架。

（3）使用二重結(jié)構(gòu)編碼開發(fā)混合遺傳算法。

（4）將傳統(tǒng)算法如雜交與遺傳算法相結(jié)合。

（5）使用變換算子來代替交叉算子。

本文選擇將遺傳算法和貪婪算法結(jié)合起來進(jìn)行使用，構(gòu)建使用背包問題的合同組合優(yōu)化模型，避免了局部最優(yōu)解的漏洞，并得出最終最優(yōu)解[16]。貪婪算法屬于啟發(fā)式算法的一種，每次使用貪婪規(guī)則進(jìn)行決策，其結(jié)果都是不可撤銷的。貪婪算法沒有很多可行解的同步選擇，最終只能得到一個最優(yōu)的可行解。使用貪婪算法進(jìn)行遺傳算法求解，其所獲得的解精確度更高，更接近最優(yōu)解。將其應(yīng)用在合同選擇中，即每次進(jìn)化選取一個中標(biāo)合同，直到實現(xiàn)項目資源的完全利用。比較常用的貪婪準(zhǔn)則參數(shù)是價值密度參數(shù)，也稱為貪婪策略，即在諸多建筑工程項目投標(biāo)合同中，選擇可以適合項目的價值c/w值最大的合同。

2.2 結(jié)合貪婪算法的遺傳算法求解流程

本問題求解的流程如下：

（1）通過基因編碼將問題空間變成遺傳空間?；蚓幋a可以將若干個基因碼按照一定的順序進(jìn)行排列，其排列順序就是遺傳編碼結(jié)構(gòu)。選擇二進(jìn)制編碼進(jìn)行表述，編碼串中1表示將選中的投標(biāo)合同，0表示未選中合同。如“110111”就代表一套合適的分包商選擇方案和資源分配方式，它表示選擇第1，2，4，5，6號投標(biāo)合同簽訂最終協(xié)議，并分配合同資源。

（2）使用貪婪算法對初始編碼進(jìn)行修復(fù)?；镜倪z傳算法雖然可以通過對編碼串進(jìn)行操作，從當(dāng)前的群體中選擇出具有優(yōu)良基因的染色體使其延續(xù)下去，但它們并不一定是最滿足限制條件的可行解。為了避免產(chǎn)生無效染色體，本文使用貪婪算法對初始形成的編碼進(jìn)行修正來獲得合適的最優(yōu)解。

貪婪算法修復(fù)的基本思想為：選定一個合適的參數(shù)資源效益比值（C/W)為參照，在項目入圍的所有投標(biāo)合同中，計算待選合同所帶來的效益及所耗費的資源的比值，將結(jié)果最小的合同選擇出來，直到滿足項目限定范圍的資源限制為止。經(jīng)過迭代過程可獲得一些新的基因編碼串，這些新編碼串所代表的合同選擇相對更優(yōu)，而且能夠滿足項目所面臨的條件的限制。

（3）選擇適應(yīng)度函數(shù)。由于將貪婪算法和遺傳算法進(jìn)行結(jié)合，彌補了遺傳算法中產(chǎn)生無效染色體的情形，故不必使用罰函數(shù)法，而是確定適應(yīng)度函數(shù)對個體的適應(yīng)度進(jìn)行計算，并進(jìn)行進(jìn)化和淘汰。背包問題中常用的適應(yīng)度值是物品價值和目標(biāo)值，本文直接選取目標(biāo)值作為適應(yīng)度函數(shù)值，公式為：

（4）輪盤賭選擇。

對于基因的選擇方法有很多。本文采用輪盤賭方法進(jìn)行選擇。為了避免適應(yīng)度函數(shù)為負(fù)值并防止有效信息的丟失，使用公式fi(i)=fit(i)-min(fit)+1對適應(yīng)值進(jìn)行處理，以獲得合適的信息。

（5）使用交叉概率參數(shù)進(jìn)行交叉。本文采用交叉概率pc=0.5，并選擇一點為交叉點，使用單點交叉方式，隨機選取一點作為基因的交叉點，設(shè)交叉概率pc=0.5。

（7）對形成的新種群使用迭代方法繼續(xù)進(jìn)化下去，直到獲得最優(yōu)組合。

3 算例

本文選取以某大型海外工程設(shè)備項目作為算例進(jìn)行分析，從項目存儲的招投標(biāo)數(shù)據(jù)集中，選用投標(biāo)合同100份，作為待選樣本。由于不同的投標(biāo)合同，投標(biāo)商的資質(zhì)信用能力各方面存在差異，所消耗的資源種類也有差別。故通過專家評價和歸一化方法，將不同的合同所代表的資源和為項目所產(chǎn)生的效益以統(tǒng)一的數(shù)值來表示，其中c代表合同中的資源，value代表合同的效益，m1代表項目預(yù)期要投入的總成本，構(gòu)建模型進(jìn)行分析。

3.1 遺傳算法建模

在使用遺傳算法對合同選擇進(jìn)行優(yōu)化的時候，使用基因?qū)?yīng)每個待選合同，而基因值則代表合同簽訂所需投入的資源。

（1）初始化合同所消耗的資源c和所帶來的效益value，數(shù)值如下（單位為萬元）：

本文用g代表合同所耗費的項目資源及合同為項目所帶來的效益的比值，得到g值如下：

設(shè)項目的預(yù)算總資源值為m1=1000萬元。則目標(biāo)如下：

第一，希望選出一組合同i1,i2,i3,…

（2）使用遺傳算法＋貪婪算法修正對問題進(jìn)行求解。

1）大型設(shè)備和課桌椅放置在一起不現(xiàn)實。若要真正實現(xiàn)學(xué)生技能訓(xùn)練，按照五人一組，40人一班計算，需要八套設(shè)備。設(shè)備以汽車為例，試想一下需要占據(jù)多大的空間？需要多大的教室？所以一些學(xué)校真實的做法就是擺上一套設(shè)備裝裝樣子，實際使用率很低。

本文采用matlab編制目標(biāo)函數(shù)文件，使用貪婪算法進(jìn)行修正，貪婪算法的處理為：

（3）確定適應(yīng)度函數(shù)：根據(jù)算法的特點，要將初始的目標(biāo)函數(shù)換算為適應(yīng)度函數(shù)，當(dāng)函數(shù)值最小時，所獲得的結(jié)果即為最優(yōu)解。將適應(yīng)度函數(shù)用目標(biāo)函數(shù)值來表示，公式為：

（4）初始化和參數(shù)設(shè)定。選擇輪盤賭方法進(jìn)行選擇，并產(chǎn)生要配對的父代的序號，經(jīng)過N次順序調(diào)換，將原有順序打亂，使相鄰兩個個體作為交叉的父代。

（5）變異，計算出適應(yīng)度最大的合同和適應(yīng)度最小的合同。本文選擇的參數(shù)值是pc=0.5，pm=0.01。

3.2 仿真及結(jié)果分析

本文將參數(shù)按上述步驟輸入Matlab程序進(jìn)行仿真，選擇種群大小150，代數(shù)500代，變異概率0.01為參數(shù)進(jìn)行計算。程序運行耗時10.6秒。

隨著種群進(jìn)化，最佳合同組合的效益也在不斷提高，演化軌跡如圖1所示。

圖1 最佳合同演化軌跡圖

可以看出程序在330代之后開始收斂。得到結(jié)果如下，最優(yōu)方案編碼為：

對應(yīng)合同排列序號為：

（1）合同的成本和收益：

合同成本

合同收益

（2）總成本和總效益：

此時Ctotal非常接近我們總成本1000，說明此時資源利用率是最高的。表1列出了該項目優(yōu)先選出的前25個合同。

表1 前25個合同優(yōu)化序列

4 結(jié)論

對于大型建筑工程項目，如何合適的選擇合同進(jìn)行簽約，以及簽約后如何排列履行合同的先后順序，合同選擇方案不同，會影響到整個項目最終實施，并對后續(xù)項目的成功完成和客戶滿意度提高具有重要意義。本文采用遺傳算法特有的模擬技術(shù)，使用數(shù)學(xué)模型來模擬合同的優(yōu)化選擇策略，根據(jù)進(jìn)化選擇和基因遺傳的原理，進(jìn)行搜索設(shè)置，從而找到最合適的合同群組。遺傳算法與神經(jīng)網(wǎng)絡(luò)技術(shù)及其他技術(shù)相比，具有所需的信息量少的優(yōu)勢，更適合應(yīng)用于信息有限的合同前期。將遺傳算法和貪婪算法結(jié)合，則可以避免選擇局部最優(yōu)的合同，從而得出整體的合同組合優(yōu)化策略。該合同優(yōu)化方法可以運用于大型工程項目尤其是海外大型項目的實際合同管理過程中，具有重要的實踐意義。