一种基于精英策略的改进蚁群算法及应用

《一种基于精英策略的改进蚁群算法及应用》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、一种基于精英策略的改进蚁群算法及应用ImprovedAntColonyAlgorithmBasedonElitistStrategyandApplication摘要：针对基本蚁群算法求解速度慢，容易出现早熟和搜索停滞现象，木文基于粕英策略并将遗传算法中排序的概念扩展到精英机制当中，提出了一种改进蚁群算法模型。改进算法根据蚂蚁排序，提出一种新的加权方法进行信息素更新。将该算法模型应用于配送优化问题,対30城市配送问题仿真结果表明：改进算法的求解速度和求解梢确度都明显优于基本蚁群算法。关键词：蚁群算法；搜索停滞；精英策略；排序abstract：Thebasicantcolonyalgorit

2、hmconvergesslowly,ispronetoplungeintopartialoptimumandresultsinsearchstagnation.Inthispaper,improvedantcolonyalgorithmisproposed.Improvedalgorithmisbasedonelitiststrategywhichtheoptimizedcompositorisintroducedinto.Accordingtoantcompositor,newweightedcoefficientisdesignedforpheromoneupdating.Newal

3、gorithmisappliedtothedistributionroutesoptimization.Thesimulationresultsshowthatimprovedalgorithmismuchmoreefficientthanthebasicantcolonyalgorithm.keywords：antcolonyalgorithm(ACA)；searchstagnation；elitiststrategy；compositor;1引言蚁群算法（AntColonyAlgorithm,ACA）111又称作蚂蚁算法，是由意大利的MarcoDorigo于1992年在他的博士论文中

4、首先提出，其基木思想是模仿蚂蚁依赖信息素进行通信而显示出的社会行为，在Agent总体的基础上，rfl—•个贪心算法指导下的白催化过程引导每个Agent的行动。该算法模拟了蚂蚁觅食吋的行为，按照启发式思想，通过信息素的诱导作用，逐步收敛到问题的最优解。其主要特点就是：通过正反馈、分布式协作来寻找最优路径。忖前，蚁群算法已经广泛应用于旅行商问题、二次分配问题、作业车间调度问题、车辆路径安排问题等问题，成为解决组合优化问题最有效的算法之一。基本蚁群算法复杂度较高，一•般需要较长的搜索时间，而且容易出现搜索停滞现象基金项H:国家自然科学基金（theNationalNaturalScienceFo

5、undationofChinaunderGrantNo.50904032）；湛江师范学院青年基金项冃（QW0712）；作者简介：张家善（1979-）,男，四川巴中人，讲师，博士研究生，从事信息管理和物流管理的研究工作，zhjiashan@163.com；王志宏，教授，博导，研究方向：技术经济；陈应显，讲师，博士。（StagnationBehaviour）,即搜索进行到一定程度后，所有个体所发现的解完全--致，不能对解空间进一步进行搜索，不利于发现更好的解。围绕该问题，学者们发表了不少文献，如文献［3］在路径选择时提出了一种不再考虑距离因素，仅考虑信息素强度的方法；文献［4］通过在局部搜索

6、屮采用聚类进行二次搜索，取得了较好求解效果；文献⑸基于蚂蚁分类，提出了-•种改进粹英策略算法。但是，实例验证表明，上述算法求解结果并不理想。本文基于梢英策略并将遗传算法中排序的概念扩展到精英机制当中，对蚁群算法进行改进，试图在较短时间内获得问题的满意最优解。2.基本蚁群算法"26】蚂蚁在觅食过程中对所经过路段釋放一种被称为信息素的物质，其他经过该路段的蚂蚁通过对残留信息素的数量判断是否重复该路段，从而找到一条巢穴到食物源Z间的最短路径。该路段残留信息素越多，所有蚂蚁选择该路段的可能性也就越大。蚁群算法正是模拟真实蚁群觅食行为策略而产生的一种启发式算法。假设有m只蚂蚁放入到n个随机选择的需

7、求节点中，每一只蚂蚁将根据线路上的信息浓度选择下一个它还没有访问的节点；同吋在完成一步（从一个节点到达另外一个节点）或者一个循环（完成対所有n个节点的访问）后，更新所有路径上的残留信息浓度。加是蚁群中蚂蚁的数量，《是城市，到城市丿之间的距离，偽•是边（7,丿）的能见度，切=仙,反映由城市，转移到城市丿的启发程度，S•是边（7,力上的信息素轨迹强度，△时是蚂蚁k在边（/,丿）上工sea!!owedkTis⑴址⑴0留卜的单位长度轨迹信