基于ACO算法的建设项目施工多目标优化

胡潇

摘要：本文通过分析网络计划中的逻辑关系，构建求解施工项目多目标优化的数学模型。将施工网络图模型抽象为蚂蚁觅食模型，运用ACO算法求解较优的施工模式路径组合，并利用Pareto思想选择保留较优的组合。最后，利用一个算例证明了智能化的蚁群算法可以克服传统多目标优化结果单一并且受人为因素影响的缺点，从而实现提高优化效率、优化运算结果。

Abstract： In this paper， a mathematical model for multi-objective optimization of construction projects is constructed by analyzing the logic relationship in network planning. The construction network graph model is abstracted as an ant foraging model. The ACO algorithm is used to solve the optimal construction mode path combination. And the Pareto thought is used to select the optimal combination. In the last， this manuscript uses an example to prove that intelligent ant colony optimization algorithm can overcome the shortage that the result of traditional multi-objective optimization is single and is easily affected by man-made factors. As well as the ant colony optimization can achieve the goal of improving the efficiency of optimization and optimizing operation results.

關键词：建设项目;ACO算法;施工网络计划;多目标优化

Key words： construction project;the ACO algorithm;the construction network plan;multi-objective optimization

中图分类号：TP18                                        文献标识码：A                                  文章编号：1006-4311（2018）34-0103-04

0  引言

项目管理是实现工期、成本、质量、安全、环境等多目标优化的管理，而对于网络计划多目标优化的方式大体有三种。第一种是传统数学理论，包括约束法、权重法、距离函数法、最小最大法等。第二种是利用网络计划技术，主要是结合CPM和PERT。第三种是智能化方法，在其蓬勃发展的今天，智能化算法也越来越多地用于求解多目标的优化问题。

本文通过对施工网络计划中逻辑关系的研究，明确了建设项目工期、成本、质量、安全、绿色度的数学模型，并建立了以耗费工期最短，使用成本最少，质量最好，安全度高，绿色度最高作为目标函数。通过对蚁群群算法觅食模型的研究，并结合到建设项目施工网络图中，将网络计划图各个节点依次编号，抽象为旅行商问题，实现了智能求解多目标优化问题，可以筛选出满足安全条件的施工模式组合，克服了人工随机组合的局限性和随机性。

1  网络计划技术五大目标的数学模型

1.1 工期优化

在网络计划中，工程实施工期的控制性因素是关键线路，所以减短工期的关键是关注关键线路。工期数学模型如下：

作节点所需要的时间;

Tq—工程项目最大总工期限。

1.2 成本优化

直接成本、间接成本、工程延期赔偿费构成工程成本的主要部分。直接费用中包括人工费、原材料费、机械的使用费、其他直接费以及现场经费工程项目的。间接费用指完成施工任务所需费用中除去直接费以外的部分。成本数学模型如下：

2  蚁群算法

由于受到蚂蚁群能够发现从蚁巢走到食物源的最短路径现象的引导，意大利的学者M.Dorigo[2]等人于1992年提出了蚂蚁系统，这是一种基于种群的模拟进化算法，并证明此方法能够很好的解决旅行商等问题。

2.1 蚁群算法的基本原理

蚂蚁在寻觅食物时，能在它们经过的路径上释放一种叫做“信息素”的物质，并且使得一定范围内的其他蚂蚁能够感知到并朝这种物质浓度高的地方移动。在某一个点上，如果一只蚂蚁要从不同的路径中选择一条路径，那么那些被之前走过的蚂蚁大量选择的路径被后来的蚂蚁选中的概率会更大，路径上留有较多的信息素的代表着达到目标的较短的路径。

2.2 蚁群算法的数学模型

蚁群算法基本参数：m表示人工蚂蚁的数量;n表示城市数量;dij表示两个城市之间的距离，i，j？缀（1，n）;？子ij（t）表示在t时刻路过的蚂蚁群在路径ij上残留下的信息素含量地多少，设？子ij（0）=C;蚂蚁选择路径的概率公式如下[3]：

式中：？琢为信息启发式因子，表示对应的路径的相对重要性;？茁为期望启发式因子，表示蚂蚁由城市i转移到城市j的期望值的相对重要性;为在t时刻，蚂蚁k可以选择走的城市;tabuk（k=1，2，3…m）为禁忌表，记录蚂蚁k当前已经走过的城市;？浊ij为启发式信息，表示蚂蚁由城市i转移到城市j的期望值。

3  Pareto解个体适应值计算

利用Pareto最优解对解排序并赋适应值，计算共享函数值，将Pareto最优解均布于非劣最优域。下面采用與类似的分类原理。

①通过非劣分层的方法将种群P分为？籽组;

②第一层定义为最优非劣组，赋予第一层中的每个个体适应值为fi=N（N为种群个数）;

