《蚁群算法基本原理及综述(4页).doc》由会员分享，可在线阅读，更多相关《蚁群算法基本原理及综述(4页).doc（4页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、-第 1 页蚁群算法基本原理及综述-第 2 页蚁群算法基本原理及综述蚁群算法基本原理及综述作者：陈少杰 麻莉娜来源：科技创新与应用2016年第 31期摘 要：虽然蚁群算法出现时间并不长，但由于其自身具有较好的鲁棒性，以及较强的正反馈机制，使得其在解决 TSP 问题中取得了较好的成果。在其他问题的解决中，由于其全局搜索性较差，极易出现局部收敛。文章通过对蚁群算法的基本原理与相关方法进行分析，以期对相关问题的改善提供借鉴与参考。关键词：蚁群算法；基本原理；分析1 概述鉴于传统优化技术的使用需要建立在规范的数学基础上，进而使得在求解过程中存在一定的限制。这就使得大量的现实问题不能解决。为进一步解决上
2、述问题，上世纪 80 年代初兴起的启发式算法对上述现象进行了一种全新的尝试。启发式算法，即为一种常用求解方式，该方式可以在能接受的经费范围内获得最优解，然而却无法保证所获得的解存在可行性，同时还有可能无法描述所获得的解的近似程度1。在这一系列算法中，以遗传算法（GA）、禁忌搜索算法（tabu search）、模拟退火（Simulated Annealing）算法、粒子群算法（Particles Swarm Optimization）、蚁群算法（AntOptimization）为代表，这些算法主要应用于传统优化问题中难以建立数学模型的题目，也就是优化理论中 NP-hard 问题。另外，由于上述算
3、法拥有一定的普及应用型，并且对目标函数与约束条件的限制相对宽松，因此已经普及到解决实际问题的各个方面中。2 蚁群算法的基本原理蚁群算法是意大利学者 Dorigo Mden 等人在上世纪九十年代，以蚂蚁在自然界中协同工作寻找食物为模型，模拟蚂蚁运动规律，并在运动过程中以信息素为牵引，控制蚂蚁寻找最优路径。由于信息素的加入，使得该算法具有了正反馈机制，具有良好的局部搜索能力。因此，蚁群算法已在多个领域得到了验证，尤其是在车辆路径以及车间调度方面。蚁群算法来源于商旅问题。商旅问题就是指一位商人，从 A 地出发，经过多个城市，最后返回 A 地。在这一过程中全部的城市则必须被访问一次，且仅一次，从而获得
4、路径最短的距离。在蚁群算法构建中，蚂蚁们将随机决定下一个要访问的城市。当 t 时刻位于城市 i 的蚂蚁 k 选择城市 j 为目标城市的概率为：-第 3 页根据信息素更新方法不同，Dorigo M 提出了三种不同的基本蚁群算法模型，分别称之为蚂蚁周期（Ant-Cycle）模型、蚂蚁数量（Ant-Quantity）模型及蚂蚁密度（Ant-Density）模型2。但伴随着算法的开展，信息素不断增加，使得全部蚂蚁都集中在某一路径中，最后全部蚂蚁所获得的解全部相同，无法对空间开展深入搜索，极易出现局部收敛的现象。基于解决上述问题的目的，经过各方的研究，提出了蚁群系统，精英蚁群系统，最大最小蚁群系统等一系
5、列算法。文章通过对多种群改进的蚁群算法、自适应蚁群算法以及与其他算法的融合这三方面的介绍，来说明蚁群算法在改进方面的一些研究成果。（1）多种群改进的蚁群算法针对传统蚁群算法容易陷入局部最优解的现状，进一步加大全局搜索，避免过早陷入局部最优解。多种群蚁群算法将蚁群随机放入不同区域，每只蚂蚁按照自身概率进行搜索，搜索一段时间后，信息素进行交换。这使得蚁群能对路径做出更多选择，以便挑选出最优解。（2）自适应蚁群算法传统算法搜索到一定程度后会造成某条路径上信息素越积越多且由于下一条路径越短则该路径被选中的概率越大，但是下一路径较短，并不意味整条路径是最短的，这会造成转移概率基本不变，使得蚂蚁总是选择转
6、移系数最大的路径，造成选择的结果具有一定的确定性。而自适应蚁群算法，在搜索过程中采用确定性选择和随机选择相结合的选择策略，动态地对挥发因子进行变动，使得在初期搜索时，最优解路径上的信息素浓度较高，挥发因子较小，造成蚁群容易聚集搜索。而到达一定搜索之后，信息素挥发因子变大，保证了全局的搜索。同时，设置信息素的浓度在一个合理区间内，使得信息素浓度不可能过大，也不可过小。（3）与其他算法的融合由于蚁群算法具有强大的正反馈机制，在这种反馈机制的引导下，使其具有了较强的局部搜索能力。遗传算法具有交叉和突变的属性，使得遗传算法具有强大的全局搜索能力，能够全面对解进行搜索，但同时交叉和突变会对原有解产生较大
7、的变化，不能对最优解进行继承和发展，使得效率减低。由此可以看出，遗传算法具有全局性，蚁群算法具有局部搜索性，两者可以很好结合。此外，粒子群算法的整体搜索能力也十分强大，其可以在显示随机性、全面性的基础上，利用迭代次数来获得次优解。再通过问题的次优解来对蚁群算法中信息素的分布进行调整，并且使用蚁群算法中的正反馈机制，利用其正反馈特点等优势来获得问题的精确解，进而全面提升求解的效率与精准度34。-第 4 页3 结束语经验证3567，以上三种算法在解决全局收敛性方面都取得了不错的效果。前两种算法，都是在传统蚁群算法的基础上，进行了部分修改，增加算法在选择方面的不确定性，而第三种算法是借鉴了其他算法中
8、全局搜索性较强的属性，来弥补自身不足。这两个方面将是以后研究的重要方面。参考文献1Reeves CR（Ed）.Modern Heuristic Techniques for Combinatorial ProblemsM.Oxford：Blackwell Scientific Publications，1993.2汪定伟，王俊伟，王洪峰，等.智能优化方法M.北京：高等教育出版社，2007.3张长春，苏昕，易克初.粒子群算法和蚁群算法的结合及其在组合优化中的应用J.空间电子技术，2007（2）.4支成秀，梁正友.融合粒子群优化算法与蚁群算法的随机搜索算法J.广西科学院学报，2006，22（4）：231-233.5王俊良.蚁群算法与遗传算法的融合及其应用研究D.南京：南京邮电学院，2005.6王颖，谢剑英.一种自适应蚁群算法及其仿真研究J.系统仿真学报，2002（1）.7胡乃平，王延智.多种群蚁群算法在多目标优化中的研究J.科技信息，2012（17）.