基本蚁群算法及其改进

《基本蚁群算法及其改进》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、维普资讯http://www.cqvip.com第5卷第6期北华大学学报(自然科学版)VOI．5NO．62004年12月JOURNALOFBEIHUAUNIVERSITY(NaturalScience)Dee．2004文章编号：1009—4822(2004)06—0572—03基本蚁群算法及其改进孔令军，张兴华，陈建国。(1．北华大学教育技术中心，吉林吉林132021；2．北华大学电气信息工程学院，吉林吉林132021；3．北华大学后勤服务总公司，吉林吉林132021)摘要：给出了群体智能的一个分支——蚁群算法的一个改进算法

2、，充分利用了算法的并行特点，提高了算法的效率关键词：蚁群算法；信息矩阵；组合优化中图分类号：TP301．6文献标识码：A近年来，计算机网络得到了飞速的发展，网络已成为社会生活不可缺少的部分．同时，人们对网络信息传输的质量和效率的要求也越来越高．为了进一步提高网络的效率，更多新算法被引入这个领域。蚁群算法就是其中之一．1初期的蚁群算法基本的蚁群算法AS可以简单表述如下：在0时刻进行初始化过程，蚂蚁放置在不同的城市，每一条边都有一个初始外激素强度值(0)．每一只蚂蚁禁忌表的第一个元素置为它的开始城市．然后，每一只蚂蚁从城市i移动

3、到城市，依据两个变量的概率函数选择移动城市(包括参数a和p，见公式(1．4))．在次循环后，所有蚂蚁都完成了一次周游，同时他们的禁忌表将满，这时，计算每一只蚂蚁k的路径长度L，△依据公式(1．3)更新．而且，保存由蚂蚁找到的最短路径(即minL，k=1，⋯，77'／)，置空所有禁忌表．重复这一过程直到周游计数器达到最大(用户定义)周游数maxNc，或者所有蚂蚁都走同一路线．后一种情况被称为停滞状态．如果算法在Nc次循环后结束，蚂蚁算法的复杂度为0(Nc··T?1)．信息素更新公式：(f+)=ID·(f)+Ar0，(1．1)其

4、中，lD是一个参数，1一lD表示在时刻f和f+之间外激素的蒸发，Ar=△r，(1．2)LXr,~是单位长度上在时刻f和f+之间第k只蚂蚁在边(i，)留下的外激素的数量，其中△．r。=JL如果在时刻f和f+之间第k只蚂蚁使用边(i，。)，(，1．3、)【0，其他．Q是一个常数，L是第k只蚂蚁周游的路程长度．第k只蚂蚁从城市i到城市的跃迁概率为一聃)：’(1．3)聃：【0，．基史三{二堕垒}，N为一组城市，tabuk表示第k只蚂蚁的禁忌表，a和p都是控制外激素与可见度维普资讯http://www.cqvip.com第6期孔令军，

5、等：基本蚁群算法及其改进573的相对重要性的参数．跃迁概率是可见度和t时刻外激素强度的权衡．综合以上所述．图1给出用基本蚁群算法原理解决路由选择优化问题的流程图图1基本蚁群算法解决问题流程Fig．1Flowofbasicantcolony2基本蚁群算法的不足之处从上面针对路由选择优化问题的分析可以看出，虽然蚁群算法已经被证明是一种有效的解决组合优化问题的方法，但是由于问世的时间比较短，还存在如下不足：(1)限于局部最优解．从算法解的性质而言，蚁群算法也是在寻找一个比较好的局部最优解，而不是强求是全局最优解．(2)工作过程的中

6、间停滞问题．和算法开始时收敛速度快一样，在算法工作过程当中，迭代到一定次数后，蚂蚁也可能在某个或某些局部最优解的邻域附近发生停滞．(3)较长的搜索时间．尽管和其他算法相比，蚁群算法在迭代次数和解的质量上都有一定的优势，但对于目前计算机网络的实际情况，还是需要较长的搜索时间．虽然计算机计算速度的提高和蚁群算法的并行性在一定程度上可以缓解这一问题，但是对于大规模复杂的计算机网络，这还是一个很大的障碍．3加强信息利用率的蚁群算法下面从实际应用的角度提出一个改进的算法——加强信息利用率的蚁群算法，其主要改进思想是蚂蚁在网络图中转移的

7、同时在信息矩阵中转移，让寻找不同路径的蚂蚁可以协同工作．根据这个思想建立了新的信息矩阵(略)，使蚂蚁遗留下的信息可以对多次工作产生影响．这充分利用了算法的并行特点，减少了算法的循环次数和计算时间，提高了算法在解决这一问题时的效率．下面通过仿真结果进行分析．节点工作：I观察连接情7．07～——————————————————————————是否有新的、6560．⋯lI6，iI．IIfIjj‘I1新信息矩阵：j5．0lfJl⋯f{IIK嘉嚣辜新的连接信息，算转移概率4．5}f『}lljlII．定下一个目更新已有的信J4．0lLL

8、』——．———否————————．————．一0510I52025303540图2建立信息矩阵流程图3路径优化情况Fig．2FlowofmodelingofinformationmatrixFig．3Chartofoptimizingroute维普资讯http://www.cqvip.co