基于混沌加速果蠅優(yōu)化算法的航電樞紐施工進(jìn)度研究

耿 敬，張 洋，李明偉，徐 前，張立東

(哈爾濱工程大學(xué) 船舶工程學(xué)院， 黑龍江 哈爾濱150001)

0 引 言

航電樞紐工程的施工條件復(fù)雜、施工周期不確定；多家承包商為了保證工程進(jìn)度，同時(shí)進(jìn)場(chǎng)、平行作業(yè)導(dǎo)致互相干擾；在施工周期中，季節(jié)性冰凍河流出現(xiàn)季節(jié)性冰凍現(xiàn)象，導(dǎo)致工程施工期縮短。這些因素為施工進(jìn)度控制造成極大困難。因此，研究計(jì)入季節(jié)性冰凍因素的航電樞紐施工進(jìn)度優(yōu)化方法對(duì)保障施工如期完工具有重要意義。

針對(duì)施工進(jìn)度優(yōu)化問(wèn)題，汪安南等[1]應(yīng)用遺傳算法，實(shí)現(xiàn)工期約束下工程費(fèi)用最低的施工優(yōu)化模型求解，完成了對(duì)施工進(jìn)度的優(yōu)化，但研究未考慮施工過(guò)程中機(jī)械、人員、材料等資源的限制；WANG J等[2]基于模糊進(jìn)化算法求解最小模糊工期，完成了對(duì)工期的優(yōu)化，研究也未考慮人力、材料等資源限制；ZHANG H等[3]利用粒子群優(yōu)化算法研究資源約束下的施工進(jìn)度優(yōu)化問(wèn)題，獲得了優(yōu)化解，但由于粒子群算法的局限性，易陷入局部最優(yōu)解，難以保證獲得全局最優(yōu)的方案。在施工進(jìn)度優(yōu)化過(guò)程中，影響因素的考慮與優(yōu)化模型求解在很大程度上決定優(yōu)化效果[4,5]。果蠅優(yōu)化算法(fruit fly oplimization algorithm, FOA)是近年來(lái)發(fā)展起來(lái)的一種全局迭代優(yōu)化進(jìn)化算法[6,7]，具有計(jì)算過(guò)程簡(jiǎn)單、參數(shù)少、全局尋優(yōu)能力強(qiáng)、收斂速度快和魯棒性強(qiáng)等特點(diǎn)[7]，但標(biāo)準(zhǔn)FOA易過(guò)早收斂、從而陷入局部最優(yōu)，同時(shí)后期種群多樣性下降，出現(xiàn)收斂緩慢等問(wèn)題。因此，盡管現(xiàn)有的施工優(yōu)化方法可有效地輔助施工管理，但還是存在不足之處。

筆者基于季節(jié)性冰凍河流航電樞紐施工進(jìn)度優(yōu)化問(wèn)題，以施工強(qiáng)度和工程資源為約束條件，建立了計(jì)入季節(jié)性冰凍因素的施工進(jìn)度優(yōu)化模型(constructoin schedule optimization model, CSOM)；為獲得CSOM的更優(yōu)解，針對(duì)標(biāo)準(zhǔn)FOA存在的不足進(jìn)行改進(jìn)，設(shè)計(jì)自適應(yīng)加速搜索算法和全局混沌擾動(dòng)算法，首次提出了混沌加速果蠅優(yōu)化算法(chaos accelerated fruit fly optimization algorithm, CAFOA)，建立了一種基于CAFOA求解計(jì)入季節(jié)性冰凍河流因素的航電樞紐施工進(jìn)度優(yōu)化方法。結(jié)合依蘭航電樞紐工程，開(kāi)展相關(guān)數(shù)值實(shí)驗(yàn)，對(duì)比分析優(yōu)化與實(shí)際結(jié)果，論證了所提方法的可行性與優(yōu)越性。

1 施工進(jìn)度優(yōu)化模型的建立

在建立航電樞紐CSOM過(guò)程中，首先假設(shè)以下條件成立：①人工與機(jī)械可以在各個(gè)工序中綜合安排使用，人工和機(jī)械資源沒(méi)有質(zhì)的區(qū)別；②對(duì)于季節(jié)性冰凍期，航電樞紐的混凝土澆筑工程停工；③施工強(qiáng)度、資源需求量與工期呈線性遞減關(guān)系；④不考慮工程成本及費(fèi)用；⑤選取關(guān)鍵路線持續(xù)時(shí)間為項(xiàng)目工期各工序開(kāi)始時(shí)間與結(jié)束時(shí)間緊密銜接，沒(méi)有機(jī)動(dòng)時(shí)間。

