Antsystem算法优化：提高效率

ant system算法由Marco Dorigo在1992年提出，是最早的蚁群优化算法，主要特征是在每一次迭代结束后，所有蚂蚁将根据当前自己的环游情况，比如路径长度，对路径上的信息素进行更新。

结合旅行商问题，看一下ant system算法的具体实现过程。

假设有n个城市，城市i和j之间的距离用dij表示，借助于有m只蚂蚁的蚁群，找出从起点到终点的最短路径。用τij（t）表示在t时刻城市i和j之间残留的信息素含量，蚂蚁k表示蚁群中的第k只蚂蚁。在初始时刻，假设各路径上信息素的含量τij（0）为一个很小的常数τ0。每次迭代时，信息素的变化量为：

其中，Q是常数，表示每只蚂蚁一次释放的信息素总量是定值，Lk是蚂蚁k巡游一次的总路径长度。这样，较短的路径上获得的信息素量就较大。

于是，每次迭代后，信息素含量变为：

其中，ρ是信息素挥发速率，m为蚂蚁总数，t+n表示执行完一次迭代后。(www.xing528.com)

蚂蚁通过一种随机机制来选择下一个要访问的城市，假设蚂蚁k在城市i，j为其还未访问过的城市，分子就是到下一个城市路径的信息素和距离综合启发信息，分母表示所有可访问的下一个城市的这些信息的总和，归一化为概率，得到蚂蚁k访问城市j的概率公式（5.12）：

其中，N（Sp）表示蚂蚁k还未访问过的所有可以访问的城市节点，参数α和β用来控制信息素和启发信息ηij的相对重要程度，ηij是城市i和j之间距离的倒数：

其中dij为城市i和j之间的距离。

通过以上方式迭代运行一定次数之后，选择路径中的最小值的路径就可以看作是全局最短路径了。