【TSP问题】基于蚁群算法求解旅行商问题含Matlab源码
1 算法介绍
1.1 蚁群算法原理
蚁群算法是受到对真实蚂蚁群觅食行为研究的启发而提出。生物学研究表明：一群相互协作的蚂蚁能
够找到食物和巢穴之间的最短路径,而单只蚂蚁则不能。生物学家经过大量细致观察研究发现,蚂蚁个体之
间的行为是相互作用相互影响的。蚂蚁在运动过程中,能够在它所经过的路径上留下一种称之为信息素的
物质,而此物质恰恰是蚂蚁个体之间信息传递交流的载体。蚂蚁在运动时能够感知这种物质,并且习惯于追
踪此物质爬行,当然爬行过程中还会释放信息素。一条路上的信息素踪迹越浓,其它蚂蚁将以越高的概率跟
随爬行此路径,从而该路径上的信息素踪迹会被加强,因此,由大量蚂蚁组成的蚁群的集体行为便表现出一
种信息正反馈现象。某一路径上走过的蚂蚁越多,则后来者选择该路径的可能性就越大。蚂蚁个体之间就
是通过这种间接的通信机制实现协同搜索最短路径的目标的。我们举例简单说明蚂蚁觅食行为：
如上图a,b,c的示意图：
a图是原始状态，蚂蚁起始点为A，要到达E，中途有障碍物，要绕过才能到达。BC和BH是绕过障碍物的
2条路径(假设只有2条)。各个路径的距离d已经标定。
b图是t=0时刻蚂蚁状态，各个边上有相等的信息素浓度，假设为15；
c图是t=1时刻蚂蚁经过后的状态，各个边的信息素浓度，有变化；因为大量蚂蚁的选择概率会不一样，
而选择概率是和路径长度相关的。所以越短路径的浓度会越来越大，经过此短路径达到目的地的蚂蚁也
会比其他路径多。这样大量的蚂蚁实践之后就找到了最短路径。所以这个过程本质可以概括为以下几
点：
1.路径概率选择机制信息素踪迹越浓的路径,被选中的概率越大
2.信息素更新机制路径越短,路径上的信息素踪迹增长得越快
3.协同工作机制蚂蚁个体通过信息素进行信息交流。
从蚂蚁觅食的原理可见,单个个体的行为非常简单蚂蚁只知道跟踪信息素爬行并释放信息素,但组合后的群
体智能又非常高蚂蚁群能在复杂的地理分布的清况下,轻松找到蚁穴与食物源之间的最短路径。这种特点
恰恰与元启发算法的特点相一致,蚁群优化算法正是受到这种生态学现象的启发后加以模仿并改进而来,觅
食的蚂蚁由人工蚁替代,蚂蚁释放的信息素变成了人工信息素,蚂蚁爬行和信息素的蒸发不再是连续不断
的,而是在离散的时空中进行。
