现代优化算法.ppt

现代优化算法
组合优化问题 3/8
例1 0-1背包问题（0-1 knapsack problem）
8
组合优化问题 4/8
9
组合优化问题 5/8
例2 旅行商问题（TSP, 2/6
优点：
（1）有可能比简化数学模型解的误差小；
（2）对有些难题，计算时间可接受；
（3）可用于某些最优化算法（如分支定界算
法）之中的估界；
（4）直观易行；
（5）速度较快；
（6）程序简单，易修改。
26
启发式算法_不足 3/6
不足：
（1）不能保证求得全局最优解；
（2）解的精度不稳定，有时好有时坏；
（3）算法设计与问题、设计者经验、技术 有关，缺乏规律性；
（4）不同算法之间难以比较。
27
启发式算法_分类 4/6
（1）一步算法
（2）改进算法（迭代算法）
(3) 数学规划算法
(4) 解空间松弛法
28
启发式算法_分类 5/6
（5）现代优化算法：
80年代初兴起
禁忌搜索（tabu search）
模拟退火（simulated annealing）
遗传算法（genetic algorithms）
神经网络（neural networks）
蚂蚁算法（Ant Algorithm，群体（群集）智能，Swarm Intelligence）
（6）其他算法：
多种启发式算法的集成.
29
启发式算法_性能分析 6/6
（1）最坏情形分析（worst case analysis）
利用最坏实例分析计算复杂性、解的效果。
(2）概率分析 （probability analysis）
用最坏情况分析，会因一个最坏实例影响总体评价.
在实例数据服从一定概率分布情形下，研究算法复杂性和解的效果.
(3)大规模计算分析
通过大量实例计算，评价算法效果.
注意数据的随机性和代表性.
30
2 蚁群优化算法
蚁群优化算法概述
蚁群优化算法概念
算法模型和收敛性分析
算法实现的技术问题
应用
参考资料
31
蚁群优化算法概述
起源
应用领域
研究背景
研究现状
应用现状
32
蚁群优化算法起源
20世纪50年代中期创立了仿生学，人们从生物进化的机理中受到启发。提出了许多用以解决复杂优化问题的新方法，如进化规划、进化策略、遗传算法等，这些算法成功地解决了一些实际问题。
20世纪90年代意大利学者M．Dorigo，V．Maniezzo，A．Colorni等从生物进化的机制中受到启发，通过模拟自然界蚂蚁搜索路径的行为，提出来一种新型的模拟进化算法—— 蚁群算法，是群智能理论研究领域的一种主要算法。用该方法求解TSP问题、分配问题、job-shop调度问题，取得了较好的试验结果．虽然研究时间不长，但是现在的研究显示出，蚁群算法在求解复杂优化问题（特别是离散优化问题）方面有一定优势，表明它是一种有发展前景的算法．
33
蚁群优化算法应用领域
这种方法能够被用于解决大多数优化问题或者能够转化为优化求解的问题。现在其应用领域已扩展到多目标优化、数据分类、数据聚类、模式识别、电信QoS管理、生物系统建模、流程规划、信号处理、机器人控制、决策支持以及仿真和系统辩识等方面，群智能理论和方法为解决这类应用问题提供了新的途径。
34
蚁群优化算法研究背景 1/3
群智能理论研究领域有两种主要的算法：蚁群算法(Ant Colony Optimization, ACO)和微粒群算法（Particle Swarm Optimization, PSO）。前者是对蚂蚁群落食物采集过程的模拟，已成功应用于许多离散优化问题。微粒群算法也是起源于对简单社会系统的模拟，最初是模拟鸟群觅食的过程，但后来发现它是一种很好的优化工具。
35
蚁群优化算法研究背景 2/3
与大多数基于梯度的应用优化算法不同，群智能依靠的是
概率搜索算法。虽然概率搜索算法通常要采用较多的评价
函数，但是与梯度方法及传统的演化算法相比，其优点还
是显著的 ，主要表现在以下几个方面：
1 无集中控制约束，不会因个别个体的故障影响整个问题
的求解，确保了系统具备更强的鲁棒性
2 以非直接的信息交流方式确保了系统的扩展性
3 并行分布式算法模型，可充分利用多处理器
4 对问题定义的连续性无特殊要求
5 算法实现简单
36
蚁群优化算法研究背景 3/3
群智能方法易于实现，算法中仅