基于混沌加速果蠅優化算法的航電樞紐施工進度研究

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

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

0 引 言

航電樞紐工程的施工條件復雜、施工周期不確定；多家承包商為了保證工程進度，同時進場、平行作業導致互相干擾；在施工周期中，季節性冰凍河流出現季節性冰凍現象，導致工程施工期縮短。這些因素為施工進度控制造成極大困難。因此，研究計入季節性冰凍因素的航電樞紐施工進度優化方法對保障施工如期完工具有重要意義。

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

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

1 施工進度優化模型的建立

在建立航電樞紐CSOM過程中，首先假設以下條件成立：①人工與機械可以在各個工序中綜合安排使用，人工和機械資源沒有質的區別；②對于季節性冰凍期，航電樞紐的混凝土澆筑工程停工；③施工強度、資源需求量與工期呈線性遞減關系；④不考慮工程成本及費用；⑤選取關鍵路線持續時間為項目工期各工序開始時間與結束時間緊密銜接，沒有機動時間。

綜合工程施工工序時間、施工強度、資源量等因素對施工的影響，考慮到季節性冰凍河流混凝土澆筑不施工，選擇施工強度與工程資源為約束條件，以實現項目工期最小化為目標，建立CSOM：

(1)

(2)

式中：N為關鍵路線上施工工序個數；TES,i、TLF,i、TOS,i、TOF,i、DP,i、DO,i、TS,J1、Di, min、Di, max分別為單項施工工序的計劃開始時間、計劃結束時間、優化后開始時間、優化后結束時間、計劃持續時間、優化后持續時間、規定完工日期、規定最短持續時間、規定最長持續時間；Ci、Ci, max、Ci, min分別為單項工程計劃工序施工強度、最大施工強度、最小施工強度；Rk為每種資源k的可用量；rik為施工工序i對k種資源的需求量；TBDS、TBDF分別為季節性冰凍期開始、結束日期；λ為施工強度增大系數；α為工期波動振幅系數；T為項目工期。

約束條件①表示總工程最早、最遲開始時間安排為0，即按照計劃施工；約束條件②表示優化后工期在規定最長持續時間與最短持續時間范圍；約束條件③表示施工強度上限值與下限值的規定；約束條件④表示計劃、優化后持續時間與計劃、優化后開始與結束時間之間關系；約束條件⑦表示優化后J工序完工日期符合的第J工序規定完工時間；約束條件⑧表示優化后持續時間內的施工強度處于規定上下限值范圍；約束條件⑨為資源約束，表示優化過程中對工序的所需資源量的限制。

考慮到季節性冰凍期間，航電樞紐工程混凝土澆筑無法施工，因此，施工優化模型通過設置約束條⑤、⑥，使得混凝土澆筑工程的開工和完工日期限定在季節性冰凍期的開始日期之后與結束日期之前，確保季節性冰凍期之前的未完工工程進行停工，在冰凍期結束之后繼續施工，體現季節性冰凍因素對航電樞紐施工的影響。

2 混沌加速果蠅優化算法

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

標準FOA在搜索過程中，果蠅個體按照隨機步長進行位置更新，難以保證在局部區域搜索到最優解，同時容易飛過全局最優解。為了果蠅個體有更多的機會在最優解附近尋找最佳解，筆者基于統計原理，根據上一代味道分布濃度序列分布規律，提出了自適應加速搜索算法(self-adaptation accelerated search algorithm, SAAS)，自適應地調整步長大小，更新果蠅個體的位置，提高搜索效率。

定義自適應調整系數μ，其值按式(3)計算，再利用式(4)更新果蠅個體位置：

(3)

(4)

基于SAAS，在進化初期，通過大步長更新位置，增大果蠅個體探索最優解的可行域范圍；在種群進化過程中，始終根據每一代的種群位置的總體分布狀態，自適應調整步長大小，果蠅種群隨著搜索次數的增加趨近于最優解，即味道濃度最佳的位置。通過小步長更新其位置，增加果蠅小范圍內最優解的搜索的機會，提高FOA的搜索效率。

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

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

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

Chebyshev映射函數如式(5)：

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

(5)

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

步驟1：假設混沌遍歷次數為M；

步驟2：設置p=1；

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

(6)

步驟5：如果p

步驟6：設置p=p+1，轉到步驟4；

步驟7：將最優個體值映射變換得到的新果蠅個體與原有的最優果蠅個體組合，按照適應度值大小進行排序，選出每個果蠅的最優個體，最后通過式(7)得到新個體適應度值的最優解：

(7)

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

CAFOA搜索過程如下：

1)設置進化種群基本必要參數，如種群規模popsize，變量個數N，步長調整系數λ，最大進化代數gmax，混沌擾動控制參數C0。

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

