基本蚁群算法及其改进.pdfVIP

维普资讯 第 5卷 第 6期 北华大学学报(自然科学版) VOI．5NO．6 2004年 12月 JOURNALOFBEIHUAUNIVERSITY(NaturalScience) Dee．2004 文章编号：1009—4822(2004)06—0572—03 基本蚁群算法及其改进 孔令军 ，张兴华 ，陈建国。 (1．北华大学 教育技术中心，吉林 吉林 132021；2．北华大学 电气信息工程学院，吉林 吉林 132021； 3．北华大学 后勤服务总公司，吉林 吉林 132021) 摘要：给出了群体智能的一个分支—— 蚁群算法的一个改进算法，充分利用了算法的并行特点，提高了算法的效率 关键词：蚁群算法；信息矩阵；组合优化 中图分类号 ：TP301．6 文献标识码 ：A 近年来，计算机网络得到了飞速的发展，网络已成为社会生活不可缺少的部分 ．同时，人们对网络信息 传输的质量和效率的要求也越来越高．为了进一步提高网络的效率，更多新算法被引入这个领域。蚁群算 法就是其中之一． 1 初期的蚁群算法 基本的蚁群算法AS可 以简单表述如下 ：在 0时刻进行初始化过程，蚂蚁放置在不同的城市，每一条边 都有一个初始外激素强度值 (0)．每一只蚂蚁禁忌表的第一个元素置为它的开始城市．然后 ，每一只蚂 蚁从城市 i移动到城市 ，依据两个变量的概率函数选择移动城市 (包括参数a和p，见公式 (1．4))．在 次 循环后，所有蚂蚁都完成了一次周游 ，同时他们 的禁忌表将满 ，这时，计算每一只蚂蚁 k的路径长度L ， △ 依据公式(1．3)更新．而且 ，保存 由蚂蚁找到的最短路径 (即minL ，k=1，…，77／)，置空所有禁忌表 ． 重复这一过程直到周游计数器达到最大(用户定义)周游数 maxNc，或者所有蚂蚁都走同一路线．后一种 情况被称为停滞状态．如果算法在 Nc次循环后结束，蚂蚁算法的复杂度为 0(Nc· ·T?1)． 信息素更新公式 ： (f+ )= ID· (f)+Ar0， (1．1) 其中，lD是一个参数 ，1一lD表示在时刻f和f+ 之间外激素的蒸发 ， Ar = △r ， (1．2) LXr~,是单位长度上在时刻f和f+ 之间第k只蚂蚁在边 (i，)留下的外激素的数量，其中 △． 。 J 如果在时刻f和f+ 之间第k只蚂蚁使用边 (i，)， ， 、 r = L 。 (1．3) 0【， 其他． Q是一个常数 ，L 是第k只蚂蚁周游的路程长度． 第 k只蚂蚁从城市 i到城市 的跃迁概率为 一 聃 )： ’ (1．33) 聃 ： 【0， ． 基史 三 { 二堕 垒}，N为一组城市，tabuk表示第k只蚂蚁的禁忌表，a和p都是控制外激素与可见度 维普资讯 第 6期 孔令军 ，等 ：基本蚁群算法及其改进 573 的相对重要性的参数．跃迁概率是可见度和 t时刻外激素强度的权衡． 综合 以上所述 ．图1给出用基本蚁群算法原理解决路