智能算法之蚁群算法.ppt

蚁群算法陈华2010-9MacroDorigo1992年,,其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。通过对这种行为的模拟,提出来一种新型的模拟进化算法——蚁群算法。目前,蚁群算法已经是群智能理论研究领域的一种主要算法。算法背景*AC*蚁群算法原理蚁群算法是对自然界蚂蚁的寻径方式进行模似而得出的一种仿生算法。蚂蚁在运动过程中,能够在它所经过的路径上留下一种称之为外激素(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路线。这也就是前面所提到的正反馈效应。