蚁群算法在交通寻路中的应用

师扬松 成都市实验外国语学校西区2019届

1 引言

蚁群优化（Ant colony optimization，ACO）是一种模仿蚂蚁觅食行为的智能仿生算法[1]。蚁群释放特殊的化学物质信息素来传达信息，并通过感知信息素浓度来选择前进道路。通过研究这种行为，结合实际场景，可以解决很多难题并大大提高效率。蚁群算法是一种用来寻找优化路径的概率型算法[2-7]。这种算法具有分布计算、信息正反馈和启发式搜索的特征，本质上是一种启发式全局优化算法。蚁群算法已经在组合优化、函数优化、网络路由、机器人路径规划、数据挖掘以及大规模集成电路的综合布线设计等领域获得了广泛的应用，并取得了较好的效果[8]。例如，在[9]中将蚁群算法的正反馈思想与分布式计算应用到概率路由中，收集机会网络的节点和拓扑信息，并结合这些信息，设计基于蚁群算法的概率路由，可以提高机会网络的消息传输性能。[10]中提出的改进的蚁群聚类算法应用在了学生成绩评价中，基于实验数据，得到了聚类结果，并对聚类分析的结果做出相应解释，提出了针对性的策略和建议，证明了改进的蚁群聚类算法的有效性。蚁群算法可以高效的向用户提供最优路径，但是现有研究中蚁群算法收敛速度较慢而且容易发生停滞，一些文章中通过改进蚁群算法，来弥补这些缺陷从而达到很好的效果[11-14]。例如，根据A*算法的启发式信息改进蚁群算法的路径选择策略，加快算法收敛速度[15]。

本文基于蚁群算法的优点，将其应用于一个简易交通寻路模型中，为此模型提供一种快速寻路解决方法。该模型为一个点对点三条通路的模型，通过设置不同的站点人员数目和不同的节点之间的时间开销来实现不同的交通路况。从该模型中抽象出一个站点人员数矩阵和一个节点间的时间开销矩阵，输出这两个矩阵来观察算法的运算情况。通过设置相同的矩阵数据，对比常规方法与应用蚂蚁算法后的时间开销，最终证明应用算法后可以大大提高交通效率。该算法优点在于可以根据模型不同变量生成一种寻路花费时间最短的方案算法。在本文中第三部分通过与常规算法相比，证明了其可以大大减少时间开销提高效率。在小区、游乐园或者大学校园的观光车或通勤车有很大的应用空间。

2 算法原理

首先，本文中提出了一个简易的通勤车模型。模型中从起点Q到终点S有三条互不相通的路。三条路上设置不同的站点数目、每个站点等待人员数目和站与站之间的间距。将模型抽象成两个矩阵，一个站点人员数目矩阵和一个时间开销矩阵。通过观察两个矩阵的数据变化可以验证算法的优劣。三条路上规定必有三辆车分别通过，接送人员。在每辆车通过本车路段到达终点后会释放信息素。通过不同的信息素起点安排合适数目的车辆进入相应路段。

图1 算法流程图

当每辆车到达站点后根据车上的空余座位和站点人数作对比，可得出离开站点所剩人员和空车位数目。到终点后发出信息素，依据浓度判断派出车辆数目，直到每个站点人员接送完毕。算法的流程图如图1所示。

每个站点之间都有不同的时间开销，在一个设定好的模型里，即间距和人员分布一样，在应用本文提出的算法和普通情况下做出对比。本文算法可以大大提高效率。此模型虽然简单，但是有很多应用，除了在小区校区通勤车的寻路中应用外，还可以在游戏中使用。是一个非常实用的算法模型。

3 仿真实现

按上述流程图，用Dev-C++实现算法，创建一个简易交通模型如图2所示。通过常规方案可以得出初始的总时间开销。然后在同样的模型下应用蚂蚁算法后得出的时间开销会小很多。通过数据对比，可以证明应用了提出的算法后可以大大提高寻路的效率。

图2 简易交通模型图。

在仿真中输出了常规算法下设置的站点数、站点间开销站点人员数目和每个时间点通过站点后的人员分布结果与总时间开销如图3所示。此处使用矩阵形式展示。并且在每个时间单位都会输出站点人

图3 常规算法下的仿真结果

