《蚁群算法的数学模型》由会员分享,可在线阅读,更多相关《蚁群算法的数学模型(3页珍藏版)》请在金锄头文库上搜索。
1、蚁群算法的数学模型蚂蚁 在运动过程中,运动转移的方向由各条路径上),21(km的信息量浓度决定。为方便记录可用 来记录第 k 只),21(tmkabu蚂蚁当前已走过的所有节点,这里可以称存放节点的表为禁忌表;这个存放节点的集合会随着蚂蚁的运动动态的调整。在算法的搜索过程中,蚂蚁会智能地选择下一步所要走的路径。 设 m 表示蚂蚁总数量,用 表示节点 i 和节点 )1,0,(dnjij 之间的距离, 表示在 t 时刻 连线上的信息素浓度。在初始)(ijt时刻,m 只蚂蚁会被随机地放置,各路径上的初始信息素浓度是相同的。在 t 时刻,蚂蚁 k 从节点 i 转移到节点 j 的状态转移概率为 other
2、palwdtkij kalowedkijijijijkij ,0j,)()(p 1-2其中, 表示蚂蚁 k 下一步可以选择的所有节kktabucl点,C 为全部节点集合; 为信息启发式因子,在算法中代表轨迹相对重要程度,反映路径上的信息量对蚂蚁选择路径所起的影响程度,该值越大,蚂蚁间的协作性就越强; 可称为期望启发式因子,在算法中代表能见度的相对重要性。 是启发函数,在算法中表示ij由节点 i 转移到节点 j 的期望程度,通常可取 。在算法运ijijd/1行时每只蚂蚁将根据(2-1)式进行搜索前进。 在蚂蚁运动过程中,为了避免在路上残留过多的信息素而使启发信息被淹没,在每只蚂蚁遍历完成后,要对
3、残留信息进行更新处理。由此,在 t+n 时刻,路径(i,j)上信息调整如下 (2-2)(1ttnt ijijij (2-3)()(1ttmkijij在式中,常数 表示信息素挥发因子,表示路径上信息量10的损耗程度, 的大小关系到算法的全局搜索能力和收敛速度,则可用 代表信息素残留因子, 表示一次寻找结束后路径(i,j)的-1)(tkij信息素增量。在初始时刻 , 表示第 k 只蚂蚁在本次遍0ij )(tkij历结束后路径(i,j)的信息素。由于信息素更新策略有所不同,学者 Dorigo M 研究发现了三种不同的基本蚁群算法模型,分别记为“蚁周系统”(Ant-Cycle)模型、 “蚁量系统”(A
4、nt-Quantity)模型及“蚁密系统”(Ant-Density)模型,三种模型求解 方式存在不同。)(tkij“蚁周系统”(Ant-Cycle)模型 第 k 只蚂蚁走过 (2-4)otherLQkij,0 ij“蚁量系统”(Ant-Quantity)模型 第 k 只蚂蚁在 t 和 t+1 之间走过 (2-5)otherdQijkij ,0 ij“蚁密系统”(Ant-Density)模型 第 k 只蚂蚁在 t 和 t+1 之间走过 (2-6)otherQkij ,0 ij从上边各公式可以看出三种模型的主要区别是:“蚁量系统”和“蚁密系统”中,信息素是在蚂蚁完成一步后更新的,即采用的是局部信息;而在“蚁周系统”中路径中信息素是在蚂蚁完成一个循环后更新的,即应用的是整体信息。在一系列标准测试问题上运行的实验表明, “蚁周系统”算法的性能优于其他两种算法。因此,对蚂蚁系统的研究正朝着更好地了解“蚁周系统”特征的方向发展。