基于蚁群算法的管道规划改进方法探究

黄钢忠 姜春涛 杨志鹄 黄泽斌 黄颖欣 冯樱

摘  要： 传统蚁群在区域规模较大时收敛速度逐渐减慢，会出现效率低、精准度下降、局部最优解概率高等弊端。文章针对传统蚁群算法出现的这些问题进行改进，提出一种双向蚁群算法，构造解空间时可以有效的降低数据规模。双向蚁群算法起点和终点并行计算，使得蚁群算法的搜索效率得到了极大的提高，并且可避免算法陷入局部最优解，提高了结果的有效性和准确性。

关键词： 传统蚁群算法; 双向蚁群算法; 并行计算; 管道规划

中图分类号：TP 301.6          文献标志码：A     文章编号：1006-8228（2019）10-40-03

Abstract： When the area scale of traditional ant colony is large， the convergence speed gradually slows down， resulting in the disadvantages of low efficiency， stagnation and high probability of local optimal solution. Aiming at the problems of traditional ant colony algorithm， this paper proposes a bidirectional ant colony algorithm， which can effectively reduce the size of data when constructing solution space. The parallel computation of the start and end points of the bidirectional ant colony algorithm greatly improves the search efficiency of ant colony algorithm， avoids the algorithm falling into the local optimal solution， and improves the accuracy of the results.

Key words： traditional ant colony algorithm; bidirectional ant colony algorithm; parallel computation; pipeline planning

0 引言

在城市進行基础工程设施规划加速建设时，原有的城市管网承载力会即将饱和，管网系统建设是城市建设至关重要的一环。所以管道路径规划作为城市建设的重要组成部分，国内外学者的研究方法主要有遗传算法[1]、粒子群算法[2]、智能蚁群算法[3]、启发式搜索方法[4]等。

蚁群算法是由意大利学者Dorigo等[5]提出的一种智能优化算法， 在解决路径规划问题上取得了不错的效果。但是蚁群算法也存在易出现局部最优解、搜索时间长和陷入死锁等问题。

本文针对蚁群算法易陷入局部最优解的问题和收敛速度慢的问题进行如下改进：1）改进概率选择策略和双向蚁群策略，提高算法收敛速度;2）双向蚁群策略可以有效减少死锁蚂蚁数量;3）通过改进的启发函数策略和信息素更新原则，防止陷入局部最优。

1 蚁群算法

昆虫学家研究蚂蚁的行为时，发现蚂蚁的觅食行为虽然简单，但却有一定的智能表现。蚁群可以在不同的环境下，寻找到抵达食物源的最短路径。因为蚁群内的蚂蚁可以通过某种信息机制实现信息的传递。蚂蚁会在其经过的路径上释放一种可以称之为“信息素”的物质，蚁群内的蚂蚁对“信息素”具有感知能力，它们会往“信息素”浓度较高的地方搜索，每一只觅食的蚂蚁都会在其经过的路径留下信息素，这种行为类似于正反馈机制。一段时间后，整个蚁群就会沿着最短路径到达食物源，也便得到最终的最优或者次优路径。

1.1 构造解空间

图1为传统蚁群算法流程图。

蚁群算法的解空间为蚂蚁可以行动的路径或区间，在可行动的范围中设置出发点和终点。

1.2 节点选择

蚂蚁从当前节点选择下一节点的方法如公式⑴。

3 总结

传统蚁群在区域规模较大时收敛速度逐渐减慢，会出现效率低、精准度下降、局部最优解概率高等弊端。本文针对传统蚁群算法出现的这些问题进行改进，提出一种双向蚁群算法，构造解空间时可以有效的降低数据规模，同时双向蚁群算法起点和终点并行计算，可以非常有效的减少算法的运行时间，使得蚁群算法的搜索效率得到极大的提高，并且可避免算法陷入局部最优解，提高了结果的有效性和准确性。

参考文献（References）：

[1] 刘二辉，姚锡凡，蓝宏宇.基于改进遗传算法的自动导引小车动态路径规划及其实现[J].计算机集成制造系统，2018.24（6）：1455-1467

[2] 许川佩，吕莹，黄喜军.基于粒子群算法的数字微流控芯片在线测试路径优化[J].电子测量与仪器学报，2017.31（8）：1192-1199

[3] 刘浩然，孙美婷，李雷.基于蚁群节点寻优的贝叶斯网络结构算法研究[J].仪器仪表学报，2017.38（1）：143-150

[4] 陈洋，谭艳平，程磊.领域约束下空地异构机器人系统路劲规划方法[J].机器人，2017.39（1）：1-7

[5] DORIGO M， GAMBARDELLA L M.Ant colony system：A cooperative learning approach to the traveling salesman problem[J].IEEE Transactions on Evolutionary Conputation，1997.1（1）：53-66