蚁群算法_原创精品文档.pptVIP

蚁群算法ACO(ant colony optimization) 大纲 1、蚁群优化算法简介 2、蚁群算法基本流程 3、蚁群算法应用举例 4、蚁群算法的改进版本 5、蚁群算法的相关应用 及当前发展趋势 蚂蚁的生物学特征 蚂蚁在8000万年前就建立起了自己的社会。许多“蚂蚁城市”往往由5000万个成员组成，并且是一个组织完好的复杂“城市”。 /v_show/id_XODEwOTg5Mg==.html 蚁群优化算法起源 蚁群优化（ant colony optimization,ACO）是20世纪90年代初由意大利学者M.Dorigo等通过模拟蚂蚁的行为而提出的一种随机优化技术。ACO算法最初用于求解旅行商问题，现在已经成功用于许多组合优化问题。本节课将介绍ACO算法的基本原理和实现技术，并通过介绍求解旅行商问题的ACO算法了解实现细节。 蚁群优化算法研究进展 最初提出的AS有三种版本：Ant-density、Ant-quantity和Ant-cycle。在Ant-density和Ant-quantity中蚂蚁在两个位置节点间每移动一次后即更新信息素，而在Ant-cycle中当所有的蚂蚁都完成了自己的行程后才对信息素进行更新，而且每个蚂蚁所释放的信息素被表达为反映相应行程质量的函数。现在我们一般所提到的AS实质上指的是蚂蚁周期这一版本的AS另外两个版本的AS因为其低劣的性能已遭淘汰。 但是当问题规模扩展时，AS的解题能力大幅度下降。 因此，其后的ACO研究工作主要都集中于AS性能的改进方面。例如：EAS, MMAS,ASrank，其思想是在算法开始后即对所有已发现的最好路径给予额外的增强，并将随后与之对应的行程记为Tb(全局最优行程)，当进行信息素更新时，对这些行程予以加权，同时将经过这些行程的蚂蚁记为“精英”，从而增大较好行程的选择机会。这种改进型算法能够以更快的速度获得更好的解。但是若选择的精英过多则算法会由于较早的收敛于局部次优解而导致有哪些信誉好的足球投注网站的过早停滞。 蚁群优化算法研究进展 了进一步克服AS中暴露出的问题，提出了蚁群系统(Ant Colony System, ACS)。ACS与AS之间存在三方面的主要差异：首先，ACS采用了更为大胆的行为选择规则；其次，只增强属于全局最优解的路径上的信息素。其中，0ρ1是信息素挥发参数， 是从寻路开始到当前为止全局最优的路径长度。试验结果表明ACS的算法性能明显优于AS，ACS是蚁群优化算法发展史上的又一里程碑 蚁群优化算法的年表： 1959年，Pierre-Paul Grassé发明了Stigmergy理论来解释白蚁建设巢的行为; 1983年， Deneubourg和他的同事们研究了蚂蚁的集体行为; 1988年， Moyson Manderick写了一篇蚂蚁自组织的文章 1989年，Goss, Aron, Deneubourg和Pasteels关于阿根廷蚂蚁的集体行为的研究， 给蚁群优化算法的思想提供了灵感; 1989年，Ebling和他的同事落实了觅食行为的模型 1991年， M. Dorigo在他的博士论文中提出了蚂蚁系统（文章于1992年发表）。 一份从论文中提取的技术报告五年后出版，由V. Maniezzo和A.Colorni合著; 1996年，蚂蚁系统的文章出版; 1996年，Hoos与Stützle发明了最大最小蚂蚁系统; 1997年，Dorigo和Gambardella发布了蚁群系统; 1997年， Schoonderwoerd和他的同事们开发了对电信网络的首次应用; 1998年，Dorigo发起了第一次蚁群算法的专题会议 1998年， Stützle提出初步的并行实现 1999年，Bonabeau, Dorigo和Theraulaz的出版了一本书，主要关于人工蚂蚁 2000年，未来计算机系统杂志上发表了蚂蚁算法特刊 2000年，调度的最早期的应用程序，调度了序列和约束的满意度 2000年， Gutjahr提供了一个蚁群算法收敛的第一个证据 2001年，COA算法首次被使用（ Eurobios和AntOptima ） 2001年， IREDA和他的同事们发表了第一个多对象算法 2002年，调度设计的首次应用，贝叶斯网络 2002年，比安奇和她的同事提出