蚁群算法可视化软件的设计和实现

陈嘉圣 李泓波 罗正德 李泽钦 彭攀宇 黄梓琛

摘   要：目前的蚁群算法一般都以数值形式展示结果，而蚁群自适应、自组织的行为过程完全被掩盖。对研究者和学习者来说，蚁群行为过程的透明性极易导致理解上的困难和偏差。针对这一问题，文章基于经典蚁群算法，采用现代化可视化方法和技术，设计和实现了面向多种策略的蚁群算法可视化软件。

关键词：蚁群算法;可视化;人工智能

近几年来，人工智能已经成为学术界的研究热点，得到越来越多学者的关注。人工智能的研究领域主要包括群体智能、机器人、语言识别、图像识别、自然语言处理和专家系统等。AlphaGo、无人汽车驾驶、刷脸支付、智能搜索、定理證明、语言和图像理解等都是人工智能的应用实例[1]。

作为群体智能研究的重要研究内容，蚁群算法近年来也得到广泛关注和研究，其应用领域目前已经涵盖了基因工程、作业调度、网络路由、车辆路径、机器人、电力系统、故障诊断、控制参数优化、特征识别、聚类分析、数据挖掘、图像处理、航迹规划、空战决策、化学工业、生命科学、布局优化、模糊控制和云计算等多个学科和领域[2-3]。

目前的蚁群算法一般都以数值形式展示结果，而蚁群自适应、自组织的行为过程完全被掩盖。开展此项研究，有助于研究者和学习者克服蚁群行为过程透明性而导致的理解困难和偏差。

1    相关研究工作

虽然蚁群算法应用如此广泛，但其可视化研究却非常鲜见。在中国知网（China National Knowledge Infrastructure，CNKI）中以关键字“蚁群算法”+“可视化”进行检索，共检索到相关文章0篇。在学术探索引擎Glgoo中以关键字“ACO”+“Visualization”进行检索，共检索11 800条记录。按Glgoo检索算法，检索出的最匹配记录应该排在最前。然而，在检索结果中排在前面的记录显然没有与检索关键字完全匹配，因此，可以断定在Glgoo的数据库中找不到与关键字完全匹配的记录。

2    蚁群算法可视化算法

基于旅行商问题的蚁群算法可视化算法包含3个主要步骤，即蚂蚁路径的构建、更新信息素、构建可视化路径和信息素。

在蚂蚁路径的构建步骤中，算法将m只蚂蚁随机放置在不同的城市点中，然后根据公式（1）为每只蚂蚁提供下一个城市的选择，直至路径构建完毕。

在此公式中，Pijk表示位于城市i的蚂蚁k到达城市j的概率，ηij=1/dij为启发信息素，即两个城市i和j之间距离的倒数，τij为城市i和j之间的信息素强度，α和β分别决定信息素和启发信息素的相对影响力，allowedk为还未被蚂蚁k访问过的城市集合。

更新信息素步骤又分为信息素蒸发和蚂蚁释放信息素，在信息素蒸发过程中，当所有蚂蚁的路径都构建完毕后，各个城市之间的信息素将会减少一部分，按公式（2）执行，其中，ρ为蒸发率。

信息素蒸发完毕后，每只蚂蚁会在经过的路径中释放信息素，按公式（3）和（4）进行更新。公式（5）中的Ck为第k只蚂蚁走完整条路径后得到的总长度。

在可视化路径和信息素中，使用C#的Graphics对象的DrawLine等方法将每一代蚂蚁构建的最佳路径绘画在显示界面上，同时以表格形式显示信息素强度。

3    算法实现效果

一开始随机创建10个城市，位置如图1所示，此时的信息素各个边的信息素强度都为0.002。

点击下一次迭代按钮后，算法找出一条蚂蚁构建的最佳路径如图2所示，其中的信息素强度如图3所示。

继续点击下一次迭代按钮后结果如图4所示，此时再继续多次点击下一次迭代按钮，不在图4中显示出来的边的信息素强度趋向于0，算法结束。

4    结语

针对蚁群算法的自适应、自组织行为的透明性问题，本文通过现代化可视化手段，基于经典蚁群算法，设计和实现了面向经典蚁群、最大最小蚂蚁、精英蚂蚁等多种策略的蚁群算法可视化软件。

[参考文献]

[1]MARZBAND M，YOUSEFNEJAD E，SUMPER A，et al.Real time experimental implementation of optimum energy management system in standalone microgrid by using multi-layer ant colony optimization[J].International Journal of Electrical Power & Energy Systems，2016（75）：265-274.

[2]KPONYO J J，NWIZEGE K S，OPARE K A，et al.A distributed intelligent traffic system using ant colony optimization：a netlogo modeling approach[C].Hangzhou：International Conference on Systems Informatics，2017.

[3]曾梦凡，陈思洋，张文茜，等.利用蚁群算法生成覆盖表：探索与挖掘[J].软件学报，2016（4）：855-878.