《蚁群算法发展.pptx》由会员分享，可在线阅读，更多相关《蚁群算法发展.pptx（20页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、会计学1蚁群算法发展蚁群算法发展蚂蚁的生物学特征蚂蚁的生物学特征 蚂蚁是一种既渺小而又平常的社会性昆虫。蚂蚁是一种既渺小而又平常的社会性昆虫。生物学家通过对蚂蚁的长期观察研究发现，每只生物学家通过对蚂蚁的长期观察研究发现，每只蚂蚁的智能并不高，但它们却能协同工作，集中蚂蚁的智能并不高，但它们却能协同工作，集中食物，建筑蚁穴并抚养后代，依靠群体能力发挥食物，建筑蚁穴并抚养后代，依靠群体能力发挥出超出个体的智能。出超出个体的智能。蚂蚁有复杂的社会体制，蚂蚁有复杂的社会体制，“蚂蚁蚂蚁”城市往往有城市往往有50005000万个成员。蚂蚁有四种不同的蚁型：蚁后、万个成员。蚂蚁有四种不同的蚁型：蚁后、雄
2、蚁、工蚁和兵蚁。雄蚁、工蚁和兵蚁。第1页/共20页蚂蚁的生物学特征蚂蚁的生物学特征n n寻找食物蚂蚁寻找食物过程中总会自动找到一条最短路径。第2页/共20页蚁群算法起源蚁群算法起源n 蚁群优化（ant colony optimization,ACO）是20世纪90年代初由意大利学者M.Dorigo等通过模拟蚂蚁的行为而提出的一种随机优化技术。ACO算法最初用于求解旅行商问题，现在已经成功用于许多组合优化问题。Macro Dorigo第3页/共20页蚁群算法的基本原理蚁群算法的基本原理 蚁群算法是对自然界蚂蚁的寻径方式进行模似而得出的一种仿生算法。蚂蚁在运动过程中，能够在它所经过的路径上留下一种
3、称之为信息素(pheromone)的物质进行信息传递，而且蚂蚁在运动过程中能够感知这种物质，并以此指导自己的运动方向，因此由大量蚂蚁组成的蚁群集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。第4页/共20页蚁群算法的基本原理蚁群算法的基本原理 在在蚁蚁群群寻寻找找食食物物时时，它它们们总总能能找找到到一一条条从从食食物物到到巢巢穴穴之之间间的的最最优优路路径径。这这是是因因为为蚂蚂蚁蚁在在寻寻找找路路径径时时会会在在路路径径上上释释放放出出一一种种特特殊殊的的信信息息素素。当当它它们们碰碰到到一一个个还还没没有有走走过过的的路路口口时时，就就随随机
4、机地地挑挑选选一一条条路路径径前前行行。与与此此同同时时释释放放出出与与路路径径长长度度有有关关的的信信息息素素。路路径径越越长长，释释放放的的激激索索浓浓度度越越低低。当当后后来来的的蚂蚂蚁蚁再再次次碰碰到到这这个个路路口口的的时时候候，选选择择激激素素浓浓度度较较高高路路径径概概率率就就会会相相对对较较大大。这这样样形形成成一一个个正正反反馈馈。最最优优路路径径上上的的激激索索浓浓度度越越来来越越大大。而而其其它它的的路路径径上上激激素素浓浓度度却却会会随随着着时时间间的的流流逝逝而而消消减。最终整个蚁群会找出最优路径。减。最终整个蚁群会找出最优路径。第5页/共20页简化蚂蚁的寻食过程简化
5、蚂蚁的寻食过程蚂蚁从A点出发，速度相同，食物在D点，可能随机选择路线ABD或ACD。假设初始时每条分配路线一只蚂蚁，每个时间单位行走一步，本图为经过9个时间单位时的情形：走ABD的蚂蚁到达终点，而走ACD的蚂蚁刚好走到C点，为一半路程。第6页/共20页简化蚂蚁的寻食过程简化蚂蚁的寻食过程本图为从开始算起，经过18个时间单位时的情形：走ABD的蚂蚁到达终点后得到食物又返回了起点A，而走ACD的蚂蚁刚好走到D点。第7页/共20页简化蚂蚁的寻食过程简化蚂蚁的寻食过程假设蚂蚁每经过一处所留下的信息素为一个单位，假设蚂蚁每经过一处所留下的信息素为一个单位，则经过则经过3636个时间单位后，所有开始一起出
6、发的蚂蚁都经个时间单位后，所有开始一起出发的蚂蚁都经过不同路径从过不同路径从DD点取得了食物，此时点取得了食物，此时ABDABD的路线往返了的路线往返了2 2趟，每一处的信息素为趟，每一处的信息素为4 4个单位，而个单位，而 ACDACD的路线往返了的路线往返了一趟，每一处的信息素为一趟，每一处的信息素为2 2个单位，其比值为个单位，其比值为2 2：1 1。寻找食物的过程继续进行，则按信息素的指导，蚁群寻找食物的过程继续进行，则按信息素的指导，蚁群在在ABDABD路线上增派一只蚂蚁（共路线上增派一只蚂蚁（共2 2只），而只），而ACDACD路线上仍路线上仍然为一只蚂蚁。再经过然为一只蚂蚁。再经
7、过3636个时间单位后，两条线路上的个时间单位后，两条线路上的信息素单位积累为信息素单位积累为1212和和4 4，比值为，比值为3 3：1 1。若按以上规则继续，蚁群在若按以上规则继续，蚁群在ABDABD路线上再增派一只蚂路线上再增派一只蚂蚁（共蚁（共3 3只），而只），而ACDACD路线上仍然为一只蚂蚁。再经过路线上仍然为一只蚂蚁。再经过3636个时间单位后，两条线路上的信息素单位积累为个时间单位后，两条线路上的信息素单位积累为2424和和6 6，比值为比值为4 4：1 1。若继续进行，则按信息素的指导，最终所有的蚂蚁会若继续进行，则按信息素的指导，最终所有的蚂蚁会放弃放弃ACDACD路线，
8、而都选择路线，而都选择ABDABD路线。这也就是前面所提路线。这也就是前面所提到的正反馈效应。到的正反馈效应。第8页/共20页蚁群算法模型的建立蚁群算法模型的建立对蚂蚁个体的抽象 蚁群算法是对自然界真实蚂蚁觅食行为的一种模拟，因此首先必须对真实蚂蚁进行抽象，而不可能也没必要对蚂蚁个体进行完全再现。把蚂蚁能够有效刻画出真实蚁群中能为算法所借鉴的特征抽象出来，同时建立与算法模型无关的因素。第9页/共20页蚁群算法模型的建立蚁群算法模型的建立问题空间的描述 蚁群算法所求解的问题空间可用一个重要的数学工具图（graph）来描述。寻找路径的抽象寻找路径的抽象 把觅食过程抽象成算法中解的构造过把觅食过程抽
9、象成算法中解的构造过程，将信息素抽象为存在于图的边上的轨程，将信息素抽象为存在于图的边上的轨迹。在每一节点上人工蚂蚁感知相邻节点迹。在每一节点上人工蚂蚁感知相邻节点边上的信息素浓度。边上的信息素浓度。第10页/共20页蚁群算法模型的建立蚁群算法模型的建立信息素挥发的抽象 自然界中，蚂蚁留下的信息素会随着时间的推移而连续不断的挥发。因此使算法中的信息素挥发方式与蚂蚁觅食过程机理相符，要使蚂蚁完成一个节点的移动后，经过一个单位时间，进行一次信息素的挥发。第11页/共20页蚁群算法模型的建立蚁群算法模型的建立启发因子的引入 蚁群算法的自组织性，似的系统的演化需要耗费较长的时间，而实际应用时对算法运行
10、时间的要求也是必不可少的。因此引入一个启发因子，给蚁群算法一个初始的引导，增加算法的时间有效性。第12页/共20页蚁群算法的基本步骤蚁群算法的基本步骤第13页/共20页基本蚁群算法的优缺点基本蚁群算法的优缺点优点n n较强的鲁棒性、全局性、普遍性较强的鲁棒性、全局性、普遍性n n分布式计算分布式计算n n易于与其它方法结合易于与其它方法结合缺点n n需要较长的计算时间，容易停滞需要较长的计算时间，容易停滞n n所有路径的信息素增量，会导致错误的引导所有路径的信息素增量，会导致错误的引导n n信息素的均匀分配策略未体现出路段的重要性信息素的均匀分配策略未体现出路段的重要性第14页/共20页 蚁群
11、优化算法研究进蚁群优化算法研究进展展 最初的蚁群算法是蚂蚁系统,由于信息素更新方式的不同还可以细分为蚁周、蚁密、蚁量三种算法模型。但是蚂蚁系统只能解决小规模的问题,比如说TSP 问题。但是当问题的规模增大时,比如说TSP中的城市规模增大时,算法的反应比较迟钝,所以产生了后来的蚁群系统,优化了蚂蚁系统在全局的更新以及蚂蚁的状态转移两个方面。为了优化整个算法的运行效率,又出现了最大最小蚂蚁系统,它是将信息素的变化限定在一个区间之内,如此加剧了各个解的信息素的差异,使收敛速度加快,但是如此容易出现早熟的问题,所以又引入了润滑的机制第15页/共20页蚁群算法的应用蚁群算法的应用一、物流中的应用一、物流
12、中的应用 蚁群算法可以用于网络的优化用以解决不同领蚁群算法可以用于网络的优化用以解决不同领域的不同问题域的不同问题,比如说运输工具、运输路线、运输比如说运输工具、运输路线、运输人员的选择方案等人员的选择方案等,比较典型的例子有指派问题、运比较典型的例子有指派问题、运输问题、车辆路径问题等。输问题、车辆路径问题等。二、聚类中的应用二、聚类中的应用 蚁群算法在聚类问题中的应用产生了蚁群聚类蚁群算法在聚类问题中的应用产生了蚁群聚类算法。蚁群聚类算法是一种全局优化的启发式算法。算法。蚁群聚类算法是一种全局优化的启发式算法。能根据聚类中心的信息素把周围数据归并到一起能根据聚类中心的信息素把周围数据归并到
13、一起,从而得到数据分类。从而得到数据分类。第16页/共20页蚁群算法的应用三、机器人中的应用 在机器人的应用中,蚁群算法可以帮助搜索最优路径,帮助确定机器人的行动路径。四、其他应用 旅行商问题 Job-Shop调度问题 网络路由问题 大规模集成电路综合布线问题 图像处理第17页/共20页蚁群算法的发展趋势 蚁群算法主要的应用领域还是离散的应用域,而在连续域的应用相对较少。随着算法研究的深入,连续域问题的解决难度会降低,算法中的参数比如说信息素,将会由线性的发展到更加复杂的数学关系,甚至是时变的,使整个算法构成一个动态的、实时的、连续的、多维的复杂系统。随着多核电脑的普及以及电脑计算性能的提高,以及下一代计算机技术以及智能网络平台的发展和成熟,并行编程将是主流的应用开发模式,而蚁群算法具有天然的并行计算性能,再加上其高效的智能计算能力以及在广泛领域的应用,蚁群算法可以在新的互联网时代获得更多的发展空间。第18页/共20页谢谢谢谢第19页/共20页