文档介绍：改进的蚁群算法及其应用
SA07011068 章宗长
SA07011065 石轲
2008-6-23
改进的蚁群算法
Macro Dorigo
Gambardella
带精英策略的蚂蚁系统
带精英策略的蚂蚁系统(Ant System with elitist strategy, ASelite)是最早的改进蚂蚁系统
遗传算法中的精英策略
传统的遗传算法可能会导致最适应个体的遗传信息丢失
精英策略的思想是保留住一代中的最适应个体
蚂蚁系统中的精英策略
每次循环之后给予最优解以额外的信息素量
这样的解被称为全局最优解(global-best solution)
找出这个解的蚂蚁被称为精英蚂蚁(elitist ants)
带精英策略的蚂蚁系统
信息素根据下式进行更新
其中
带精英策略的蚂蚁系统
上式中表示精英蚂蚁引起的路径(i, j)上的信息素量的增加
特点:
可以使蚂蚁系统找出更优的解
找到这些解的时间更短
精英蚂蚁过多会导致搜索早熟收敛
是精英蚂蚁的个数
是所找出的最优解的路径长度
蚁群系统
蚁群系统(Ant Colony System, ACS)是由Dorigo和Gambardella在1996年提出的
蚁群系统做了三个方面的改进:
状态转移规则为更好更合理地利用新路径和利用关于问题的先验知识提供了方法
全局更新规则只应用于最优的蚂蚁路径上
在建立问题解决方案的过程中,应用局部信息素更新规则
蚁群系统状态转移规则
一只位于节点r的蚂蚁通过应用下式给出的规则选择下一个将要移动到的城市s
其中,S根据下列公式得到
蚁群系统状态转移规则
q是在[0,1]区间均匀分布的随机数
q0的大小决定了利用先验知识与探索新路径之间的相对重要性。
上述状态转移规则被称为伪随机比例规则
特点:倾向于选择短的且有着大量信息素的边作为移动方向
蚁群系统全局更新规则
只有全局最优的蚂蚁才被允许释放信息素
目的:使蚂蚁的搜索主要集中在当前循环为止所找出的最好路径的领域内
全局更新在所有蚂蚁都完成它们的路径之后执行,使用下式对所建立的路径进行更新
蚁群系统全局更新规则
为信息素挥发参数,0< <1
为到目前为止找出的全局最优路径
全局更新规则的另一个类型称为迭代最优
区别:使用代替, 为当前迭代(循环)中的最优路径长度
这两种类型对蚁群系统性能的影响差别很小,全局最优的性能要稍微好一些