员矩阵，实时观察矩阵变化，直到人员接送完毕为止。最后算法出总时间开销。在输入设置过程中，因为矩阵定义的是三行四列矩阵，可以在某个点设置为0，同样对应的时间开销设置成0，这样可以表示此处没有站点，并不消耗空余座位和时间开销。在关于路程或之间开销上，每条路上的车通过所有站点到达终点后就会将人员送下车。此时车上全部是空余座位，如果没有结束运送，则车会从终点返回起始点，同起始点按照算法安排的车一起进入寻路中。从终点到起点的返回车辆所花费的开销会根据设置的站点间距不同而不同，相当于是原路返回。如此可以较为完善的模拟实际过程中的交通情况。

图4所示为应用蚂蚁算法后的仿真结果。同样的模型下最后总的时间开销应用算法后比应用常规方法要少很多。这证明了应用蚂蚁算法后可以大大提高效率。

图4 改进算法后的仿真结果

4 总结

本文基于蚁群算法的优点，通过在一个简易通勤车寻路模型中实际使用并仿真验证，应用蚁群算法后可以提高效率。为此模型提供一种快速寻路解决方法。该模型虽然简单，但是在很多实际应用中都会存在。而该算法优点在于可以根据模型不同变量生成一种寻路花费时间最短的方案算法。在小区、游乐园或者大学校园的观光车或通勤车有很大的应用空间。

而为了检验本文提出的算法，本文所做模型是从实际生活中抽象出的简易模型。模型可以做出更进一步的改进，使路况复杂化。在路与路之间做联通路径结合成网状，这样产生的路就会变得多样化、复杂化，从起始点到终点的路不再单一。而且车辆的分配也不会按照单线路运行。通过判断信息素的浓度和当前路线的状况，排列每种路线的优先级，使就近的车辆跨线到另外一条路线，先完成优先级高的路线。以上都是点对点的情况，这种模型不仅适合于交通或者游戏模型，同时也可以模拟点对点通信。假如将终点设置为多个，则会变成一对多的情况，假如应用蚁群算法在树形结构中收索，同时每个节点设置不同权重，每个节点之间设置不同开销，就是该模型该进程一对多的情况。更进一步可以设置为多对多模型、三维立体模型，不同模型可以用于不同实际情况，可以分析或实用在生活生产中。

[1]王艺睿.蚁群算法在动态优化问题上的应用研究[D].东华大学，2017.

[2]游戏引擎最短路径搜索优化遗传算法设计[J].黎忠文，覃志东，王全宇，倪仲余.计算机应用研究.2014(01).

[3]Dijkstra算法中的多邻接点与多条最短路径问题[J].王树西，李安渝.计算机科学.2014(06).

[4]喻环.改进蚁群算法在机器人路径规划上的应用研究[D].安徽大学，2017.

[5]刘建华，杨建国，刘华平，耿鹏，高蒙.基于势场蚁群算法的移动机器人全局路径规划方法[J].农业机械学报，2015，46(09)：18-27.

[6]基于Laguerre图的自优化A-Star无人机航路规划算法[J].魏瑞轩，许卓凡，王树磊，吕明海.系统工程与电子技术.2015(03).

[7]遗传算法改进策略研究[J].夏季.信息与电脑(理论版).2012(11).

[8]杨剑峰.蚁群算法及其应用研究[D].浙江大学，2007.

[9]贾磊磊.机会网络中基于蚁群算法的概率路由的设计与实现[D].内蒙古大学，2017.

[10]周颖.基于蚁群算法的聚类分析在学生成绩中的研究[D].南昌大学，2015.

[11]张家善.基于改进蚁群算法的物流配送车辆路径优化研究[D].辽宁工程技术大学，2014.

[12]曹洁，耿振节.一种改进蚁群算法在捡球机器人多目标路径规划中的应用[J].小型微型计算机系统，2015，36(10)：2384-2389.

[13]左敏，许华荣.基于改进蚁群算法的智能小车路径规划[J].心智与计算，2011，5(02)：60-68

[14]裴振兵，陈雪波.改进蚁群算法及其在机器人避障中的应用[J].智能系统学报，2015，10(01)：90-96.

[15]张志协，曹阳.基于改进型蚁群算法的最优路径问题求解[J].计算机系统应用，2012，21(10)：76-80.