《现代优化算法》课件.ppt

1、精选PPT1内 容一、启发式方法概述二、蚁群优化算法精选PPT2背 景n传统实际问题的特点 连续性问题主要以微积分为基础，且问题规模较小n传统的优化方法 追求准确精确解 理论的完美结果漂亮 主要方法：线性与非线性规划、动态规划、多目标规划、整数规划等；排队论、库存论、对策论、决策论等。n传统的评价方法 算法收敛性（从极限角度考虑）收敛速度（线性、超线性、二次收敛等）精选PPT3传统运筹学面临新挑战n现代问题的特点 离散性问题主要以组合优化（针对离散问题，定义见后）理论为基础 不确定性问题随机性数学模型 半结构或非结构化的问题计算机模拟、决 策支持系统 大规模问题并行计算、大型分解理论、近似理论

2、n现代优化方法 追求满意近似解 实用性强解决实际问题n现代优化算法的评价方法 算法复杂性精选PPT4现代优化(启发式)方法种类n禁忌搜索（tabu search）n模拟退火（simulated annealing）n遗传算法（genetic algorithms）n神经网络（neural networks）n蚁群算法（群体（群集）智能，Swarm Intelligence）n拉格朗日松弛算法（lagrangean relaxation）精选PPT51 现代优化计算方法概述n1.1 组合优化问题n1.2 计算复杂性的概念n1.3 启发式算法精选PPT61.1 组合优化问题 1/8 组合优化（co

