基于ACO算法的建設項目施工多目標優(yōu)化

胡瀟

摘要：本文通過分析網絡計劃中的邏輯關系，構建求解施工項目多目標優(yōu)化的數(shù)學模型。將施工網絡圖模型抽象為螞蟻覓食模型，運用ACO算法求解較優(yōu)的施工模式路徑組合，并利用Pareto思想選擇保留較優(yōu)的組合。最后，利用一個算例證明了智能化的蟻群算法可以克服傳統(tǒng)多目標優(yōu)化結果單一并且受人為因素影響的缺點，從而實現(xiàn)提高優(yōu)化效率、優(yōu)化運算結果。

Abstract： In this paper， a mathematical model for multi-objective optimization of construction projects is constructed by analyzing the logic relationship in network planning. The construction network graph model is abstracted as an ant foraging model. The ACO algorithm is used to solve the optimal construction mode path combination. And the Pareto thought is used to select the optimal combination. In the last， this manuscript uses an example to prove that intelligent ant colony optimization algorithm can overcome the shortage that the result of traditional multi-objective optimization is single and is easily affected by man-made factors. As well as the ant colony optimization can achieve the goal of improving the efficiency of optimization and optimizing operation results.

關鍵詞：建設項目;ACO算法;施工網絡計劃;多目標優(yōu)化

Key words： construction project;the ACO algorithm;the construction network plan;multi-objective optimization

中圖分類號：TP18? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文獻標識碼：A? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文章編號：1006-4311（2018）34-0103-04

0? 引言

項目管理是實現(xiàn)工期、成本、質量、安全、環(huán)境等多目標優(yōu)化的管理，而對于網絡計劃多目標優(yōu)化的方式大體有三種。第一種是傳統(tǒng)數(shù)學理論，包括約束法、權重法、距離函數(shù)法、最小最大法等。第二種是利用網絡計劃技術，主要是結合CPM和PERT。第三種是智能化方法，在其蓬勃發(fā)展的今天，智能化算法也越來越多地用于求解多目標的優(yōu)化問題。

本文通過對施工網絡計劃中邏輯關系的研究，明確了建設項目工期、成本、質量、安全、綠色度的數(shù)學模型，并建立了以耗費工期最短，使用成本最少，質量最好，安全度高，綠色度最高作為目標函數(shù)。通過對蟻群群算法覓食模型的研究，并結合到建設項目施工網絡圖中，將網絡計劃圖各個節(jié)點依次編號，抽象為旅行商問題，實現(xiàn)了智能求解多目標優(yōu)化問題，可以篩選出滿足安全條件的施工模式組合，克服了人工隨機組合的局限性和隨機性。

1? 網絡計劃技術五大目標的數(shù)學模型

1.1 工期優(yōu)化

在網絡計劃中，工程實施工期的控制性因素是關鍵線路，所以減短工期的關鍵是關注關鍵線路。工期數(shù)學模型如下：

作節(jié)點所需要的時間;

Tq—工程項目最大總工期限。

1.2 成本優(yōu)化

直接成本、間接成本、工程延期賠償費構成工程成本的主要部分。直接費用中包括人工費、原材料費、機械的使用費、其他直接費以及現(xiàn)場經費工程項目的。間接費用指完成施工任務所需費用中除去直接費以外的部分。成本數(shù)學模型如下：

2? 蟻群算法

由于受到螞蟻群能夠發(fā)現(xiàn)從蟻巢走到食物源的最短路徑現(xiàn)象的引導，意大利的學者M.Dorigo[2]等人于1992年提出了螞蟻系統(tǒng)，這是一種基于種群的模擬進化算法，并證明此方法能夠很好的解決旅行商等問題。

2.1 蟻群算法的基本原理

螞蟻在尋覓食物時，能在它們經過的路徑上釋放一種叫做“信息素”的物質，并且使得一定范圍內的其他螞蟻能夠感知到并朝這種物質濃度高的地方移動。在某一個點上，如果一只螞蟻要從不同的路徑中選擇一條路徑，那么那些被之前走過的螞蟻大量選擇的路徑被后來的螞蟻選中的概率會更大，路徑上留有較多的信息素的代表著達到目標的較短的路徑。

2.2 蟻群算法的數(shù)學模型

蟻群算法基本參數(shù)：m表示人工螞蟻的數(shù)量;n表示城市數(shù)量;dij表示兩個城市之間的距離，i，j？綴（1，n）;？子ij（t）表示在t時刻路過的螞蟻群在路徑ij上殘留下的信息素含量地多少，設？子ij（0）=C;螞蟻選擇路徑的概率公式如下[3]：

式中：？琢為信息啟發(fā)式因子，表示對應的路徑的相對重要性;？茁為期望啟發(fā)式因子，表示螞蟻由城市i轉移到城市j的期望值的相對重要性;為在t時刻，螞蟻k可以選擇走的城市;tabuk（k=1，2，3…m）為禁忌表，記錄螞蟻k當前已經走過的城市;？濁ij為啟發(fā)式信息，表示螞蟻由城市i轉移到城市j的期望值。

3? Pareto解個體適應值計算

利用Pareto最優(yōu)解對解排序并賦適應值，計算共享函數(shù)值，將Pareto最優(yōu)解均布于非劣最優(yōu)域。下面采用與類似的分類原理。

①通過非劣分層的方法將種群P分為？籽組;

②第一層定義為最優(yōu)非劣組，賦予第一層中的每個個體適應值為fi=N（N為種群個數(shù)）;