綜合工程施工工序時(shí)間、施工強(qiáng)度、資源量等因素對(duì)施工的影響，考慮到季節(jié)性冰凍河流混凝土澆筑不施工，選擇施工強(qiáng)度與工程資源為約束條件，以實(shí)現(xiàn)項(xiàng)目工期最小化為目標(biāo)，建立CSOM：

(1)

(2)

式中：N為關(guān)鍵路線上施工工序個(gè)數(shù)；TES,i、TLF,i、TOS,i、TOF,i、DP,i、DO,i、TS,J1、Di, min、Di, max分別為單項(xiàng)施工工序的計(jì)劃開(kāi)始時(shí)間、計(jì)劃結(jié)束時(shí)間、優(yōu)化后開(kāi)始時(shí)間、優(yōu)化后結(jié)束時(shí)間、計(jì)劃持續(xù)時(shí)間、優(yōu)化后持續(xù)時(shí)間、規(guī)定完工日期、規(guī)定最短持續(xù)時(shí)間、規(guī)定最長(zhǎng)持續(xù)時(shí)間；Ci、Ci, max、Ci, min分別為單項(xiàng)工程計(jì)劃工序施工強(qiáng)度、最大施工強(qiáng)度、最小施工強(qiáng)度；Rk為每種資源k的可用量；rik為施工工序i對(duì)k種資源的需求量；TBDS、TBDF分別為季節(jié)性冰凍期開(kāi)始、結(jié)束日期；λ為施工強(qiáng)度增大系數(shù)；α為工期波動(dòng)振幅系數(shù)；T為項(xiàng)目工期。

約束條件①表示總工程最早、最遲開(kāi)始時(shí)間安排為0，即按照計(jì)劃施工；約束條件②表示優(yōu)化后工期在規(guī)定最長(zhǎng)持續(xù)時(shí)間與最短持續(xù)時(shí)間范圍；約束條件③表示施工強(qiáng)度上限值與下限值的規(guī)定；約束條件④表示計(jì)劃、優(yōu)化后持續(xù)時(shí)間與計(jì)劃、優(yōu)化后開(kāi)始與結(jié)束時(shí)間之間關(guān)系；約束條件⑦表示優(yōu)化后J工序完工日期符合的第J工序規(guī)定完工時(shí)間；約束條件⑧表示優(yōu)化后持續(xù)時(shí)間內(nèi)的施工強(qiáng)度處于規(guī)定上下限值范圍；約束條件⑨為資源約束，表示優(yōu)化過(guò)程中對(duì)工序的所需資源量的限制。

考慮到季節(jié)性冰凍期間，航電樞紐工程混凝土澆筑無(wú)法施工，因此，施工優(yōu)化模型通過(guò)設(shè)置約束條⑤、⑥，使得混凝土澆筑工程的開(kāi)工和完工日期限定在季節(jié)性冰凍期的開(kāi)始日期之后與結(jié)束日期之前，確保季節(jié)性冰凍期之前的未完工工程進(jìn)行停工，在冰凍期結(jié)束之后繼續(xù)施工，體現(xiàn)季節(jié)性冰凍因素對(duì)航電樞紐施工的影響。

2 混沌加速果蠅優(yōu)化算法

2.1 自適應(yīng)加速搜索算法(SAAS)

標(biāo)準(zhǔn)FOA在搜索過(guò)程中，果蠅個(gè)體按照隨機(jī)步長(zhǎng)進(jìn)行位置更新，難以保證在局部區(qū)域搜索到最優(yōu)解，同時(shí)容易飛過(guò)全局最優(yōu)解。為了果蠅個(gè)體有更多的機(jī)會(huì)在最優(yōu)解附近尋找最佳解，筆者基于統(tǒng)計(jì)原理，根據(jù)上一代味道分布濃度序列分布規(guī)律，提出了自適應(yīng)加速搜索算法(self-adaptation accelerated search algorithm, SAAS)，自適應(yīng)地調(diào)整步長(zhǎng)大小，更新果蠅個(gè)體的位置，提高搜索效率。

定義自適應(yīng)調(diào)整系數(shù)μ，其值按式(3)計(jì)算，再利用式(4)更新果蠅個(gè)體位置：

