基于改進(jìn)蟻群算法在工程項(xiàng)目工期—成本優(yōu)化問(wèn)題研究

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

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

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

中圖分類號(hào)：TU72;TP18? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼：A? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文章編號(hào)：1006-4311（2018）34-0087-03

0? 引言

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

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

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

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

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

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

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

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

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

2.2 蟻群算法的改進(jìn)

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

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

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

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

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

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

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

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

3? 實(shí)例分析

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

在算法參數(shù)設(shè)置方面，對(duì)算法中各個(gè)參數(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可以直觀的看出，當(dāng)Nmax=80時(shí)，改進(jìn)后的蟻群算法取得了最優(yōu)值，此時(shí)的迭代次數(shù)為12次，具有較快的收斂速度，一定程度上避免了算法的早熟。因此本文取Nmax=80時(shí)進(jìn)行改進(jìn)蟻群算法的比較，其算法比較如圖2所示。

圖2所示為改進(jìn)后的蟻群算法與未改進(jìn)的蟻群算法尋優(yōu)結(jié)果的比較，虛線為改進(jìn)后蟻群算法，實(shí)線為未改進(jìn)蟻群算法。Nmax=80時(shí)得到最優(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)試后該項(xiàng)目的總工期T=542，壓縮費(fèi)用為C=250710元。

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

4? 結(jié)論

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

參考文獻(xiàn)：

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

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

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