群智能算法 —— 蚁群算法优化 Ant Colony Optimization

HuldaGnodim · 发表于 2022-6-21 11:29

ACO介绍
蚂蚁利用感觉(sensing)线索来寻找从它们的巢穴到食物来源的最短路线。在这些蚂蚁群中，每只蚂蚁在不知道其他蚂蚁在做什么的情况下执行非常简单的群体行动，但其结果显示出高度社会化和结构化。即使现在的路线被破坏或被障碍物阻挡，它们也能很容易地找到它们追踪目标的下一条最短路线 (Fig.1.1)。蚂蚁的这种技能得益于一种叫做信息素踪迹(pheromone trails)，这种化学品有蒸发的趋势。最初，蚂蚁随机地探索巢穴周围的区域来寻找食物来源。在寻找到食物来源后，蚂蚁携带一些食物返回其巢穴。在携带食物返回时，它们在地面上沉积一种有机化合物，被称为信息素。通常，它们在携带食物返回时沉积更多的信息素，而在寻找食物来源时产生较少的信息素。这种沉积在地上的化学物质引导它们的同伴到达食物源。附近的蚂蚁可能更喜欢追踪信息素浓度最高的路径。

Fig.1.1 Traveling Behavior of Ant Colony

a)两点之间直线最短，蚂蚁以直线行进，觅食的蚂蚁和有食物的相邻蚂蚁使用相同的路径。我们假设所有的蚂蚁都以正常的速度行驶，因此大多数蚂蚁会在平均时间内出现在最短的路径上。因此，信息素浓度将在最短路径上增加。一段时间后，这些路径上信息素水平的差异将很容易被进入系统的新蚂蚁所识别。
b)最短路径的信息素轨迹被一个障碍物打断，蚂蚁无法在这种情况下遵循最短路径，因此寻求新的路径。
c)由于信息素线索的丢失，蚂蚁会随机地左转和右转
d)一些蚂蚁找到了绕过障碍物的最短路线并迅速积累起中断的信息素。与那些走长路的蚂蚁相比，它们会迅速积累中断的信息素踪迹。由于更多的蚂蚁遵循新的最短的路径，信息素浓度水平将不断增加。

Ant System (AS ) 蚂蚁系统理论

特点：在每一次迭代中，信息素的浓度都会被更新（蚂蚁在迭代中参与了解决方案的构建）。

a)所有蚂蚁m在开始阶段被随机初始化
b)这m只蚂蚁被设置在构建框架的顶点上，并且在所有的边上都分配了恒定的信息素踪迹强度, i.e. τ (i, j) = 1 (i, j) ∈ Allowed, Allowed代表蚂蚁的可行邻居的集合
每只人造蚂蚁都是具有以下特征的代理(Agent)：
a) 更倾向于在信息素概率最高的框架上行走
b) 已经访问过的边被禁止，直到回路完成
c) 当旅程结束时，“踪迹”在每个访问过的边上被更新
理论：在每一个解决方案的构建级别或步骤中，每只蚂蚁都会逐步将其部分物质添加到部分构建解决方案框架中。假设第i条边的第k只蚂蚁，在第t个建筑步骤中，从第i条边到建筑的下一条边进行随机行走，在每条边上，蚂蚁都会做出随机的决定来选择下一个节点或边。这些决定是根据一条边到另一条边相对于蚂蚁当前边的过渡概率(transition probability)作出的。位于第i条边的第k只蚂蚁向第j条边移动的过渡概率可以通过随机比例状态过渡法来确定。

τ(i, j)表示路径(i, j)的信息素强度，是边i和j之间的连接。η(i, j)是一个启发式的值(heuristic value)，也被称为路径(i, j)的可见度(visibility)，通常被设定为连接成本或距离的倒数。
假设d（i，j）代表路径（i，j）的长度，那么η（i，j）的值可以被计算为1/d（i，j）。
N(sp)是第i条边上第k只蚂蚁的可行组件或权宜的邻居集合。 α和β是控制参数，用于决定信息素与启发式值的相对重要性，α, β ∈（0，1]。

τk(i, j)被称为第k只蚂蚁铺设的信息素数量，以路径（i, j）的每单位长度来衡量

Q和Lk分别代表常数（通常，Q=1）和第k只蚂蚁的总行程长度

举例说明:起点和终点-星星
CG:在两条边之间旅行所涉及的成本
PG:两条边之间的信息素计算值
一只新的蚂蚁从边缘星开始它的旅程，将向三角形代表的边缘移动，因为这条路径的信息素浓度最高，即0.1，相比之下，其他两条路径的信息素浓度分别为0.07和0.03

算法流程图

数学计算举例

TSP问题（traveling salesman problem）

