基于改進蟻群算法在工程項目工期—成本優化問題研究

葉民權 吳佳潔 鄭晨虹 喻婧

摘要：為了解決蟻群算法容易陷入局部最優，求解容易出現停滯現象，本文從轉移概率和信息素揮發因子兩方面對蟻群算法進行改進，并將其應用于工程項目工期成本優化問題中。本文將改進后的蟻群算法應用于某變電站土建項目，結果表明改進后的蟻群算法其性能優于基本蟻群算法，解決了算法由于固定參數而導致的停滯問題，在工程項目工期成本優化問題的應用取得了良好的效果。

Abstract： Ant colony optimization （ACO） is easy to fall in local optimum and has slow convergence rate. In order to solve the problem， this paper employs an improved ant colony optimization （IACO） algorithm which is modified in volatile factor as well as transition probability and successfully applies to time-cost optimization in specific example. Comparing with basic ant colony algorithm， this new method increases the ability of global searching and constringency， thus can settle out the stagnation of the process and find the optimum value. The results indicate that the improved ant colony algorithm is effective in time-cost optimization.

關鍵詞：蟻群算法;工程項目;參數改進;工期成本優化

Key words： ant colony algorithm;project;improved parameters;time-cost optimization

中圖分類號：TU72;TP18? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文獻標識碼：A? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文章編號：1006-4311（2018）34-0087-03

0? 引言

工程項目的工期和成本一直以來受到項目管理者的重視，其也直接影響到工程的質量，項目的工期和成本存在相互制約、相互影響的關系。一直以來，工程的工期—成本優化問題一直是優化領域的一個重點研究對象，其要求在特定的約束條件下，保證每個供需能夠以最優的方案執行，滿足項目管理的需要，確保工程項目順利完成。

到目前為止，對工期—成本優化問題的求解方法有很多，傳統的線性規劃方法[1]是一種運用較為成熟的優化方法，具有計算方法簡單、求解速度較快優點。但是在實際的應用過程中，其存在計算誤差大，精度較低的缺點，也限制了其在實際問題的應用。隨著計算機技術以及人工智能技術的不斷進步，人工智能優化算法也被廣泛運用到項目工期—成本優化問題上，其主要有禁忌搜索法[2]（TS）、模擬退火法[3]（SA）、粒子群算法[4]（PSO）、遺傳算法[5]（GA）等。這些算法具有較快的求解速度，能夠較為高效的完成最優解搜索，在一定程度上較傳統優化方法提高了最優解的質量，但是上述方法均存在計算時間過長以及容易陷于局部最優等問題，難以實際應用到項目工期—費用優化問題中。

本文用改進參數的蟻群算法解決項目工期—成本優化問題。以規定工期條件下成本最小作為優化目標，比較得出改進的蟻群算法獲得的最優解均優于普通蟻群算法，而且收斂速度也較快。

1? 工期—成本優化問題的描述以及數學模型

在工程項目實施過程中，包含n個項目活動。為保證基建項目工期—費用優化問題的解決，先采用PERT網絡技術建立優化模型。在該優化模型中，假定在優化過程中關鍵路線不發生變化。結合工程項目實施過程中的特點，本文以壓縮工期確定的條件下成本最小作為優化的目標，其工期—費用優化模型的表達式為：

其中，ci是單位時間內項目活動i的壓縮費用，xi是項目活動i的壓縮時間，TC是需要壓縮的工期，tj和xj分別為閉合圈內關鍵路線上項目活動i的平均持續時間和壓縮時間，tk和xk分別為閉合圈內非關鍵路線上項目活動的平均持續時間和壓縮時間，？啄j是第j個閉合圈內所有項目活動的方差的均方根，？姿j是第j個閉合圈在規定日期內完工的概率，Di是項目活動i的極限壓縮時間;式（1）是目標函數，表示基建項目的成本最小;式（2）～（4）是約束函數，表示壓縮過程中必須滿足的四個約束條件。

2? 蟻群算法基本內容及其改進原理

2.1 蟻群算法基本內容

蟻群算法（Ant Colony Optimization，ACO），又稱為螞蟻算法，是由意大利著名學者M.Dorigo于20世紀90年代初提出的一種新的模擬進化算法[6-7]。蟻群算法最初用于解決旅行商問題（TSP），也是最典型的應用問題，即給定n個城市，旅行上需要遍歷所有的城市，最終回到出發城市，從而尋找最短的旅行路線;另外，每個城市只能經過一次，但是出發城市可以經過兩次。

2.2 蟻群算法的改進

蟻群算法在優化問題求解的過程中經常會遇到收斂速度慢、搜索能力較弱的問題，為了解決上述缺陷，本文從信息揮發因子和轉移概率兩個方面進行優化，確保蟻群算法的求解能力[8]。

2.2.1 揮發因子的改進

蟻群算法的全局搜索能力和收斂速度的大小，其揮發因子？籽具有相當重要的地位，本文針對蟻群算法揮發因子的不足與缺點，創新的提出一種可以隨時間調整揮發因子值的大小的優化方法，目的是及時調整各個時間段參數的適應能力，保證蟻群算法的求解能力。其具體做法如下：

籽的初始值？籽（t0）=1，當蟻群算法求得的最優值在N次循環后沒有明顯改進時，？籽按照以下公式進行調整：

式中，？籽min為？籽的最小值，從根本上防止？籽過小而導致算法的搜索速度減慢的現象發生，一般設定？籽min=0.1。每次求解完成后，對本次的最優解進行儲存，提高了算法的搜索能力。

