《蚁群算法发展》.ppt

该【《蚁群算法发展》 】是由【相惜】上传分享，文档一共【20】页，该文档可以免费在线阅读，需要了解更多关于【《蚁群算法发展》 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。蚁群算法编辑课件蚂蚁的生物学特征蚂蚁是一种既渺小而又平常的社会性昆虫。生物学家通过对蚂蚁的长期观察研究发现,每只蚂蚁的智能并不高,但它们却能协同工作,集中食物,建筑蚁穴并抚养后代,依靠群体能力发挥出超出个体的智能。蚂蚁有复杂的社会体制,“蚂蚁〞城市往往有5000万个成员。蚂蚁有四种不同的蚁型:蚁后、雄蚁、工蚁和兵蚁。编辑课件蚂蚁的生物学特征寻找食物蚂蚁寻找食物过程中总会自动找到一条最短路径。编辑课件蚁群算法起源蚁群优化〔antcolonyoptimization,ACO〕。ACO算法最初用于求解旅行商问题,现在已经成功用于许多组合优化问题。MacroDorigo编辑课件蚁群算法的根本原理蚁群算法是对自然界蚂蚁的寻径方式进行模似而得出的一种仿生算法。蚂蚁在运动过程中,能够在它所经过的路径上留下一种称之为信息素(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路线。这也就是前面所提到的正反响效应。编辑课件蚁群算法模型的建立对蚂蚁个体的抽象 蚁群算法是对自然界真实蚂蚁觅食行为的一种模拟,因此首先必须对真实蚂蚁进行抽象,而不可能也没必要对蚂蚁个体进行完全再现。把蚂蚁能够有效刻画出真实蚁群中能为算法所借鉴的特征抽象出来,同时建立与算法模型无关的因素。编辑课件