算法设计与分析-蚁群算法介绍

《算法设计与分析-蚁群算法介绍》由会员分享，可在线阅读，更多相关《算法设计与分析-蚁群算法介绍（110页珍藏版）》请在金锄头文库上搜索。

1、算法设计与分析 第七章补充材料 蚁群算法介绍山东师范大学计算机系 授课：徐连诚，#3432#，http:/ 2005年9月5日2006年1月20日1内 容一、启发式方法概述二、蚁群优化算法2背 景n传统实际问题的特点连续性问题主要以微积分为基础，且问题规模较小n传统的优化方法追求准确精确解理论的完美结果漂亮主要方法：线性与非线性规划、动态规划、多目标规划、 整数规划等；排队论、库存论、对策论、决策论等。n传统的评价方法算法收敛性（从极限角度考虑）收敛速度（线性、超线性、二次收敛等）3传统运筹学面临新挑战n现代问题的特点离散性问题主要以组合优化（针对离散问题，定义 见后）理论为基础不确定性问题随

2、机性数学模型半结构或非结构化的问题计算机模拟、决策支持系统大规模问题并行计算、大型分解理论、近似理论n现代优化方法追求满意近似解实用性强解决实际问题n现代优化算法的评价方法算法复杂性4现代优化(启发式)方法种类n禁忌搜索（tabu search）n模拟退火（simulated annealing）n遗传算法（genetic algorithms）n神经网络（neural networks）n蚁群算法（群体（群集）智能，Swarm Intelligence） n拉格朗日松弛算法（lagrangean relaxation ）51 现代优化计算方法概述n1.1 组合优化问题n1.2 计算复杂性的概

3、念n1.3 启发式算法61.1 组合优化问题 1/8组合优化（combinatorial optimization）:解决离散 问题的优化问题运筹学分支。通过数学方法的研 究去寻找离散事件的最优编排、分组、次序或筛选 等，可以涉及信息技术、经济管理、工业工程、交 通运输和通信网络等许多方面。数学模型：71.1 组合优化问题 2/8组合优化问题的三参数表示：81.1 组合优化问题 3/8n例1 0-1背包问题（0-1 knapsack problem ）91.1 组合优化问题 4/8101.1 组合优化问题 5/8n例2 旅行商问题（TSP,traveling salesman problem）

4、管梅谷教授1960年首先提出，国际上称 之为中国邮递员问题。问题描述：一商人去n个城市销货，所 有城市走一遍再回到起点，使所走路程 最短。111.1 组合优化问题 6/8121.1 组合优化问题 7/8例3 装箱问题（bin packing）尺寸为1的箱子有若干个，怎样用最少 的箱子装下n个尺寸不超过1 的物品， 物品集合为： 。131.1 组合优化问题 8/8141.2 计算复杂性的概念 1/11n评价算法的好坏计算时间的多少、解 的偏离程度n例 非对称距离TSP问题的算法实现：所 有路径枚举。计算时间：n个城市，固定1个为起终点需 要(n-1)!个枚举，设计算机1秒能完成24个 城市的枚举

5、，则城市数与计算时间的关系 如下表：151.2 计算复杂性的概念 2/11城市 数2425262728293031计算 时 间1 sec24 sec10 min4.3 hour4.9 day136. 5 day10.8 year325 year随城市增多，计算时间增加很快。 到31个城市时，要计算325年。描述算法的好坏计算复杂性讨论计算时间与问题规模 之间的关系。以目前二进制计算机中的存储和计算为基础， 以理论的形式系统描述，是评估算法性能的基础。161.2 计算复杂性的概念 3/11n问题（problem）：要回答的一般性提问，通常含有 若干个满足一定条件的参数（或自由变量）。可以 从两方

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

7、：加、减、乘、除、比较的总运算次数与实例的 计算机计算时的二进制输入数据的大小关系。n正整数x的二进制位数是:(整数到二进制的转换 )191.2 计算复杂性的概念 6/11n算法计算量的度量之例TSP枚举 法计算量的统计：201.2 计算复杂性的概念 7/11n实例的输入长度：n实例的输入长度是n的多项式函数n枚举法的基本计算量是n的阶乘函数，随n的增加，比指数函数增加得还快.211.2 计算复杂性的概念 8/11221.2 计算复杂性的概念 9/11定义 多项式算法 给定问题P，算法A，对一个实例I，存在多项式 函数g(x)，使（XX ）成立，称算法A对实例I是 多项式算法； 若存在多项式函

