蚁群算法之二

蚁群算法之二：蚂蚁系统模型的建立，给定G=(V,A)，其中V为定点集，A为各顶点互相连接组成的边集,已知各顶点之间的连接距离，要求确定一条长度最短的回路，仅遍历一次所有顶点的回路。

引入记号：

m：蚁群中蚂蚁的数量；bi（t）：t时刻位于城市i的蚂蚁的数量 dij：城市i和j之间的距离 nij：边（i，j）的能见度，反映城市i转移到城市j的启发程度（启发程度越高，选择该路的概率越高）；γij:(i,j)边上的信息素轨迹强度；蝶儿他γij，蚂蚁在边（i，j）上留下的单位长度轨迹信息素量；pkij:,蚂蚁k的转移概率，j是将要到的城市。

每只蚂蚁完成的操作如下所示：

① 从城市i转移到城市j的过程或是完成一次循环之后，蚂蚁在边（i，j）上释放信息素；

② 蚂蚁概率地选择下个要访问的城市，这个函数与连接两城市的路径上的信息素有关。

③ 为了满足问题的约束条件，在完成一次循环之前，不允许蚂蚁选择已经访问过的城市。（这个问题的约束条件是什么？）

简单的蚁群算法的基本流程

① 初始化蚁群

② 选择第i只蚂蚁（i从0开始），对每只蚂蚁的适应度做一评价

③ 释放信息素 蚂蚁的适应度越高，释放的信息素越多

④ 蚂蚁移动 蚂蚁根据前面蚂蚁累积的信息素和自己的判断移动

④ 信息素的挥发

初始时刻，各条路径上的信息素量相等。在T=0的时候，初始信息素轨迹强度全为C。蚂蚁使用的状态转移规则称为随机比例规则，转移概率的计算如下：对于允许到达的重点来说，转移状态=要走的路的信息素轨迹强度的α次*要走的路的可见度的β次/（所有路的信息素轨迹强度的α次之和*所有路的可见度β次之和）。可以通过调整α和β来反映相对重要性。

蚁密系统模型：一只蚂蚁经过路径（i，j）上释放的信息量为每单位Q

蚁量模型：一只蚂蚁在经过路径（i，j）上释放的信息量为每单位长度Q/dij.