2.2.2 轉移概率的改進

蟻群算法的求解速度和精度的大小，其參數？琢與？茁在發揮著不可或缺的作用，其決定了狀態轉移概率的大小。目前為止，二者的取值一般根據經驗設定，沒有較為科學的取值方法。為了解決以上問題，本文提出了以下的方法對兩參數進行設置：

其中，Nmax為最大迭代次數，公式（10）將參數？琢與Nmax相互關聯，隨著Nmax的變化而變化;公式（11）則體現了參數？茁通過參數？琢的取值來決定，二者也是相互關聯的。依據上述公式，可以直觀的看出參數？琢與？茁的取值與Nmax進行關聯，保證了算法各個參數之間的聯動，減弱算法參數設置的隨機性。

3? 實例分析

本文按照變電站土建項目的特點，以變電站土建部分為研究對象，進行變電站的工期—費用優化問題的研究。圖1為該變電站的PERT網絡圖，表1為各個工序的相關參數。依據該項目的施工組織設計，其計劃總工期為582天，而業主單位在542天內完成土建建設部分。

在算法參數設置方面，對算法中各個參數初始化，首先設定最大迭代次數Nmax，由此得到相應的參數？琢、？茁;設定螞蟻數量m=28;最小揮發系數？籽=0.1;Q=1。由于Nmax的大小直接與參數？琢、？茁的大小相關，也將影響算法的求解能力，本文設定了不同的迭代次數，從而獲取不同的優化結果。其優化結果如表2所示。

從表2可以直觀的看出，當Nmax=80時，改進后的蟻群算法取得了最優值，此時的迭代次數為12次，具有較快的收斂速度，一定程度上避免了算法的早熟。因此本文取Nmax=80時進行改進蟻群算法的比較，其算法比較如圖2所示。

圖2所示為改進后的蟻群算法與未改進的蟻群算法尋優結果的比較，虛線為改進后蟻群算法，實線為未改進蟻群算法。Nmax=80時得到最優壓縮天數為x={5，0，0，0，0，0，2，3，14，0，0，0，0，5，0，0，0，0，0，6，5，5}，壓縮后最優工期為d={25，45，61，123，72，154，38，88，129，123，92，76，105，19，

123，92，72，91，31，30，27，25}，壓縮調試后該項目的總工期T=542，壓縮費用為C=250710元。

從圖中可以明顯看出改進蟻群算法的尋優結果優于未改進的蟻群算法，其主要表現在兩方面：①改進的蟻群算法得到的最優值明顯優于未改進蟻群算法的最優值，改進算法得到的最小壓縮成本為250710元，而蟻群算法得到的壓縮成本為268790元;②改進蟻群算法擺脫了蟻群算法早熟，易陷入局部最優解的缺點。圖中蟻群算法在迭代次數為7時得到本次迭代的最優解，算法明顯早熟，而改進蟻群算法在12次時算法才得到最優解，避免了算法的早熟。因此，改進參數后的蟻群算法對項目工期成本優化問題有更好的應用。

4? 結論

工程項目的工期—成本優化問題一直以來都受到項目管理單位的重視，其優化問題在學術領域也是一個難點和重點。為了解決蟻群算法搜索速度較慢，搜索能力較弱的缺陷，本文提出了自適應調整信息素揮發因子和狀態轉移概率參數的改進方法，增強算法的適時調整能力，有效地將算法參數聯動。通過變電站土建工程案例分析，可以直觀的看到，改進后的蟻群算法相比傳統的蟻群算法能夠較快的得到最優解，并且該最優解為全局最優，保證了算法的求解能力，避免了局部最優和早熟的問題。結果表明，改進后的蟻群算法在工程項目工期成本優化問題中具有一定的推廣性。

參考文獻：

[1]Liu L，Bruns S A，Feng C W.Construction time-cost trade-off analysis using LP–IP hybrid method[J].Journal of Construction Engineering and Management， 1995，121（4）：446-454.

[2]Peng， JN， Sun， YZ， Wang， HF. Optimal PMU placement for full network observability using Tabu search algorithm[J]， INTERNATIONAL JOURNAL OF ELECTRICAL POWER & ENERGY SYSTEMS，2006，5：223-231.

[3]Bandyopadhyay， S， Saha，S， Maulik，U， Deb，K. A simulated annealing-based multi-objective optimization algorithm： AMOSA [J]. IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION，2008：269-283.

[4]Del Valle Y， Venayagamoorthy G K， Mohagheghi S， et al. Particle swarm optimization： basic concepts， variants and applications in power systems[J]. Evolutionary Computation， IEEE Transactions on， 12（2）， 2008：171-195.

[5]Santosh Mungle ，Lyes Benyoucef，Young-JunSon，M.K.Tiwari.A fuzzy clustering-based genetical agorithm approach for time–cost quality trade-off problems：A case study of highway construction project[J].Engineering Applications of Artificial Intelligence 26 （2013）1953-1966.

[6]熊鷹，匡亞萍.施工項目工期與成本優化問題的蟻群算法[J].浙江大學學報，2007，41（1）：177-180.

[7]熊鷹，匡亞萍.基于蟻群算法的施工項目工期-成本優化[J].系統工程理論與實踐，2007，3：105-111.

[8]馬天男.城市配電網網架優化研究[D].華北電力大學（保定），2014.