蚁群算法

文章目录
  1. 1. 来龙去脉
  2. 2. 主要内容
  3. 3. 应用领域
    1. 3.1. 蚁群算法实现
    2. 3.2. 性能、问题和改进
    3. 3.3. 蚁群算法应用
  4. 4. 参考文档

来龙去脉

知识工程这门课,主要讲三类算法:演化计算、群智能计算和神经计算。

演化计算,包括遗传算法、遗传规划、进化策略和进化规划。
群智能计算,包括蚁群算法和粒子群算法。
神经计算,包括人工神经网络和深度学习神经网络。

本文,主要介绍一下群智能计算中的蚁群算法。

什么是蚁群算法?
蚁群算法(ant colony optimization, ACO),又称蚂蚁算法,是一种用来在图中寻找优化路径的机率型算法。它由Marco Dorigo于1992年在他的博士论文中提出,其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种模拟进化算法,初步的研究表明该算法具有许多优良的性质,并且现在已用于我们生活的方方面面。

主要内容

基本概念(最好举例说明)、蚁群算法描述、蚁群算法实例、蚁群算法特点等。(细节介绍,通常20分钟左右)

应用领域

利用文献法来总结蚁群算法各种领域的应用现状,把你阅读的文献(至少3篇)提前3天发到云盘中. (重点内容介绍,通常讲解20分钟左右),比如,
a)蚁群算法具体如何实现的?
b)性能如何?存在怎样的问题?改进方向如何?
c)在哪些领域的哪些方面应用了蚁群算法?

蚁群算法实现

蚂蚁在运动过程中,会留下一种称为信息素的东西,并且会随着移动的距离,播散的信息素越来越少,所以往往在家或者食物的周围,信息素的浓度是最强的,而蚂蚁自身会根据信息素去选择方向,当然信息素越浓,被选择的概率也就越大,并且信息素本身具有一定的挥发作用。蚂蚁的运动过程可以简单归纳如下:

1、当周围没有信息素指引时,蚂蚁的运动具有一定的惯性,并有一定的概率选择其他方向。
2、当周围有信息素的指引时,按照信息素的浓度强度概率性的选择运动方向。
3、找食物时,蚂蚁留下家相关的A信息素,找家时,蚂蚁留下食物相关的B信息素,并随着移动距离的增加,洒播的信息素越来越少。
4、随着时间推移,信息素会自行挥发。

一个简单的例子,如果现在有两条通往食物的路径,一条较长路径A,一条较短路径B,虽然刚开始A,B路径上都有蚂蚁,又因为B比A短,蚂蚁通过B花费的时间较短,随着时间的推移和信息素的挥发,逐渐的B上的信息素浓度会强于A,这时候因为B的浓度比A强,越来越多的蚂蚁会选择B,而这时候B上的浓度只会越来越强。如果蚂蚁一开始只在A上呢,注意蚂蚁的移动具有一定小概率的随机性,所以当一部分蚂蚁找到B时,随着时间的推移,蚂蚁会收敛到B上,从而可以跳出局部最优。

性能、问题和改进

问题
当蚂蚁在一条路径上觅食很久时,再放置一个近的食物基本没有效果。可以理解为当一只蚂蚁找到一条路径时,过了很久的时间,大多数蚂蚁都选择了这条路径,就在这时候,突然有一只蚂蚁找到了较近的食物,但因为时间过得太久,两条路径上浓度相差太大(浓度越大,被选择的概率就越大),整个系统基本已经停滞了,陷入了局部最优。所以简单的蚂蚁系统是存在一些问题的,如:

1、搜索到一定程度,会出现停滞状态,陷入局部最优的情况。
2、盲目的随机搜索,搜索时间较长。

改进
解决以上问题的办法:

1、增加蚂蚁的数量。
2、减小残留的信息素(所有蚂蚁都减小,部分蚂蚁减小)。
3、减小蚂蚁选择信息素强的路径的概率。
4、给蚂蚁和环境一定的记忆能力,减少搜索空间,从而减少搜索时间。

改进小结

1、蚂蚁数量的选择。
蚂蚁数量 m 是蚁群算法的重要参数之一。蚂蚁数量多,可以提高蚁群算法的全局搜索能力以及算法的稳定性,但大量被搜索过的路径信息素变得平均,会减弱信息正反馈的作用,使搜索的随机性增强,从而降低收敛速度;反之,蚂蚁数量少,特别是当要处理的问题规模比较大时,而从未搜索过的路径信息素接近0,蚁群会倾向选择信息量大的路径,会使搜索的随机性减弱,虽然收敛速度加快,但会使算法的全局搜索能力降低,稳定性差,容易出现停滞现象(局部最优)。

2、信息启发式因子的选择。
信息启发式因子α的大小反映了信息素因素作用的强度。其值越大,蚂蚁选择以前走过路径的可能性越大,搜索的随机性减弱。当α值过大时会使蚁群的搜索过早陷于局部最优;当α值较小时,搜索的随机性增强,算法收敛速度减慢。

3、期望值启发式因子的选择。
期望值启发式因子β的大小反映了先验性、确定性因素作用的强度。其值越大,蚂蚁在某个局部点上选择局部最短路径的可能性越大,算法的随机性减弱,易于陷入局部最优;而β过小,将导致蚂蚁群体陷入纯粹的随机搜索,很难找到最优解。

4、信息素挥发因子的选择。
信息素挥发因子 ρ 的大小直接关系到蚁群算法的全局搜索能力及其收敛速度。 ρ 就是信息素残留系数,反映了信息消逝程度。较大时,由于信息正反馈的作用占主导地位,以前搜索过的路径被再次选择的可能性过大,搜索的随机性减弱;反之,当 ρ 很小时,信息正反馈的作用相对较弱,搜索的随机性增强,因此蚁群算法收敛速度很慢。

改进方法:最大最小蚁群算法、最优最差蚁群算法、分段变异蚁群算法、排序蚁群算法、基于遗传算法的蚁群算法等。

蚁群算法应用

组合优化问题
旅行商问题、0-1背包问题、加工调度问题、装箱问题、图着色问题、聚类问题、最大团问题、最大割问题。
理论上每个组合优化问题都可以通过枚举的方法得到最优解,但枚举是以时间为代价的。有的枚举时间还能接受,有的则不可能接受,即所谓的“组合爆炸”。对于NP完全的组合优化问题,至今尚无很好的解析算法,一般采用启发式算法来解决。

参考文档

自话蚁群算法

自话粒子群算法

自话遗传算法

NP完全问题