智能算法之蚁群算法介绍.ppt

应用蚁群算法求解连续对象优化问题，目前的处理方法大致为: 1.将解空间的每一个分量分成许多小区间，这样整个解空间被分成许多小多面体，将每个多面体看为一个节点，然后用人工蚂蚁在这些节点之间行走最后找到最优解。 2.在解空间中随机生成一些蚂蚁，每个蚂蚁表示一个解，并构成一个区域，根据蚂蚁的评价值，可将这些区域分成优势区和劣势区，劣势区的蚂蚁会按一定概率原则向优势区移动，直到所有蚂蚁都移动到优势区。这类处理方法我们认为己经不是原本意义上的蚁群算法，其实质是模拟了生态环境的一种宏观演化过程。 * 蚁群优化算法—参考书1 蚁群算法及其应用.李士勇.哈工大出版社 国内首部蚁群算法的专著，系统地阐述蚁群算法的基本原理、基本蚁群算法及改进算法，蚁群算法与遗传、免疫算法的融合，自适应蚁群算法，并行蚁群算法，蚁群算法的收敛性与理论模型及其在优化问题中的应用。本书可供人工智能、计算机科学、信息科学、控制工程、管理工程、交通工程、网络工程、智能优化算法及智能自动化等领域的广大师生和科技人员学习及参考。 * 蚁群算法—参考书2 智能蚁群算法及应用.吴启迪.上海科技出版社 从基本结构、算法特点、改进方法、突破途径、实现模式及应用模式等方面进行了论述。主要内容有蚁群算法的由来、研究成果、应用综述、算法的具体描述及改进、算法的典型优化问题求解模式、算法的典型应用及拓展应用。 蚁群算法 陈华 2010-9 Macro Dorigo 1992年，意大利学者M．Dorigo在他的博士论文中引入蚁群算法，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。通过对这种行为的模拟，提出来一种新型的模拟进化算法—— 蚁群算法。目前，蚁群算法已经是群智能理论研究领域的一种主要算法。 算法背景 * A C * A C * A C * 蚁群算法原理 蚁群算法是对自然界蚂蚁的寻径方式进行模似而得出的一种仿生算法。蚂蚁在运动过程中，能够在它所经过的路径上留下一种称之为外激素(pheromone)的物质进行信息传递，而且蚂蚁在运动过程中能够感知这种物质，并以此指导自己的运动方向，因此由大量蚂蚁组成的蚁群集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。 * 蚁群算法原理 为了说明蚁群算法的原理，先简要介绍一下蚂蚁搜寻食物的具体过程。在蚁群寻找食物时，它们总能找到一条从食物到巢穴之间的最优路径。这是因为蚂蚁在寻找路径时会在路径上释放出一种特殊的信息素。当它们碰到一个还没有走过的路口时，就随机地挑选一条路径前行，与此同时释放出与路径长度有关的信息素。路径越长，释放的激索浓度越低，当后来的蚂蚁再次碰到这个路口的时候，选择激素浓度较高路径概率就会相对较大，这样形成一个正反馈。最优路径上的激索浓度越来越大，而其它的路径上激素浓度却会随着时间的流逝而消减，最终整个蚁群会找出最优路径。 * 简化的蚂蚁寻食过程 蚂蚁从A点出发，速度相同，食物在D点，可能随机选择路线ABD或ACD。假设初始时每条分配路线一只蚂蚁，每个时间单位行走一步，本图为经过9个时间单位时的情形：走ABD的蚂蚁到达终点，而走ACD的蚂蚁刚好走到C点，为一半路程。 * 简化的蚂蚁寻食过程 本图为从开始算起，经过18个时间单位时的情形：走ABD的蚂蚁到达终点后得到食物又返回了起点A，而走ACD的蚂蚁刚好走到D点。 * 简化的蚂蚁寻食过程 假设蚂蚁每经过一处所留下的信息素为一个单位，则经过36个时间单位后，所有开始一起出发的蚂蚁都经过不同路径从D点取得了食物，此时ABD的路线往返了2趟，每一处的信息素为4个单位，而 ACD的路线往返了一趟，每一处的信息素为2个单位，其比值为2：1。 寻找食物的过程继续进行，则按信息素的指导，蚁群在ABD路线上增派一只蚂蚁（共2只），而ACD路线上仍然为一只蚂蚁。再经过36个时间单位后，两条线路上的信息素单位积累为12和4，比值为3：1。 若按以上规则继续，蚁群在ABD路线上再增派一只蚂蚁（共3只），而ACD路线上仍然为一只蚂蚁。再经过36个时间单位后，两条线路上的信息素单位积累为24和6，比值为4：1。 若继续进行，则按信息素的指导，最终所有的蚂蚁会放弃ACD路线，而都选择ABD路线。这也就是前面所提到的正反馈效应。 * 自然蚁群与人工蚁群算法 基于以上蚁群寻找食物时的最优路径选择问题，可以构造人工蚁群，来解决最优化问题，如TSP问题。 人工蚁群中把具有简单功能的工作单元看作蚂蚁。二者的相似之处在于都是优先选择信息素浓度大的路径。较短路径的信息素浓