蚁群算法及算例.pptVIP

蚁群优化箕法 (AcO算法) 、概述 二、蚂蚁系统(AS) 三、算例 四、改进的AC0算法 Valadon onry. ch Asposeslides for NET 4o dient P Evaluation only. Created with Aspose Slides for NET 4.0 dient Profilo 71 Copyright 2004-2017Aspose Pty L  、概述 (一)算法背景——蚁群的自组织行为特征 1、高度结构化的组织——虽然蚂蚁的个体行为极其 简单,但由个体组成的蚁群却构成高度结构化的社会 组织,蚂蚁社会的成员有分工,有相互的通信和信息 传递。 2、自然优化—蚁群在觅食过程中,在没有任何提示 下总能找到从蚁巢到食物源之间的最短路径;当经过的 路线上出现障碍物时,还能迅速找到新的最优路径。 3、信息正反馈——蚂蚁在寻找食物时,在其经过的路 径上释放信息素(外激素)。蚂蚁基本没有视觉,但能 在小范围内察觉同类散发的信息素的轨迹,由此来决定 何去何从,并倾向于朝着信息素强度高的方向移动。 4、自催化行为——某条路径上走过的蚂蚁越多,留下 的信息素也越多(随时间蒸发一部分),后来蚂蚁选择 该路径的概率也越高。 Valadon onry. ch Asposeslides for NET 4o dient P Evaluation only. Created with Aspose Slides for NET 4.0 dient Profilo 71 Copyright 2004-2017Aspose Pty L  (二)算法的产生与发展 1、产生—受蚁群觅食行为启发,意大利学者 MDorigo 于1991年在其博士论文中首次系统地提出一种基于蚂蚁种群 的新型智能优化算法“蚂蚁系统( Ant system,简称AS)”, 并用该法求解旅行商问题,获得了较好的效果。 2、发展——后来,提出者及许多研究者对该算法作了各种 改进,将其应用于更为广泛的领域,如图着色问题、二次分 配问题、工件排序问题、车辆路径问题、车间作业调度问题、 网络路由问题、大规模集成电路设计等。近些年来, MDorigo 等人把蚂蚁算法进一步发展成一种通用的优化技术“蚁群优化 ( Ant Colony Optimization,简称AcO)”,并将所有符合Aco 框架的算法称为“蚁群优化算法( ACo algorithm)” 3、展望一—初步的研究结果已显示出AcO算法在求解复杂 优化问题,特别是离散优化问题方面的优越性。虽然严格的 理论基础尚未奠定,但从当前的应用效果来看,此算法具有 光明的发展前景。 Valadon onry. ch Asposeslides for NET 4o dient P Evaluation only. Created with Aspose Slides for NET 4.0 dient Profilo 71 Copyright 2004-2017Aspose Pty L  (三)特点 ◆是一种基于多主体的智能算法,不是 单个蚂蚁行动,而是多个蚂蚁同时有哪些信誉好的足球投注网站, 具有分布式的协同优化机制。 ◆本质上属于随机有哪些信誉好的足球投注网站算法(概率算法), 具有概率有哪些信誉好的足球投注网站的特征。 ◆是一种全局有哪些信誉好的足球投注网站算法,能够有效地避免 局部最优。 Valadon onry. ch Asposeslides for NET 4o dient P Evaluation only. Created with Aspose Slides for NET 4.0 dient Profilo 71 Copyright 2004-2017Aspose Pty L  (四)优点 ◆求解问题的快速性——由正反馈机制 决定 ◆全局优化性——由分布式计算决定 避免蚁群在寻优空间中过早收敛; ◆有限时间内答案的合理性——由贪婪 式有哪些信誉好的足球投注网站模式决定,使能在有哪些信誉好的足球投注网站过程的早期 就找到可以接受的较好解。 Valadon onry. ch Asposeslides for NET 4o dient P Evaluation only. Created with Aspose Slides for NET 4.0 dient Profilo 71 Copyright 2004-2017Aspose Pty L  二、蚂蚁系统(AS算法)——最早的AC0算法 (一)算法基本思想(以旅行商为例说明) 1、根据具体问题设置多只蚂蚁,分头并行搜 索 2、每只蚂蚁完成一次周游后,在行进的路上 释放信息素,信息素量