数学建模：matlab蚁群算法解决TSP问题

很久以前，生物学家就对蚂蚁捕食行为很好奇。因为，可能大家不知道，蚂蚁的视力特别差，你可以把它当成瞎子，可是每次却都能找到食物，并且从它所找到的路径，还是从洞穴到食物的最短路径。大家可以想一想，每次你的桌子上有掉一颗糖，过不了多久，就立马有蚂蚁出现了，而且还是一成群的蚂蚁沿着同一条线路过来的。这是为什么呢？难道是蚂蚁的鼻子很灵敏吗？

后来生物学家们经过长时间的研究发现，并不是蚂蚁的鼻子很灵敏，而是他们之间有一种很特别的信息传递方式——信息素，正是这种特别的信息传递方式，使得蚂蚁这种生物，不会迷路。

言归正传，这个信息素是怎么用的呢？其实是这样的，蚂蚁在行走的过程会释放一种化学物质，这种化学物质就叫“信息素”，这是用来标识自己的行走路径。而在寻找食物的过程中，蚂蚁根据这个信息素的浓度来选择行走的方向，最终就到达了食物的所在地。

假设蚂蚁们在A点，食物在B点，蚂蚁要去食物有两条路径，即路径a和路径b。现在A点有两只蚂蚁要去取食物，假设两只蚂蚁分别名字分别为蚂蚁a和蚂蚁b，即蚂蚁a沿a路径走，蚂蚁b沿b路径走。

现在咱们假设两只蚂蚁的速率、留下信息素速率和信息素挥发速率是一样的。

那么显然蚂蚁a比蚂蚁b更快到达B点，即a路径的信息素已经布满a路径(假设在a路径最开始端的信息素没有挥发完)，那么b路径的信息素目前只分布到一半(可能到红叉之前)，那么现在蚂蚁a开始取上食物往回走。 蚂蚁a往回走会选择信息素浓度高的路径，即a路径，那么蚂蚁a沿原路径回到A点的路上时，蚂蚁b到达B点，蚂蚁b也要取上食物往回走，也要沿信息素浓度最高的路径走，因为a路径蚂蚁a走过两次，所以信息素浓度比b路径高，那么蚂蚁b也会沿着a路径往回走，那么此时a路径的浓度又会增加。

那么，每当以后有蚂蚁要从A点去B点取食物，便会沿着信息素浓度高的路径，即a路径，那么a路径的信息素浓度也会越来越高。那么信息素最多的路径即为最短路径。

蚁群算法就是蚂蚁寻找食物的过程，而把多个食物放在不同的地方，就是著名的TSP(Traveling Salesman Problem)问题,而信息素分布最的路线就是最短的路径。

α − − 信 息 素 启 发 式 因 子 ， 它 反 映 了 信 息 素 对 蚂 蚁 路 径 选 择 的 作 用 ； β − − 期 望 启 发 式 因 子 ， 它 反 映 了 信 息 素 在 蚂 蚁 选 择 路 径 时 被 重 视 的 程 度 ； d i j − − 城 市 i 和 j 之 间 的 距 离 ; η i j ( t ) − − 启 发 函 数 ， 表 达 式 为 η i j ( t ) = 1 d i j ； t a b u k − − 禁 忌 表 ， 记 录 蚂 蚁 k 当 前 所 走 过 的 城 市 ； τ i j − − 城 市 i 到 城 市 j 的 路 径 上 的 信 息 素 的 量 ； \alpha-- 信息素启发式因子，它反映了信息素对蚂蚁路径选择的作用；\\ \beta -- 期望启发式因子，它反映了信息素在蚂蚁选择路径时被重视的程度；\\ d_{ij} -- 城市i和j之间的距离;\\ \eta_{ij}(t)-- 启发函数，表达式为\eta_{ij}(t)=\frac{1}{d_{ij}}；\\ tabu_k -- 禁忌表，记录蚂蚁k当前所走过的城市；\\ \tau_{ij} -- 城市i到城市j的路径上的信息素的量；\\ α−−信息素启发式因子，它反映了信息素对蚂蚁路径选择的作用；β−−期望启发式因子，它反映了信息素在蚂蚁选择路径时被重视的程度；dij​−−城市i和j之间的距离;ηij​(t)−−启发函数，表达式为ηij​(t)=dij​1​；tabuk​−−禁忌表，记录蚂蚁k当前所走过的城市；τij​−−城市i到城市j的路径上的信息素的量；

2. 蚂蚁留下的信息素，因为是化学物质，因此随着时间的过去信息素也应该要以一定的速率挥发。根据不同的规则我们可以将蚁群算法分为三种模型——蚁周模型(Ant-Cycle)、蚁量模型(Ant-Quantity)和蚁密模型(Ant-Density)。 　 区别： (1).蚁周模型利用的是全局信息，即蚂蚁完成一个循环后更新所有路径上的信息素； (2).蚁量和蚁密模型利用的是局部信息，即蚂蚁完成一步后更新路径上的信息素。

