1、TSP问题介绍

旅行商问题(TravelingSalesmanProblem，TSP)是一个经典的组合优化问题。经典的TSP可以描述为：一个商品推销员要去若干个城市推销商品，该推销员从一个城市出发，需要经过所有城市后，回到出发地。应如何选择行进路线，以使总的行程最短。

2、实例

本问以下列城市点作为实例来编写对应的蚁群算法代码（假定推销员任意选择一个城市出发）。

用图形表示如下：

3、蚁群算法

关于蚁群算法的介绍就不在这浪费时间了，可以去网上搜一下，但为了对蚁群算法有个系统的认知还是要上蚁群算法的流程图，对着流程图来介绍具体是如何实现的。

3.1、变量初始化

变量初始化主要是设置蚂蚁个数m，信息素挥发因子等参数（不懂的先不要紧，继续看后面的，这些参数都是为后续步骤服务的）。

3.2、将m只蚂蚁放到n个元素上

将m只蚂蚁随机放到n个城市，如将6个蚂蚁放到30个城市，则可以使用randperm函数（randperm函数不会使用的可参考matlab文档）随机选择一个城市点的序号，然后循环为每个蚂蚁选择一个城市。

3.3、m只蚂蚁按概率完成周游

以1只蚂蚁为例（m只蚂蚁可使用循环进行对应操作），此时需要一个禁忌表（也就是存储蚂蚁已经到达过的城市）以及一个待访问的城市表，如蚂蚁已访问过的城市为[1,2]，则待访问城市列表为[3,4,...,29,30]，下面需要计算蚂蚁从2号城市去往[3,4,...,29,30]这几个城市的概率，概率计算公式（代表从i号城市去往j号城市的概率）如下：

Jk(i)代表从i号城市可继续访问的城市（待访问城市[3,4,...,29,30]），s代表待访问城市中的任意一个。 \tau{ij}(t)

代表第t次迭代是从i号城市去往j号城市的信息素， \eta{ij}(t)表示从i号城市到j号城市的期望程度，通常取i号城市到j号城市的距离倒数（i号城市距离j号城市距离越小，则待其倒数越大，从而期望程度越大）。

为蚂蚁从i号城市去往待访问城市所有的信息素与期望程度乘积的和，从而可得到蚂蚁从i号城市去往每个待访问城市的概率。

接下来采用轮盘赌的形式决定蚂蚁下个城市去往哪。轮盘赌的操作如下（为了使表述方便，现假定蚂蚁已经走完前24个城市[1,2,...,23,24]），可通过上述概率计算得到蚂蚁从24号城市去往去往剩下6个城市的概率P，假定计算得到的P值如下:

由于上述概率不好进行操作，所以需先对概率进行归一化（用各个概率/6个城市的概率和）得到归一化后的P:

用饼图可表示为：

这就相当于投飞镖扔中那个就去那个，但由于matlab的rand函数只能生成（0,1）之间的随机数，所以再将归一化后的P进行逐次累和得到：

这样如生成的随机数为0.2时位于区间（0.1875,0.2500）之间，因此蚂蚁下一个选择的城市可定为27号城市。

3.4记录本次最佳路线

根据上述得到的m只蚂蚁的访问路径可得到每个蚂蚁访问完所有城市的总距离，然后选择最短距离的路程作为本次迭代的最佳路径。

3.5更新信息表

第t+n次迭代的信息表可通过以下公式更新：

其中前半部分为信息素的一个挥发（模拟自然的蚂蚁信息素随时间挥发，也就是每次迭代信息素会减少），后半部分代表从i号城市到j号城市蚂蚁走过留下的信息素（从i号城市到j号城市的信息素越高根据上面的概率计算公式则代表从i到j的概率越大，也就是从i到j的距离相对从i到其他城市来说距离更近）。

Q为一个常数，Lk为蚂蚁k访问完所有城市的距离。

运行结果如下：

本文代码可通过我的个人公众号 MATLAB分享 自取。

建议照着我的代码敲一遍，这样可以更好的理解。