蚁群算法详细讲.ppt

*蚁群算法及其应用蚂蚁觅食行为与觅食策略蚂蚁系统——蚁群系统的原型改进的蚁群优化算法蚁群优化算法的仿真研究蚁群算法的应用——对QoS组播路由问题求解***,人们从生物进化的机理中受到启发。提出了许多用以解决复杂优化问题的新方法,如进化规划、进化策略、遗传算法等,这些算法成功地解决了一些实际问题。,,,通过模拟自然界蚂蚁搜索路径的行为,提出来一种新型的模拟进化算法——蚁群算法,是群智能理论研究领域的一种主要算法。用该方法求解TSP问题、分配问题、job-shop调度问题,,但是现在的研究显示出,蚁群算法在求解复杂优化问题(特别是离散优化问题)方面有一定优势,表明它是一种有发展前景的算法.*。现在其应用领域已扩展到多目标优化、数据分类、数据聚类、模式识别、电信QoS管理、生物系统建模、流程规划、信号处理、机器人控制、决策支持以及仿真和系统辩识等方面,群智能理论和方法为解决这类应用问题提供了新的途径。*:蚁群算法(AntColonyOptimization,ACO)和微粒群算法(ParticleSwarmOptimization,PSO)。前者是对蚂蚁群落食物采集过程的模拟,已成功应用于许多离散优化问题。微粒群算法也是起源于对简单社会系统的模拟,最初是模拟鸟群觅食的过程,但后来发现它是一种很好的优化工具。*,群智能依靠的是概率搜索算法。虽然概率搜索算法通常要采用较多的评价函数,但是与梯度方法及传统的演化算法相比,其优点还是显著的,主要表现在以下几个方面:1无集中控制约束,不会因个别个体的故障影响整个问题的求解,确保了系统具备更强的鲁棒性2以非直接的信息交流方式确保了系统的扩展性3并行分布式算法模型,可充分利用多处理器4对问题定义的连续性无特殊要求5算法实现简单*,算法中仅涉及各种基本的数学操作,其数据处理过程对CPU和内存的要求也不高。而且,这种方法只需目标函数的输出值,而无需其梯度信息。已完成的群智能理论和应用方法研究证明群智能方法是一种能够有效解决大多数全局优化问题的新方法。更为重要是,群智能潜在的并行性和分布式特点为处理大量的以数据库形式存在的数据提供了技术保证。无论是从理论研究还是应用研究的角度分析,群智能理论及其应用研究都是具有重要学术意义和现实价值的。*---蚂蚁系统(AntSystem,AS)并将其应用于解决计算机算法学中经典的旅行商问题(TSP)。从蚂蚁系统开始,基本的蚁群算法得到了不断的发展和完善,并在TSP以及许多实际优化问题求解中进一步得到了验证。这些AS改进版本的一个共同点就是增强了蚂蚁搜索过程中对最优解的探索能力,它们之间的差异仅在于搜索控制策略方面。而且,取得了最佳结果的ACO是通过引入局部搜索算法实现的,这实际上是一些结合了标准局域搜索算法的混合型概率搜索算法,有利于提高蚁群各级系统在优化问题中的求解质量。