通常使用的是蚁周模型，故本文只介绍蚁周模型。 　 根据上面所提供的信息，我们可以知道，当所有的蚂蚁完成一次路径循环后，才更新信息素。因此路径上的信息素应该分为两部分：之前未挥发所残留的信息素 + 经过当前循环所有蚂蚁在经过该路径后所留下的信息素。用公式表述如下： τ ( t + n ) = ( 1 − ρ ) ⋅ τ i j ( t ) + Δ τ i j ( t , t + n ) Δ τ i j ( t , t + n ) = ∑ k = 1 m Δ τ i j k ( t , t + n ) \tau (t+n)=(1-\rho)·\tau_{ij}(t)+\Delta \tau_{ij}(t,t+n)\\ \Delta \tau_{ij}(t,t+n)=\sum^m_{k=1} \Delta \tau^k_{ij}(t,t+n) τ(t+n)=(1−ρ)⋅τij​(t)+Δτij​(t,t+n)Δτij​(t,t+n)=k=1∑m​Δτijk​(t,t+n) 其 中 ， ρ − − 信 息 素 挥 发 因 子 ， ρ ∈ [ 0 , 1 ) ρ ∈ [ 0 , 1 ) ； Δ τ i j ( t , t + n ) − − 经 过 一 次 循 环 后 城 市 i 到 城 市 j 的 路 径 上 的 信 息 素 的 增 量 ； 　 　 ( t , t + n ) − − 走 过 n 步 以 后 蚂 蚁 即 完 成 一 次 循 环 ； Δ τ i j k ( t , t + n ) − − 表 示 经 过 一 次 循 环 后 蚂 蚁 k 在 它 走 过 的 路 上 的 信 息 素 增 量 。 其中， \rho -- 信息素挥发因子，ρ∈[0,1)ρ∈[0,1)；\\ Δτ_{ij}(t,t+n) -- 经过一次循环后城市i到城市j的路径上的信息素的增量；　　\\ (t,t+n) -- 走过n步以后蚂蚁即完成一次循环；\\ Δτ_{ij}^k(t,t+n) -- 表示经过一次循环后蚂蚁k在它走过的路上的信息素增量。\\ 其中，ρ−−信息素挥发因子，ρ∈[0,1)ρ∈[0,1)；Δτij​(t,t+n)−−经过一次循环后城市i到城市j的路径上的信息素的增量；　　(t,t+n)−−走过n步以后蚂蚁即完成一次循环；Δτijk​(t,t+n)−−表示经过一次循环后蚂蚁k在它走过的路上的信息素增量。 　好了，现在我们的未挥发所残留的信息素很好解，定义一个信息素挥发因子ρρ便能解决。但是，经过一次循环所有蚂蚁留下的信息素该怎么定义？在蚁周模型中，它被定义如下： Δ τ i j k ( t , t + n ) = { Q L k                     A n t k w a l k t h o u g h p a t h ( i , j ) 0                                                            o t h e r \Delta \tau^k_{ij}(t,t+n)= \left\{ \begin{aligned} \frac {Q}{L_k} ~~~~~~~~~~~~~~~~~~~Ant k walk though path (i,j)\\0~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ other \end{aligned} \right. Δτijk​(t,t+n)=⎩⎪⎨⎪⎧​Lk​Q​                   Antkwalkthoughpath(i,j)0                                                          other​ 　　它表明，蚂蚁留下的信息素跟它走过的完整路径的总长度有关。越长则留下的信息素越少，这个应该很好理解。为了找到更短的路径，就应该让短的路径信息素浓度高些。

3.蚁群算法基本步骤 (1) 参数初始化：

通常可以按照以下策略来进行参数组合设定：

确定蚂蚁数目 参数粗调：即调整取值范围较大的α，β及Q； 参数微调：即调整取值范围较小的ρ； (2) 随机将蚂蚁放于不同出发点，对每只蚂蚁计算其下个访问城市，直到所有蚂蚁访问完所有城市。 (3)计算蚂蚁经过的路径长度 (4) 判断是否达到最大迭代次数，若否，返回步骤2；是，结束程序。 (5) 输出结果，并根据需要输出寻优过程中的相关指标，如运行时间、收敛迭代次数等。

下面是各个地方的xy坐标

1304 2312 3639 1315 4177 2244 3712 1399 3488 1535 3326 1556 3238 1229 4196 1004 4312 790 4386 570 3007 1970 2562 1756 2788 1491 2381 1676 1332 695 3715 1678 3918 2179 4061 2370 3780 2212 3676 2578 4029 2838 4263 2931 3429 1908 3507 2367 3394 2643 3439 3201 2935 3240 3140 3550 2545 2357 2778 2826 2370 2975

转载请标明出处，谢谢！。

如果感觉本文对您有帮助，请留下您的赞，您的支持是我坚持写作最大的动力，谢谢！