③每層內都使用共享函數(shù)的方法，首先計算第一層中個體i與個體j標準化的歐拉距離

⑦第二層中每個個體原始適應值為fi=N-？籽/N，按照第一層的方法調整第二層中的個體適應值，以此類推。

4? 基于ACO算法的建設項目多目標優(yōu)化

4.1 算例

選用一個算例來說明蟻群算法用于此問題的有效性以及建立的應用模型的準確性。本文采用文獻[1]中所用算例，其邏輯關系及各方面的數(shù)據(jù)見文獻[1]中所示。算例網絡圖如圖1。

4.2 算法模型建立

將網絡計劃圖中的每一個節(jié)點按順序編號，每一個節(jié)點對應的工作模式也分別編號。模型圖如圖2所表示，節(jié)點的編號為S1-Sm，矩形框內序列表示每個節(jié)點所對應的不同的工作模式的編號。把每個節(jié)點看作一級，每個節(jié)點都對應一定數(shù)目的工作模式，從第一級到最后一級工作節(jié)點，就是在每一級下隨機選擇一個工作模式的編號，他們之間的連線就可以看成一個工作模式組合解。

螞蟻在各個點之間移動的時候，根據(jù)目標函數(shù)判斷路徑上的信息素量的多少，引導螞蟻移動方向。經過一段時間的運行，滿足目標函數(shù)要求的組合路徑信息素比較多。螞蟻從工作節(jié)點S1到Sm的狀態(tài)轉移公式如下：

式（8）可以看出，在多次循環(huán)后，各個節(jié)點處的信息素的增量由解的質量決定，若對應的質量好、安全度高、工期短、成本低、綠色度高，則增加的信息素的量比較多，相反則增加的信息素含量低。通過對各節(jié)點上信息素的分配，整個系統(tǒng)能夠得到多個目標條件下較優(yōu)解的目的。

4.3 蟻群算法求解多目標優(yōu)化步驟

①初始化目標函數(shù)的參數(shù)、蟻群算法的參數(shù)包括螞蟻的個數(shù)、節(jié)點的數(shù)目等以及螞蟻的初始位置。

②建立外部種群，初始化迭代次數(shù)T=0。

③螞蟻開始遍歷各個節(jié)點處，進行搜索，T=T+1。

④根據(jù)4.2所示方法計算每條路徑組合的目標函數(shù)適應值，并保留Pareto較優(yōu)解組合到外部種群中。

⑤根據(jù)公式（8）更新各個節(jié)點信息素含量。

⑥若迭代次數(shù)達到要求，輸出外部種群，即pareto較優(yōu)解組合，若迭代次數(shù)不足，則返回第③步。

4.4 運行結果

在一次運行中可以獲得43組Pareto最優(yōu)解，將Pareto解在三維坐標里顯示，如圖3、圖4。

部分Pareto解如表1所示。

5? 結語

本文在前人探索的基礎上總結了網絡計劃包含的邏輯關系，并根據(jù)其中的邏輯關系建立了施工項目多目標優(yōu)化的數(shù)學模型;將網絡計劃的優(yōu)化轉化為蟻群算法的覓食模型;最后通過仿真實驗得到了較優(yōu)的施工模式組合，與免疫遺傳粒子群算法比較得到的解更優(yōu)，驗證了ACO算法用于此類問題的正確性與合理性。

參考文獻：

[1]楊森.基于免疫遺傳粒子群算法的工程項目多目標綜合優(yōu)化研究[D].西安建筑科技大學碩士論文，2014.

[2]Dorigo M， Gambardella L M.Ant colony system： a cooperative learning approach to the traveling salesman problem[J].IEEE Transactions on Evolutionary Computation，1997，1（1）：53-56.

[3]李彥蒼，周書敬，吳超.仿生智能算法及其在土木工程中的應用[M].北京：科學出版社，2015：1-3.

[4]Colorni A， Dorigo M， Maniezzo V. Ant colony system for job-shop scheduling[J]. Belgian J of Operations Research Statistics and Computer Science， 1994，34（1）：39-53.

[5]Dorigo M， Maniezzo V， Colorni A. The ant system： Optimization by a colony of cooperating agents[J]. IEEE Trans on smc，1996，26（1）：28-41.

[6]張勇德，黃莎白.多目標優(yōu)化問題的蟻群算法研究[J].控制與決策，2005，20（2）：170-176.

[7]劉曉峰，陳通，張連營.基于微粒群算法的工程項目質量、費用和工期綜合優(yōu)化[J].土木工程學報，2006，39（10）：122-126.

[8]陸寧，馮妍萍，王芳，王小萌，俞允凱，王森浩.單位工程四大目標的可靠度綜合控制[J].西安建筑科技大學學報（自然科學版），2007（05）.

[9]胡華選.網絡計劃工期費用優(yōu)化及其蟻群算法[D].大連理工大學碩士論文，2007.

[10]阮宏博.基于遺傳算法的工程多目標優(yōu)化研究[D].大連理工大學碩士論文，2007.

[11]史玉芳，李慧民，陸寧.基于遺傳算法的公路施工項目成本優(yōu)化研究[J].建筑經濟，2009（07）.

[12]陸寧，等.建筑工程項目施工安全管理掙值法研究[J].中國安全科學學報，2013，23（3）：145-149.

[13]周書敬，趙丹，李永吉.基于蟻群算法的施工項目成本優(yōu)化[J].施工技術，2015，44（18）：86-89.