蚁群算法基本原理及综述讲课讲稿

1、蚁群算法基本原理及综述蚁群算法基本原理及综述 作者：陈少杰麻莉娜来源：科技创新与应用2016年第31期摘要：虽然蚁群算法出现时间并不长，但由于其自身具有较好的鲁棒性，以及较强的正 反馈机制，使得其在解决TSP问题中取得了较好的成果。在其他问题的解决中，由于其全局 搜索性较差，极易出现局部收敛。文章通过对蚁群算法的基本原理与相关方法进行分析，以期 对相关问题的改善提供借鉴与参考。关键词：蚁群算法；基本原理；分析1概述鉴于传统优化技术的使用需要建立在规范的数学基础上，进而使得在求解过程中存在一定 的限制。这就使得大量的现实问题不能解决。为进一步解决上述问题，上世纪80年代初兴起 的启发式算法对上述

2、现象进行了一种全新的尝试。启发式算法，即为一种常用求解方式，该方 式可以在能接受的经费范围内获得最优解，然而却无法保证所获得的解存在可行性，同时还有 可能无法描述所获得的解的近似程度1。在这一系列算法中，以遗传算法(GA)、禁忌搜索算法(tabu search)、模拟退火 (Simulated Annealing)算法、粒子群算法(Particles Swarm Optimization)、蚁群算法(Ant Optimization)为代表，这些算法主要应用于传统优化问题中难以建立数学模型的题目，也就 是优化理论中NP-hard问题。另外，由于上述算法拥有一定的普及应用型，并且对目标函数与 约

3、束条件的限制相对宽松，因此已经普及到解决实际问题的各个方面中。2蚁群算法的基本原理蚁群算法是意大利学者Dorigo Mden等人在上世纪九十年代，以蚂蚁在自然界中协同工作 寻找食物为模型，模拟蚂蚁运动规律，并在运动过程中以信息素为牵引，控制蚂蚁寻找最优路 径。由于信息素的加入，使得该算法具有了正反馈机制，具有良好的局部搜索能力。因此，蚁 群算法已在多个领域得到了验证，尤其是在车辆路径以及车间调度方面。蚁群算法来源于商旅问题。商旅问题就是指一位商人，从A地出发，经过多个城市，最 后返回A地。在这一过程中全部的城市则必须被访问一次，且仅一次，从而获得路径最短的 距离。在蚁群算法构建中，蚂蚁们将随机

4、决定下一个要访问的城市。当t时刻位于城市i的蚂 蚁k选择城市j为目标城市的概率为：根据信息素更新方法不同，Dorigo M提出了三种不同的基本蚁群算法模型，分别称之为 蚂蚁周期(Ant-Cycle)模型、蚂蚁数量(Ant-Quantity)模型及蚂蚁密度(Ant-Density)模型2。但伴随着算法的开展，信息素不断增加，使得全部蚂蚁都集中在某一路径中，最后全部蚂 蚁所获得的解全部相同，无法对空间开展深入搜索，极易出现局部收敛的现象。基于解决上述 问题的目的，经过各方的研究，提出了蚁群系统，精英蚁群系统，最大最小蚁群系统等一系列 算法。文章通过对多种群改进的蚁群算法、自适应蚁群算法以及与其他算

5、法的融合这三方面的 介绍，来说明蚁群算法在改进方面的一些研究成果。（1）多种群改进的蚁群算法针对传统蚁群算法容易陷入局部最优解的现状，进一步加大全局搜索，避免过早陷入局部 最优解。多种群蚁群算法将蚁群随机放入不同区域，每只蚂蚁按照自身概率进行搜索，搜索一 段时间后，信息素进行交换。这使得蚁群能对路径做出更多选择，以便挑选出最优解。（2）自适应蚁群算法传统算法搜索到一定程度后会造成某条路径上信息素越积越多且由于下一条路径越短则该 路径被选中的概率越大，但是下一路径较短，并不意味整条路径是最短的，这会造成转移概率 基本不变，使得蚂蚁总是选择转移系数最大的路径，造成选择的结果具有一定的确定性。而自

6、适应蚁群算法，在搜索过程中采用确定性选择和随机选择相结合的选择策略，动态地对挥发因 子进行变动，使得在初期搜索时，最优解路径上的信息素浓度较高，挥发因子较小，造成蚁群 容易聚集搜索。而到达一定搜索之后，信息素挥发因子变大，保证了全局的搜索。同时，设置 信息素的浓度在一个合理区间内，使得信息素浓度不可能过大，也不可过小。（3）与其他算法的融合由于蚁群算法具有强大的正反馈机制，在这种反馈机制的引导下，使其具有了较强的局部 搜索能力。遗传算法具有交叉和突变的属性，使得遗传算法具有强大的全局搜索能力，能够全面对解 进行搜索，但同时交叉和突变会对原有解产生较大的变化，不能对最优解进行继承和发展，使 得效

7、率减低。由此可以看出，遗传算法具有全局性，蚁群算法具有局部搜索性，两者可以很好 结合。此外，粒子群算法的整体搜索能力也十分强大，其可以在显示随机性、全面性的基础上， 利用迭代次数来获得次优解。再通过问题的次优解来对蚁群算法中信息素的分布进行调整，并 且使用蚁群算法中的正反馈机制，利用其正反馈特点等优势来获得问题的精确解，进而全面提 升求解的效率与精准度34。3结束语经验证3567，以上三种算法在解决全局收敛性方面都取得了不错的效果。前两种算 法，都是在传统蚁群算法的基础上，进行了部分修改，增加算法在选择方面的不确定性，而第 三种算法是借鉴了其他算法中全局搜索性较强的属性，来弥补自身不足。这两个方面将是以后 研究的重要方面。参考文献1Reeves CR（Ed）. Modern Heuristic Techniques for Combinatorial ProblemsM. Oxford : Blackwell Scientific Publications， 1993.汪定伟，王俊伟，王洪峰，等.智能优化方法M.北京：高等教育出版社，2007.张长春，苏昕，易克初.粒子群算法和蚁群算法的结合及其在组合优化中的应用J.空间 电子技术，2007（2）.支成秀，梁正友.融合粒子群优化算法与蚁群算法的随机搜索算法J.广西科学院学报， 2006， 22 （4）： 23