《现代优化算法》ppt课件-文库吧

【正文】

算法 _分类 4/6 （ 1）一步算法 （ 2）改进算法（迭代算法） (3) 数学规划算法 (4) 解空间松弛法 29 启发式算法 _分类 5/6 （ 5）现代优化算法： 80年代初兴起  禁忌搜索（ tabu search）  模拟退火（ simulated annealing）  遗传算法（ geic algorithms）  神经网络（ neural works）  蚂蚁算法（ Ant Algorithm， 群体（群集）智能， Swarm Intelligence） （ 6）其他算法： 多种启发式算法的集成 . 30 启发式算法 _性能分析 6/6 （ 1）最坏情形分析 （ worst case analysis） 利用最坏实例分析计算复杂性、解的效果。 (2）概率分析 （ probability analysis） 用最坏情况分析，会因一个最坏实例影响总体评价 . 在实例数据服从一定概率分布情形下，研究算法复杂性和解的效果 . (3)大规模计算分析 通过大量实例计算，评价算法效果 .  注意数据的随机性和代表性 . 31 2 蚁群优化算法 1. 蚁群优化算法概述 2. 蚁群优化算法概念 3. 算法模型和收敛性分析 4. 算法实现的技术问题 5. 应用 6. 参考资料 32 蚁群优化算法概述  起源  应用领域  研究背景  研究现状  应用现状 33 蚁群优化算法起源 20世纪 50年代中期创立了仿生学，人们从生物进化的机理中受到启发。提出了许多用以解决复杂优化问题的新方法，如进化规划、进化策略、遗传算法等，这些算法成功地解决了一些实际问题。 20世纪 90年代意大利学者 M． Dorigo， V． Maniezzo，A． Colorni等从生物进化的机制中受到启发，通过模拟自然界蚂蚁搜索路径的行为，提出来一种新型的模拟进化算法 —— 蚁群算法，是群智能理论研究领域的一种主要算法。用该方法求解 TSP问题、分配问题、 jobshop调度问题，取得了较好的试验结果．虽然研究时间不长，但是现在的研究显示出，蚁群算法在求解复杂优化问题（特别是离散优化问题）方面有一定优势，表明它是一种有发展前景的算法． 34 蚁群优化算法应用领域 这种方法能够被用于解决大多数优化问题或者能够转化为优化求解的问题。现在其应用领域已扩展到多目标优化、数据分类、数据聚类、模式识别、电信 QoS管理、生物系统建模、流程规划、信号处理、机器人控制、决策支持以及仿真和系统辩识等方面，群智能理论和方法为解决这类应用问题提供了新的途径 。 35 蚁群优化算法研究背景 1/3 群智能理论研究领域有两种主要的算法：蚁群算法 (Ant Colony Optimization, ACO)和微粒群算法（ Particle Swarm Optimization, PSO）。前者是对蚂蚁群落食物采集过程的模拟，已成功应用于许多离散优化问题。微粒群算法也是起源于对简单社会系统的模拟，最初是模拟鸟群觅食的过程，但后来发现它是一种很好的优化工具。 36 蚁群优化算法研究背景 2/3 与大多数基于梯度的应用优化算法不同，群智能依靠的是 概率搜索算法。虽然概率搜索算法通常要采用较多的评价 函数，但是与梯度方法及传统的演化算法相比，其优点还 是显著的 ，主要表现在以下几个方面： 1 无集中控制约束，不会因个别个体的故障影响整个问题 的求解，确保了系统具备更强的鲁棒性 2 以非直接的信息交流方式确保了系统的扩展性 3 并行分布式算法模型，可充分利用多处理器 4 对问题定义的连续性无特殊要求 5 算法实现简单 37 蚁群优化算法研究背景 3/3 群智能方法易于实现，算法中仅涉及各种基本的数学操作，其数据处理过程对 CPU和内存的要求也不高。而且，这种方法只需目标函数的输出值，而无需其梯度信息。已完成的群智能理论和应用方法研究证明群智能方法是一种能够有效解决大多数全局优化问题的新方法。更为重要是，群智能潜在的并行性和分布式特点为处理大量的以数据库形式存在的数据提供了技术保证。无论是从理论研究还是应用研究的角度分析，群智能理论及其应用研究都是具有重要学术意义和现实价值的。 38 蚁群优化算法研究现状 1/7 90年代 Dorigo最早提出了蚁群优化算法 蚂蚁系统（ Ant System, AS）并将其应用于解决计算机算法学中经典的旅行商问题（ TSP）。从蚂蚁系统开始，基本的蚁群算法得到了不断的发展和完善，并在 TSP以及许多实际优化问题求解中进一步得到了验证。这些 AS改进版本的一个共同点就是增强了蚂蚁搜索过程中对最优解的探索能力，它们之间的差异仅在于搜索控制策略方面。而且，取得了最佳结果的 ACO是通过引入局部搜索算法实现的，这实际上是一些结合了标准局域搜索算法的混合型概率搜索算法，有利于提高蚁群各级系统在优化问题中的求解质量。 39 2/7 最初提出的 AS有三种版本： Antdensity、 Antquantity和 Antcycle。在 Antdensity和 Antquantity中蚂蚁在两个位置节点间每移动一次后即更新信息素，而在 Antcycle中当所有的蚂蚁都完成了自己的行程后才对信息素进行更新，而且每个蚂蚁所释放的信息素被表达为反映相应行程质量的函数。通过与其它各种通用的启发式算法相比，在不大于 75城市的 TSP中，这三种基本算法的求解能力还是比较理想的，但是当问题规模扩展时， AS的解题能力大幅度下降。 因此，其后的 ACO研究工作主要都集中于 AS性能的改进方面。较早的一种改进方法是精英策略 (Elitist Strategy)，其思想是在算法开始后即对所有已发现的最好路径给予额外的增强，并将随后与之对应的行程记为 Tgb(全局最优行程 )，当进行信息素更新时，对这些行程予以加权，同时将经过这些行程的蚂蚁记为 “ 精英 ” ，从而增大较好行程的选择机会。这种改进型算法能够以更快的速度获得更好的解。但是若选择的精英过多则算法会由于较早的收敛于局部次优解而导致搜索的过早停滞。 40 3/7 为了进一步克服 AS中暴露出的问题，提出了蚁群系统 (Ant Colony System, ACS)。该系统的提出是以 AntQ算法为基础的。AntQ将蚂蚁算法和一种增强型学习算法 Qlearning有机的结合了起来。 ACS与 AS之间存在三方面的主要差异：首先， ACS采用了更为大胆的行为选择规则；其次，只增强属于全局最优解的路径上的信息素。其中， 0ρ1是信息素挥发参数， 是从寻路开始到当前为止全局最优的路径长度。 41 4/7 再次，还引入了负反馈机制，每当一只蚂蚁由一个节点移动到另一个节点时，该路径上的信息素都按照如下公式被相应的消除一部分，从而实现一种信息素的局部调整，以减小已选择过的路径再次被选择的概率。 42 5/7 在对 AS进行直接完善的方法中， MAXMIN Ant System是一个典型代表。该算法修改了 AS的信息素更新方式，每次迭代之后只有一只蚂蚁能够进行信息素的更新以获取更好的解。为了避免搜索停滞，路径上的信息素浓度被限制在 [MAX， MIN ]范围内，另外，信息素的初始值被设为其取值上限，这样有助于增加算法初始阶段的搜索能力。 43 6/7 另一种对 AS改进的算法是 Rankbased Version AS。与“ 精英策略 ” 相似，在此算法中总是更新更好进程上的信息素，选择的标准是其行程长度 决定的排序，且每个蚂蚁放置信息素的强度通过下式中的排序加权处理确定，其中，ｗ为每次迭代后放置信息素的蚂蚁总数。 44 7/7 这种算法求解 TSP的能力与 AS、精英策略 AS、遗传算法和模拟退火算法进行了比较。在大型TSP问题中（最多包含 132座城市），基于 AS的算法都显示出了优于 GA和 SA的特性。而且在 Rankbased AS和精英策略 AS均优于基本 AS的同时，前者还获得了比精英策略 AS更好的解。 45 蚁群优化算法应用现状 1/5 随着群智能理论和应用算法研究的不断发展，研究者已尝试着将其用于各种工程优化问题，并取得了意想不到的收获。多种研究表明，群智能在离散求解空间和连续求解空间中均表现出良好的搜索效果，并在组合优化问题中表现突出。 蚁群优化算法并不是旅行商问题的最佳解决方法，但是它却为解决组合优化问题提供了新思路，并很快被应用到其它组合优化问题中。比较典型的应用研究包括：网络路由优化、数据挖掘以及一些经典的组合优化问题。 46 蚁群优化算法应用现状 2/5 蚁群算法在电信路由优化中已取得了一定的应用成果。 HP公司和英国电信公司在 90年代中后期都开展了这方面的研究，设计了蚁群路由算法（ Ant Colony Routing, ACR）。 每只蚂蚁就像蚁群优化算法中一样，根据它在网络上的经验与性能，动态更新路由表项。如果一只蚂蚁因为经过了网络中堵塞的路由而导致了比较大的延迟，那么就对该表项做较大的增强。同时根据信息素挥发机制实现系统的信息更新，从而抛弃过期的路由信息。这样，在当前最优路由出现拥堵现象时， ACR算法就能迅速的搜寻另一条可替代的最优路径，从而提高网络的均衡性、负荷量和利用率。目前这方面的应用研究仍在升温，因为通信网络的分布式信息结构、非稳定随机动态特性以及网络状态的异步演化与 ACO的算法本质和特性非常相似。 47 蚁群优化算法应用现状 3/5 基于群智能的聚类算法起源于对蚁群蚁卵的分类研究。Lumer和 Faieta将 Deneubourg提出将蚁巢分类模型应用于数据聚类分析。其基本思想是将待聚类数据随机地散布到一个二维平面内，然后将虚拟蚂蚁分布到这个空间内，并以随机方式移动，当一只蚂蚁遇到一个待聚类数据时即将之拾起并继续随机运动，若运动路径附近的数据与背负的数据相似性高于设置的标准则将其放置在该位置，然后继续移动，重复上述数据搬运过程。按照这样的方法可实现对相似数据的聚类。 48 蚁群优化算法应用现状 4/5 ACO还在许多经典组合优化问题中获得了成功的应用，如二次规划问题（ QAP）、机器人路径规划、作业流程规划、图着色（ Graph Coloring）等问题。 经过多年的发展， ACO已成为能够有效解决实际二次规划问题的几种重要算法之一。 AS在作业流程计划（ Jobshop Scheduling）问题中的应用实例已经出现，这说明了 AS在此领域的应用潜力。利用 MAXMIN AS解决 PAQ也取得了比较理想的效果，并通过实验中的计算数据证明采用该方法处理 PAQ比较早的 SA算法更好，且与禁忌搜索算法性能相当。利用 ACO实现对生产流程和特料管理的综合优化，并通过与遗传、模拟退火和禁忌搜索算法的比较证明了 ACO的工程应用价值。 49 蚁群优化算法应用现状 5/5 许多研究者将 ACO用于了武器攻击目标分配和优化问题、车辆运行路径规划、区域性无线电频率自动分配、 Bayesian works的训练和集合覆盖等应用优化问题。 Costa和 Herz还提出了一种 AS在规划问题方面的扩展应用 —— 图着色问题，并取得了可与其他启发式算法相比的效果。 50 蚁群优化算法概念 蚁群算法原理 简化的蚂蚁寻食过程 自然蚁群与人工蚁群算法 蚁群算法与 TSP问题 初始的蚁群优化算法 — 基于图的蚁群系统（ GBAS） 一般蚁群算法的框架 51 蚁群算法原理 蚁群算法是对自然界蚂蚁的寻径方式进行模似而得出的一种仿生算法。蚂蚁在运动过程中，能够在它所经过的路径上留下一种称之为外激素 (pheromone)的物质进行信息传递，而且蚂蚁在运动过程中能够感知这种物质，并以此指导自己的运动方向，因此由大量蚂蚁组成的蚁群集体行为便表现出一种信息正反馈现象：某一路径上走过的蚂蚁越多，则后来者选择该路径的概率就越大。 为了说明蚁群算法的原理，先简要介绍一下蚂蚁搜寻食物的具体过程。在蚁群寻找食物时，它们总能找到一条从食物到巢穴之间的最优路径。这是因为蚂蚁在寻找路径时会在路径上释放出一种特殊的信息素。当它们碰到一个还没有走过的路口时．就随机地挑选一条路径前行。与此同时释放出与路径长度有关的信息素。路径越长