《蚁群算法详细讲解》PPT课件

《《蚁群算法详细讲解》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1蚁群算法及其应用蚂蚁觅食行为与觅食策略蚂蚁系统——蚁群系统的原型改进的蚁群优化算法蚁群优化算法的仿真研究蚁群算法的应用——对QoS组播路由问题求解2341.1蚁群优化算法概述1.1.1起源1.1.2应用领域1.1.3研究背景1.1.4研究现状1.1.5应用现状51.1.1蚁群优化算法起源20世纪50年代中期创立了仿生学，人们从生物进化的机理中受到启发。提出了许多用以解决复杂优化问题的新方法，如进化规划、进化策略、遗传算法等，这些算法成功地解决了一些实际问题。20世纪90年代意大利学者M．Dorigo，V

2、．Maniezzo，A．Colorni等从生物进化的机制中受到启发，通过模拟自然界蚂蚁搜索路径的行为，提出来一种新型的模拟进化算法——蚁群算法，是群智能理论研究领域的一种主要算法。用该方法求解TSP问题、分配问题、job-shop调度问题，取得了较好的试验结果．虽然研究时间不长，但是现在的研究显示出，蚁群算法在求解复杂优化问题（特别是离散优化问题）方面有一定优势，表明它是一种有发展前景的算法．61.1.2蚁群优化算法应用领域这种方法能够被用于解决大多数优化问题或者能够转化为优化求解的问题。现在其应用领域已

3、扩展到多目标优化、数据分类、数据聚类、模式识别、电信QoS管理、生物系统建模、流程规划、信号处理、机器人控制、决策支持以及仿真和系统辩识等方面，群智能理论和方法为解决这类应用问题提供了新的途径。72.1.3蚁群优化算法研究背景1/3群智能理论研究领域有两种主要的算法：蚁群算法(AntColonyOptimization,ACO)和微粒群算法（ParticleSwarmOptimization,PSO）。前者是对蚂蚁群落食物采集过程的模拟，已成功应用于许多离散优化问题。微粒群算法也是起源于对简单社会系统的模

4、拟，最初是模拟鸟群觅食的过程，但后来发现它是一种很好的优化工具。81.1.3蚁群优化算法研究背景2/3与大多数基于梯度的应用优化算法不同，群智能依靠的是概率搜索算法。虽然概率搜索算法通常要采用较多的评价函数，但是与梯度方法及传统的演化算法相比，其优点还是显著的，主要表现在以下几个方面：1无集中控制约束，不会因个别个体的故障影响整个问题的求解，确保了系统具备更强的鲁棒性2以非直接的信息交流方式确保了系统的扩展性3并行分布式算法模型，可充分利用多处理器4对问题定义的连续性无特殊要求5算法实现简单91.1.3蚁

5、群优化算法研究背景3/3群智能方法易于实现，算法中仅涉及各种基本的数学操作，其数据处理过程对CPU和内存的要求也不高。而且，这种方法只需目标函数的输出值，而无需其梯度信息。已完成的群智能理论和应用方法研究证明群智能方法是一种能够有效解决大多数全局优化问题的新方法。更为重要是，群智能潜在的并行性和分布式特点为处理大量的以数据库形式存在的数据提供了技术保证。无论是从理论研究还是应用研究的角度分析，群智能理论及其应用研究都是具有重要学术意义和现实价值的。101.1.4蚁群优化算法研究现状1/790年代Dorig

6、o最早提出了蚁群优化算法---蚂蚁系统（AntSystem,AS）并将其应用于解决计算机算法学中经典的旅行商问题（TSP）。从蚂蚁系统开始，基本的蚁群算法得到了不断的发展和完善，并在TSP以及许多实际优化问题求解中进一步得到了验证。这些AS改进版本的一个共同点就是增强了蚂蚁搜索过程中对最优解的探索能力，它们之间的差异仅在于搜索控制策略方面。而且，取得了最佳结果的ACO是通过引入局部搜索算法实现的，这实际上是一些结合了标准局域搜索算法的混合型概率搜索算法，有利于提高蚁群各级系统在优化问题中的求解质量。111

7、.1.4蚁群优化算法研究现状2/7最初提出的AS有三种版本：Ant-density、Ant-quantity和Ant-cycle。在Ant-density和Ant-quantity中蚂蚁在两个位置节点间每移动一次后即更新信息素，而在Ant-cycle中当所有的蚂蚁都完成了自己的行程后才对信息素进行更新，而且每个蚂蚁所释放的信息素被表达为反映相应行程质量的函数。通过与其它各种通用的启发式算法相比，在不大于75城市的TSP中，这三种基本算法的求解能力还是比较理想的，但是当问题规模扩展时，AS的解题能力大幅度下

8、降。因此，其后的ACO研究工作主要都集中于AS性能的改进方面。较早的一种改进方法是精英策略(ElitistStrategy)，其思想是在算法开始后即对所有已发现的最好路径给予额外的增强，并将随后与之对应的行程记为Tgb(全局最优行程)，当进行信息素更新时，对这些行程予以加权，同时将经过这些行程的蚂蚁记为“精英”，从而增大较好行程的选择机会。这种改进型算法能够以更快的速度获得更好的解。但是若选择的精英过多则算法会由于较早的收敛于