李辉

摘 要：群居性昆虫行为的研究为计算机科学家提供了设计分布式控制和优化算法的有力方法。对以蚁群算法为代表的群集智能的研究已经逐渐成为一个研究热点。蚁群算法在实际的生活中有很大的用处，比如求解旅行商问题，文章介绍了一种求解复杂TSP的蚁群算法，阐述了该算法的基本原理及实现过程，并且在本文中尝试用编码的形式将基本蚁群算法应用到求解旅行商问题中去。

关键词：基本蚁群算法；信息素；旅行商问题

1 意义和目标

近年来，许多学者对蜜蜂、蚂蚁等一些昆虫的行为进行了大量的研究，特别是他们的集体行为，而这些动物一般都是群居昆虫。每个昆虫的能力虽然十分有限，但昆虫群体的能力却远远超过所有个体能力的总和。比如，蚂蚁群可以快速建立起巢穴与食物之间的最短路径。令人惊奇的是，每只蚂蚁并不直接比较每条路径，而仅仅只是遵守信息素释放/跟随规则就能找到最佳路径。蚂蚁群的这种能力很自然地引起了计算机科学家的兴趣。旅行商问题的定义并不统一，一般广泛认为这样定义：假若有多个城市，而这多个城市的距离为已知条件，这个距离也可以理解为多个城市之间的开销，若要得到某一个旅行商走遍所有城市的一条回路，但必须满足所有城市之间的距离的和为最小，也可以是城市之间的开销达到最小值的这样的一条回路。求解TSP问题的算法较多，但文章使用基本蚁群算法来解决旅行商问题。……