假设五个城市，坐标分别为 X=[79,87,13,67,63], Y = [31,90,23,82,17]
Step 1：定义ACO算法参数，例如population size = 4, maximum iteration = 1, α = 1.0, β = 1.0, τ0 = 0.01, and ρ = 0.02.
Step 2：决定euclidean distances

Step 3: 决定启发式的η（路径的可见性）

Step 4:初始信息素强度τ是随机分配给边缘

Step 5：开始ACO算法的迭代循环。检查：是否达到了最大的迭代次数——是，Step18，否则Step6。
Step 6：随机选择一个顶点/节点/城市来开始蚂蚁1号的旅程。假设是城市 “3”，则蚂蚁1号将从城市3开始其旅程。
Step 7：更新蚂蚁的循环。如果所有蚂蚁的路径都被覆盖，那么Step15，否则Step8。

Step 8：使用（1.1）来确定蚂蚁1号从城市3号出发到其他城市的路径的概率。蚂蚁1号去到城市1号的概率：

Step 9: RWS(roulette wheel selection)on P, 计算最可能拜访的城市，假设4号城市概率最高，那么蚂蚁1号

的根被更新为 ant(1,:)=[3,4]
Step 10:重复Step8,计算蚂蚁1号从当前城市4去其他城市的概率 P $P^T_{4} =[0.1031\ 0.6759\ 0.1850\ 0\ 0.0361]^T$
Step 11:已拜访城市概率设置为0，以避免重复造访。 $P^T_{4} =[0.1031\ 0.6759\ 0\ 0\ 0.0361]^T$
假设(RWS)指定拜访2号城市。路径更新： $ant(1,:)=[3,4,2]$ 类似假设蚂蚁1号旅行结束返回3号城市： $ant(1,:)=[3,4,2,5,1,3]$
Step 12:计算fitness或蚂蚁travel的距离：
$D(3,4)=79.98\\ D(4,2)=21.54\\ D(2,5)=76.84\\ D(5,1)=21.26\\ D(1,3)=66.48\\ Fit(1)=266.10 (以上相加)$

重复Step8-Step12，得到其他蚂蚁的相关数据：

  Step 13: 比较得出最好的fitness, 保存为最短路径

Step 14:  返回Step7
Step 15:  更新信息素密度(pheromone intensity) τ :

类似的，其他蚂蚁的信息素更新：

Step 16：蒸发掉ρ量的信息素,剩下的信息素密度：

Step 17: 返回Step15.
Step 18: print the best ant, i.e. best_ant, and its fitness, best_fit.
总结

ACO：基于模型的搜索（MBS）技术（model based search)
寻找组合优化问题的最优解
a.Scheduling Prob 进度安排问题
b.Vehicle Routing Prob 车辆路径
c.Assignment Prob 分派问题
d.Device Sizing Prob in Physical Design 物理设计中的设备量尺问题
e.Edge Detection in Image Processing 图像处理中的边缘检测
f.Classification 分类
g.Data Mining 数据挖掘
特点
(1)采用正反馈机制，使得搜索过程不断收敛，最终逼近最优解。
(2)每个个体可以通过释放信息素来改变周围的环境，且每个个体能够感知周围环境的实时变化，个体间通过环境进行间接地通讯。
(3)搜索过程采用分布式计算方式，多个个体同时进行并行计算，大大提高了算法的计算能力和运行效率。
(4)启发式的概率搜索方式不容易陷入局部最优，易于寻找到全局最优解。
规则
(1)感知范围：蚂蚁观察到的范围是一个方格世界，相关参数为速度半径，一般为3，可观察和移动的范围为3x3方格。
(2)环境信息：蚂蚁所在环境中有障碍物、其他蚂蚁、信息素，其中信息素包括食物信息素(找到食物的蚂蚁留下的)、窝信息素(找到窝的蚂蚁留下的)，信息素以一定速率消失。
(3)觅食规则：蚂蚁在感知范围内寻找食物，如果感知到就会过去；否则朝信息素多的地方走，每只蚂蚁会以小概率犯错误，并非都往信息素最多的方向移动。蚂蚁找窝的规则类似，仅对窝信息素有反应。
(4)移动规则：蚂蚁朝信息素最多的方向移动，当周围没有信息素指引时，会按照原来运动方向惯性移动。而且会记住最近走过的点，防止原地转圈。
(5)避障规则：当蚂蚁待移动方向有障碍物时，将随机选择其他方向；当有信息素指引时，将按照觅食规则移动。
(6)散发信息素规则：在刚找到食物或者窝时，蚂蚁散发的信息素最多；当随着走远时，散发的信息素将逐渐减少。

		自动登录	找回密码
密码			立即注册

群智能算法 —— 蚁群算法优化 Ant Colony Optimization

本帖子中包含更多资源