蚁群算法求解TSP问题（Python实现）_蚁群算法解决tsp问题

 算法简介

        蚁群系统(Ant System或Ant Colony System)是由意大利学者Dorigo、Maniezzo等人于20世纪90年代首先提出来的。他们在研究蚂蚁觅食的过程中，发现单个蚂蚁的行为比较简单，但是蚁群整体却可以体现一些智能的行为。例如蚁群可以在不同的环境下，寻找最短到达食物源的路径。这是因为蚁群内的蚂蚁可以通过某种信息机制实现信息的传递。后又经进一步研究发现，蚂蚁会在其经过的路径上释放一种可以称之为“信息素”的物质，蚁群内的蚂蚁对“信息素”具有感知能力，它们会沿着“信息素”浓度较高路径行走，而每只路过的蚂蚁都会在路上留下“信息素”，这就形成一种类似正反馈的机制，这样经过一段时间后，整个蚁群就会沿着最短路径到达食物源了。

        蚁群算法应用于解决优化问题的基本思路为：用蚂蚁的行走路径表示待优化问题的可行解，整个蚂蚁群体的所有路径构成待优化问题的解空间。路径较短的蚂蚁释放的信息素量较多，随着时间的推进，较短的路径上累积的信息素浓度逐渐增高，选择该路径的蚂蚁个数也愈来愈多。最终，整个蚂蚁会在正反馈的作用下集中到最佳的路径上，此时对应的便是待优化问题的最优解。

蚁群觅食过程分析

举个简单的例子

 

         蚂蚁群要从A（巢穴）到B（食物），最开始会派出一部分蚂蚁（代号1）走ACB路径，还有一部分蚂蚁（代号2）会走ADB路径，因为起初蚂蚁也不知道哪条路径短，所以每条路径都会有一部分蚂蚁去试探。在1走完路径到达B时，2还在路途中，此时ACB整条路径都已经有蚂蚁1留下的信息素了，而ADB只有一部分路径有信息素。在蚂蚁1返回到起点A的时候，蚂蚁2仍在途中（甚至可能还没有到达B点）。这样一来蚂蚁1就在路径ACB上留下了两次信息素，信息素浓度肯定比ADB路径上的高。

        随后的蚂蚁就会选择信息素的浓度大的路径，由此往复加上信息素的挥发，最终所有蚂蚁都会选择最短的一条路径。其余路径的信息素都会挥发至0。

TSP求解思路        

首先将m只蚂蚁随机放置在n个城市，然后对单个蚂蚁进行路径搜索。

t时刻位于城市i的第k只蚂蚁选择下一个城市j的概率为:

Allowed:蚂蚁k下一步允许选择的城市集合

表示t时刻边(i,j)上的信息浓度

是距离定义的启发信息

参数α和β反映了信息素与启发信息的相对重要性，用来调节信息素与距离的重要程度。其中如果令α=0，β!=0该算法则成了贪婪启发式算法。单只蚂蚁仅根据距离来选择下一城市。如果令α!=0，β=0，则单只蚂蚁仅根据信息素来选择下一城市。

距离采用欧氏距离，根据题目所给坐标点，计算两点之间的欧氏距离即可。

信息素更新方法如下:

其中：Q为常数, wk表示第k只蚂蚁在本轮迭代中走过的路径，Lk为