智能优化技术课件

智能优化技术

IntelligentOptimizationTechnology

1马龙华副教授浙江大学控制科学与工程系2011年5月智能优化技术

IntelligentOptimizatio目录第一部分导言第二部分基于自然生命进化的智能优化技术

（遗传算法GA,免疫优化）第三部分基于群（swarm）的智能优化技术

(蚁群优化ACO，粒子群优化PSO,捕食搜索PS,群落选址算法CLA)第四部分基于物理自然的智能计算技术

(模拟退火(SA),禁忌搜索TS,神经网络优化NN)第五部分其他智能技术方法第六部分结语与展望

2目录第一部分导言2教材中英文文献：1.雷德明，严新平“多目标智能优化算法及其应用”，科学出版社，2009年3月2.邢文训，谢金星“现代优化计算方法”，清华大学出版社，1999年3教材中英文文献：3第一部分 导言4第一部分 导言4第一章导言最优化的重要性一.传统优化方法的基本步骤——三步曲二.传统优化方法的局限性三.实际问题中对最优化方法的要求四.智能优化算法的产生与发展五.应用前景局限性和研究方向5第一章导言最优化的重要性5〇.最优化的重要性（1）从广义上说：人类的一切活动都是认识世界和改造世界的过程即：认识世界→ 改造世界 ↓ ↓

(建模过程)(优化过程)

6〇.最优化的重要性（1）6〇.最优化的重要性（2）一切学科都是建模与优化在某个特定领域中的应用 概念模型(定性)→结构模型(图)→ →数学模型→智能模型

7〇.最优化的重要性（2）7最优化的重要性（2）从我们控制学科上说：优化控制：如PID参数优化整定，系统优化：节能减排。8最优化的重要性（2）从我们控制学科上说：8最优化的重要性（3）最优化理论的发展极值理论；运筹学的兴起(OperationResearch)；数学规划：线性规划(LP)；非线性规划(NLP)；动态规划(PP)；马尔托夫规划(MDP)；排队轮；决策论；存储论。最优化理论在国民经济中的广泛应用 9最优化的重要性（3）最优化理论的发展9一.传统优化方法的基本步骤—三步曲（1）如下面框图所示选一个初始解LP:大M，二阶段法NLP:任意点或一个内点 10一.传统优化方法的基本步骤—三步曲（1）10一.传统优化方法的基本步骤—三步曲（2）停止判据——停止规则最优性检验LP:检验数 当∏≥0时有可能减小NLP:11一.传统优化方法的基本步骤—三步曲（2）11一.传统优化方法的基本步骤—三步曲（3）向改进方向移动——改进解LP:转轴变换(进基、退基)NLP:向负梯度方向移动(共轭梯度方向、牛顿方向) 12一.传统优化方法的基本步骤—三步曲（3）1213停机选择一个初始解停止准则向改进方向移动启动YN一.传统优化方法的基本步骤—三步曲（4）13停机选择一个初始解停止准则向改进方向移动启动YN一.传统二.传统优化方法的局限性（1）对问题中目标函数、约束函数有很高的要求——有显式表达，线性、连续、可微，且高阶可微;2. 只从一个初始点出发，难以进行并行、网络计算，难以提高计算效率；同时最优解对初始点的强烈依赖性，容易陷入局部最优解

14二.传统优化方法的局限性（1）14二.传统优化方法的局限性（2）最优性达到的条件太苛刻——问题的函数为凸，可行域为凸；在非双凸条件下，没有跳出局部最优解的能力。没有跳出局部最优解的能力，是传统优化算法的致命弱点。

15二.传统优化方法的局限性（2）15三.实际问题中对最优化方法的要求（1）对问题的描述要宽松(目标和约束函数)——