(3)

(4)

基于SAAS，在進(jìn)化初期，通過(guò)大步長(zhǎng)更新位置，增大果蠅個(gè)體探索最優(yōu)解的可行域范圍；在種群進(jìn)化過(guò)程中，始終根據(jù)每一代的種群位置的總體分布狀態(tài)，自適應(yīng)調(diào)整步長(zhǎng)大小，果蠅種群隨著搜索次數(shù)的增加趨近于最優(yōu)解，即味道濃度最佳的位置。通過(guò)小步長(zhǎng)更新其位置，增加果蠅小范圍內(nèi)最優(yōu)解的搜索的機(jī)會(huì)，提高FOA的搜索效率。

2.2 全局混沌擾動(dòng)算法(GCPA)

FOA只向當(dāng)前最優(yōu)果蠅個(gè)體聚集，但是若該個(gè)體不是全局最優(yōu)，易陷入局部最優(yōu)?；煦鐑?yōu)化是一種全局優(yōu)化技術(shù)，在改進(jìn)進(jìn)化算法中得到了廣泛的應(yīng)用[8,9]。為了避免算法在搜索后期陷入局部最優(yōu)、種群早熟收斂，筆者嘗試運(yùn)用混沌映射理論改進(jìn)FOA，設(shè)計(jì)全局混沌擾動(dòng)算法(global chaos perturbation algorithm, GCPA)，增強(qiáng)FOA種群的多樣性。通過(guò)對(duì)種群最優(yōu)解可行域的遍歷搜索，加快了搜索速率，避免陷入局部最優(yōu)，提高了局部和全局搜索能力。

目前，用于改進(jìn)進(jìn)化算法的混沌映射大多采用Logistics映射、Tent映射和An映射等[10-12]。筆者使用具有更好混沌特性的Chebyshev映射來(lái)執(zhí)行全局混沌擾動(dòng)[13]，設(shè)置混沌擾動(dòng)控制參數(shù)C0，基于混沌映射規(guī)則，將當(dāng)前果蠅最優(yōu)位置映射到混沌變量的取值范圍內(nèi)，利用混沌變量的遍歷性和規(guī)律性搜索當(dāng)前最佳位置，通過(guò)混沌遍歷搜索，獲取最新的果蠅位置，直到滿足終止條件，最終獲得全局最優(yōu)解[14]，從而避免在搜索過(guò)程中陷入極值。

Chebyshev映射函數(shù)如式(5)：

xp+1=cos(4·cos-1xp),xp∈[-1,1]

(5)

基于Chebyshev映射函數(shù)的GCPA具體步驟如下：

步驟1：假設(shè)混沌遍歷次數(shù)為M；

步驟2：設(shè)置p=1；

步驟3：根據(jù)映射函數(shù)，隨機(jī)初始化生成混沌向量(a11,a12,…,a1N)；

(6)

步驟5：如果p

步驟6：設(shè)置p=p+1，轉(zhuǎn)到步驟4；

步驟7：將最優(yōu)個(gè)體值映射變換得到的新果蠅個(gè)體與原有的最優(yōu)果蠅個(gè)體組合，按照適應(yīng)度值大小進(jìn)行排序，選出每個(gè)果蠅的最優(yōu)個(gè)體，最后通過(guò)式(7)得到新個(gè)體適應(yīng)度值的最優(yōu)解：

(7)

2.3 混沌加速果蠅優(yōu)化算法(CAFOA)

CAFOA搜索過(guò)程如下：

1)設(shè)置進(jìn)化種群基本必要參數(shù)，如種群規(guī)模popsize，變量個(gè)數(shù)N，步長(zhǎng)調(diào)整系數(shù)λ，最大進(jìn)化代數(shù)gmax，混沌擾動(dòng)控制參數(shù)C0。

3)通過(guò)GCPA過(guò)程，GCPA的新個(gè)體將被送回FOA的下一代，直到滿足算法停止準(zhǔn)則。CAFOA流程如圖1。

圖1 CAFOA的進(jìn)化流程Fig. 1 Evolutionary processes of CAFOA

3 基于CAFOA求解施工進(jìn)度優(yōu)化模型

3.1 果蠅編碼設(shè)計(jì)

3.2 適應(yīng)度值的確定

