现代优化算法.ppt

内 容
一、启发式方法概述
二、蚁群优化算法
1
背 景
传统实际问题的特点
连续性问题——主要以微积分为基础，且问题规模较小
传统的优化方法
追求准确——精确解
理论的完美——结果漂亮
主要方量是n的阶乘函数，
随n的增加，比指数函数增加得还快.
20
计算复杂性的概念 8/11
21
计算复杂性的概念 9/11
定义 多项式算法
给定问题P，算法A，对一个实例I，存在多项式
函数g(x)，使（XX ）成立，称算法A对实例I是
多项式算法；
若存在多项式函数g(x)，使（XX ）对问题P的任
意实例I都成立，称算法A为解决该问题P的多项
式算法.
当g(x)为指数函数时，称A为P的指数时间算法。
22
计算复杂性的概念 10/11
利用复杂性分析对组合优化问题归类。
定义多项式问题
给定一个组合优化问题，若存在一个多项式算法，称该问题为多项式时间可解问题，或简称多项式问题(或P问题). 所有多项式问题的集合记为P.
例：线性规划是否为多项式问题？
23
计算复杂性参考书 11/11
计算复杂性, 作者：Christos，Papadimitriou清华大学出版社，2004年9月第1版
计算复杂性导论，作者：堵丁柱等，
高等教育出版社，2002年8月第1版
24
启发式算法_定义 1/6
启发式算法（heuristic algorithm）
定义1. 基于直观或经验构造的算法，在可接受的花费（时间、空间）下，给出待解组合优化问题的每个实例的一个可行解，该可行解与最优解偏差事先不一定可以预计.
定义2. 启发式算法是一种技术，在可接受的计算费用内寻找最好解，但不保证该解的可行性与最优性，无法描述该解与最优解的近似程度。
特点（与传统优化方法不同）：凭直观和经验给出算法；不考虑所得解与最优解的偏离程度.
25
启发式算法_优点 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调度问题，