自适应蚁群算法在求解TSP问题中的应用

卢宇凡，张 莉

（西安工程大学 电子信息学院，陕西 西安 710048）

旅行商问题[1]（TSP）是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径。限制条件是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是所有路程之中的最小值。TSP问题是一个组合优化问题，任何能使该问题的求解得以简化的方法，都将受到高度的评价和关注。

蚁群算法[2]是源于生物世界仿生类随机搜索算法，它应用于组合优化中具有很强的发现解的能力，且具有分布式计算、易于与其他方法相结合及鲁棒性强的优点。在仿真中表现出高度的灵活性、健壮性。但是还存在较多的问题，例如搜索速度慢，局部寻优能力差等。针对这些问题，将算法进行改进，调节信息素Q与信息素挥发系数ρ，使其变为动态的自适应信息素与动态的信息素挥发系数，进行仿真测试改进的优化算法，从而达到更优的结果。

1 基本蚁群算法及其改进

1.1 基本蚁群算法

蚂蚁在寻找食物过程中总能找到一条食物所在地和蚁穴地之间的最短路程，经研究发现蚂蚁会在其走过的路径上留下称之为信息素的物质，其他蚂蚁可以感知这种物质并以此指引其运动的方向。这种信息素允许叠加，走过同一条路径的蚂蚁数量越多，这条路径上的信息素浓度越大。由此可以吸引其他蚂蚁以更大的概率走此路径。反之，走过的蚂蚁越少，信息素的浓度就越低，行走该路径的概率就越小，同时，这种信息素还会随着时间的推移而挥发[3]。……