貪婪算法與遺傳算法結合的建設項目合同優化選擇

李霄鵬

（齊魯工業大學（山東省科學院）管理學院，濟南 250300）

0 引言

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

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

1 復雜建筑項目合同優化模型構建

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

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

2 合同優化數學模型的遺傳算法實現

使用背包問題求解優化方案的算法很多。有的算法比較精確，如常用的分支定界法、動態規劃法等算法，有的算法則屬于近似算法，如使用蟻群算法、遺傳算法、神經網絡算法來求解背包問題。本文選擇遺傳算法進行數據處理和仿真。

2.1 遺傳算法及改進

遺傳算法簡稱為GA，它是一種模擬方法，使用數學模型來模仿生物的一系列進化過程。生物進化是通過染色體作為遺傳基因的承載體，遺傳算法則用一串數組來模擬染色體，并通過對染色體的操作和選取，對問題進行優化以獲得相對最優解。它是基于自然進化選擇和基因遺傳的原理來進行搜索的優化設置，很適合解決優化計算問題，目前已經應用于人口模型構建、工程資源、通訊網絡優化等多種領域[11]，還將在解決人工生命的進化模型和復雜系統的模擬設計中進行廣泛應用。

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

（1）將遺傳算法與啟發式搜索算法貪心算法結合改良性能。

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

（3）使用二重結構編碼開發混合遺傳算法。

（4）將傳統算法如雜交與遺傳算法相結合。

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

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

2.2 結合貪婪算法的遺傳算法求解流程

本問題求解的流程如下：

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

（2）使用貪婪算法對初始編碼進行修復。基本的遺傳算法雖然可以通過對編碼串進行操作，從當前的群體中選擇出具有優良基因的染色體使其延續下去，但它們并不一定是最滿足限制條件的可行解。為了避免產生無效染色體，本文使用貪婪算法對初始形成的編碼進行修正來獲得合適的最優解。

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

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

（4）輪盤賭選擇。

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

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

（7）對形成的新種群使用迭代方法繼續進化下去，直到獲得最優組合。

3 算例

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

3.1 遺傳算法建模

在使用遺傳算法對合同選擇進行優化的時候，使用基因對應每個待選合同，而基因值則代表合同簽訂所需投入的資源。

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

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

設項目的預算總資源值為m1=1000萬元。則目標如下：

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

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

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

本文采用matlab編制目標函數文件，使用貪婪算法進行修正，貪婪算法的處理為：

（3）確定適應度函數：根據算法的特點，要將初始的目標函數換算為適應度函數，當函數值最小時，所獲得的結果即為最優解。將適應度函數用目標函數值來表示，公式為：

（4）初始化和參數設定。選擇輪盤賭方法進行選擇，并產生要配對的父代的序號，經過N次順序調換，將原有順序打亂，使相鄰兩個個體作為交叉的父代。

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

3.2 仿真及結果分析

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

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

圖1 最佳合同演化軌跡圖

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

對應合同排列序號為：

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

合同成本

合同收益

（2）總成本和總效益：

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

表1 前25個合同優化序列

4 結論

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