以施工強(qiáng)度和工程資源為約束條件，以縮短工期為目標(biāo)，選取出符合條件的果蠅個(gè)體進(jìn)行排序，最終選取工期最短的果蠅個(gè)體作為最優(yōu)個(gè)體。在算法進(jìn)化過(guò)程中，以項(xiàng)目工期為適應(yīng)度函數(shù)，按式(8)計(jì)算選取適應(yīng)度函數(shù)最小值為適應(yīng)度值：

(8)

4 工程實(shí)例分析

4.1 工程實(shí)例

依蘭航電樞紐工程位于依蘭縣，是集航運(yùn)、發(fā)電、灌溉、水產(chǎn)養(yǎng)殖、生態(tài)環(huán)境、旅游等多行業(yè)結(jié)合和綜合利用的工程[14]，選取影響工程完工時(shí)間的關(guān)鍵路線上11個(gè)工程進(jìn)行數(shù)值實(shí)驗(yàn)，如表1。

表1 關(guān)鍵路線工程Table 1 Construction of key routes

對(duì)于戧堤砂礫石填筑工程，砂礫石材料充分；混凝土攪拌樓限制為2座，高峰澆筑強(qiáng)度185.7 m3/h，混凝土運(yùn)輸泵車數(shù)量限制為10輛，內(nèi)設(shè)3個(gè)800 t散裝水泥罐，2個(gè)600 t粉煤灰罐?；优潘仨氃谑┕さ?年年底完成；土石方開(kāi)挖在施工第2年四月中旬前完成；混凝土澆筑在施工第3年九月末完成。每年的十月中旬到第2年的四月中旬期間為季節(jié)性冰凍期，混凝土澆筑工程停工，金屬安裝工程照常進(jìn)行施工。

4.2 算法選取及參數(shù)設(shè)置

以依蘭航電樞紐關(guān)鍵路線工程為例，采用筆者提出的CAFOA與標(biāo)準(zhǔn)FOA、粒子群算法(particale swarm optimization, PSO)、SAAS-FOA和GCPA-FOA分別對(duì)所建立的CSOM求解。考慮到算法參數(shù)設(shè)置與優(yōu)化性能相關(guān)聯(lián)，目前尚無(wú)理論性的確定方法，因此筆者通過(guò)分析不同參數(shù)值的數(shù)值實(shí)驗(yàn)，選取適應(yīng)于各個(gè)算法的最佳參數(shù)。

對(duì)于上述的5種算法除了需要特殊設(shè)置參數(shù)外，其它參數(shù)采用相同標(biāo)準(zhǔn)，算法種群規(guī)模M=100，最大迭代次數(shù)gmax=100，變量個(gè)數(shù)N=11。

1)筆者提出CAFOA：步長(zhǎng)調(diào)整系數(shù)λ=0.5，混沌擾動(dòng)控制參數(shù)g0=20；

2)FOA：步長(zhǎng)L=5；

3)PSO參數(shù)：學(xué)習(xí)因子c1=c2=1.0，慣性權(quán)重w=0.4；

4)SAAS-FOA參數(shù)：步長(zhǎng)調(diào)整系數(shù)λ=0.5；

5)GCPA-FOA參數(shù)：混沌擾動(dòng)控制參數(shù)為g0=20。

數(shù)值計(jì)算利用Visual C# 4.0編制算法程序，運(yùn)行環(huán)境為Core(TM)i7-4900CPU，3.60GHz，8.00G內(nèi)存的微機(jī)，操作系統(tǒng)為Windows7。

4.3 CSOM性能分析

考慮每次優(yōu)化結(jié)果均不相同，具有隨機(jī)性，分別基于5種算法對(duì)施工優(yōu)化模型獨(dú)立求解50次，并將50次求解所得結(jié)果求取算術(shù)平均值作為該算法優(yōu)化的結(jié)果，各個(gè)施工工序持續(xù)時(shí)間優(yōu)化結(jié)果如表2。

表2 各個(gè)施工工序持續(xù)時(shí)間優(yōu)化結(jié)果對(duì)比Table 2 Contrast of optimization results for duration of each construction process d

由表2可知：

1)PSO平均優(yōu)化百分比為4.38%，對(duì)工期優(yōu)化了2.86%，優(yōu)化后工期與計(jì)劃相比縮短了45 d；

2)FOA平均優(yōu)化百分比為5.03%，對(duì)工期優(yōu)化了3.06%，優(yōu)化后工期與計(jì)劃相比縮短了48 d；

