葉民權(quán) 吳佳潔 鄭晨虹 喻婧

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

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.

關(guān)鍵詞：蟻群算法;工程項目;參數(shù)改進;工期成本優(yōu)化

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

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

0? 引言

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

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

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

1? 工期—成本優(yōu)化問題的描述以及數(shù)學模型

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

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

2? 蟻群算法基本內(nèi)容及其改進原理

2.1 蟻群算法基本內(nèi)容

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

2.2 蟻群算法的改進

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

2.2.1 揮發(fā)因子的改進

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

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

式中，？籽min為？籽的最小值，從根本上防止？籽過小而導(dǎo)致算法的搜索速度減慢的現(xiàn)象發(fā)生，一般設(shè)定？籽min=0.1。每次求解完成后，對本次的最優(yōu)解進行儲存，提高了算法的搜索能力。

2.2.2 轉(zhuǎn)移概率的改進

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

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

3? 實例分析

本文按照變電站土建項目的特點，以變電站土建部分為研究對象，進行變電站的工期—費用優(yōu)化問題的研究。圖1為該變電站的PERT網(wǎng)絡(luò)圖，表1為各個工序的相關(guān)參數(shù)。依據(jù)該項目的施工組織設(shè)計，其計劃總工期為582天，而業(yè)主單位在542天內(nèi)完成土建建設(shè)部分。

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

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

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

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

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

4? 結(jié)論

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

參考文獻：

[1]Liu L，Bruns S A，F(xiàn)eng 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]熊鷹，匡亞萍.施工項目工期與成本優(yōu)化問題的蟻群算法[J].浙江大學學報，2007，41（1）：177-180.

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

[8]馬天男.城市配電網(wǎng)網(wǎng)架優(yōu)化研究[D].華北電力大學（保定），2014.