72个时间单位后,两条线路上的信息素单位积累为12和4, 比值为3:1。
若按以上规则继续,蚁群在ABD路线上再增派一只蚂蚁(共 3只),ACD路线上仍然是一只蚂蚁。
再36个时间单位后,两条线路上的信息素单位积累为24和6 ,比值为4:1。
若继续进行,按信息素指导,最终所有蚂蚁会放弃ACD路 线,都选择ABD路线,这就是正反馈效应。
这种改进型算法能以更快的速度获得更好的解。但是若选择的精英过多,则算法会 由于较早收敛于局部次优解,而导致搜索的过早停滞。
寻找路径时,在路径上释放出一种特殊的信息素。
碰到没有走过的路口,随机挑选一条路径,并释放出与路 径长度有关的信息素。
路径越长,释放的激素浓度越低。
后来的蚂蚁再次碰到这个路口的时候,选择激素浓度较高 路径概率相对较大。
1
1
6
1 24
0 1 12
1 24 0
1 24 16
1 24 1 6 1 24
0
0 1 12 1 12 1 12
0
1 1
12 12
0 1 12
1 12 0
1
12
1 12
1 1 2 1 1 2 1 1 2
0
k
1k1ijk1w k 1 i,j是 w 上 的 一 条 弧
148 148 0 524
196 196 0 1148
148 524 148
0
196 1148 196
0
信息素的更新有2种方式:
• 挥发——所有路径上信息素以一定比率减少 • 增强——给评价值“好”(有蚂蚁走过)的边增加信息素
STEP 0 对n个城市的TSP问题,N 1 ,2 ,...,n A i,ji,j N