1.3.1 基本思想

自然界中，蚁群寻找食物时，它们总能找到一条最优的路径。这是因为蚂蚁在寻找路径时会释放出一种特殊的信息素。开始时，环境中没有信息素，蚂蚁完全随机地寻找路径。但随后的蚂蚁会根据先前蚂蚁遗留下来的信息素来选择路径，路径上信息素的强度越高，该路径被选择的概率越大。同时，信息素是一种挥发性物质，如果每只蚂蚁在单位距离上遗留的信息素相同，那么较短路径上的信息素浓度就会更高，最终蚁群会找出最优路径。

首先将m只蚂蚁随机地放到n座城市，并将每只蚂蚁的禁忌表tabu中的第一个元素设置为它此时所在的城市，让各城市之间路径上的信息素量相同，设τ_ij（0）=c，c为较小的常数。让每只蚂蚁根据路径上的信息素量和启发式信息独立地选择将要去的下一个城市，在时刻t，蚂蚁k从城市i转移到城市j的概率为

其中，J_k（i）表示可供蚂蚁k下一次选择的城市的集合，J_k（i）={1，2，…，n}-tabu_k。

tabu_k表中记录了蚂蚁k走过的城市，当所有的城市都进入tabu_k表，表明蚂蚁k完成了一次周游。此时，蚂蚁k走过的路径便是TSP问题的一个可行解。η_ij是一个启发因子，表示蚂蚁从城市i转移到城市j的期望大小。η_ij通常为城市i到城市j距离的倒数。α和β表示信息素和期望启发因子的相对重要程度。当所有的蚂蚁完成一次周游，各条路径上的信息素根据式（1-4）更新：

其中，ρ（0＜ρ＜1）为信息素的蒸发系数，1-ρ表示信息素的持久性系数，Δτ_ij表示此次迭代中路径（i，j）上的信息素增量，Δτ_ij为第k只蚂蚁在本次迭代中留在路径（i，j）上的信息素量。如果蚂蚁k没有经过路径（i，j），则Δτ_ij的值设为0。Δτ_ij的表达式为

其中，Q为正常数，L_k表示第k只蚂蚁在此次周游中所走过路径的长度。