智能算法-蚁群算法(2)

智能算法-蚁群算法(2)插图

 

1. 蚁群算法

蚁群算法基本概念介绍及名词解释请见上一篇博文:智能算法-蚁群算法(1)

故事性简单理解:一群蚂蚁想寻找食物。在讨论下,它们决定分头去寻找食物,为每只蚂蚁随机选择出发地,规定每只蚂蚁爬行速度相同,并且每只蚂蚁在爬过的地方会释放信息素,信息素会随着时间逐渐挥发,残留在地上的浓度会越来越低。之后的蚂蚁会更倾向于去探索信息素残留浓度高的那条路,因为这说明上一只蚂蚁爬过这条路找到当前最优解所用的时间短,也就是这条路的距离更短。以这样的方式,不断重复,最终找到最优解。

2. 示例详解

2.1 问题阐述

以蚁群算法解决旅行商问题(TSP)举例。旅行商问题,即从一个城市出发,经过所有城市,最终再回到出发城市,请找到最短的路径的方案。四个城市A、B、C、D之间的举例矩阵如下所示:

智能算法-蚁群算法(2)插图1 规定:蚂蚁种群的规模 m=3,预先设置的参数𝛼=1,预先设置的参数𝛽=2,信息素的蒸发率 𝜌=0.5

2.2 步骤一:初始化

首先使用贪婪算法得到路径(ACDBA),则该初始路径所用的距离为 Cnn=f(ACDBA)=1+2+4+3=10

路径初始信息素浓度:

智能算法-蚁群算法(2)插图2

初始化所有边上的信息素: 𝜏𝑖𝑗=𝜏0

2.3 步骤二:为每只蚂蚁选择探索路径

2.3.1 选择每只蚂蚁初始出发城市

本题设定共有3只蚂蚁,为每只蚂蚁随机选择出发城市,假设蚂蚁1选择城市 A,蚂蚁2选择城市 B,蚂蚁3选择城市 D(此处出发城市选择是随机的,也可以使用其他方式来选择)。

2.3.2 选择下一个访问城市

为每只蚂蚁选择下一访问城市。以蚂蚁1为例,当前出发城市 i=A

可访问城市集合:𝐽1(i) = {𝐵,𝐶,𝐷}

蚂蚁𝑘当前从城市 𝑖 出发,选择城市 𝑗 作为下一个访问对象的概率为: 智能算法-蚁群算法(2)插图3

通过以上固定公式计算蚂蚁1选择B、C、D作为下一访问城市的概率:

智能算法-蚁群算法(2)插图4

轮盘赌法则选择下一访问城市。假设产生的随机数 q=random(0,1)=0.05<0.081,则蚂蚁1将会选择城市 B (此处使用的是轮盘赌选择方式,也可以使用其他选择方式,例如:直接选择概率最大的作为下一个访问城市)

用同样的方法为蚂蚁2和3选择下一访问城市,假设蚂蚁2选择城市 D,蚂蚁3选择城市 A

2.3.3 继续选择下一个访问城市

当前蚂蚁1所在城市 B,路径记忆向量 𝑅1=(𝐴𝐵),可访问城市集合𝐽2 (𝑖) = {𝐶,𝐷}。

计算蚂蚁1选择 𝐶𝐷 作为下一城市的概率:

智能算法-蚁群算法(2)插图5 同样使用轮盘赌选择策略选择下一访问城市。假设产生的随机数 𝑞=𝑟𝑎𝑛𝑑𝑜𝑚(0,1)=0.67,则蚂蚁1将会选择城市 𝐷

用同样的方法为蚂蚁2和3选择下一访问城市,假设蚂蚁2选择城市 𝐶,蚂蚁3选择城市 𝐷

2.3.4 构造出三只蚂蚁的完整路径

此时三只蚂蚁第一次探索的路径已经构造完毕:

  • 蚂蚁1构建的路径为 (**AB**CDA)
  • 蚂蚁2构建的路径为 (BDC**AB**)
  • 蚂蚁3构建的路径为 (DACBD)

2.4 步骤三:信息素更新

计算每只蚂蚁构建的路径长度:

  • 蚂蚁1的路径长度:C1=3+4+2+1=10
  • 蚂蚁2的路径长度:C2=4+2+1+3=10
  • 蚂蚁3的路径长度:C3=2+1+5+4=12

更新每条边上的信息素:初始路径上挥发剩下的信息素+3只蚂蚁刚走过的信息素 智能算法-蚁群算法(2)插图6 注:(1/10+1/10)是因为3只蚂蚁中有两只蚂蚁经过了AB路径,(1/12)是因为3只蚂蚁有一只经过了AC路径。

2.5 步骤四:循环迭代

如果满足约束条件(算法循环结束条件),则输出全局最优结果并结束程序,否则,转向步骤2.3.1继续执行。

发表评论

后才能评论