基于混沌加速果蝇优化算法的航电枢纽施工进度研究

耿 敬，张 洋，李明伟，徐 前，张立东

(哈尔滨工程大学 船舶工程学院， 黑龙江 哈尔滨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)将笔者提出的施工进度优化方法用于季节性冰冻河流航电枢纽工程建造管理，缩短了施工工期，实现了管理效益和使用效率综合更优。