《蚁群算法发展》PPT课件.ppt

《《蚁群算法发展》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《蚁群算法发展》PPT课件.ppt（20页珍藏版）》请在三一办公上搜索。

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

2、已经成功用于许多组合优化问题。,Macro Dorigo,蚁群算法的基本原理,蚁群算法是对自然界蚂蚁的寻径方式进行模似而得出的一种仿生算法。蚂蚁在运动过程中，能够在它所经过的路径上留下一种称之为信息素(pheromone)的物质进行信息传递，而且蚂蚁在运动过程中能够感知这种物质，并以此指导自己的运动方向，因此由大量蚂蚁组成的蚁群集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。,蚁群算法的基本原理,在蚁群寻找食物时，它们总能找到一条从食物到巢穴之间的最优路径。这是因为蚂蚁在寻找路径时会在路径上释放出一种特殊的信息素。当它们碰到一个还没有走过的路口时，

3、就随机地挑选一条路径前行。与此同时释放出与路径长度有关的信息素。路径越长，释放的激索浓度越低。当后来的蚂蚁再次碰到这个路口的时候，选择激素浓度较高路径概率就会相对较大。这样形成一个正反馈。最优路径上的激索浓度越来越大。而其它的路径上激素浓度却会随着时间的流逝而消减。最终整个蚁群会找出最优路径。,简化蚂蚁的寻食过程,蚂蚁从A点出发，速度相同，食物在D点，可能随机选择路线ABD或ACD。假设初始时每条分配路线一只蚂蚁，每个时间单位行走一步，本图为经过9个时间单位时的情形：走ABD的蚂蚁到达终点，而走ACD的蚂蚁刚好走到C点，为一半路程。,简化蚂蚁的寻食过程,本图为从开始算起，经过18个时间单位时的

4、情形：走ABD的蚂蚁到达终点后得到食物又返回了起点A，而走ACD的蚂蚁刚好走到D点。,简化蚂蚁的寻食过程,假设蚂蚁每经过一处所留下的信息素为一个单位，则经过36个时间单位后，所有开始一起出发的蚂蚁都经过不同路径从D点取得了食物，此时ABD的路线往返了2趟，每一处的信息素为4个单位，而 ACD的路线往返了一趟，每一处的信息素为2个单位，其比值为2：1。寻找食物的过程继续进行，则按信息素的指导，蚁群在ABD路线上增派一只蚂蚁（共2只），而ACD路线上仍然为一只蚂蚁。再经过36个时间单位后，两条线路上的信息素单位积累为12和4，比值为3：1。若按以上规则继续，蚁群在ABD路线上再增派一只蚂蚁（共3只

5、），而ACD路线上仍然为一只蚂蚁。再经过36个时间单位后，两条线路上的信息素单位积累为24和6，比值为4：1。若继续进行，则按信息素的指导，最终所有的蚂蚁会放弃ACD路线，而都选择ABD路线。这也就是前面所提到的正反馈效应。,蚁群算法模型的建立,对蚂蚁个体的抽象 蚁群算法是对自然界真实蚂蚁觅食行为的一种模拟，因此首先必须对真实蚂蚁进行抽象，而不可能也没必要对蚂蚁个体进行完全再现。把蚂蚁能够有效刻画出真实蚁群中能为算法所借鉴的特征抽象出来，同时建立与算法模型无关的因素。,蚁群算法模型的建立,问题空间的描述 蚁群算法所求解的问题空间可用一个重要的数学工具图（graph）来描述。,寻找路径的抽象 把

6、觅食过程抽象成算法中解的构造过程，将信息素抽象为存在于图的边上的轨迹。在每一节点上人工蚂蚁感知相邻节点边上的信息素浓度。,蚁群算法模型的建立,信息素挥发的抽象 自然界中，蚂蚁留下的信息素会随着时间的推移而连续不断的挥发。因此使算法中的信息素挥发方式与蚂蚁觅食过程机理相符，要使蚂蚁完成一个节点的移动后，经过一个单位时间，进行一次信息素的挥发。,蚁群算法模型的建立,启发因子的引入 蚁群算法的自组织性，似的系统的演化需要耗费较长的时间，而实际应用时对算法运行时间的要求也是必不可少的。因此引入一个启发因子，给蚁群算法一个初始的引导，增加算法的时间有效性。,蚁群算法的基本步骤,基本蚁群算法的优缺点,优点

7、较强的鲁棒性、全局性、普遍性分布式计算易于与其它方法结合缺点需要较长的计算时间，容易停滞所有路径的信息素增量，会导致错误的引导信息素的均匀分配策略未体现出路段的重要性,蚁群优化算法研究进展,最初的蚁群算法是蚂蚁系统,由于信息素更新方式的不同还可以细分为蚁周、蚁密、蚁量三种算法模型。但是蚂蚁系统只能解决小规模的问题,比如说TSP 问题。但是当问题的规模增大时,比如说TSP中的城市规模增大时,算法的反应比较迟钝,所以产生了后来的蚁群系统,优化了蚂蚁系统在全局的更新以及蚂蚁的状态转移两个方面。为了优化整个算法的运行效率,又出现了最大最小蚂蚁系统,它是将信息素的变化限定在一个区间之内,如此加剧了各个解

8、的信息素的差异,使收敛速度加快,但是如此容易出现早熟的问题,所以又引入了润滑的机制,蚁群算法的应用,一、物流中的应用 蚁群算法可以用于网络的优化用以解决不同领域的不同问题,比如说运输工具、运输路线、运输人员的选择方案等,比较典型的例子有指派问题、运输问题、车辆路径问题等。二、聚类中的应用 蚁群算法在聚类问题中的应用产生了蚁群聚类算法。蚁群聚类算法是一种全局优化的启发式算法。能根据聚类中心的信息素把周围数据归并到一起,从而得到数据分类。,蚁群算法的应用,三、机器人中的应用 在机器人的应用中,蚁群算法可以帮助搜索最优路径,帮助确定机器人的行动路径。四、其他应用 旅行商问题 Job-Shop调度问题 网络路由问题 大规模集成电路综合布线问题 图像处理,蚁群算法的发展趋势,蚁群算法主要的应用领域还是离散的应用域,而在连续域的应用相对较少。随着算法研究的深入,连续域问题的解决难度会降低,算法中的参数比如说信息素,将会由线性的发展到更加复杂的数学关系,甚至是时变的,使整个算法构成一个动态的、实时的、连续的、多维的复杂系统。随着多核电脑的普及以及电脑计算性能的提高,以及下一代计算机技术以及智能网络平台的发展和成熟,并行编程将是主流的应用开发模式,而蚁群算法具有天然的并行计算性能,再加上其高效的智能计算能力以及在广泛领域的应用,蚁群算法可以在新的互联网时代获得更多的发展空间。,谢谢,