③每层内都使用共享函数的方法，首先计算第一层中个体i与个体j标准化的欧拉距离

⑦第二层中每个个体原始适应值为fi=N-？籽/N，按照第一层的方法调整第二层中的个体适应值，以此类推。

4  基于ACO算法的建设项目多目标优化

4.1 算例

选用一个算例来说明蚁群算法用于此问题的有效性以及建立的应用模型的准确性。本文采用文献[1]中所用算例，其逻辑关系及各方面的数据见文献[1]中所示。算例网络图如图1。

4.2 算法模型建立

将网络计划图中的每一个节点按顺序编号，每一个节点对应的工作模式也分别编号。模型图如图2所表示，节点的编号为S1-Sm，矩形框内序列表示每个节点所对应的不同的工作模式的编号。把每个节点看作一级，每个节点都对应一定数目的工作模式，从第一级到最后一级工作节点，就是在每一级下随机选择一个工作模式的编号，他们之间的连线就可以看成一个工作模式组合解。

蚂蚁在各个点之间移动的时候，根据目标函数判断路径上的信息素量的多少，引导蚂蚁移动方向。经过一段时间的运行，满足目标函数要求的组合路径信息素比较多。蚂蚁从工作节点S1到Sm的状态转移公式如下：

式（8）可以看出，在多次循环后，各个节点处的信息素的增量由解的质量决定，若对应的质量好、安全度高、工期短、成本低、绿色度高，则增加的信息素的量比较多，相反则增加的信息素含量低。通过对各节点上信息素的分配，整个系统能够得到多个目标条件下较优解的目的。

4.3 蚁群算法求解多目标优化步骤

①初始化目标函数的参数、蚁群算法的参数包括蚂蚁的个数、节点的数目等以及蚂蚁的初始位置。

②建立外部种群，初始化迭代次数T=0。

③蚂蚁开始遍历各个节点处，进行搜索，T=T+1。

④根据4.2所示方法计算每条路径组合的目标函数适应值，并保留Pareto较优解组合到外部种群中。

⑤根据公式（8）更新各个节点信息素含量。

⑥若迭代次数达到要求，输出外部种群，即pareto较优解组合，若迭代次数不足，则返回第③步。

4.4 运行结果

在一次运行中可以获得43组Pareto最优解，将Pareto解在三维坐标里显示，如图3、图4。

部分Pareto解如表1所示。

5  结语

本文在前人探索的基础上总结了网络计划包含的逻辑关系，并根据其中的逻辑关系建立了施工项目多目标优化的数学模型;将网络计划的优化转化为蚁群算法的觅食模型;最后通过仿真实验得到了较优的施工模式组合，与免疫遗传粒子群算法比较得到的解更优，验证了ACO算法用于此类问题的正确性与合理性。

参考文献：

[1]杨森.基于免疫遗传粒子群算法的工程项目多目标综合优化研究[D].西安建筑科技大学硕士论文，2014.

[2]Dorigo M， Gambardella L M.Ant colony system： a cooperative learning approach to the traveling salesman problem[J].IEEE Transactions on Evolutionary Computation，1997，1（1）：53-56.

[3]李彦苍，周书敬，吴超.仿生智能算法及其在土木工程中的应用[M].北京：科学出版社，2015：1-3.

[4]Colorni A， Dorigo M， Maniezzo V. Ant colony system for job-shop scheduling[J]. Belgian J of Operations Research Statistics and Computer Science， 1994，34（1）：39-53.

[5]Dorigo M， Maniezzo V， Colorni A. The ant system： Optimization by a colony of cooperating agents[J]. IEEE Trans on smc，1996，26（1）：28-41.

[6]张勇德，黄莎白.多目标优化问题的蚁群算法研究[J].控制与决策，2005，20（2）：170-176.

[7]刘晓峰，陈通，张连营.基于微粒群算法的工程项目质量、费用和工期综合优化[J].土木工程学报，2006，39（10）：122-126.

[8]陆宁，冯妍萍，王芳，王小萌，俞允凯，王森浩.单位工程四大目标的可靠度综合控制[J].西安建筑科技大学学报（自然科学版），2007（05）.

[9]胡华选.网络计划工期费用优化及其蚁群算法[D].大连理工大学硕士论文，2007.

[10]阮宏博.基于遗传算法的工程多目标优化研究[D].大连理工大学硕士论文，2007.

[11]史玉芳，李慧民，陆宁.基于遗传算法的公路施工项目成本优化研究[J].建筑经济，2009（07）.

[12]陆宁，等.建筑工程项目施工安全管理挣值法研究[J].中国安全科学学报，2013，23（3）：145-149.

[13]周书敬，赵丹，李永吉.基于蚁群算法的施工项目成本优化[J].施工技术，2015，44（18）：86-89.