蚁群优化算法之精华蚂蚁系统和排列蚂蚁系统学习笔记

一、基础知识点笔记

启发式信息：它是利用问题拥有的启发信息来引导搜索，达到减少搜索范围、降低问题复杂度的目的，这种利用启发信息的搜索过程称为启发式搜索。
算法收敛：算法的收敛是指经过多步迭代之后得出的数值不应该无限的增大, 而是趋于某个数值, 不收敛的算法是不能用的, 你也根本得不出结果的, 更不用考虑其可靠性了。
TSP（旅行商问题）：找到从某个城市 C i 出发，访问所有城市且只访问一次，最后回到C i 的最短封闭路径。
贪婪算法：在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解。
算法早熟：一般称之为“早熟”，是遗传算法中的一种现象。指在遗传算法早期，在种群中出现了超级个体，该个体的适应值大大超过当前种群的平均个体适应值。从而使得该个体很快在种群中占有绝对的比例，种群的多样性迅速降低，群体进化能力基本丧失，从而使得算法较早收敛于局部最优解的现象。
早熟收敛的本质特征：是指群体中的各个个体非常相似，群体的多样性急剧减少，当前群体缺乏有效等位基因（最优解位串上的等位基因），在遗传算子作用下不能生成高阶竞争模式。

二、精华蚂蚁系统

回忆AS算法：
其中表示初始信息素，m是蚂蚁的个数，是由贪婪算法构造的路径长度。
AS中城市i与城市j的相连边上的信息素计算公式：
由此公式可知，蚂蚁在其爬过的边上释放与其构建路径长度成反比的信息素量，蚂蚁构建的路径越好，属于路径的各个边上的信息素就越多，这些边在以后的迭代中被蚂蚁选择的概率越大。
AS算法的局限：我们仍然以TSP(旅行商问题)举例，当城市的规模较大时，问题的复杂度呈指数增长，仅仅靠这样一个基础单一的信息素更新机制引导搜索偏向，搜索效率有瓶颈，为此我们想通过一种额外的手段强化某些最有可能成为最优路径的边，让蚂蚁搜索的范围更快、更正确的收敛。
精华蚂蚁系统：是对AS的一次改进，它在原AS信息素更新的原则的基础上增加了一个对至今最优路径的强化手段，在每轮信息素更新完毕后，搜索到至今最优路径（Tb )的那只蚂蚁将会为这条路径添加额外的信息素。
信息素跟新公式：
- 公式分析：上述公式在原AS系统信息素公式：

增加了 b (i,j)，并定义参数e 作为 b (i,j) 的权值。Cb 是算法开始至今最优路径的长度，可见，ESA在每轮迭代中为属于Tb 的边增加了额外的 e / Cb 的信息素量，一般设置e等于城市规模n。

结论：ESA引入这种额外的信息素强化手段有助于更好地引导蚂蚁搜索的偏向，使算法更快收敛。Dorigo等人对ESA求解TSP问题进行了实验仿真，结果表明在一个合适的参数e值作用下,ESA有着较AS更高的求解精度与更快的进化速度。

三、居于排列的蚂蚁系统

引言：在精华蚂蚁系统被提出后，人们想有没有一种方法能使得Tb 各边的信息浓度得到加强，同时对其余边的信息素更新机制也有改善？
基于排列的蚂蚁系统：它就是上述的改进版本，它在AS的基础上给蚂蚁要释放的信息素大小 k (i,j)加上一个权值，进一步加大各边信息素量的差异，以知道搜索。
核心思想：在每一轮所有蚂蚁构建完路径后，它们讲按照所得路径的长短进行排名，只有生成了至今最优路径的蚂蚁和排名在前（w-1）的蚂蚁才被允许释放信息素，蚂蚁在边（i,j）上释放的信息素 k (i,j)的权值由蚂蚁的排名决定。
公式：
- w：构建至今最优路径Tb （该路径不一定出现在当前迭代的路径中，各种蚁群算法均假设有记忆功能，至今最优的路径总是能被记住的）的蚂蚁产生信息素的权值大小。
- Cb 是算法开始至今最优路径的长度。
- 路径Tb 将获得最多的信息素量，w b (i,j) 等价于 w/Cb 。
- 路径长度排名越前的蚂蚁释放的信息数量越大，权值（w-k）对不同路径的信息素浓度差异起到了一个放大的作用。
结果：ASrank 具有较 AS 已经 EAS更高的寻优能力和更快的求解速度。