蚁群算法及算例ppt课件.pptx

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

1、蚁群优化算法（ACO算法）一、概述二、蚂蚁系统（AS）三、算例四、改进的ACO算法一、概述（一）算法背景——蚁群的自组织行为特征1、高度结构化的组织——虽然蚂蚁的个体行为极其简单，但由个体组成的蚁群却构成高度结构化的社会组织，蚂蚁社会的成员有分工，有相互的通信和信息传递。2、自然优化——蚁群在觅食过程中，在没有任何提示下总能找到从蚁巢到食物源之间的最短路径；当经过的路线上出现障碍物时，还能迅速找到新的最优路径。3、信息正反馈——蚂蚁在寻找食物时，在其经过的路径上释放信息素（外激素）。蚂蚁基本没有视觉，但能在小范围内察觉同类散发的信息素的轨迹，由此

2、来决定何去何从，并倾向于朝着信息素强度高的方向移动。4、自催化行为——某条路径上走过的蚂蚁越多，留下的信息素也越多（随时间蒸发一部分），后来蚂蚁选择该路径的概率也越高。（二）算法的产生与发展1、产生——受蚁群觅食行为启发，意大利学者M.Dorigo于1991年在其博士论文中首次系统地提出一种基于蚂蚁种群的新型智能优化算法“蚂蚁系统（Antsystem,简称AS）”，并用该法求解旅行商问题，获得了较好的效果。2、发展——后来，提出者及许多研究者对该算法作了各种改进，将其应用于更为广泛的领域，如图着色问题、二次分配问题、工件排序问题、车辆路径问题、车

3、间作业调度问题、网络路由问题、大规模集成电路设计等。近些年来，M.Dorigo等人把蚂蚁算法进一步发展成一种通用的优化技术“蚁群优化（AntColonyOptimization,简称ACO）”，并将所有符合ACO框架的算法称为“蚁群优化算法（ACOalgorithm）”。3、展望——初步的研究结果已显示出ACO算法在求解复杂优化问题，特别是离散优化问题方面的优越性。虽然严格的理论基础尚未奠定，但从当前的应用效果来看，此算法具有光明的发展前景。（三）特点◆是一种基于多主体的智能算法，不是单个蚂蚁行动，而是多个蚂蚁同时搜索，具有分布式的协同优化机制。

4、◆本质上属于随机搜索算法（概率算法），具有概率搜索的特征。◆是一种全局搜索算法，能够有效地避免局部最优。（四）优点◆求解问题的快速性——由正反馈机制决定；◆全局优化性——由分布式计算决定，避免蚁群在寻优空间中过早收敛；◆有限时间内答案的合理性——由贪婪式搜索模式决定，使能在搜索过程的早期就找到可以接受的较好解。二、蚂蚁系统（AS算法）——最早的ACO算法（一）算法基本思想（以旅行商为例说明）1、根据具体问题设置多只蚂蚁，分头并行搜索。2、每只蚂蚁完成一次周游后，在行进的路上释放信息素，信息素量与解的质量成正比。3、蚂蚁路径的选择根据信息素强度大小

5、（初始信息素量设为相等），同时考虑两点之间的距离，采用随机的局部搜索策略。这使得距离较短的边，其上的信息素量较大，后来的蚂蚁选择该边的概率也较大。4、每只蚂蚁只能走合法路线（经过每个城市1次且仅1次），为此设置禁忌表来控制。5、所有蚂蚁都搜索完一次就是迭代一次，每迭代一次就对所有的边做一次信息素更新，原来的蚂蚁死掉，新的蚂蚁进行新一轮搜索。6、更新信息素包括原有信息素的蒸发和经过的路径上信息素的增加。7、达到预定的迭代步数，或出现停滞现象（所有蚂蚁都选择同样的路径，解不再变化），则算法结束，以当前最优解作为问题的最优解。（二）参数含义及符号——蚂

6、蚁数量；——蚂蚁编号；——时刻；——城市数；——城市之间的距离；——启发式因子（能见度），反映蚂蚁由城市转移到城市的启发程度；——边上的信息素量；——第只蚂蚁在本次迭代中留在边上的信息素量；——信息素蒸发（或挥发）系数，——持久性（或残留）系数，；——时刻蚂蚁由城市转移到城市的概率（转移概率）；——本次迭代边上的信息素增量；——蚂蚁的禁忌表。（三）计算公式1、转移概率计算公式：——蚂蚁下一步允许选择的城市集合。——信息素的相对重要程度；——启发式因子的相对重要程度；2、启发式因子计算公式：3、信息素计算公式——正常数，——蚂蚁在本次周游中所走路径

7、的长度。当所有蚂蚁完成1次周游后，各路径上的信息素为：开始时，令（四）算法步骤1、初始化参数：开始时每条边的信息素量都相等。2、将各只蚂蚁放置各顶点，禁忌表为对应的顶点。3、取1只蚂蚁，计算转移概率，按轮盘赌的方式选择下一个顶点，更新禁忌表，再计算概率，再选择顶点，再更新禁忌表，直至遍历所有顶点1次。4、计算该只蚂蚁留在各边的信息素量，该蚂蚁死去。5、重复3~4，直至只蚂蚁都周游完毕。6、计算各边的信息素增量和信息素量。7、记录本次迭代的路径，更新当前的最优路径，清空禁忌表。8、判断是否达到预定的迭代步数，或者是否出现停滞现象。若是，算法结束，输

8、出当前最优路径；否，转2，进行下一次迭代。优点较强的鲁棒性——稍加修改即可应用于其他问题。（鲁棒性就是系统的健壮性，用以表征控制系统对特