蚁群算法在路径优化问题的应用研究

摘 要：蚁群算法是根据自然界中蚁群觅食行为而提出的一种智能优化算法，是一种可以寻找最优路径的概率型算法，具有自组织、正反馈、鲁棒性强等特点，具备全局搜索能力，被广泛应用于各种路径优化问题。本文介绍蚁群算法的来源、核心思想以及基本最优路径的搜索过程，并分析蚁群算法在各个领域中路径优化问题的应用技术。

关键词：蚁群算法；智能算法；路径优化；应用

DOI：10.16640/ki.37-1222/t.2017.08.209

1 蚁群算法

蚂蚁是一种生物个体，觅食过程中可以在其经过的路径上留下一种物质，称为信息素，并在觅食过程中能够感知信息素的强度，以此指导自己的行动方向。蚁群总是朝着信息素浓度高的方向移动，以较高的概率搜索出一条信息素浓度较高的路径，从而得到一条最佳的路径。

根据蚂蚁“寻找食物”的群体行为，意大利学者Dorigo M等最早提出蚁群算法的基本模型，并阐述了蚁群算法的核心思想。该算法中蚂蚁需要具备三种智能行为，分别是蚂蚁互相通信是通过信息素，蚂蚁会在经过的路径上释放信息素，其他蚂蚁根据信息素浓度选择路径；蚂蚁具有一定记忆能力，其选择过一次的路径不会被再次选择，可由禁忌表模拟；蚁群活动，在某一路径上行走的蚂蚁越多，留下的信息素浓度越大，该路径被选择的概率也就越大，越利于选择出最优路径。

蚁群算法的最优路径搜索过程是：初始化，将若干只蚂蚁随机放置到若干个地点，并为每条路径设定相等的信息素初始值；更新禁忌表，每当蚂蚁走过一个地点，将该地点编号添加至禁忌表中，以防止蚂蚁走重复的路径；确定行走方向，根据转移概率公式，计算转移概率，从而选择出蚂蚁下一个要访问的地点；计算信息素增量，每只蚂蚁完成一次周游之后，计算每只蚂蚁走过的路径长度，保存最短路径，并且根据每只蚂蚁在经过边的信息素释放量，更新每条边上的信息素，则路径长度最短的路径各边信息素浓度更大，从而该路径在之后迭代中被选择的概率也就越大；判断终止准则，蚂蚁完成一次循环后，会将禁忌表清空，重新回到初始地点，进行下一次周游，以此循环，直到蚂蚁的周游次数满足停止准则，得到最优路径。

2 蚁群算法在路径优化问题的应用

蚁群算法是一种自组织、正反馈、鲁棒性较强的算法，通过人工蚂蚁释放信息素相互通信，信息素越多的路径被选择的概率越大，从而使得蚁群自发地不断接近于最优解，从而寻找到最优路径，具有全局搜索能力，因此被广泛应用在各种路径优化问题。从大量文献看出，学者将蚁群算法不断改进，使蚁群算法在路径优化问题上的应用涉及社会各个方面，包括物流配送、居民出行、避灾逃生、农业应用、智能机器人等领域。

在物流配送方面，涉及到应急物流、医疗器械运送、快递配送、粮食输送、矿山运输等。其中，文献[1]提出了基于主次种群蚁群算法的物流配送车辆的路径优化方法，针对主次种群蚁群算法前期信息素积累较慢的缺点，分别使用路径去交叉算法和节约策略进行改进，以陕西省西安市某快递公司物流配送为例，仿真证明改进的主次种群蚁群算法在解决该快递物流问题上有明显优势。文献[2]采用了一种改进的蚁群算法进行医疗器械物流配送的路径优化，将免疫算法与传统蚁群算法相结合，具有更快的收敛速度、更短的搜索时间，实验仿真证明免疫蚁群算法的路径优化结果优于传统蚁群算法。在应急运输车辆路径优化问题中，一种改进的蚁群算法针对地震、泥石流、洪水等应急条件下的路况不稳定，加入动态路况因子，仿真使用21个真实城市作为应急情况下的货物供应点和需求点，证明了该算法可有效解决应急物流分配问题。

在居民出行方面，文献[3]研究了一种基于蚁群优化的居民公交出行路径选择算法，根据城市公交系统，设计基于蚁群算法的居民出行的公交最优路径选择模型，当乘客设定起点终点后，自动为乘客配置出最优的公交路径方案，并验证了该算法的准确性和有效性。

在避灾逃生方面，学者将蚁群算法应用到了大型公共建筑火灾的智能逃生路径规划研究中，在此加入蚂蚁体力值，使蚂蚁寻找最优路径同时也考虑到火灾发生时各种复杂的风险因素，以降低人员伤亡率，仿真表明改进后的蚁群算法不仅可以适应危险环境，而且满足实r计算的收敛性需求。

在农业应用方面，一种节水灌溉路径优化方案提出了采用信息素优化的改进蚁群算法进行灌溉路径优化设计，该方案以田间地块坐标作为数据源，采用改进的蚁群算法对田间地块布线路径进行设计，最终可以在相同的迭代次数内找到路径更短、代价更小的节水灌溉管线路径[4]。

在智能机器人方面，一种动态搜索策略的蚁群算法应用在了机器人路径规划中，其通过新的动态搜索诱导算子来改进蚁群算法性能，为增加种群的多样性，在初期设定较大阈值；进化过程中为加快收敛速度，动态调整较小阈值，实验结果表明该改进蚁群算法的收敛速度高，且解的质量得到优化，将其应用在复杂环境下的机器人路径规划问题，验证出较好的实际应用效果。

3 结束语

蚁群算法是一种集群智能算法，模拟蚁群觅食原理，某路径上人工蚂蚁释放的信息素越多，被蚂蚁选择的概率会越大，由此不断接近并找到最优路径。本文总结了蚁群算法针对路径优化问题在社会各个领域中已有的应用研究，该算法可以结合其它智能算法与技术，实现更加复杂的多因素路径优化问题。

参考文献

[1]康燕妮.基于主次种群蚁群算法的物流配送车辆路径优化研究[D].西安建筑科技大学，2015（06）.

[2]费腾，张立毅，韩应征，张锦.免疫蚁群算法在常规医疗器械配送路径优化中的应用[J].天津商业大学学报，2010（03）.

[3]林泉，基于蚁群优化的居民公交出行路径选择算法及仿真研究[D].华南理工大学，2010（06）.

[4]邓蕾蕾，于合龙，于亚洲，张献，基于蚁群算法的农业节水灌溉路径优化部署[J].吉林农业大学学报，2012（04）.