改进蚁群算法及其仿真.pdf

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

1、日经验窒鎏旦doi：10．3969／j．issn．1671—1041．2010．04．030改进蚁群算法及其仿真田婧，孙建平，苑一方(华北电力大学自动化系，保定071003)摘要：蚁群算法是近几年优化领域中出现的一种启发式仿生类并行智i转移到城市的状态转移概率能进化算法。该算法采用分布式并行计算和正反馈机制，易于与其他方法结合。本文提出了一种改进型的蚁群算法，引入了搜索方向。并对信息素的更新方式进行了改进。仿真实验证明。改进后的蚁群算法能够pP：：』{——!立[．r(￡)][77(f)，若～。。ed

2、(1)．l一。肋删获得较好的控制效果。L0，否则关键词：蚁群算法；信息素；搜索方向式中，，口分别表示蚂蚁在运动中所积累的信息和启发式因子中图分类号：TP273文献标识码：B在蚂蚁选择路径中起的不同作用；allowed表示第k(k=1，2，Animprovedantcolonyalgorithm⋯，m)只蚂蚁下一步允许行进的城市集合，他随着蚂蚁k的行andthesimulation进过程而动态改变；叩(t)表示由城市i转移到城市的期望程度，其表达式如下：TIANjing，SUNJian-ping，YU

3、ANYi-fang(f)=1(2)(DepartmentofAutomation，NorthChinaElectricPowerUniversity。Baoding071003。China)式中d表示相邻两城市之间的距离。对蚂蚁k而言，d越小，Abstract：Antcolonyalgorithmisanovelcategoryofbionicmeta-则’7(t)越大，P(t)也越大。heuristicalgorithmandparallelcomputationandpositivefeedba

4、ck随着时间的推移，以前留下的信息逐渐消逝，P表示信息mechanismareadoptedinthisalgorithm．Theantcolonyalgorithm素挥发度，经过个n时刻所有蚂蚁完成一次循环，各路径上的hasstrongrobustnessandeasytocombinewithothermethodsinoptimization．Thispaperpresentsanimprovedantcolonyalgorithm-信息量要根据下式进行更新：byIntroducingthem

5、echanismofsearchdirectionandimprovingther(n+)=(1一P)(t)+△(t)(3)pheromoneupdatingrules．Simulatedexperimentsshowsthemodi-fledantcolonyalgorithmswouldgetbe~erresults．△(t)=△Jr：(t)(4)Keywords：antcolonyalgorithm；pheromone；searchdirection式中，P为信息挥发系数，取值范围为Pc[0，

6、1)，△f(t)，表示第k只蚂蚁在本次循环中留在路径(i，)上的信息量，其计算0引言方法可以由计算模型而定，在最常用的AntCircleSystem模蚁群算法是意大利学者M．Dorigo、V．Maniezzo、A．Colorini型中等人首先提出的“，他们称之为蚁群系统(AntColonySys—tern)，并用该方法来解决旅行商旅问题、指派问题、Job—shop调△r(￡)：』，若第只蚂蚁在本次循环中经过(，J)度问题等，并取得了一系列较好的实验结果。蚁群算法是一L0。否则种基于种群的启发式仿生类

7、并行智能进化算法，由于它采用(5)分布式并行计算机制，易于与其他方法结合，具有较强的鲁棒式中，Q为常数，表示第k只蚂蚁在本次循环中所走路径的性，而它的正反馈过程能够帮助更快的发现较好的解。总长度。当进化趋势不明显或循环次数达到上限时，停止迭代虽然蚁群算法能够解决组合优化问题，但也容易出现搜计算输出问题的解。索速度慢，易于陷入局部最优解等问题。本文提出了一种改1．2基本蚁群算法存在的问题进型的蚁群算法，引入了搜索方向，并对信息素的更新方式进蚁群算法作为求解组合优化问题的有效手段，对一般函行了改进，使其

8、能在较大搜索空间条件下避开局部最优解，提数的优化问题也表现出优异的性能，它可以克服传统优化方高收敛速度，在全局优化的实现过程中迅速的找到连续空间法的许多不足和缺陷，实现和操作简单，对函数不连续、不可优化问题的全局最优解。微、局部极值点密集等苛刻的情况，更是具有很好的寻优能力。但是，在实际应用中，因为算法搜索过程中的概率性以及正反l基本蚁群算法馈作用，有时容易陷入局部最优解，而不是全局最优解，而且该1．1原理算法的全局搜索能力强，局部搜索能力弱，因此在应用中往往以TSP