第7讲_蚁群算法.ppt

2.1 蚁群优化算法概述 2.1.1 起源 2.1.2 应用领域 2.1.3 研究背景 2.1.1 蚁群优化算法起源 1/2 2.1.2 蚁群优化算法应用领域 2.1.3 蚁群优化算法研究背景 1/3 群智能理论研究领域有两种主要的算法：蚁群算法(Ant Colony Optimization, ACO)和粒子群算法（Particle Swarm Optimization, PSO）。前者是对蚂蚁群落食物采集过程的模拟，已成功应用于许多离散优化问题。粒子群算法也是起源于对简单社会系统的模拟，最初是模拟鸟群觅食的过程，但后来发现它是一种很好的优化工具。 2.1.3 蚁群优化算法研究背景 2/3 2.1.3 蚁群优化算法研究背景 3/3 群智能方法易于实现，算法中仅涉及各种基本的数学操作，其数据处理过程对CPU和内存的要求也不高。而且，这种方法只需目标函数的输出值，而无需其梯度信息。已完成的群智能理论和应用方法研究证明群智能方法是一种能够有效解决大多数全局优化问题的新方法。更为重要是，群智能潜在的并行性和分布式特点为处理大量的以数据库形式存在的数据提供了技术保证。无论是从理论研究还是应用研究的角度分析，群智能理论及其应用研究都是具有重要学术意义和现实价值的。 2.2 蚁群优化算法原理及实现 2.2.1 蚁群算法原理 2.2.2 简化的蚂蚁寻食过程 2.2.3 自然蚁群与人工蚁群算法 2.2.4 实数编码的小生境蚁群算法（NACA） 2.2.1 蚁群算法原理 1/2 蚁群算法是对自然界蚂蚁的寻径方式进行模似而得出的一种仿生算法。蚂蚁在运动过程中，能够在它所经过的路径上留下一种称之为外激素(pheromone) 的物质进行信息传递，而且蚂蚁在运动过程中能够感知这种物质，并以此指导自己的运动方向，因此由大量蚂蚁组成的蚁群集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。 2.2.2 简化的蚂蚁寻食过程 1/4 2.2.2 简化的蚂蚁寻食过程 2/4 2.2.2 简化的蚂蚁寻食过程 3/4 假设蚂蚁每经过一处所留下的信息素为一个单位，则经过36个时间单位后，所有开始一起出发的蚂蚁都经过不同路径从D点取得了食物，此时ABD的路线往返了2趟，每一处的信息素为4个单位，而 ACD 的路线往返了一趟，每一处的信息素为2个单位，其比值为2：1。 寻找食物的过程继续进行，则按信息素的指导，蚁群在ABD路线上增派一只蚂蚁（共2只），而ACD 路线上仍然为一只蚂蚁。再经过 36 个时间单位后，两条线路上的信息素单位积累为 12 和4，比值为3：1。 2.2.3 自然蚁群与人工蚁群算法 2.2.4 实数编码的小生境蚁群算法（NACA） 1/5 NACA的基本思路：随机产生N个蚂蚁的初始群体，使蚂蚁随机分布在函数的可行域上，根据优化函数计算每个蚂蚁的初始信息素，信息素正比于函数值，根据每个蚂蚁的当前信息素和全局最优信息素求出蚂蚁的转移概率，根据转移概率更新每个蚂蚁的位置，新位置限制在函数可行域内，蚂蚁移动到新位置后就立即更新自己的信息素。 2.4 练习 1、理解和掌握蚁群算法的基本思想和算法流程。 2、利用蚁群算法求出下面函数的极小值： z=2-exp[-(x2+y2)], x,y?[-5,+5] * * Matlab 基 础 武汉学院数学建模系列课件 第7讲 蚁群算法 2.1 蚁群优化算法概述 2.2 蚁群优化算法原理及实现 2.3 小生境蚁群算法应举例 2.4 练习 20世纪50年代中期创立了仿生学，人们从生物进化的机理中受到启发。提出了许多用以解决复杂优化问题的新方法，如进化规划、进化策略、遗传算法等，这些算法成功地解决了一些实际问题。 2.1.1 蚁群优化算法起源 2/2 20世纪90年代意大利学者M．Dorigo，V．Maniezzo，A．Colorni等从生物进化的机制中受到启发，通过模拟自然界蚂蚁有哪些信誉好的足球投注网站路径的行为，提出来一种新型的模拟进化算法——蚁群算法，是群智能理论研究领域的一种主要算法。用该方法求解TSP问题、分配问题、job-shop 调度问题，取得了较好的试验结果．虽然研究时间不长，但是现在的研究显示出，蚁群算法在求解复杂优化问题（特别是离散优化问题）方面有一定优势，表明它是一种有发展前景的算法。 这种方法能够被用于解决大多数优化问题或者能够转化为优化求解的问题。现在其应用领域已扩展到多目标优化、数据分类、数据聚类、模式识别、电信QoS管理、生物系统建模、流程规划、信号处理、机器人控制、决策支持以及仿真和系统辩识等方面，群智能理论和方法为解决这类应用问题提供了新的