2024年4月20日发(作者：)
...
2.1 蚁群算法的基本原理
蚁群优化算法是模拟蚂蚁觅食的原理，设计出的一种群集智能算法。蚂蚁在
觅食过程中能够在其经过的路径上留下一种称之为信息素的物质，并在觅食过程
中能够感知这种物质的强度，并指导自己行动方向，它们总是朝着该物质强度高
的方向移动，因此大量蚂蚁组成的集体觅食就表现为一种对信息素的正反馈现
象。某一条路径越短，路径上经过的蚂蚁越多，其信息素遗留的也就越多，信息
素的浓度也就越高，蚂蚁选择这条路径的几率也就越高，由此构成的正反馈过程，
从而逐渐的逼近最优路径，找到最优路径。
蚂蚁在觅食过程时，是以信息素作为媒介而间接进行信息交流，当蚂蚁从食
物源走到蚁穴，或者从蚁穴走到食物源时，都会在经过的路径上释放信息素，从
而形成了一条含有信息素的路径，蚂蚁可以感觉出路径上信息素浓度的大小，并
且以较高的概率选择信息素浓度较高的路径。
15cm
A
蚁穴
B
食物源
蚁穴 1
B
A
2 食物源
(a)
人工蚂蚁的搜索主要包括三种智能行为：
(b)
（1）蚂蚁的记忆行为。一只蚂蚁搜索过的路径在下次搜索时就不再被该蚂蚁选
择，因此在蚁群算法中建立禁忌表进行模拟。
（2）蚂蚁利用信息素进行相互通信。蚂蚁在所选择的路径上会释放一种信息素
的物质，当其他蚂蚁进行路径选择时，会根据路径上的信息素浓度进行选择，这
样信息素就成为蚂蚁之间进行通信的媒介。
（3）蚂蚁的集群活动。通过一只蚂蚁的运动很难达到事物源，但整个蚁群进行
搜索就完全不同。当某些路径上通过的蚂蚁越来越多时，路径上留下的信息素数
量也就越多，导致信息素强度增大，蚂蚁选择该路径的概率随之增加，从而进一
步增加该路径的信息素强度，而通过的蚂蚁比较少的路径上的信息素会随着时间
的推移而挥发，从而变得越来越少。3.3.1蚂蚁系统
蚂蚁系统是最早的蚁群算法。其搜索过程大致如下：
m
只蚂蚁随机放置于城市中，在初始时刻，各条路径上的信息素初始值相等，
设为：
ij
(0)
0
为信息素初始值，可设
0
mL
m
，
L
m
是由最近邻启发式方法构
造的路径长度。其次，蚂蚁
k(k1,2,
..
m)
，按照随机比例规则选择下一步要转
...
移的城市，其选择概率为：
[
ij
(t)]
[
ij
(t)]
,jallowed
k
[
is
(t)]
[
is
(t)]
k
p
ij
(t)
sallowed
k
0，否则
其中，
ij
为边
(i,j)
上的信息素，
ij
1d
ij
为从城市
i
转移到城市
j
的启发式
因子，
allowed
k
为蚂蚁
k
下一步被允许访问的城市集合。
为了不让蚂蚁选择已经访问过的城市，采用禁忌表
tabu
k
来记录蚂蚁
k
当前
所走过的城市。经过
t
时刻，所有蚂蚁都完成一次周游，计算每只蚂蚁所走过的
路径长度，并保存最短的路径长度，同时，更新各边上的信息素。首先是信息素
挥发，其次是蚂蚁在它们所经过的边上释放信息素，其公式如下：
ij
(1
)
ij
，其中
为信息素挥发系数，且
0
1
。
k
k
ij
ij
ij
，其中
ij
是第
k
只蚂蚁向它经过的边释放的信息素，定义
k1
m
k
1d
ij
，如果边(i,j)在路径T上
为：
（3.2）
0，否则
k
ij
根据（3.2）可知，蚂蚁构建的路径长度
d
ij
越小，则路径上各条边就会获得
更多的信息素，则在以后的迭代中就更有可能被其他的蚂蚁选择。
蚂蚁完成一次循环后，清空禁忌表，重新回到初始城市，准备下一次周游。
大量的仿真实验发现，蚂蚁系统在解决小规模TSP问题时性能尚可，能较快
的发现最优解，但随着测试问题规模的扩大，AS算法的性能下降的比较严重，
容易出现停滞现象。因此，出现了大量的针对其缺点的改进算法。
3.3.2精英蚂蚁系统
精英蚂蚁系统
[11]
是对基本AS算法的第一次改进，它首先由Dorigo等人中提
出，它的设计思想是对算法每次循环之后给予最优路径额外的信息素量。找出这
个解的蚂蚁称为精英蚂蚁。
将这条最优路径记为
T
bs
（best-so-far tour）。针对路径
T
bs
的额外强化是
通过向
T
bs
中的每一条边增加
e/L
bs
大小的信息素得到的，其中e是一个参数，它
定义了给予路径
T
bs
的权值大小，
L
bs
代表了
T
bs
的长度。这样相应的信息素的更
新公式如式（3.3）：
kbs
ij
(t1)(1
)
ij
(t)
ij
(t)e
ij
(t)
（3.3）
k1
m
k
bs
其中，
ij
：
(t)
的定义方法跟以前的相同，
ij
(t)
的定义则如式（3.4）
..
发布评论