《OK蚁群算法》PPT课件

1、 蚁群算法Ant Colony Algorithm 1精选PPT1 蚁群优化算法概念1.1 蚁群算法原理1.2 简化的蚂蚁寻食过程1.3 蚁群现象1.4 蚂蚁简单规则的两个方面1.4 蚁群算法与TSP问题1.5 初始的蚁群优化算法基于图的蚁群系统（GBAS）2精选PPT1.1 蚁群算法原理 蚁群算法是对自然界蚂蚁的寻径方式进行模似而得出的一种仿生算法。蚂蚁在运动过程中，能够在它所经过的路径上留下一种称之为外激素(pheromone)的物质进行信息传递，而且蚂蚁在运动过程中能够感知这种物质，并以此指导自己的运动方向，因此由大量蚂蚁组成的蚁群集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁

2、越多，则后来者选择该路径的概率就越大。3精选PPT为了说明蚁群算法的原理，先简要介绍一下蚂 蚁搜寻食物的具体过程： 在蚁群寻找食物时，它们总能找到一条从食物到巢穴之间的最优路径。这是因为蚂蚁在寻找路径时会在路径上释放出一种特殊的信息素。当它们碰到一个还没有走过的路口时就随机地挑选一条路径前行。与此同时释放出与路径长度有关的信息素。路径越长，释放的激索浓度越低.当后来的蚂蚁再次碰到这个路口的时候选择激素浓度较高路径概率就会相对较大。这样形成一个正反馈。最优路径上的激索浓度越来越大而其它的路径上激素浓度却会随着时间的流逝而消减。最终整个蚁群会找出最优路径。4精选PPT1.2 简化的蚂蚁寻食过程蚂蚁

3、从A点出发，速度相同，食物在D点，可能随机选 择路线ABD或ACD。假设初始时每条分配路线一只蚂 蚁，每个时间单位行走一步，本图为经过9个时间单位 时的情形：走ABD的蚂蚁到达终点，而走ACD的蚂蚁 刚好走到C点，为一半路程。5精选PPT本图为从开始算起，经过18个时间单位时的情形：走 ABD的蚂蚁到达终点后得到食物又返回了起点A，而 走ACD的蚂蚁刚好走到D点。6精选PPT 假设蚂蚁每经过一处所留下的信息素为一个单位，则经过36个时间单位后，所有开始一起出发的蚂蚁都经过不同路径从D点取得了食物，此时ABD的路线往返了2趟，每一处的信息素为4个单位，而 ACD的路线往返了一趟，每一处的信息素为

4、2个单位，其比值为2：1。 寻找食物的过程继续进行，则按信息素的指导，蚁群在ABD路线上增派一只蚂蚁（共2只），而ACD路线上仍然为一只蚂蚁。再经过36个时间单位后，两条线路上的信息素单位积累为12和4，比值为3：1。7精选PPT 若按以上规则继续，蚁群在ABD路线上再增派一只蚂蚁（共3只），而ACD路线上仍然为一只蚂蚁。再经过36个时间单位后，两条线路上的信息素单位积累为24和6，比值为4：1。 若继续进行，则按信息素的指导，最终所有的蚂蚁会放弃ACD路线，而都选择ABD路线。这是正反馈效应。8精选PPT信息素的更新方式有2种： 一是挥发：也就是所有路径上的信息素以一定的比率进行减少，模拟自

5、然蚁群的信息素随时间挥发的过程； 二是增强：给评价值“好”(有蚂蚁走过)的边增加信息素。9精选PPT1.3 蚁群现象蚂蚁正常行进，突然环境变化，增加了障碍物10精选PPT蚁群现象：蚂蚁以同等概率选择各条路径，紧接着，随着时间的增 加较短路径信息浓度高，选择该路径的蚂蚁逐渐增多。11精选PPT蚁群现象：蚂蚁最终绕过障碍物找到最优路径12精选PPT1.4 蚂蚁简单规则的两个方面：1多样性：蚂蚁在觅食的时候路线不一，随 机性的向着某个方向行走，打破常规，进行创新。2正反馈：优化的路线不断被保存并加大自身概率，保证了相对优良的信息能够被保存下来。 多样性保证了系统的创新能力，正反馈保证了优良特性能够得

6、到强化，两者要恰到好处的结合。 13精选PPT1.5 蚁群算法在TSP问题中的应用旅行商问题，即TSP问题又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路经的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。 14精选PPT算法步骤如下：15精选PPT16精选PPT17精选PPT18精选PPT按 的不同取法，可形成三种类型的蚂蚁算法模型：（1）Ant-Circle System模型，有式中，Q为常量， 为第k只蚂蚁在本次循环中所走路径的长度。（2）Ant-Quantity System模型19精选PPT（3）Ant-Density System模型 很明显在后两种模型中，利用的都是局部信息，而第一种模型利用的是整体信息。这三种模型在求解不同问题时各有优势。20精选PPT21精选PPT22精选PPT23精选PPT24精选PPT这样循环，最终得到了最优路线。25精选PPT实际的概率公式：定义 为他