3、mbinatorial optimization）:解决离散问题的优化问题运筹学分支。通过数学方法的研究去寻找离散事件的最优编排、分组、次序或筛选等，可以涉及信息技术、经济管理、工业工程、交通运输和通信网络等许多方面。数学模型：决策变量有限点集约束函数目标函数,.,0)(.)(minDxxgtsxf精选PPT71.1 组合优化问题 2/8组合优化问题的三参数表示：.|)(min)(,:,0)(,|:),(FxxfxfFxxFxfxgDxxFDfFD最优解，如果可行解（点）目标函数有限点集可行域决策变量定义域精选PPT81.1 组合优化问题 3/8n例1 0-1背包问题（0-1 knapsack

4、 problem）装包？问题：如何以最大价值件物品单位价值，第件物品单位体积，第背包容积.,1:.,1:niicniiabii精选PPT91.1 组合优化问题 4/8.1,0i0i 1(1.3).,1,1,0 (1.2),as.t.(1.1)maxn1ii1iniiiniiDxnixbxxc物品，不装第物品装第，其中决策变量包容量限制总价值数学模型：精选PPT101.1 组合优化问题 5/8n例2 旅行商问题（TSP,traveling salesman problem）管梅谷教授1960年首先提出，国际上称之为中国邮递员问题。问题描述：一商人去n个城市销货，所有城市走一遍再回到起点，使所走路

5、程最短。精选PPT111.1 组合优化问题 6/8ij1ij1min (1.4)s.t.1.1,2,(1.5)i 1.1,2,ijijijnjnid xxinxjn数学模型：总路长只从城市 出来一次,(1.6)1,21,1,2,(1.7)0,1,1,2,.(1.8):ij,s :s 1,iji jsijijijjxssnsnxi jn ijdijx只走入城市 一次在任意城市子集中不形成回路决策变量其中城市 与城市 之间的距离集合 中元素的个数，走城市 和城市0.:,:,ijjiijjiijTSPddi jTSPddi j之间的路径，不走城市 和城市 之间的路径对称距离非对称距离精选PPT121

6、.1 组合优化问题 7/8例3 装箱问题（bin packing）尺寸为1的箱子有若干个，怎样用最少的箱子装下n个尺寸不超过1 的物品，物品集合为：。12,.na aa精选PPT131.1 组合优化问题 8/811min.1,1,2,1,1,2,0,1,1,2,;1,2,B:1,0 .BibbniibiibibBs txina xbBxin bBibxib数 学 模 型：其 中装 下 全 部 物 品 需 要 的 箱 子，第 物 品 装 在 第个 箱 子，第 物 品 不 装 在 第个 箱 子精选PPT141.2 计算复杂性的概念 1/11n评价算法的好坏计算时间的多少、解的偏离程度n例 非对称距

7、离TSP问题的算法实现：所有路径枚举。计算时间：n个城市，固定1个为起终点需要(n-1)!个枚举，设计算机1秒能完成24个城市的枚举，则城市数与计算时间的关系如下表：精选PPT151.2 计算复杂性的概念 2/11随城市增多，计算时间增加很快。到31个城市时，要计算325年。描述算法的好坏计算复杂性讨论计算时间与问题规模之间的关系。以目前二进制计算机中的存储和计算为基础，以理论的形式系统描述，是评估算法性能的基础。精选PPT161.2 计算复杂性的概念 3/11n问题问题（problem）：要回答的一般性提问，通常含有若干个满足一定条件的参数（或自由变量）。可以从两方面描述：（1）对所有参数的

8、一般性描述；（2）答案（或解）必须满足的性质。n实例实例（instance）:给问题的所有参数指定具体值，得到问题的一个实例。这些具体值称为数据数据；这些数据输入计算机所占的空间称为实例的长度实例的长度（size）.精选PPT171.2 计算复杂性的概念 4/11 一类最优化问题是由一些类似的具体问题（实例）组成的，每一个具体问题可表达成二元组（F,C）.F为可行解集合;C是费用函数，是由F到R（实数集）的映像。问题是在F中找到一个点f*，使对F中任意的f，有C(f*)C(f),称f*为这一具体问题的最优解（或全局最优解）.精选PPT181.2 计算复杂性的概念 5/11n算法计算量的度量：算

9、法计算量的度量：加、减、乘、除、比较的总运算次数与实例的计算机计算时的二进制输入数据的大小关系。n正整数正整数x的二进制位数是的二进制位数是:(整数到二进制的转换)2()()log(|1)2xl xl xx记 的输入规模（编码长度）为，则其中2是考虑了1个符号位和1个数据分隔位。精选PPT191.2 计算复杂性的概念 6/11n算法计算量的度量之例算法计算量的度量之例TSP枚举法枚举法21,(1)!(1)!;(1)!(1)!nniinnnnnnnn城市数第一城市为始终点，计算一条路径（,1）长度的基本运算为两两城市间距离的 个数求和,共有条路径,求和运算次数为：枚举所有路径进行次比较可得最优路

10、径,基本计算总次数为总计算量:计算量的统计：计算量的统计：精选PPT201.2 计算复杂性的概念 7/11n实例的输入长度：22,(1)(log12)log12ijijdKLn nKn设 对有则（）（）n实例的输入长度是n的多项式函数n枚举法的基本计算量是n的阶乘函数，随n的增加，比指数函数增加得还快.精选PPT211.2 计算复杂性的概念 8/11AAA,()AC(I)()()()()()Il Ig xC(I)g l ICIO g l Ig x 实例实例规模：，算法基本计算总次数：存在函数和一个常数，使得对于该问题的任意实例都满足（）则二者关系表示为：的性质决定了算法的性能。精选PPT221

11、.2 计算复杂性的概念 9/11定义定义 多项式算法多项式算法给定问题P，算法A，对一个实例I，存在多项式函数g(x)，使（XX）成立，称算法算法A对实例对实例I是是多项式算法多项式算法；若存在多项式函数g(x)，使（XX）对问题P的任意实例I都成立，称算法算法A为解决该问题为解决该问题P的多项的多项式算法式算法.当当g(x)为指数函数时，称为指数函数时，称A为为P的指数时间算法。的指数时间算法。精选PPT231.2 计算复杂性的概念 10/11n利用复杂性分析对组合优化问题归类。n定义多项式问题多项式问题 给定一个组合优化问题，若存在一个多项式算法，称该问题为多项式时间可解问题，或简称多项式

12、问题多项式问题(或或P问题问题).所有多项式问题的集合记为P.n例：线性规划是否为多项式问题？精选PPT241.2 计算复杂性参考书 11/11n计算复杂性计算复杂性,作者：Christos，Papadimitriou清华大学出版社，2004年9月第1版n计算复杂性导论，计算复杂性导论，作者：堵丁柱等，高等教育出版社，2002年8月第1版精选PPT251.3 启发式算法_定义 1/6n启发式算法（heuristic algorithm）n定义定义1.基于直观或经验直观或经验构造的算法，在可接受的花费（时间、空间）下，给出待解组合优化问题的每个实例的一个可行解可行解，该可行解与最优解偏差事先不一

13、定可以预计.n定义定义2.启发式算法是一种技术，在可接受的计算费用内寻找最好解，但不保证该解的可行性与最优性，无法描述该解与最优解的近似程度。n特点（与传统优化方法不同）：特点（与传统优化方法不同）：凭直观和经验给出凭直观和经验给出算法；不考虑所得解与最优解的偏离程度算法；不考虑所得解与最优解的偏离程度.精选PPT261.3 启发式算法_优点 2/6 优点：优点：（1）有可能比简化数学模型解的误差小；（2）对有些难题，计算时间可接受；（3）可用于某些最优化算法（如分支定界算 法）之中的估界；（4）直观易行；（5）速度较快；（6）程序简单，易修改。精选PPT271.3 启发式算法_不足 3/6不

14、足：不足：（1）不能保证求得全局最优解；（2）解的精度不稳定，有时好有时坏；（3）算法设计与问题、设计者经验、技术 有关，缺乏规律性；（4）不同算法之间难以比较。精选PPT281.3 启发式算法_分类 4/6（1）一步算法）一步算法（2）改进算法（迭代算法）改进算法（迭代算法）(3)数学规划算法数学规划算法(4)解空间松弛法解空间松弛法 精选PPT291.3 启发式算法_分类 5/6（5）现代优化算法：）现代优化算法：80年代初兴起n禁忌搜索（tabu search）n模拟退火（simulated annealing）n遗传算法（genetic algorithms）n神经网络（neural

15、networks）n蚂蚁算法（Ant Algorithm，群体（群集）智能，Swarm Intelligence）（6 6）其他算法：）其他算法：多种启发式算法的集成.精选PPT301.3 启发式算法_性能分析 6/6（1）最坏情形分析（worst case analysis）利用最坏实例分析计算复杂性、解的效果。(2）概率分析（probability analysis）用最坏情况分析，会因一个最坏实例影响总体评价.在实例数据服从一定概率分布情形下，研究算法复杂性和解的效果.(3)大规模计算分析 通过大量实例计算，评价算法效果.n注意数据的随机性和代表性.精选PPT312 蚁群优化算法n蚁群优

16、化算法概述n蚁群优化算法概念n算法模型和收敛性分析n算法实现的技术问题n应用n参考资料精选PPT322.1 蚁群优化算法概述n2.1.1 起源n2.1.2 应用领域n2.1.3 研究背景n2.1.4 研究现状n2.1.5 应用现状精选PPT332.1.1 蚁群优化算法起源 20世纪50年代中期创立了仿生学，人们从生物进化的机理中受到启发。提出了许多用以解决复杂优化问题的新方法，如进化规划、进化策略、遗传算法等，这些算法成功地解决了一些实际问题。20世纪90年代意大利学者MDorigo，VManiezzo，AColorni等从生物进化的机制中受到启发，通过模拟自然界蚂蚁搜索路径的行为，提出来一种

17、新型的模拟进化算法 蚁群算法，是群智能理论研究领域的一种主要算法。用该方法求解TSP问题、分配问题、job-shop调度问题，取得了较好的试验结果虽然研究时间不长，但是现在的研究显示出，蚁群算法在求解复杂优化问题（特别是离散优化问题）方面有一定优势，表明它是一种有发展前景的算法精选PPT342.1.2 蚁群优化算法应用领域 这种方法能够被用于解决大多数优化问题或者能够转化为优化求解的问题。现在其应用领域已扩展到多目标优化、数据分类、数据聚类、模式识别、电信QoS管理、生物系统建模、流程规划、信号处理、机器人控制、决策支持以及仿真和系统辩识等方面，群智能理论和方法为解决这类应用问题提供了新的途径

18、。精选PPT352.1.3 蚁群优化算法研究背景 1/3 群智能理论研究领域有两种主要的算法：蚁群算法(Ant Colony Optimization,ACO)和微粒群算法（Particle Swarm Optimization,PSO）。前者是对蚂蚁群落食物采集过程的模拟，已成功应用于许多离散优化问题。微粒群算法也是起源于对简单社会系统的模拟，最初是模拟鸟群觅食的过程，但后来发现它是一种很好的优化工具。精选PPT362.1.3 蚁群优化算法研究背景 2/3与大多数基于梯度的应用优化算法不同，群智能依靠的是概率搜索算法。虽然概率搜索算法通常要采用较多的评价函数，但是与梯度方法及传统的演化算法相

19、比，其优点还是显著的，主要表现在以下几个方面：1 无集中控制约束，不会因个别个体的故障影响整个问题 的求解，确保了系统具备更强的鲁棒性 2 以非直接的信息交流方式确保了系统的扩展性 3 并行分布式算法模型，可充分利用多处理器 4 对问题定义的连续性无特殊要求 5 算法实现简单 精选PPT372.1.3 蚁群优化算法研究背景 3/3 群智能方法易于实现，算法中仅涉及各种基本的数学操作，其数据处理过程对CPU和内存的要求也不高。而且，这种方法只需目标函数的输出值，而无需其梯度信息。已完成的群智能理论和应用方法研究证明群智能方法是一种能够有效解决大多数全局优化问题的新方法。更为重要是，群智能潜在的并

20、行性和分布式特点为处理大量的以数据库形式存在的数据提供了技术保证。无论是从理论研究还是应用研究的角度分析，群智能理论及其应用研究都是具有重要学术意义和现实价值的。精选PPT382.1.4 蚁群优化算法研究现状 1/7 90年代Dorigo最早提出了蚁群优化算法-蚂蚁系统（Ant System,AS）并将其应用于解决计算机算法学中经典的旅行商问题（TSP）。从蚂蚁系统开始，基本的蚁群算法得到了不断的发展和完善，并在TSP以及许多实际优化问题求解中进一步得到了验证。这些AS改进版本的一个共同点就是增强了蚂蚁搜索过程中对最优解的探索能力，它们之间的差异仅在于搜索控制策略方面。而且，取得了最佳结果的A

21、CO是通过引入局部搜索算法实现的，这实际上是一些结合了标准局域搜索算法的混合型概率搜索算法，有利于提高蚁群各级系统在优化问题中的求解质量。精选PPT392.1.4蚁群优化算法研究现状 2/7 最初提出的AS有三种版本：Ant-density、Ant-quantity和Ant-cycle。在Ant-density和Ant-quantity中蚂蚁在两个位置节点间每移动一次后即更新信息素，而在Ant-cycle中当所有的蚂蚁都完成了自己的行程后才对信息素进行更新，而且每个蚂蚁所释放的信息素被表达为反映相应行程质量的函数。通过与其它各种通用的启发式算法相比，在不大于75城市的TSP中，这三种基本算法的

22、求解能力还是比较理想的，但是当问题规模扩展时，AS的解题能力大幅度下降。因此，其后的ACO研究工作主要都集中于AS性能的改进方面。较早的一种改进方法是精英策略(Elitist Strategy)，其思想是在算法开始后即对所有已发现的最好路径给予额外的增强，并将随后与之对应的行程记为Tgb(全局最优行程)，当进行信息素更新时，对这些行程予以加权，同时将经过这些行程的蚂蚁记为“精英”，从而增大较好行程的选择机会。这种改进型算法能够以更快的速度获得更好的解。但是若选择的精英过多则算法会由于较早的收敛于局部次优解而导致搜索的过早停滞。精选PPT402.1.4蚁群优化算法研究现状 3/7 为了进一步克服

23、AS中暴露出的问题，提出了蚁群系统(Ant Colony System,ACS)。该系统的提出是以Ant-Q算法为基础的。Ant-Q将蚂蚁算法和一种增强型学习算法Q-learning有机的结合了起来。ACS与AS之间存在三方面的主要差异：首先，ACS采用了更为大胆的行为选择规则；其次，只增强属于全局最优解的路径上的信息素。其中，01是信息素挥发参数，是从寻路开始到当前为止全局最优的路径长度。精选PPT412.1.4蚁群优化算法研究现状 4/7 再次，还引入了负反馈机制，每当一只蚂蚁由一个节点移动到另一个节点时，该路径上的信息素都按照如下公式被相应的消除一部分，从而实现一种信息素的局部调整，以减

24、小已选择过的路径再次被选择的概率。精选PPT422.1.4蚁群优化算法研究现状 5/7 在对AS进行直接完善的方法中，MAX-MIN Ant System是一个典型代表。该算法修改了AS的信息素更新方式，每次迭代之后只有一只蚂蚁能够进行信息素的更新以获取更好的解。为了避免搜索停滞，路径上的信息素浓度被限制在MAX，MIN 范围内，另外，信息素的初始值被设为其取值上限，这样有助于增加算法初始阶段的搜索能力。精选PPT432.1.4蚁群优化算法研究现状 6/7 另一种对AS改进的算法是Rank-based Version AS。与“精英策略”相似，在此算法中总是更新更好进程上的信息素，选择的标准是

25、其行程长度 决定的排序，且每个蚂蚁放置信息素的强度通过下式中的排序加权处理确定，其中，为每次迭代后放置信息素的蚂蚁总数。精选PPT442.1.4蚁群优化算法研究现状 7/7 这种算法求解TSP的能力与AS、精英策略AS、遗传算法和模拟退火算法进行了比较。在大型TSP问题中（最多包含132座城市），基于AS的算法都显示出了优于GA和SA的特性。而且在Rank-based AS和精英策略AS均优于基本AS的同时，前者还获得了比精英策略AS更好的解。精选PPT452.1.5 蚁群优化算法应用现状 1/5 随着群智能理论和应用算法研究的不断发展，研究者已尝试着将其用于各种工程优化问题，并取得了意想不到

26、的收获。多种研究表明，群智能在离散求解空间和连续求解空间中均表现出良好的搜索效果，并在组合优化问题中表现突出。蚁群优化算法并不是旅行商问题的最佳解决方法，但是它却为解决组合优化问题提供了新思路，并很快被应用到其它组合优化问题中。比较典型的应用研究包括：网络路由优化、数据挖掘以及一些经典的组合优化问题。精选PPT462.1.5 蚁群优化算法应用现状 2/5 蚁群算法在电信路由优化中已取得了一定的应用成果。HP公司和英国电信公司在90年代中后期都开展了这方面的研究，设计了蚁群路由算法（Ant Colony Routing,ACR）。每只蚂蚁就像蚁群优化算法中一样，根据它在网络上的经验与性能，动态更

27、新路由表项。如果一只蚂蚁因为经过了网络中堵塞的路由而导致了比较大的延迟，那么就对该表项做较大的增强。同时根据信息素挥发机制实现系统的信息更新，从而抛弃过期的路由信息。这样，在当前最优路由出现拥堵现象时，ACR算法就能迅速的搜寻另一条可替代的最优路径，从而提高网络的均衡性、负荷量和利用率。目前这方面的应用研究仍在升温，因为通信网络的分布式信息结构、非稳定随机动态特性以及网络状态的异步演化与ACO的算法本质和特性非常相似。精选PPT472.1.5 蚁群优化算法应用现状 3/5 基于群智能的聚类算法起源于对蚁群蚁卵的分类研究。Lumer和Faieta将Deneubourg提出将蚁巢分类模型应用于数据

28、聚类分析。其基本思想是将待聚类数据随机地散布到一个二维平面内，然后将虚拟蚂蚁分布到这个空间内，并以随机方式移动，当一只蚂蚁遇到一个待聚类数据时即将之拾起并继续随机运动，若运动路径附近的数据与背负的数据相似性高于设置的标准则将其放置在该位置，然后继续移动，重复上述数据搬运过程。按照这样的方法可实现对相似数据的聚类。精选PPT482.1.5 蚁群优化算法应用现状 4/5 ACO还在许多经典组合优化问题中获得了成功的应用，如二次规划问题（QAP）、机器人路径规划、作业流程规划、图着色（Graph Coloring）等问题。经过多年的发展，ACO已成为能够有效解决实际二次规划问题的几种重要算法之一。A

29、S在作业流程计划（Job-shop Scheduling）问题中的应用实例已经出现，这说明了AS在此领域的应用潜力。利用MAX-MIN AS解决PAQ也取得了比较理想的效果，并通过实验中的计算数据证明采用该方法处理PAQ比较早的SA算法更好，且与禁忌搜索算法性能相当。利用ACO实现对生产流程和特料管理的综合优化，并通过与遗传、模拟退火和禁忌搜索算法的比较证明了ACO的工程应用价值。精选PPT492.1.5 蚁群优化算法应用现状 5/5 许多研究者将ACO用于了武器攻击目标分配和优化问题、车辆运行路径规划、区域性无线电频率自动分配、Bayesian networks的训练和集合覆盖等应用优化问题

30、。Costa和Herz还提出了一种AS在规划问题方面的扩展应用图着色问题，并取得了可与其他启发式算法相比的效果。精选PPT502.2 蚁群优化算法概念2.2.1 蚁群算法原理2.2.2 简化的蚂蚁寻食过程2.2.3 自然蚁群与人工蚁群算法2.2.4 蚁群算法与TSP问题2.2.5 初始的蚁群优化算法基于图的蚁群系统（GBAS）2.2.6 一般蚁群算法的框架精选PPT512.2.1 蚁群算法原理 蚁群算法是对自然界蚂蚁的寻径方式进行模似而得出的一种仿生算法。蚂蚁在运动过程中，能够在它所经过的路径上留下一种称之为外激素(pheromone)的物质进行信息传递，而且蚂蚁在运动过程中能够感知这种物质，

31、并以此指导自己的运动方向，因此由大量蚂蚁组成的蚁群集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。为了说明蚁群算法的原理，先简要介绍一下蚂蚁搜寻食物的具体过程。在蚁群寻找食物时，它们总能找到一条从食物到巢穴之间的最优路径。这是因为蚂蚁在寻找路径时会在路径上释放出一种特殊的信息素。当它们碰到一个还没有走过的路口时就随机地挑选一条路径前行。与此同时释放出与路径长度有关的信息素。路径越长，释放的激索浓度越低.当后来的蚂蚁再次碰到这个路口的时候选择激素浓度较高路径概率就会相对较大。这样形成一个正反馈。最优路径上的激索浓度越来越大而其它的路径上激素浓度却会随

32、着时间的流逝而消减。最终整个蚁群会找出最优路径。精选PPT522.2.2 简化的蚂蚁寻食过程 1/3蚂蚁从A点出发，速度相同，食物在D点，可能随机选择路线ABD或ACD。假设初始时每条分配路线一只蚂蚁，每个时间单位行走一步，本图为经过9个时间单位时的情形：走ABD的蚂蚁到达终点，而走ACD的蚂蚁刚好走到C点，为一半路程。精选PPT532.2.2 简化的蚂蚁寻食过程 2/3本图为从开始算起，经过18个时间单位时的情形：走ABD的蚂蚁到达终点后得到食物又返回了起点A，而走ACD的蚂蚁刚好走到D点。精选PPT542.2.2 简化的蚂蚁寻食过程 3/3 假设蚂蚁每经过一处所留下的信息素为一个单位，则经

33、过36个时间单位后，所有开始一起出发的蚂蚁都经过不同路径从D点取得了食物，此时ABD的路线往返了2趟，每一处的信息素为4个单位，而 ACD的路线往返了一趟，每一处的信息素为2个单位，其比值为2：1。寻找食物的过程继续进行，则按信息素的指导，蚁群在ABD路线上增派一只蚂蚁（共2只），而ACD路线上仍然为一只蚂蚁。再经过36个时间单位后，两条线路上的信息素单位积累为12和4，比值为3：1。若按以上规则继续，蚁群在ABD路线上再增派一只蚂蚁（共3只），而ACD路线上仍然为一只蚂蚁。再经过36个时间单位后，两条线路上的信息素单位积累为24和6，比值为4：1。若继续进行，则按信息素的指导，最终所有的蚂蚁

34、会放弃ACD路线，而都选择ABD路线。这也就是前面所提到的正反馈效应。精选PPT552.2.3 自然蚁群与人工蚁群算法 基于以上蚁群寻找食物时的最优路径选择问题，可以构造人工蚁群，来解决最优化问题，如TSP问题。人工蚁群中把具有简单功能的工作单元看作蚂蚁。二者的相似之处在于都是优先选择信息素浓度大的路径。较短路径的信息素浓度高，所以能够最终被所有蚂蚁选择，也就是最终的优化结果。两者的区别在于人工蚁群有一定的记忆能力，能够记忆已经访问过的节点。同时，人工蚁群再选择下一条路径的时候是按一定算法规律有意识地寻找最短路径，而不是盲目的。例如在TSP问题中，可以预先知道当前城市到下一个目的地的距离。精选

35、PPT562.2.4 蚁群算法与TSP问题 1/3TSP问题表示为一个N个城市的有向图G=（N，A），其中城市之间距离目标函数为 ，其中 为城市1,2，n的一个排列，。,|j),(iA n1,2,.,NNjinnijd)(nliilldwf11)(),(21niiiw11iin精选PPT572.2.4 蚁群算法与TSP问题 2/3 TSP问题的人工蚁群算法中，假设m只蚂蚁在图的相邻节点间移动，从而协作异步地得到问题的解。每只蚂蚁的一步转移概率由图中的每条边上的两类参数决定：1 信息素值 也称信息素痕迹。2 可见度，即先验值。信息素的更新方式有2种，一是挥发，也就是所有路径上的信息素以一定的比率

36、进行减少，模拟自然蚁群的信息素随时间挥发的过程；二是增强，给评价值“好”(有蚂蚁走过)的边增加信息素。精选PPT582.2.4 蚁群算法与TSP问题 3/3 蚂蚁向下一个目标的运动是通过一个随机原则来实现的，也就是运用当前所在节点存储的信息，计算出下一步可达节点的概率，并按此概率实现一步移动，逐此往复，越来越接近最优解。蚂蚁在寻找过程中，或者找到一个解后，会评估该解或解的一部分的优化程度，并把评价信息保存在相关连接的信息素中。精选PPT592.2.5 初始的蚁群优化算法基于图的蚁群系统（GBAS）1/12初始的蚁群算法是基于图的蚁群算法，graph-based ant system,简称为GB

37、AS，是由Gutjahr W J在2000年的Future Generation Computing Systems提出的，课本的参考文献2。算法步骤如下：STEP 0 对n个城市的TSP问题，城市间的距离矩阵为 ，给TSP图中的每一条弧 赋信息素初值 ，假设m只蚂蚁在工作，所有蚂蚁都从同一城市 出发。当前最好解是。,|j),(iA n1,2,.,NNjinnijd)(),(ji|1)0(Aij0i),2,1(nw精选PPT602.2.5 初始的蚁群优化算法基于图的蚁群系统（GBAS）2/12STEP 1 （外循环）如果满足算法的停止规则，则停止计算并输出计算得到的最好解。否则使蚂蚁s从起点

38、出发，用 表示蚂蚁s行走的城市集合，初始 为空集，。STEP 2 (内循环)按蚂蚁 的顺序分别计算。当蚂蚁在城市i，若 完成第s只蚂蚁的计算。否则，若，则以概率，到达j，；若则到达重复STEP 2。0i)(sL)(sLms 11sm()|(,),()L sNli lA lL s 或0()|(,),()L sNTli lA lL si 且(1),(1)ijijijl TkpjTk0,ijpjT()(),:L sL sjij0()|(,),()L sNTli lA lL si 且000,()(),:;i L sL siii精选PPT612.2.5 初始的蚁群优化算法基于图的蚁群系统（GBAS）3/

39、12STRP 3 对 ，若 ，按 中城市的顺序计算路径程度；若 ，路径长度置为一个无穷大值（即不可达）。比较m只蚂蚁中的路径长度，记走最短路径的蚂蚁为t。若 ，则 。用如下公式对W路径上的信息素痕迹加强，对其他路径上的信息素进行挥发。得到新的 ，重复步骤STEP 1。1sm()L sN()L s()L sN()()f L tf L W()WL t(),:1ijk kk111()(1)(1)(,)()(1)(1)(,)kijkijijkijkki jWWkki jW为上的一条弧不是上的一条弧精选PPT622.2.5 初始的蚁群优化算法基于图的蚁群系统（GBAS）4/12在STEP 3 中，挥发因

40、子 对于一个固定的 ，满足并且 经过k次挥发，非最优路径的信息素逐渐减少至消失。kln1,ln(1)kkkKk 1K 1kk 精选PPT632.2.5初始的蚁群优化算法基于图的蚁群系统（GBAS）5/12 以上算法中，在蚂蚁的搜寻过程中，以信息素的概率分布来决定从城市i到城市j的转移。算法中包括信息素更新的过程 1 信息素挥发（evaporation）信息素痕迹的挥发过程是每个连接上的信息素痕迹的浓度自动逐渐减弱的过程，由 表示，这个挥发过程主要用于避免算法过快地向局部最优区域集中，有助于搜索区域的扩展。2 信息素增强（reinforcement）增强过程是蚁群优化算法中可选的部分，称为离线更

41、新方式（还有在线更新方式）。这种方式可以实现由单个蚂蚁无法实现的集中行动。也就是说，增强过程体现在观察蚁群（m只蚂蚁）中每只蚂蚁所找到的路径，并选择其中最优路径上的弧进行信息素的增强，挥发过程是所有弧都进行的，不于蚂蚁数量相关。这种增强过程中进行的信息素更新称为离线的信息素更新。在STEP 3中，蚁群永远记忆到目前为止的最优解。(1)()kijk 精选PPT64图的蚁群系统（GBAS）6/12可以验证，下式满足：即 是一个随机矩阵。()k(,)()1,0iji jAkk 四个城市的非对称TSP问题，距离矩阵和城市图示如下：010.511011()1.55011110ijDd精选PPT652.2

42、.5 初始的蚁群优化算法基于图的蚁群系统（GBAS）7/12假设共4只蚂蚁，所有蚂蚁都从城市A出发，挥发因子 。此时，观察GBAS的计算过程。矩阵共有12条弧，初始信息素记忆矩阵为：1,1,2,32kk01121121121120112112(0)(0)11211201121121121120ij精选PPT662.2.5 初始的蚁群优化算法基于图的蚁群系统（GBAS）8/12执行GBAS算法的步骤2，假设蚂蚁的行走路线分别为：当前最优解为，这个解是截止到当前的最优解，碰巧是实际最优解1:,(1)4;2:,(2)3.5;3:,(3)8;4:,(4)4.5;WABCDA f WWACDBA f W

43、WADCBA f WWABDCA f W第一只第二只第三只第四只精选PPT672.2.5 初始的蚁群优化算法基于图的蚁群系统（GBAS）9/12按算法步骤3的信息素更新规则，得到更新矩阵这是第一次外循环结束的状态。01 241 61 241 601 241 24(1)(1)1 241 1201 61 241 61 240ij精选PPT682.2.5 初始的蚁群优化算法基于图的蚁群系统（GBAS）10/12重复外循环，由于上一次得到的W2已经是全局最优解，因此按算法步骤3的信息素更新规则，无论蚂蚁如何行走，都只是对W2路线上的城市信息素进行增强，其他的城市信息素进行挥发。得到更新矩阵这是第一次外

44、循环结束的状态。01 485 241 485 2401 481 48(2)(2)1 481 4805 241 485 241 480ij精选PPT692.2.5 初始的蚁群优化算法基于图的蚁群系统（GBAS）11/12重复外循环，由于W2全局最优解，GBAS只记录第一个最优解，因此一但得到了全局最优解，信息素的更新将不再依赖于以群的行走路线，而只是不断增强最优路线的信息素，同时进行挥发。第三次外循环后得到的信息素矩阵为：01 9611 481 9611 4801 961 96(3)(3)1 961 96011 481 9611 481 960ij精选PPT702.2.5 初始的蚁群优化算法基于

45、图的蚁群系统（GBAS）12/12 蚂蚁以一定的概率从城市i到城市j进行转移，信息素的更新在STEP 3 完成，并随K而变化。假设第K次外循环后得到信息素矩阵 ，得到当前最优解 。第K次循环前的信息素和最优解为 ，经过第K次外循环后，得到 。由于蚂蚁的一步转移概率是随机的，从 到 也是随机的，是一个马尔可夫过程。()()|(,)ijkki jA()W k(1),(1)kW k(),()k W k(1),(1)kW k(),()k W k精选PPT712.2.6 一般蚁群算法的框架一般蚁群算法的框架和GBAS基本相同，有三个组成部分：蚁群的活动；信息素的挥发；信息素的增强；主要体现在前面的算法中

46、步骤2和步骤3中的转移概率公式和信息素更新公式。精选PPT722.3 蚁群优化算法算法模型和收敛性分析2.3.0 马氏过程的收敛定义2.3.1 GBAS算法的收敛性分析2.3.2其他算法及收敛性分析精选PPT732.3.0 马氏过程的收敛定义 蚁群优化算法的每步迭代对应随机变量 其中 为信息素痕迹；为n城市的一个排列，最多有 个状态。第s只蚂蚁在第k轮转移只由 决定，这个蚂蚁行走的路径和 一起，共同决定了 ，再通过信息素的更新原则可以进一步得到 。的变化仅由 决定，而与先前的状态无关，这是一个典型的马尔可夫过程。定义定义：若一个马尔可夫过程 ，对任意给定的 满足 则称马尔可夫过程 依概率1收敛

47、到 。(),(),0,1,.,kXk W kk()k()W k!n(1)k(1)W k()W k()k1kXkX,0,1,.kXk 0*X,0,1,2,.kXk*lim1kkp XX精选PPT742.3.1 GBAS算法的收敛性分析 1/8 定理 满足指定条件的马尔可夫过程 依概率1收敛到 ,其中 为一条最优路径,定义为:证明分析:蚁群算法中,一但达到全局最优,由 只记录第一个最优解.证明分三部分:n 证明以概率1达到一个最优路径n 证明(1)上式成立n 证明以概率1收敛到一个最优路径(),(),0,1,.,kXk W kk*(,)XW*W*1,(,)0(1)ijWi jW为的一条弧其他f(L

48、(t)f(w)精选PPT752.3.1 GBAS算法的收敛性分析 2/8证明以概率1到达一个最优路径 对于最优路径 ,令 为蚁群中的一个蚂蚁在第k次外循环后第一次走到最优路径 的事件.表示仅第k次外循环没有走到 的事件,但前k-1次可能走到过这条最优路径.永远不会被走到的事件为 ,其概率为:*WkF*WkF*W*W12FF12*1*1()|)(2kkP FFPkWPkW*第 次循环蚁群没有走到第ik次循环蚁群没有走到W前 次循环蚁群没有走到精选PPT762.3.1 GBAS算法的收敛性分析 3/8 任意给定的固定弧(i,j),在第k次循环后,其信息素值的下界可以计算出.111111111()(

49、1)(1)ln(1)(1)ln(1)ln(1)(1)ln1(1)ln(1)(3)lni jkijllKklijllKKlijlKlijlkllKkKk 精选PPT772.3.1 GBAS算法的收敛性分析 4/8令,任何一个固定节点最多有(n-1)后续节点,并且其弧上的信息素值都小于1或者等于1.得:蚁群中的一只蚂蚁在第 次循环走到路径 W*的概率为一个蚁群中至少有一只蚂蚁，因此这是一个蚁群到达最优路径的一个下界.上式右侧与k无关,11(1)ln(1)KlijlK,(1)lnijpkKnkk(kK)*(,)*()()(4)1)lnWiji jWp knk精选PPT782.3.1 GBAS算法的收

50、敛性分析 5/8 则取对数有从而得到*(,*)1()1()(1)lnwiji j WPkWpknk 前 次循环蚁群没有走到*1*(1()(1)ln(2)(5)kwk KPkWnk前 次循环蚁群没有走到*ln(1()()(1)ln(1)lnwwk Kk Knknk12()1P FF精选PPT792.3.1 GBAS算法的收敛性分析 6/8 证明右式成立 随机过程 以概率1达到一条最优路径.当某条最优路径Z在第k次循环被首次走到后,在第k+1轮循环按信息素的更新原则,可以用归纳法证明,对于任意*1,(,)0ijWi jW为的一条弧其他(i,j)W*,r=1,2,.111011()(1)()(1)*