可以用一段程序来描述(程序中带判断、循环)，函数可以非连续、非凸、非可微、非显式；并不苛求最优解——通常满意解、理想解就可以了；16三.实际问题中对最优化方法的要求（1）对问题的描述要宽松(目三.实际问题中对最优化方法的要求（2）计算快速、高效,可随时终止(根据时间定解的质量)；能够处理数据、信息的不确定性(如数据的模糊性，事件的随机性)。17三.实际问题中对最优化方法的要求（2）计算快速、高效,可随时四.智能优化算法的产生与发展（1）智能优化算法的产生一个重要原因是为了改善传统优化算法局部邻域收索，获得全局最优解。1975年holland提出遗传算法

(GeneticAlgorithm)1977年Glouer提出禁忌搜索算法

(TabnSearch) 18四.智能优化算法的产生与发展（1）智能优化算法的产生一个重要四.智能优化算法的产生与发展（2）1982年Kirkpatrick提出模拟退火算(SimulatedAnnealing)，以可控性概率接受劣解来逃离局部最优。人工神经元网络1995年Dorigo提出蚁群算法

(AntColonyOptimization)19四.智能优化算法的产生与发展（2）1982年Kirkpatr四.智能优化算法的产生与发展（3）1995年Kennedy&Eherhart提出粒子群优化(ParticleSwarmOptimization)其它文化算法(CulturalAlgorithm)人工生命算法(Artificial-LifeAlgorithm)20四.智能优化算法的产生与发展（3）1995年Kennedy四.智能优化算法的产生与发展（4）我们统称以上算法为人工生命计算(ArtificialLifeComputation)人工生命计算+模糊逻辑(FuzzyLogic)=

软计算(SoftComputation)人工生命计算+进化编程=

进化算法(Evolutionarycomputation)21四.智能优化算法的产生与发展（4）我们统称以上算法为人工生命五.应用前景局限性和研究方向、注意事项（1）应用前景十分广阔——国民经济的各个领域局限性——不能保证最优解，理论上不完备22五.应用前景局限性和研究方向、注意事项（1）应用前景十分广阔五.应用前景局限性和研究方向、注意事项（2）研究方向及注意事项以应用为主，扩大面向新问题的应用；不要刻意做理论研究，若碰上也不拒绝;算法改进表现在以下几个方面：问题的描述、编码方法、算法构造及可行性修复策略;要进行大量的上机计算；23五.应用前景局限性和研究方向、注意事项（2）研究方向及注意事五.应用前景局限性和研究方向、注意事项（3）算例的选取，以下算例的说服力降序排列：网上的测试用例、文献中的例子、实际例子、随机产生的例子、自己编的例子;如何检验算法的好坏：比较计算速度、可解规模、(从不同的随机种子出发)达优率。24五.应用前景局限性和研究方向、注意事项（3）算例的选取，以下TSP问题的概述旅行商问题，即TSP问题（TravelingSalesmanProblem）是数学领域中著名问题之一。假设有一个旅行商人要拜访N个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值，这是一个NP难问题25TSP问题的概述旅行商问题，即TSP问题（TraveliFile:TspByGA.jpg26File:TspByGA.jpg26

第二部分基于自然进化的智能计算技术

遗传算法GA,免疫优化27

第二部分基于自然进化的智能计算技术

遗传算法GA,2第三部分基于群（swarm）的智能计算技术粒子群优化PSO,蚁群优化ACO，捕食搜索PS,群落选址算法CLA28第三部分基于群（swarm）的智能计算技术粒子群优化P29遗传算法(GA)的产生

1975年，Holland提出GA

著名的书：

AdaptationinNaturalandArtificialSystems(中文名称：自然与人工系统的自适应性)

后来，DeJong和Goldberg做了大量工作，使GA更加完善。一.导言（1）29遗传算法(GA)的产生一.导言（1）30遗传算法(GA)的来源： 生物的进化：自然选择、适者生存生物的遗传和变异

(GA)缺点：无人的主动性； 解决方法有以下三个：定向培育随机算法网格法一.导言（2）30遗传算法(GA)的来源：一.导言（2）31313232第四章基于物理自然的智能计算技术模拟退火(SA),禁忌搜索TS,神经网络优化NN