一种基于改进全局信息素更新效率的蚁群算法及仿真

《一种基于改进全局信息素更新效率的蚁群算法及仿真》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第３１卷第１期计算机应用与软件Ｖｏｌ３１Ｎｏ．１２０１４年１月ＣｏｍｐｕｔｅｒＡｐｐｌｉｃａｔｉｏｎｓａｎｄＳｏｆｔｗａｒｅＪａｎ．２０１４一种基于改进全局信息素更新效率的蚁群算法及仿真１２叶仕通万智萍１（广东工业大学华立学院广东增城５１１３２５）２（中山大学新华学院广东广州５１０５２０）摘要针对目前蚁群算法在搜索过程花费时间长且易出现局部最优化等现象，提出一种基于改进全局信息素更新效率的蚁群算法。通过在蚁群算法中引入“精英策略”，让算法的搜索具有一定的方向性，并且在此基础上对信息素初始值的定义与对算法中的挥发因

2、子ρ的取值进行改进，从而缩短算法的搜索时间。通过验证，改进后的算法相比一般的蚁群算法具有更好的搜索效率与较高的精确性，更适用于比较大型的ＴＳＰ问题，在路径搜索领域具有较好的发展前景。关键词蚁群算法信息素挥发因子中图分类号　ＴＰ３１２　　　　文献标识码　Ａ　　　　ＤＯＩ：１０．３９６９／ｊ．ｉｓｓｎ．１０００３８６ｘ．２０１４．０１．０４６ＡＮＡＮＴＣＯＬＯＮＹＡＬＧＯＲＩＴＨＭＢＡＳＥＤＯＮＩＭＰＲＯＶＩＮＧＧＬＯＢＡＬＰＨＥＲＯＭＯＮＥＵＰＤＡＴＥＥＦＦＩＣＩＥＮＣＹＡＮＤＩＴＳＳＩＭＵＬＡＴＩＯＮ１２ＹｅＳｈ

3、ｉｔｏｎｇ　ＷａｎＺｈｉｐｉｎｇ１（ＨｕａｌｉＣｏｌｌｅｇｅ，ＧｕａｎｇｄｏｎｇＵｎｉｖｅｒｓｉｔｙｏｆＴｅｃｈｎｏｌｏｇｙ，Ｚｅｎｇｃｈｅｎｇ５１１３２５，Ｇｕａｎｇｄｏｎｇ，Ｃｈｉｎａ）２（ＸｉｎｈｕａＣｏｌｌｅｇｅ，ＳｕｎＹａｔｓｅｎＵｎｉｖｅｒｓｉｔｙ，Ｇｕａｎｇｚｈｏｕ５１０５２０，Ｇｕａｎｇｄｏｎｇ，Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ　　Ｏｎａｃｃｏｕｎｔｏｆｔｈｅｐｈｅｎｏｍｅｎａｔｈａｔｃｕｒｒｅｎｔａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍｔａｋｅｓａｌｏｎｇｔｉｍｅｉｎｔｈｅｓｅａｒｃｈｐｒｏｃｅｓｓａｎ

4、ｄｉｓｐｒｏｎｅｔｏｌｏｃａｌｏｐｔｉｍｉｓａｔｉｏｎ，ｗｅｐｒｅｓｅｎｔａｎａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍｗｈｉｃｈｉｓｂａｓｅｄｏｎｉｍｐｒｏｖｉｎｇｔｈｅｅｆｆｉｃｉｅｎｃｙｏｆｇｌｏｂａｌｐｈｅｒｏｍｏｎｅｕｐｄａｔｅ．Ｔｈｒｏｕｇｈｉｎｔｒｏｄｕｃｉｎｇｔｈｅ＂ｅｌｉｔｅｓｔｒａｔｅｇｙ＂ｔｏａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍ，ｔｈｅｓｅａｒｃｈｉｎｔｈｅａｌｇｏｒｉｔｈｍｉｓｅｎａｂｌｅｄｔｏｈａｖｅｃｅｒｔａｉｎｄｉｒｅｃｔｉｖｉｔｙ，ａｎｄｏｎｔｈｉｓｂａｓｉｓｔｈｅｄｅｆｉｎｉｔｉｏｎｏｆ