圖1 CAFOA的進化流程Fig. 1 Evolutionary processes of CAFOA

3 基于CAFOA求解施工進度優化模型

3.1 果蠅編碼設計

3.2 適應度值的確定

以施工強度和工程資源為約束條件，以縮短工期為目標，選取出符合條件的果蠅個體進行排序，最終選取工期最短的果蠅個體作為最優個體。在算法進化過程中，以項目工期為適應度函數，按式(8)計算選取適應度函數最小值為適應度值：

(8)

4 工程實例分析

4.1 工程實例

依蘭航電樞紐工程位于依蘭縣，是集航運、發電、灌溉、水產養殖、生態環境、旅游等多行業結合和綜合利用的工程[14]，選取影響工程完工時間的關鍵路線上11個工程進行數值實驗，如表1。

表1 關鍵路線工程Table 1 Construction of key routes

對于戧堤砂礫石填筑工程，砂礫石材料充分；混凝土攪拌樓限制為2座，高峰澆筑強度185.7 m3/h，混凝土運輸泵車數量限制為10輛，內設3個800 t散裝水泥罐，2個600 t粉煤灰罐。基坑排水必須在施工第1年年底完成；土石方開挖在施工第2年四月中旬前完成；混凝土澆筑在施工第3年九月末完成。每年的十月中旬到第2年的四月中旬期間為季節性冰凍期，混凝土澆筑工程停工，金屬安裝工程照常進行施工。

4.2 算法選取及參數設置

以依蘭航電樞紐關鍵路線工程為例，采用筆者提出的CAFOA與標準FOA、粒子群算法(particale swarm optimization, PSO)、SAAS-FOA和GCPA-FOA分別對所建立的CSOM求解。考慮到算法參數設置與優化性能相關聯，目前尚無理論性的確定方法，因此筆者通過分析不同參數值的數值實驗，選取適應于各個算法的最佳參數。

對于上述的5種算法除了需要特殊設置參數外，其它參數采用相同標準，算法種群規模M=100，最大迭代次數gmax=100，變量個數N=11。

1)筆者提出CAFOA：步長調整系數λ=0.5，混沌擾動控制參數g0=20；

2)FOA：步長L=5；

3)PSO參數：學習因子c1=c2=1.0，慣性權重w=0.4；

4)SAAS-FOA參數：步長調整系數λ=0.5；

5)GCPA-FOA參數：混沌擾動控制參數為g0=20。

數值計算利用Visual C# 4.0編制算法程序，運行環境為Core(TM)i7-4900CPU，3.60GHz，8.00G內存的微機，操作系統為Windows7。

4.3 CSOM性能分析

考慮每次優化結果均不相同，具有隨機性，分別基于5種算法對施工優化模型獨立求解50次，并將50次求解所得結果求取算術平均值作為該算法優化的結果，各個施工工序持續時間優化結果如表2。

表2 各個施工工序持續時間優化結果對比Table 2 Contrast of optimization results for duration of each construction process d

由表2可知：

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

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

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

4)CAFOA對第5項工序計劃持續時間優化效果最高，為17.55%，同時，CAFOA較PSO優化效果提高了2.17%。

綜上，筆者提出的CAFOA對項目工期優化幅度較大，可應用于施工進度優化，可有效縮短工期，優化配置資源。

根據CAFOA優化前后的各項單位工程工期，繪制施工橫道圖，見圖2。

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

4.4 優化算法性能分析

基于5種算法對CSOM分別獨立求解50次，按照工期大小進行排序，得出最短優化工期和最長優化工期，計算工期平均值和優化工期方差，統計結果見表3。可以看出，與被選擇的其他4種算法相比，CAFOA所得的優化結果波動最小。

表3 5種算法優化結果波動對比Table 3 Contrast of optimization results fluctuation for 5 kinds ofalgorithm

為測試CAFOA的收斂性能，根據每次迭代的項目工期的算術平均值，繪制適應度值平均進化曲線。5種算法下航電樞紐工程工期收斂曲線如圖3。

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

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

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

5 結 論

筆者計入季節性冰凍河流因素，面向航電樞紐工程，提出了一種基于CAFOA的施工進度優化方法。通過數值實驗，對比分析了所建立的CSOM和CAFOA的可行性和優越性，得到以下結論：

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

2)應用建立的CSOM對季節性冰凍河流航電樞紐施工工期進行優化，能夠獲得在已有施工邊界條件下未來施工進度規劃的較優方案。

3)將筆者提出的施工進度優化方法用于季節性冰凍河流航電樞紐工程建造管理，縮短了施工工期，實現了管理效益和使用效率綜合更優。