蚁群算法解决旅行商问题的原理与应用

蚂蚁系统（ant system，AS）是最早被提出和实现的蚁群优化算法（Dorigo et al.，1996），也是后续大量蚁群优化算法的原型。

为了说明蚂蚁系统，首先引入旅行商问题（traveling salesman problem，TSP）。旅行商问题是典型的组合优化问题，非常直观和容易理解，但却又是难以解决的NP-complete问题（郭平、鄢文晋，2007）。旅行商问题可以描述为：已知n个城市和城市之间的距离，求一条路径，使旅行商人依次经过每一个城市，总路程最短，且每个城市只经过一次。

TSP问题可以抽象为一个图G=（V，A），其中V为顶点集，A为各顶点相互连接组成的边集，已知各条边的距离，要求寻找其最短的哈密尔顿回路。

对于蚂蚁系统，假设蚁群中存在m只人工蚂蚁，从某个顶点出发遍历各个顶点并最终回到原点。顶点a与顶点b之间的边（a，b）长度为δ（a，b），能见度为η（a，b）。能见度为边的启发式信息，在蚂蚁系统中是固定的，不随着蚂蚁的移动而改变。边（a，b）上的信息素浓度为τ（a，b），随着蚂蚁的移动而逐步更新。

初始化时，设定各条边的初始信息素浓度相同，即τ（a，b）=τ0，τ0为一常数。人工蚂蚁k在搜索过程中，根据各条边的信息素浓度与启发式信息决定选择哪一条边。蚂蚁的选择决策遵循设定的状态转移规则（state transition rule），一般倾向于选择信息素浓度较高的、边长较短的边。在蚂蚁系统中，蚂蚁k从顶点a转移到顶点b的概率Pk（a，b）遵循随机比例原则（randomproportional rule）：

其中，Dk（a）表示蚂蚁k在顶点a可以选择的顶点集合；β表示信息素信息和启发式信息的相对重要程度（β>0）。

可见状态转移概率Pk（a，b）是信息素浓度τ和启发式信息η的函数。对于TSP，一般取边长的倒数为启发式信息：

在蚂蚁系统中，需要对蚂蚁经过的各条边上的信息素进行更新。Dorigo等（1996）设计了三种不同的模型来计算信息素增加量。在蚁密模型（antdensity model）中，当蚂蚁走过一条边时，就需要对这条边的信息素进行更新，其增量为一个常量：(www.xing528.com)

在蚁量模型（ant-quantity model）中，也采用类似的局部更新规则（local updating rule），对蚂蚁所走过的边进行信息素更新，其信息素增量与边长成反比：

而在蚁周模型（ant-cycle model）中，则采用全局更新规则（global updating rule），在蚂蚁完成一个循环，遍历了n个顶点之后，所有边上的信息素按照以下规则进行更新：

其中，ρ为信息素衰减系数（pheromone decay parameter），0<ρ<1；Δτk（a，b）则表示蚂蚁k在边（a，b）上释放的信息素增量：

其中，Hk为第k只蚂蚁在本次循环中所走的哈密尔顿回路，Lk为该回路的长度。

对于上述三种模型，若在本次循环中第k只蚂蚁没有经过边（a，b），则Δτk（a，b）均为0。在前两种模型中，蚂蚁每经过一条边都会更新这条边上的信息素浓度，采用的是局部更新规则；而在蚁周模型中，蚂蚁只有在遍历全部顶点后才更新信息素浓度，采用的是全局更新规则。Dorigo等（1996）对这三种模型进行了计算测试，发现蚁周模型的效果最好。

蚁周算法（ant-cycle algorithm）的伪代码如下所示：

在上述蚂蚁系统中，蚂蚁相互之间并没有直接的交流，而是通过信息素实现间接沟通，这就是所谓的媒介质（stigmergy）（Dorigo et al.，1999）。不过，人工蚂蚁与现实蚂蚁存在明显的区别（郭平、鄢文晋，2007）：（1）人工蚂蚁具有一定的记忆能力，可以引入禁忌表记住已经走过的路径，以保证不会重复走到相同的地点；而现实中的蚂蚁是没有记忆的，蚂蚁完全可能走回到曾经到达过的地点。（2）现实中的蚂蚁只依靠信息素来选择路径；而人工蚂蚁在采用信息素信息的同时，还可以依据一定的启发式信息，比如相邻边的长度，来选择合适的路径。（3）人工蚂蚁生活在一个离散的时间环境中。系统仅考虑人工蚂蚁位于某个节点，而不考虑蚂蚁在节点之间的移动过程，即只考虑在某些离散时间点上的蚂蚁；而现实世界中的蚂蚁则处于一个连续的时间维度中。