8、数g(x)，使（XX ）对问题P的任 意实例I都成立，称算法A为解决该问题P的多项 式算法. 当g(x)为指数函数时，称A为P的指数时间算法 。231.2 计算复杂性的概念 10/11n利用复杂性分析对组合优化问题归类。n定义多项式问题 给定一个组合优化问题，若存在一个多项 式算法，称该问题为多项式时间可解问题 ，或简称多项式问题(或P问题). 所有多 项式问题的集合记为P.n例：线性规划是否为多项式问题？241.2 计算复杂性参考书 11/11n计算复杂性, 作者：Christos， Papadimitriou 清华大学出版社，2004年9月第1版n计算复杂性导论，作者：堵丁柱等，高等教育出

9、版社，2002年8月第1版251.3 启发式算法_定义 1/6n启发式算法（heuristic algorithm）n定义1. 基于直观或经验构造的算法，在可接受的 花费（时间、空间）下，给出待解组合优化问题 的每个实例的一个可行解，该可行解与最优解偏 差事先不一定可以预计.n定义2. 启发式算法是一种技术，在可接受的计算 费用内寻找最好解，但不保证该解的可行性与最 优性，无法描述该解与最优解的近似程度。n特点（与传统优化方法不同）：凭直观和经验给 出算法；不考虑所得解与最优解的偏离程度.261.3 启发式算法_优点 2/6优点： （1）有可能比简化数学模型解的误差小； （2）对有些难题，计算

10、时间可接受； （3）可用于某些最优化算法（如分支定界算法）之中的估界； （4）直观易行； （5）速度较快； （6）程序简单，易修改。271.3 启发式算法_不足 3/6不足： （1）不能保证求得全局最优解； （2）解的精度不稳定，有时好有时坏； （3）算法设计与问题、设计者经验、技 术 有关，缺乏规律性； （4）不同算法之间难以比较。281.3 启发式算法_分类 4/6（1）一步算法 （2）改进算法（迭代算法）(3) 数学规划算法(4) 解空间松弛法291.3 启发式算法_分类 5/6 （5）现代优化算法：80年代初兴起n禁忌搜索（tabu search）n模拟退火（simulated ann

11、ealing）n遗传算法（genetic algorithms）n神经网络（neural networks）n蚂蚁算法（Ant Algorithm，群体（群集） 智能，Swarm Intelligence） （6）其他算法：多种启发式算法的集成. 301.3 启发式算法_性能分析 6/6（1）最坏情形分析（worst case analysis）利用最坏实例分析计算复杂性、解的效果。(2）概率分析 （probability analysis）用最坏情况分析，会因一个最坏实例影响总体评价.在实例数据服从一定概率分布情形下，研究算法复杂性和 解的效果.(3)大规模计算分析通过大量实例计算，评价算法

12、效果.n注意数据的随机性和代表性.312 蚁群优化算法n蚁群优化算法 概述n蚁群优化算法 概念n算法模型和收 敛性分析n算法实现的技术问 题n应用n参考资料322.1 蚁群优化算法概述n2.1.1 起源n2.1.2 应用领域n2.1.3 研究背景n2.1.4 研究现状n2.1.5 应用现状332.1.1 蚁群优化算法起源20世纪50年代中期创立了仿生学，人们从生物进化的机理中 受到启发。提出了许多用以解决复杂优化问题的新方法，如进 化规划、进化策略、遗传算法等，这些算法成功地解决了一些 实际问题。20世纪90年代意大利学者MDorigo，VManiezzo，A Colorni等从生物进化的机制

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

14、和系统辩识等方面，群智能理论和方法 为解决这类应用问题提供了新的途径。352.1.3 蚁群优化算法研究背景 1/3群智能理论研究领域有两种主要的算法： 蚁群算法(Ant Colony Optimization, ACO)和 微粒群算法（Particle Swarm Optimization, PSO）。前者是对蚂蚁群落食物采集过程的 模拟，已成功应用于许多离散优化问题。微 粒群算法也是起源于对简单社会系统的模拟 ，最初是模拟鸟群觅食的过程，但后来发现 它是一种很好的优化工具。362.1.3 蚁群优化算法研究背景 2/3与大多数基于梯度的应用优化算法不同，群智能依靠的是 概率搜索算法。虽然概率搜

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

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