3)SAAS-FOA、GCPA-FOA、CAFOA平均優(yōu)化百分比為6.47%、7.35%、8.62%，對(duì)優(yōu)化工期百分比為3.88%、4.32%、5.03%，相比項(xiàng)目工期縮短了61、68、79 d，相比FOA優(yōu)化工期，效果提高了0.82%、1.26%、1.97%；

4)CAFOA對(duì)第5項(xiàng)工序計(jì)劃持續(xù)時(shí)間優(yōu)化效果最高，為17.55%，同時(shí)，CAFOA較PSO優(yōu)化效果提高了2.17%。

綜上，筆者提出的CAFOA對(duì)項(xiàng)目工期優(yōu)化幅度較大，可應(yīng)用于施工進(jìn)度優(yōu)化，可有效縮短工期，優(yōu)化配置資源。

根據(jù)CAFOA優(yōu)化前后的各項(xiàng)單位工程工期，繪制施工橫道圖，見(jiàn)圖2。

圖2 航電樞紐工程優(yōu)化前后施工橫道圖Fig. 2 Gantt chart of navigation-power junction project before and after optimization

4.4 優(yōu)化算法性能分析

基于5種算法對(duì)CSOM分別獨(dú)立求解50次，按照工期大小進(jìn)行排序，得出最短優(yōu)化工期和最長(zhǎng)優(yōu)化工期，計(jì)算工期平均值和優(yōu)化工期方差，統(tǒng)計(jì)結(jié)果見(jiàn)表3。可以看出，與被選擇的其他4種算法相比，CAFOA所得的優(yōu)化結(jié)果波動(dòng)最小。

表3 5種算法優(yōu)化結(jié)果波動(dòng)對(duì)比Table 3 Contrast of optimization results fluctuation for 5 kinds ofalgorithm

為測(cè)試CAFOA的收斂性能，根據(jù)每次迭代的項(xiàng)目工期的算術(shù)平均值，繪制適應(yīng)度值平均進(jìn)化曲線。5種算法下航電樞紐工程工期收斂曲線如圖3。

由圖3可知，5種算法均收斂，獲得工期最優(yōu)解，但PSO、FOA、SAAS-FOA、GCPA-FOA、CAFOA分別在第25、24、18、30、13代時(shí)收斂，為1 526、1 523、1 510、1 503、1 492 d；FOA最佳適應(yīng)度值與PSO近似，收斂代數(shù)相近；SAAS-FOA由于在FOA中加入SAAS，加快工期收斂速度，在FOA前收斂；GCPA-FOA由于在FOA中加入了GCPA使算法更大程度上對(duì)可行域進(jìn)行遍歷，提升了工期效果優(yōu)化。

圖3 航電樞紐工程工期收斂曲線Fig. 3 Convergence curve of total time limit for navigation-powerjunction project

綜上，SAAS-FOA比GCPA-FOA收斂速度快，但GCPA-FOA的求解效果更加優(yōu)秀；CAFOA綜合了SAAS-FOA和GCPA-FOA的優(yōu)點(diǎn)，既得到更加優(yōu)秀的解，又提高了算法的收斂速度。

5 結(jié) 論

筆者計(jì)入季節(jié)性冰凍河流因素，面向航電樞紐工程，提出了一種基于CAFOA的施工進(jìn)度優(yōu)化方法。通過(guò)數(shù)值實(shí)驗(yàn)，對(duì)比分析了所建立的CSOM和CAFOA的可行性和優(yōu)越性，得到以下結(jié)論：

1)CAFOA在求解的穩(wěn)定性和優(yōu)化效果方面均優(yōu)于PSO、FOA、SAAS-FOA、GCPA-FOA，說(shuō)明CAFOA在求解CSOM過(guò)程中具有更好的求解能力，證明了將新算法用于改善施工進(jìn)度優(yōu)化效果的嘗試是可行的。

2)應(yīng)用建立的CSOM對(duì)季節(jié)性冰凍河流航電樞紐施工工期進(jìn)行優(yōu)化，能夠獲得在已有施工邊界條件下未來(lái)施工進(jìn)度規(guī)劃的較優(yōu)方案。

3)將筆者提出的施工進(jìn)度優(yōu)化方法用于季節(jié)性冰凍河流航電樞紐工程建造管理，縮短了施工工期，實(shí)現(xiàn)了管理效益和使用效率綜合更優(yōu)。