下载

1下载券

加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 蚁群算法设计与分析

蚁群算法设计与分析 .ppt

蚁群算法设计与分析

山水树涛
2012-12-21 0人阅读 举报 0 0 暂无简介

简介:本文档为《蚁群算法设计与分析 ppt》,可适用于IT/计算机领域

算法设计与分析第七章补充材料蚁群算法介绍算法设计与分析第七章补充材料蚁群算法介绍山东师范大学计算机系授课:徐连诚##lchxucomhttp:lchxuwelkindnet年月日年月日内容内容一、启发式方法概述二、蚁群优化算法背景背景传统实际问题的特点连续性问题主要以微积分为基础且问题规模较小传统的优化方法追求准确精确解理论的完美结果漂亮主要方法:线性与非线性规划、动态规划、多目标规划、整数规划等排队论、库存论、对策论、决策论等。传统的评价方法算法收敛性(从极限角度考虑)收敛速度(线性、超线性、二次收敛等)传统运筹学面临新挑战传统运筹学面临新挑战现代问题的特点离散性问题主要以组合优化(针对离散问题定义见后)理论为基础不确定性问题随机性数学模型半结构或非结构化的问题计算机模拟、决策支持系统大规模问题并行计算、大型分解理论、近似理论现代优化方法追求满意近似解实用性强解决实际问题现代优化算法的评价方法算法复杂性现代优化(启发式)方法种类现代优化(启发式)方法种类禁忌搜索(tabusearch)模拟退火(simulatedannealing)遗传算法(geneticalgorithms)神经网络(neuralnetworks)蚁群算法(群体(群集)智能SwarmIntelligence)拉格朗日松弛算法(lagrangeanrelaxation)现代优化计算方法概述现代优化计算方法概述组合优化问题计算复杂性的概念启发式算法组合优化问题组合优化问题组合优化(combinatorialoptimization):解决离散问题的优化问题运筹学分支。通过数学方法的研究去寻找离散事件的最优编排、分组、次序或筛选等可以涉及信息技术、经济管理、工业工程、交通运输和通信网络等许多方面。数学模型:组合优化问题组合优化问题组合优化问题的三参数表示:组合优化问题组合优化问题例背包问题(knapsackproblem)组合优化问题组合优化问题组合优化问题组合优化问题例旅行商问题(TSP,travelingsalesmanproblem)管梅谷教授年首先提出国际上称之为中国邮递员问题。问题描述:一商人去n个城市销货所有城市走一遍再回到起点使所走路程最短。组合优化问题组合优化问题组合优化问题组合优化问题例装箱问题(binpacking)尺寸为的箱子有若干个怎样用最少的箱子装下n个尺寸不超过的物品物品集合为:。组合优化问题组合优化问题计算复杂性的概念计算复杂性的概念评价算法的好坏计算时间的多少、解的偏离程度例非对称距离TSP问题的算法实现:所有路径枚举。计算时间:n个城市固定个为起终点需要(n)!个枚举设计算机秒能完成个城市的枚举则城市数与计算时间的关系如下表:计算复杂性的概念计算复杂性的概念随城市增多计算时间增加很快。到个城市时要计算年。描述算法的好坏计算复杂性讨论计算时间与问题规模之间的关系。以目前二进制计算机中的存储和计算为基础以理论的形式系统描述是评估算法性能的基础。计算复杂性的概念计算复杂性的概念问题(problem):要回答的一般性提问通常含有若干个满足一定条件的参数(或自由变量)。可以从两方面描述:()对所有参数的一般性描述()答案(或解)必须满足的性质。实例(instance):给问题的所有参数指定具体值得到问题的一个实例。这些具体值称为数据这些数据输入计算机所占的空间称为实例的长度(size)计算复杂性的概念计算复杂性的概念一类最优化问题是由一些类似的具体问题(实例)组成的每一个具体问题可表达成二元组(F,C)F为可行解集合C是费用函数是由F到R(实数集)的映像。问题是在F中找到一个点f*使对F中任意的f有C(f*)C(f),称f*为这一具体问题的最优解(或全局最优解)计算复杂性的概念计算复杂性的概念算法计算量的度量:加、减、乘、除、比较的总运算次数与实例的计算机计算时的二进制输入数据的大小关系。正整数x的二进制位数是:(整数到二进制的转换)计算复杂性的概念计算复杂性的概念算法计算量的度量之例TSP枚举法计算量的统计:计算复杂性的概念计算复杂性的概念实例的输入长度:实例的输入长度是n的多项式函数枚举法的基本计算量是n的阶乘函数随n的增加比指数函数增加得还快计算复杂性的概念计算复杂性的概念计算复杂性的概念计算复杂性的概念定义多项式算法给定问题P算法A对一个实例I存在多项式函数g(x)使(XX)成立称算法A对实例I是多项式算法若存在多项式函数g(x)使(XX)对问题P的任意实例I都成立称算法A为解决该问题P的多项式算法当g(x)为指数函数时称A为P的指数时间算法。计算复杂性的概念计算复杂性的概念利用复杂性分析对组合优化问题归类。定义多项式问题给定一个组合优化问题若存在一个多项式算法称该问题为多项式时间可解问题或简称多项式问题(或P问题)所有多项式问题的集合记为P例:线性规划是否为多项式问题?计算复杂性参考书计算复杂性参考书计算复杂性,作者:ChristosPapadimitriou清华大学出版社年月第版计算复杂性导论作者:堵丁柱等高等教育出版社年月第版启发式算法定义启发式算法定义启发式算法(heuristicalgorithm)定义基于直观或经验构造的算法在可接受的花费(时间、空间)下给出待解组合优化问题的每个实例的一个可行解该可行解与最优解偏差事先不一定可以预计定义启发式算法是一种技术在可接受的计算费用内寻找最好解但不保证该解的可行性与最优性无法描述该解与最优解的近似程度。特点(与传统优化方法不同):凭直观和经验给出算法不考虑所得解与最优解的偏离程度启发式算法优点启发式算法优点优点:()有可能比简化数学模型解的误差小()对有些难题计算时间可接受()可用于某些最优化算法(如分支定界算法)之中的估界()直观易行()速度较快()程序简单易修改。启发式算法不足启发式算法不足不足:()不能保证求得全局最优解()解的精度不稳定有时好有时坏()算法设计与问题、设计者经验、技术有关缺乏规律性()不同算法之间难以比较。启发式算法分类启发式算法分类()一步算法()改进算法(迭代算法)()数学规划算法()解空间松弛法启发式算法分类启发式算法分类()现代优化算法:年代初兴起禁忌搜索(tabusearch)模拟退火(simulatedannealing)遗传算法(geneticalgorithms)神经网络(neuralnetworks)蚂蚁算法(AntAlgorithm群体(群集)智能SwarmIntelligence)()其他算法:多种启发式算法的集成启发式算法性能分析启发式算法性能分析()最坏情形分析(worstcaseanalysis)利用最坏实例分析计算复杂性、解的效果。()概率分析(probabilityanalysis)用最坏情况分析会因一个最坏实例影响总体评价在实例数据服从一定概率分布情形下研究算法复杂性和解的效果()大规模计算分析通过大量实例计算评价算法效果注意数据的随机性和代表性蚁群优化算法蚁群优化算法蚁群优化算法概述蚁群优化算法概念算法模型和收敛性分析算法实现的技术问题应用参考资料蚁群优化算法概述蚁群优化算法概述起源应用领域研究背景研究现状应用现状蚁群优化算法起源蚁群优化算法起源世纪年代中期创立了仿生学人们从生物进化的机理中受到启发。提出了许多用以解决复杂优化问题的新方法如进化规划、进化策略、遗传算法等这些算法成功地解决了一些实际问题。世纪年代意大利学者M.DorigoV.ManiezzoA.Colorni等从生物进化的机制中受到启发通过模拟自然界蚂蚁搜索路径的行为提出来一种新型的模拟进化算法蚁群算法是群智能理论研究领域的一种主要算法。用该方法求解TSP问题、分配问题、jobshop调度问题取得了较好的试验结果.虽然研究时间不长但是现在的研究显示出蚁群算法在求解复杂优化问题(特别是离散优化问题)方面有一定优势表明它是一种有发展前景的算法.蚁群优化算法应用领域蚁群优化算法应用领域这种方法能够被用于解决大多数优化问题或者能够转化为优化求解的问题。现在其应用领域已扩展到多目标优化、数据分类、数据聚类、模式识别、电信QoS管理、生物系统建模、流程规划、信号处理、机器人控制、决策支持以及仿真和系统辩识等方面群智能理论和方法为解决这类应用问题提供了新的途径。蚁群优化算法研究背景蚁群优化算法研究背景群智能理论研究领域有两种主要的算法:蚁群算法(AntColonyOptimization,ACO)和微粒群算法(ParticleSwarmOptimization,PSO)。前者是对蚂蚁群落食物采集过程的模拟已成功应用于许多离散优化问题。微粒群算法也是起源于对简单社会系统的模拟最初是模拟鸟群觅食的过程但后来发现它是一种很好的优化工具。蚁群优化算法研究背景蚁群优化算法研究背景与大多数基于梯度的应用优化算法不同群智能依靠的是概率搜索算法。虽然概率搜索算法通常要采用较多的评价函数但是与梯度方法及传统的演化算法相比其优点还是显著的主要表现在以下几个方面:无集中控制约束不会因个别个体的故障影响整个问题的求解确保了系统具备更强的鲁棒性以非直接的信息交流方式确保了系统的扩展性并行分布式算法模型可充分利用多处理器对问题定义的连续性无特殊要求算法实现简单蚁群优化算法研究背景蚁群优化算法研究背景群智能方法易于实现算法中仅涉及各种基本的数学操作其数据处理过程对CPU和内存的要求也不高。而且这种方法只需目标函数的输出值而无需其梯度信息。已完成的群智能理论和应用方法研究证明群智能方法是一种能够有效解决大多数全局优化问题的新方法。更为重要是群智能潜在的并行性和分布式特点为处理大量的以数据库形式存在的数据提供了技术保证。无论是从理论研究还是应用研究的角度分析群智能理论及其应用研究都是具有重要学术意义和现实价值的。蚁群优化算法研究现状蚁群优化算法研究现状年代Dorigo最早提出了蚁群优化算法蚂蚁系统(AntSystem,AS)并将其应用于解决计算机算法学中经典的旅行商问题(TSP)。从蚂蚁系统开始基本的蚁群算法得到了不断的发展和完善并在TSP以及许多实际优化问题求解中进一步得到了验证。这些AS改进版本的一个共同点就是增强了蚂蚁搜索过程中对最优解的探索能力它们之间的差异仅在于搜索控制策略方面。而且取得了最佳结果的ACO是通过引入局部搜索算法实现的这实际上是一些结合了标准局域搜索算法的混合型概率搜索算法有利于提高蚁群各级系统在优化问题中的求解质量。蚁群优化算法研究现状蚁群优化算法研究现状最初提出的AS有三种版本:Antdensity、Antquantity和Antcycle。在Antdensity和Antquantity中蚂蚁在两个位置节点间每移动一次后即更新信息素而在Antcycle中当所有的蚂蚁都完成了自己的行程后才对信息素进行更新而且每个蚂蚁所释放的信息素被表达为反映相应行程质量的函数。通过与其它各种通用的启发式算法相比在不大于城市的TSP中这三种基本算法的求解能力还是比较理想的但是当问题规模扩展时AS的解题能力大幅度下降。因此其后的ACO研究工作主要都集中于AS性能的改进方面。较早的一种改进方法是精英策略(ElitistStrategy)其思想是在算法开始后即对所有已发现的最好路径给予额外的增强并将随后与之对应的行程记为Tgb(全局最优行程)当进行信息素更新时对这些行程予以加权同时将经过这些行程的蚂蚁记为“精英”从而增大较好行程的选择机会。这种改进型算法能够以更快的速度获得更好的解。但是若选择的精英过多则算法会由于较早的收敛于局部次优解而导致搜索的过早停滞。蚁群优化算法研究现状蚁群优化算法研究现状为了进一步克服AS中暴露出的问题提出了蚁群系统(AntColonySystem,ACS)。该系统的提出是以AntQ算法为基础的。AntQ将蚂蚁算法和一种增强型学习算法Qlearning有机的结合了起来。ACS与AS之间存在三方面的主要差异:首先ACS采用了更为大胆的行为选择规则其次只增强属于全局最优解的路径上的信息素。其中<ρ<是信息素挥发参数是从寻路开始到当前为止全局最优的路径长度。蚁群优化算法研究现状蚁群优化算法研究现状再次还引入了负反馈机制每当一只蚂蚁由一个节点移动到另一个节点时该路径上的信息素都按照如下公式被相应的消除一部分从而实现一种信息素的局部调整以减小已选择过的路径再次被选择的概率。蚁群优化算法研究现状蚁群优化算法研究现状在对AS进行直接完善的方法中MAXMINAntSystem是一个典型代表。该算法修改了AS的信息素更新方式每次迭代之后只有一只蚂蚁能够进行信息素的更新以获取更好的解。为了避免搜索停滞路径上的信息素浓度被限制在MAXMIN范围内另外信息素的初始值被设为其取值上限这样有助于增加算法初始阶段的搜索能力。蚁群优化算法研究现状蚁群优化算法研究现状另一种对AS改进的算法是RankbasedVersionAS。与“精英策略”相似在此算法中总是更新更好进程上的信息素选择的标准是其行程长度决定的排序且每个蚂蚁放置信息素的强度通过下式中的排序加权处理确定其中w为每次迭代后放置信息素的蚂蚁总数。蚁群优化算法研究现状蚁群优化算法研究现状这种算法求解TSP的能力与AS、精英策略AS、遗传算法和模拟退火算法进行了比较。在大型TSP问题中(最多包含座城市)基于AS的算法都显示出了优于GA和SA的特性。而且在RankbasedAS和精英策略AS均优于基本AS的同时前者还获得了比精英策略AS更好的解。蚁群优化算法应用现状蚁群优化算法应用现状随着群智能理论和应用算法研究的不断发展研究者已尝试着将其用于各种工程优化问题并取得了意想不到的收获。多种研究表明群智能在离散求解空间和连续求解空间中均表现出良好的搜索效果并在组合优化问题中表现突出。蚁群优化算法并不是旅行商问题的最佳解决方法但是它却为解决组合优化问题提供了新思路并很快被应用到其它组合优化问题中。比较典型的应用研究包括:网络路由优化、数据挖掘以及一些经典的组合优化问题。蚁群优化算法应用现状蚁群优化算法应用现状蚁群算法在电信路由优化中已取得了一定的应用成果。HP公司和英国电信公司在年代中后期都开展了这方面的研究设计了蚁群路由算法(AntColonyRouting,ACR)。每只蚂蚁就像蚁群优化算法中一样根据它在网络上的经验与性能动态更新路由表项。如果一只蚂蚁因为经过了网络中堵塞的路由而导致了比较大的延迟那么就对该表项做较大的增强。同时根据信息素挥发机制实现系统的信息更新从而抛弃过期的路由信息。这样在当前最优路由出现拥堵现象时ACR算法就能迅速的搜寻另一条可替代的最优路径从而提高网络的均衡性、负荷量和利用率。目前这方面的应用研究仍在升温因为通信网络的分布式信息结构、非稳定随机动态特性以及网络状态的异步演化与ACO的算法本质和特性非常相似。蚁群优化算法应用现状蚁群优化算法应用现状基于群智能的聚类算法起源于对蚁群蚁卵的分类研究。Lumer和Faieta将Deneubourg提出将蚁巢分类模型应用于数据聚类分析。其基本思想是将待聚类数据随机地散布到一个二维平面内然后将虚拟蚂蚁分布到这个空间内并以随机方式移动当一只蚂蚁遇到一个待聚类数据时即将之拾起并继续随机运动若运动路径附近的数据与背负的数据相似性高于设置的标准则将其放置在该位置然后继续移动重复上述数据搬运过程。按照这样的方法可实现对相似数据的聚类。蚁群优化算法应用现状蚁群优化算法应用现状ACO还在许多经典组合优化问题中获得了成功的应用如二次规划问题(QAP)、机器人路径规划、作业流程规划、图着色(GraphColoring)等问题。经过多年的发展ACO已成为能够有效解决实际二次规划问题的几种重要算法之一。AS在作业流程计划(JobshopScheduling)问题中的应用实例已经出现这说明了AS在此领域的应用潜力。利用MAXMINAS解决PAQ也取得了比较理想的效果并通过实验中的计算数据证明采用该方法处理PAQ比较早的SA算法更好且与禁忌搜索算法性能相当。利用ACO实现对生产流程和特料管理的综合优化并通过与遗传、模拟退火和禁忌搜索算法的比较证明了ACO的工程应用价值。蚁群优化算法应用现状蚁群优化算法应用现状许多研究者将ACO用于了武器攻击目标分配和优化问题、车辆运行路径规划、区域性无线电频率自动分配、Bayesiannetworks的训练和集合覆盖等应用优化问题。Costa和Herz还提出了一种AS在规划问题方面的扩展应用图着色问题并取得了可与其他启发式算法相比的效果。蚁群优化算法概念蚁群优化算法概念蚁群算法原理简化的蚂蚁寻食过程自然蚁群与人工蚁群算法蚁群算法与TSP问题初始的蚁群优化算法基于图的蚁群系统(GBAS)一般蚁群算法的框架蚁群算法原理蚁群算法原理蚁群算法是对自然界蚂蚁的寻径方式进行模似而得出的一种仿生算法。蚂蚁在运动过程中能够在它所经过的路径上留下一种称之为外激素(pheromone)的物质进行信息传递而且蚂蚁在运动过程中能够感知这种物质并以此指导自己的运动方向因此由大量蚂蚁组成的蚁群集体行为便表现出一种信息正反馈现象:某一路径上走过的蚂蚁越多则后来者选择该路径的概率就越大。为了说明蚁群算法的原理先简要介绍一下蚂蚁搜寻食物的具体过程。在蚁群寻找食物时它们总能找到一条从食物到巢穴之间的最优路径。这是因为蚂蚁在寻找路径时会在路径上释放出一种特殊的信息素。当它们碰到一个还没有走过的路口时.就随机地挑选一条路径前行。与此同时释放出与路径长度有关的信息素。路径越长释放的激索浓度越低当后来的蚂蚁再次碰到这个路口的时候.选择激素浓度较高路径概率就会相对较大。这样形成一个正反馈。最优路径上的激索浓度越来越大.而其它的路径上激素浓度却会随着时间的流逝而消减。最终整个蚁群会找出最优路径。简化的蚂蚁寻食过程简化的蚂蚁寻食过程蚂蚁从A点出发速度相同食物在D点可能随机选择路线ABD或ACD。假设初始时每条分配路线一只蚂蚁每个时间单位行走一步本图为经过个时间单位时的情形:走ABD的蚂蚁到达终点而走ACD的蚂蚁刚好走到C点为一半路程。简化的蚂蚁寻食过程简化的蚂蚁寻食过程本图为从开始算起经过个时间单位时的情形:走ABD的蚂蚁到达终点后得到食物又返回了起点A而走ACD的蚂蚁刚好走到D点。简化的蚂蚁寻食过程简化的蚂蚁寻食过程假设蚂蚁每经过一处所留下的信息素为一个单位则经过个时间单位后所有开始一起出发的蚂蚁都经过不同路径从D点取得了食物此时ABD的路线往返了趟每一处的信息素为个单位而ACD的路线往返了一趟每一处的信息素为个单位其比值为:。寻找食物的过程继续进行则按信息素的指导蚁群在ABD路线上增派一只蚂蚁(共只)而ACD路线上仍然为一只蚂蚁。再经过个时间单位后两条线路上的信息素单位积累为和比值为:。若按以上规则继续蚁群在ABD路线上再增派一只蚂蚁(共只)而ACD路线上仍然为一只蚂蚁。再经过个时间单位后两条线路上的信息素单位积累为和比值为:。若继续进行则按信息素的指导最终所有的蚂蚁会放弃ACD路线而都选择ABD路线。这也就是前面所提到的正反馈效应。自然蚁群与人工蚁群算法自然蚁群与人工蚁群算法基于以上蚁群寻找食物时的最优路径选择问题可以构造人工蚁群来解决最优化问题如TSP问题。人工蚁群中把具有简单功能的工作单元看作蚂蚁。二者的相似之处在于都是优先选择信息素浓度大的路径。较短路径的信息素浓度高所以能够最终被所有蚂蚁选择也就是最终的优化结果。两者的区别在于人工蚁群有一定的记忆能力能够记忆已经访问过的节点。同时人工蚁群再选择下一条路径的时候是按一定算法规律有意识地寻找最短路径而不是盲目的。例如在TSP问题中可以预先知道当前城市到下一个目的地的距离。蚁群算法与TSP问题蚁群算法与TSP问题TSP问题表示为一个N个城市的有向图G=(NA)其中城市之间距离目标函数为其中为城市,…n的一个排列。蚁群算法与TSP问题蚁群算法与TSP问题TSP问题的人工蚁群算法中假设m只蚂蚁在图的相邻节点间移动从而协作异步地得到问题的解。每只蚂蚁的一步转移概率由图中的每条边上的两类参数决定:信息素值也称信息素痕迹。可见度即先验值。信息素的更新方式有种一是挥发也就是所有路径上的信息素以一定的比率进行减少模拟自然蚁群的信息素随时间挥发的过程二是增强给评价值“好”(有蚂蚁走过)的边增加信息素。蚁群算法与TSP问题蚁群算法与TSP问题蚂蚁向下一个目标的运动是通过一个随机原则来实现的也就是运用当前所在节点存储的信息计算出下一步可达节点的概率并按此概率实现一步移动逐此往复越来越接近最优解。蚂蚁在寻找过程中或者找到一个解后会评估该解或解的一部分的优化程度并把评价信息保存在相关连接的信息素中。初始的蚁群优化算法基于图的蚁群系统(GBAS)初始的蚁群优化算法基于图的蚁群系统(GBAS)初始的蚁群算法是基于图的蚁群算法graphbasedantsystem,简称为GBAS是由GutjahrWJ在年的FutureGenerationComputingSystems提出的课本的参考文献。算法步骤如下:STEP对n个城市的TSP问题城市间的距离矩阵为给TSP图中的每一条弧赋信息素初值假设m只蚂蚁在工作所有蚂蚁都从同一城市出发。当前最好解是。初始的蚁群优化算法基于图的蚁群系统(GBAS)初始的蚁群优化算法基于图的蚁群系统(GBAS)STEP(外循环)如果满足算法的停止规则则停止计算并输出计算得到的最好解。否则使蚂蚁s从起点出发用表示蚂蚁s行走的城市集合初始为空集。STEP(内循环)按蚂蚁的顺序分别计算。当蚂蚁在城市i若完成第s只蚂蚁的计算。否则若则以概率到达j若则到达重复STEP。初始的蚁群优化算法基于图的蚁群系统(GBAS)初始的蚁群优化算法基于图的蚁群系统(GBAS)STRP对若按中城市的顺序计算路径程度若路径长度置为一个无穷大值(即不可达)。比较m只蚂蚁中的路径长度记走最短路径的蚂蚁为t。若则。用如下公式对W路径上的信息素痕迹加强对其他路径上的信息素进行挥发。得到新的重复步骤STEP。初始的蚁群优化算法基于图的蚁群系统(GBAS)初始的蚁群优化算法基于图的蚁群系统(GBAS)在STEP中挥发因子对于一个固定的满足并且经过k次挥发非最优路径的信息素逐渐减少至消失。初始的蚁群优化算法基于图的蚁群系统(GBAS)初始的蚁群优化算法基于图的蚁群系统(GBAS)以上算法中在蚂蚁的搜寻过程中以信息素的概率分布来决定从城市i到城市j的转移。算法中包括信息素更新的过程信息素挥发(evaporation)信息素痕迹的挥发过程是每个连接上的信息素痕迹的浓度自动逐渐减弱的过程由表示这个挥发过程主要用于避免算法过快地向局部最优区域集中有助于搜索区域的扩展。信息素增强(reinforcement)增强过程是蚁群优化算法中可选的部分称为离线更新方式(还有在线更新方式)。这种方式可以实现由单个蚂蚁无法实现的集中行动。也就是说增强过程体现在观察蚁群(m只蚂蚁)中每只蚂蚁所找到的路径并选择其中最优路径上的弧进行信息素的增强挥发过程是所有弧都进行的不于蚂蚁数量相关。这种增强过程中进行的信息素更新称为离线的信息素更新。在STEP中蚁群永远记忆到目前为止的最优解。图的蚁群系统(GBAS)图的蚁群系统(GBAS)可以验证下式满足:即是一个随机矩阵。四个城市的非对称TSP问题距离矩阵和城市图示如下:初始的蚁群优化算法基于图的蚁群系统(GBAS)初始的蚁群优化算法基于图的蚁群系统(GBAS)假设共只蚂蚁所有蚂蚁都从城市A出发挥发因子。此时观察GBAS的计算过程。矩阵共有条弧初始信息素记忆矩阵为:初始的蚁群优化算法基于图的蚁群系统(GBAS)初始的蚁群优化算法基于图的蚁群系统(GBAS)执行GBAS算法的步骤假设蚂蚁的行走路线分别为:当前最优解为这个解是截止到当前的最优解碰巧是实际最优解初始的蚁群优化算法基于图的蚁群系统(GBAS)初始的蚁群优化算法基于图的蚁群系统(GBAS)按算法步骤的信息素更新规则得到更新矩阵这是第一次外循环结束的状态。初始的蚁群优化算法基于图的蚁群系统(GBAS)初始的蚁群优化算法基于图的蚁群系统(GBAS)重复外循环由于上一次得到的W已经是全局最优解因此按算法步骤的信息素更新规则无论蚂蚁如何行走都只是对W路线上的城市信息素进行增强其他的城市信息素进行挥发。得到更新矩阵这是第一次外循环结束的状态。初始的蚁群优化算法基于图的蚁群系统(GBAS)初始的蚁群优化算法基于图的蚁群系统(GBAS)重复外循环由于W全局最优解GBAS只记录第一个最优解因此一但得到了全局最优解信息素的更新将不再依赖于以群的行走路线而只是不断增强最优路线的信息素同时进行挥发。第三次外循环后得到的信息素矩阵为:初始的蚁群优化算法基于图的蚁群系统(GBAS)初始的蚁群优化算法基于图的蚁群系统(GBAS)蚂蚁以一定的概率从城市i到城市j进行转移信息素的更新在STEP完成并随K而变化。假设第K次外循环后得到信息素矩阵得到当前最优解。第K次循环前的信息素和最优解为经过第K次外循环后得到。由于蚂蚁的一步转移概率是随机的从到也是随机的是一个马尔可夫过程。一般蚁群算法的框架一般蚁群算法的框架一般蚁群算法的框架和GBAS基本相同有三个组成部分:蚁群的活动信息素的挥发信息素的增强主要体现在前面的算法中步骤和步骤中的转移概率公式和信息素更新公式。蚁群优化算法算法模型和收敛性分析蚁群优化算法算法模型和收敛性分析马氏过程的收敛定义GBAS算法的收敛性分析其他算法及收敛性分析马氏过程的收敛定义马氏过程的收敛定义蚁群优化算法的每步迭代对应随机变量其中为信息素痕迹为n城市的一个排列最多有个状态。第s只蚂蚁在第k轮转移只由决定这个蚂蚁行走的路径和一起共同决定了再通过信息素的更新原则可以进一步得到。的变化仅由决定而与先前的状态无关这是一个典型的马尔可夫过程。定义:若一个马尔可夫过程对任意给定的满足则称马尔可夫过程依概率收敛到。GBAS算法的收敛性分析GBAS算法的收敛性分析定理满足指定条件的马尔可夫过程依概率收敛到,其中为一条最优路径,定义为:证明分析:蚁群算法中,一但达到全局最优,由只记录第一个最优解证明分三部分:证明以概率达到一个最优路径证明()上式成立证明以概率收敛到一个最优路径GBAS算法的收敛性分析GBAS算法的收敛性分析证明以概率到达一个最优路径对于最优路径,令为蚁群中的一个蚂蚁在第k次外循环后第一次走到最优路径的事件表示仅第k次外循环没有走到的事件,但前k次可能走到过这条最优路径永远不会被走到的事件为,其概率为:GBAS算法的收敛性分析GBAS算法的收敛性分析任意给定的固定弧(i,j),在第k次循环后,其信息素值的下界可以计算出GBAS算法的收敛性分析GBAS算法的收敛性分析令,任何一个固定节点最多有(n)后续节点,并且其弧上的信息素值都小于或者等于得:蚁群中的一只蚂蚁在第次循环走到路径W*的概率为一个蚁群中至少有一只蚂蚁因此这是一个蚁群到达最优路径的一个下界上式右侧与k无关,GBAS算法的收敛性分析GBAS算法的收敛性分析则取对数有从而得到GBAS算法的收敛性分析GBAS算法的收敛性分析证明右式成立随机过程以概率达到一条最优路径当某条最优路径Z在第k次循环被首次走到后,在第k轮循环按信息素的更新原则,可以用归纳法证明,对于任意GBAS算法的收敛性分析GBAS算法的收敛性分析由于级数是发散的,可知因此,当时,在第K轮迭代之后,该弧永远不再被加强,从而有也既弧上的信息素之和将趋于对于信息素的更新公式(),可以归纳证明()式的第二项与(i,j)弧无关,结合()式可得的极限存在,且所有的极限之和为对于所有的GBAS算法的收敛性分析GBAS算法的收敛性分析结合前两部分讨论,当Xn首次到达最优路径后,对于任何最优路径上的弧,()式的转移概率,即依概率收敛到其他算法及收敛性分析其他算法及收敛性分析MAXMIN蚁群优化算法指定挥发系数不随时间变化,这是和GBAS算法不同的一点,改变了信息素挥发和增强的规则(式)同时给出一个下界控制信息素的挥发定理在MAXMIN算法中,其他算法及收敛性分析其他算法及收敛性分析其他算法及收敛性分析其他算法及收敛性分析其他算法及收敛性分析其他算法及收敛性分析蚁群优化算法技术问题蚁群优化算法技术问题解的表达形式与算法的实现每一节点的记忆信息和系数的确定蚁群的规模和停止规则信息素的更改解的表达形式与算法的实现解的表达形式解的表达形式与算法的实现解的表达形式解的表达形式基于TSP问题的蚁群优化算法其解的形式是所有城市的一个排列(闭圈这种情况下谁在第一并不重要)信息素痕迹按每个弧记录。而对于一般以顺序作为解的优化问题谁在第一是很重要的。蚁群算法在解决这类问题时只需要建立一个虚拟的始终点就可以把TSP问题的解法推广用于诸多的优化问题。诸如车间作业及下料等问题他们的共同特点是解以一个顺序表示。TSP问题寻找的是最短回路而一般优化问题中STEP中的判断条件需要根据实际问题进行修改。解的表达形式与算法的实现算法的实现解的表达形式与算法的实现算法的实现例:背包问题的解顺序表达形式与算法实现。设有一个容积为b的背包n个尺寸分别为价值分别为的物品背包问题的数学模型为:假设其解的顺序表达形式为        其中   为      的一个排列。解的表达形式与算法的实现算法的实现解的表达形式与算法的实现算法的实现建立有向图其中A中共有条弧。初始信息素痕迹定义为。设第s只蚂蚁第k步所走的路线为表示蚂蚁从点出发顺序到达。第步按TSP算法的转移概率公式行走选择。若则否则此蚂蚁不再继续行走退回起点。解的表达形式与算法的实现算法的实现解的表达形式与算法的实现算法的实现对蚁群重复以上过程比较m只蚂蚁的装包值并记忆具有最大装包值的蚂蚁为t。把GBAS算法中步骤中的改为若满足此条件则替换当前最好解为对W上的弧进行信息素的加强其他弧进行信息素的挥发。算法中记录了三个信息:信息素痕迹行走路线和问题的约束条件以确定是否将加入。每一节点的记忆信息和系数的确定需要记忆的信息每一节点的记忆信息和系数的确定需要记忆的信息算法中需要记忆的信息有三部分。第一部分信息是存在每个节点的路由表数据结构由此决定的的转移概率为其中T可以看成节点i的邻域。每一节点的记忆信息和系数的确定需要记忆的信息每一节点的记忆信息和系数的确定需要记忆的信息第二部分需要记忆的信息是每个蚂蚁的记忆表中存储着的自身的历史信息这一部分主要由算法的中的记忆表示蚂蚁已经行走过的节点。第三部分为问题的约束条件。在GBAS中T集合表示满足约束条件的候选集在背包问题的蚁群算法中由判别条件来实现记忆功能。每一节点的记忆信息和系数的确定系数的确定每一节点的记忆信息和系数的确定系数的确定残留信息的相对重要程度和预见值的相对重要程度体现了相关信息痕迹和预见度对蚂蚁决策的相对影响。Dorigo在求解TSP问题时推荐参数的最佳设置为:。蚁群的规模和停止规则蚁群的规模和停止规则一、蚁群大小一般情况下蚁群中蚂蚁的个数不超过TSP图中节点的个数。二、终止条件给定一个外循环的最大数目表明已经有足够的蚂蚁工作当前最优解连续K次相同而停止其中K是一个给定的整数表示算法已经收敛不再需要继续目标值控制规则给定优化问题(目标最小化)的一个下界和一个误差值当算法得到的目标值同下界之差小于给定的误差值时算法终止。信息素的更改信息素的更改信息素的更新分为离线和在线两种方式。离线方式(同步更新方式)的主要思想是在若干只蚂蚁完成n个城市的访问后统一对残留信息进行更新处理。信息素的在线更新(异步更新方式)即蚂蚁每行走一步立即回溯并且更新行走路径上的信息素。信息素的更改信息素的更改离线方式的信息素更新可以进一步分为单蚂蚁离线更新和蚁群离线更新。蚁群离线更新方式是在蚁群中的m只蚂蚁全部完成n城市的访问(第k次蚁群循环)后统一对残留信息进行更新处理。其中为第k次循环后的的信息素的痕迹值。单蚂蚁离线更新是在第s只蚂蚁完成对所有n个城市的访问后进行路径回溯更新行走路径上的信息素同时释放分配给它的资源。更新公式为第s只蚂蚁根据重新计算路由表。信息素的更改信息素的更改TSP问题中蚁群优化算法根据信息素痕迹更新方式不同可以分为不同的算法采用离线方式并且时其中W为t循环中m只蚂蚁所行走的最佳路线或第t只蚂蚁所行走的一条路径。Q为一个常数该算法名为蚁环算法(antcyclealgotithm),特点是行走的路径越短对应保存的信息素的值就越大。信息素的更改信息素的更改GBAS算法是典型的离线信息素更新方式。该算法中蚁群中蚂蚁的先后出行顺序没有相关性但是每次循环需要记忆m只蚂蚁的行走路径以进行比较选择最优路径。相对而言单蚂蚁离线更新方式记忆信息少只需要记忆第s只蚂蚁的路径并通过信息素更新后释放该蚂蚁的所有记录信息。实际上这种方式等价于蚁群离线方式中只有一只蚂蚁。信息素的更改信息素的更改与单蚂蚁离线更新方式相比信息量记忆更小的是信息素在线更新方式即蚂蚁每走一步马上回溯并且更新刚刚走过的路径上的信息素其规则为其中k为蚂蚁行走的第k步。信息素的更改信息素的更改蚁量算法(antquantityalgorithm)的信息素更新为,Q为常量表示i到j的距离这样信息浓度会随城市距离的减小而加大。蚁密算法(antdensityalgorithm)信息素更新为。以上三种算法中蚁环算法效果最好因为他用的是全局信息而其余两种算法用的是局部信息。蚁环离线更新方法很好地保证了残留信息不至于无限积累非最优路径会逐渐随时间推移被忘记。应用应用光网络的智能管理分布式动态选路及波长分配(RWA,RoutingandWavelengthAssignment)是指在实时业务情况下光通路的路由选择和波长分配的优化问题,是实现自动交换光网络(ASON,AutomaticallySwitchedOpticalNetwork)的关键技术之一。研究RWA问题的目的是尽可能减少所需要的波长数和降低光路连接请求的阻塞率。由于RWA问题是NPC问题,文献中大多将RWA问题拆分成路由和波长分配两个子问题分别加以解决。但是,由于RWA问题本身是一个不可分割的整体,把RWA分开考虑必然造成难以得到全局最优解的后果。应用应用同时,分布式的计算方式则克服了传统集中式算法可扩展性差的缺点,更适应现代频繁变化的大型光网络。因此,近年来国内外对RWA并行的分布式算法表现出极大的兴趣,此类算法建立的基础是分层图模型。 用蚁群算法在分层图模型的基础上求解动态RWA问题。基于蚂蚁“信息素表”来完成局部信息的刷新计算。以分布的形式做少量的计算来刷新全局路由选择信息。参考文献:基于蚁群系统的分布式RWA算法研究孙海金,朱 娜,周乃富年 第期光通信研究应用应用蚁群算法用于计算机网络路由参考文献:计算机网络中的组播路由算

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

文档小程序码

使用微信“扫一扫”扫码寻找文档

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/110

蚁群算法设计与分析

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利