5、ｔｈｅｉｎｉｔｉａｌｖａｌｕｅｏｆｐｈｅｒｏｍｏｎｅａｎｄｔｈｅｖａｌｕｉｎｇｏｆｔｈｅｖｏｌａｔｉｌｅｆａｃｔｏｒρｉｎｔｈｅａｌｇｏｒｉｔｈｍａｒｅｂｏｔｈｉｍｐｒｏｖｅｄ，ｔｈｅｒｅｂｙｔｈｅｓｅａｒｃｈｔｉｍｅｏｆｔｈｅａｌｇｏｒｉｔｈｍｉｓｓｈｏｒｔｅｎｅｄａｓｗｅｌｌ；Ｔｈｒｏｕｇｈｔｈｅｖｅｒｉｆｉｃａｔｉｏｎ，ｔｈｅｉｍｐｒｏｖｅｄａｌｇｏｒｉｔｈｍｐｒｏｐｏｓｅｄｉｎｔｈｅｐａｐｅｒｈａｓｂｅｔｔｅｒｓｅａｒｃｈｅｆｆｉｃｉｅｎｃｙａｎｄｈｉｇｈｅｒａｃｃｕｒａｃｙｉｎｃｏｍｐａｒｉｓｏｎｗｉｔｈ

6、ｔｈｅｇｅｎｅｒａｌａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍｓ，ｉｔｉｓｍｏｒｅｓｕｉｔａｂｌｅｆｏｒｔｈｅｐｌｕｓｌａｒｇｅｓｃａｌｅＴＳＰｐｒｏｂｌｅｍｓ，ａｎｄｈａｓｇｏｏｄｄｅｖｅｌｏｐｍｅｎｔｐｒｏｓｐｅｃｔｓｉｎｔｈｅｆｉｅｌｄｏｆｍｕｌｔｉｐａｔｈｓｅａｒｃｈ．Ｋｅｙｗｏｒｄｓ　　Ａｎｔｃｏｌｏｎｙａｌｇｏｒｉｔｈｍ　Ｐｈｅｒｏｍｏｎｅ　Ｖｏｌａｔｉｌｅｆａｃｔｏｒ性，或是优化搜索过程的信息素的量，但往往是效果不佳或间接０　引言地增加了算法的计算量，使得该算法很难得到进一步的推［４－９］广；针对该现象

7、，本文通过在蚁群算法中引进“精英策略”蚁群算法又称蚁群优化ＡＣＯ（ＡｎｔＣｏｌｏｎｙＯｐｔｉｍｉｚａｔｉｏｎ），Ｍ．［１０］的方法，让该算法在搜索的过程中在一定程度上具体有方向［１］Ｄｏｒｉｇｏ等人提出三大人工蚂蚁模拟自然界蚂蚁行为之特性，性，进而避免了算法在初始阶段的盲目搜索；而且根据研究蚁群通过利用信息素的正反馈与搜索过程中的并行搜索方式来对所算法的原理我们可以发现，蚁群算法的搜索速度的快慢和搜索有搜索路径进行选优，通过模仿自然界中的蚁群觅食行为而产的质量取决于信息素和初始搜索，而如今的改进算法中，虽然对生的，

8、使得该算法具有较多的优点，例如：具有较强的鲁棒性，良这一方面进行研究的人很多，但其提出的方法都具有一定的局好的扩展性，并且在搜索过程中结合了并行分布计算机制，在计［１１］限性，因此，本文根据算法中各参数的特点，通过在算法的初算过程中无需依赖具体的数学问题等；在求解的过程与旅行商始搜索过程中规定其信息素的挥发速度，与合理设置挥发因子［１２］问题（ＴＳＰ）很相似