《蚁群算法发展》PPT课件

《《蚁群算法发展》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、蚁群算法蚂蚁的生物学特征蚂蚁是一种既渺小而又平常的社会性昆虫。生物学家通过对蚂蚁的长期观察研究发现，每只蚂蚁的智能并不高，但它们却能协同工作，集中食物，建筑蚁穴并抚养后代，依靠群体能力发挥出超出个体的智能。蚂蚁有复杂的社会体制，“蚂蚁”城市往往有5000万个成员。蚂蚁有四种不同的蚁型：蚁后、雄蚁、工蚁和兵蚁。蚂蚁的生物学特征寻找食物蚂蚁寻找食物过程中总会自动找到一条最短路径。蚁群算法起源蚁群优化（antcolonyoptimization,ACO）是20世纪90年代初由意大利学者M.Dorigo等通过模拟蚂蚁的行为而

2、提出的一种随机优化技术。ACO算法最初用于求解旅行商问题，现在已经成功用于许多组合优化问题。MacroDorigo蚁群算法的基本原理蚁群算法是对自然界蚂蚁的寻径方式进行模似而得出的一种仿生算法。蚂蚁在运动过程中，能够在它所经过的路径上留下一种称之为信息素(pheromone)的物质进行信息传递，而且蚂蚁在运动过程中能够感知这种物质，并以此指导自己的运动方向，因此由大量蚂蚁组成的蚁群集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。蚁群算法的基本原理在蚁群寻找食物时，它们总能

3、找到一条从食物到巢穴之间的最优路径。这是因为蚂蚁在寻找路径时会在路径上释放出一种特殊的信息素。当它们碰到一个还没有走过的路口时，就随机地挑选一条路径前行。与此同时释放出与路径长度有关的信息素。路径越长，释放的激索浓度越低。当后来的蚂蚁再次碰到这个路口的时候，选择激素浓度较高路径概率就会相对较大。这样形成一个正反馈。最优路径上的激索浓度越来越大。而其它的路径上激素浓度却会随着时间的流逝而消减。最终整个蚁群会找出最优路径。简化蚂蚁的寻食过程蚂蚁从A点出发，速度相同，食物在D点，可能随机选择路线ABD或ACD。假设初始时每

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

5、单位，其比值为2：1。寻找食物的过程继续进行，则按信息素的指导，蚁群在ABD路线上增派一只蚂蚁（共2只），而ACD路线上仍然为一只蚂蚁。再经过36个时间单位后，两条线路上的信息素单位积累为12和4，比值为3：1。若按以上规则继续，蚁群在ABD路线上再增派一只蚂蚁（共3只），而ACD路线上仍然为一只蚂蚁。再经过36个时间单位后，两条线路上的信息素单位积累为24和6，比值为4：1。若继续进行，则按信息素的指导，最终所有的蚂蚁会放弃ACD路线，而都选择ABD路线。这也就是前面所提到的正反馈效应。蚁群算法模型的建立对蚂蚁个体

6、的抽象蚁群算法是对自然界真实蚂蚁觅食行为的一种模拟，因此首先必须对真实蚂蚁进行抽象，而不可能也没必要对蚂蚁个体进行完全再现。把蚂蚁能够有效刻画出真实蚁群中能为算法所借鉴的特征抽象出来，同时建立与算法模型无关的因素。蚁群算法模型的建立问题空间的描述蚁群算法所求解的问题空间可用一个重要的数学工具——图（graph）来描述。寻找路径的抽象把觅食过程抽象成算法中解的构造过程，将信息素抽象为存在于图的边上的轨迹。在每一节点上人工蚂蚁感知相邻节点边上的信息素浓度。蚁群算法模型的建立信息素挥发的抽象自然界中，蚂蚁留下的信息素会随着

7、时间的推移而连续不断的挥发。因此使算法中的信息素挥发方式与蚂蚁觅食过程机理相符，要使蚂蚁完成一个节点的移动后，经过一个单位时间，进行一次信息素的挥发。蚁群算法模型的建立启发因子的引入蚁群算法的自组织性，似的系统的演化需要耗费较长的时间，而实际应用时对算法运行时间的要求也是必不可少的。因此引入一个启发因子，给蚁群算法一个初始的引导，增加算法的时间有效性。蚁群算法的基本步骤基本蚁群算法的优缺点优点较强的鲁棒性、全局性、普遍性分布式计算易于与其它方法结合缺点需要较长的计算时间，容易停滞所有路径的信息素增量，会导致错误的引导

8、信息素的均匀分配策略未体现出路段的重要性蚁群优化算法研究进展最初的蚁群算法是蚂蚁系统,由于信息素更新方式的不同还可以细分为蚁周、蚁密、蚁量三种算法模型。但是蚂蚁系统只能解决小规模的问题,比如说TSP问题。但是当问题的规模增大时,比如说TSP中的城市规模增大时,算法的反应比较迟钝,所以产生了后来的蚁群系统,优化了蚂蚁系统在全局的更新以及蚂蚁的状态