智能优化技术课件.pptx

1、智能智能优化优化技术技术Intelligent Optimization Technology目录目录第一部分第一部分 导言导言第二部分第二部分 基于自然生命基于自然生命进化进化的智能优化技术的智能优化技术 （遗传算法（遗传算法GA, GA, 免疫优化）免疫优化）第三部分第三部分 基于基于群群（swarmswarm）的智能优化技术）的智能优化技术 ( (蚁群优化蚁群优化ACOACO，粒子群优化，粒子群优化PSO, PSO, 捕食搜索捕食搜索PS, PS, 群落选址算法群落选址算法CLA)CLA)第四部分第四部分 基于物理自然的智能计算技术基于物理自然的智能计算技术 ( (模拟退火模拟退火(SA

2、), (SA), 禁忌搜索禁忌搜索TS, TS, 神经网络优化神经网络优化 NN)NN)第五部分第五部分 其他智能技术方法其他智能技术方法第六部分第六部分 结语与展望结语与展望 教材教材 中英文文献：中英文文献：1.1.雷德明，严新平雷德明，严新平“多目标智能优化算法及多目标智能优化算法及其应用其应用”，科学出版社，科学出版社，20092009年年3 3月月2.2.邢文训，谢金星邢文训，谢金星“现代优化计算方法现代优化计算方法”，清华大学出版社，清华大学出版社，19991999年年第一部分第一部分 导言导言第一章第一章 导言导言最优化的重要性最优化的重要性一一. .传统优化方法的基本步骤传统优

3、化方法的基本步骤三步曲三步曲二二. .传统优化方法的局限性传统优化方法的局限性三三. .实际问题中对最优化方法的要求实际问题中对最优化方法的要求四四. .智能优化算法的产生与发展智能优化算法的产生与发展五五. .应用前景局限性和研究方向应用前景局限性和研究方向. .最优化的重要性（最优化的重要性（1 1）1.1. 从广义上说：人类的一切活动都是认识世界从广义上说：人类的一切活动都是认识世界和改造世界的过程和改造世界的过程 即：即： 认识世界认识世界 改造世界改造世界 ( (建模过程建模过程) () (优化过程优化过程) ). .最优化的重要性（最优化的重要性（2 2）2.2. 一切学科都是建模

4、与优化在某个特定领域中一切学科都是建模与优化在某个特定领域中的应用的应用概念模型概念模型( (定性定性) ) 结构模型结构模型( (图图) 数学模型数学模型 智能模型智能模型最优化的重要性（最优化的重要性（2 2） 从我们控制学科上说：1. 优化控制：如PID参数优化整定，2. 系统优化：节能减排。最优化的重要性（最优化的重要性（3 3）3. 最优化理论的发展最优化理论的发展 极值理论；极值理论； 运筹学的兴起运筹学的兴起(Operation Research)； 数学规划：线性规划数学规划：线性规划(LP)；非线性规划；非线性规划(NLP)；动态规划动态规划(PP)；马尔托夫规划；马尔托夫规

5、划(MDP)；排队；排队轮；决策论；存储论。轮；决策论；存储论。4. 最优化理论在国民经济中的广泛应用最优化理论在国民经济中的广泛应用一一.传统优化方法的基本步骤传统优化方法的基本步骤三步曲（三步曲（1）如下面框图所示如下面框图所示1. 选一个初始解选一个初始解 LP:大大M，二阶段法，二阶段法 NLP:任意点或一个内点任意点或一个内点一一.传统优化方法的基本步骤传统优化方法的基本步骤三步曲（三步曲（2）停止判据停止判据停止规则最优性检验停止规则最优性检验LP:检验数检验数当当0时有可能减小时有可能减小NLP:TNTBCNBC1NBA|TNBCCC|0)(xf一一.传统优化方法的基本步骤传统优

6、化方法的基本步骤三步曲（三步曲（3）3. 向改进方向移动向改进方向移动改进解改进解 LP:转轴变换转轴变换(进基、退基进基、退基) NLP:向负梯度方向移动向负梯度方向移动(共轭梯度方向、牛顿共轭梯度方向、牛顿方向方向)停机停机选择一个初始解选择一个初始解停止准则停止准则向改进方向移动向改进方向移动启动启动YN二二.传统优化方法的局限性（传统优化方法的局限性（1）1. 对问题中目标函数、约束函数有很高的要对问题中目标函数、约束函数有很高的要求求有显式表达，线性、连续、可微，且有显式表达，线性、连续、可微，且高阶可微高阶可微;2. 只从一个初始点出发，难以进行并行、网络只从一个初始点出发，难以进

7、行并行、网络计算，难以提高计算效率；计算，难以提高计算效率；同时最优解对初同时最优解对初始点的强烈依赖性，容易陷入局部最优解始点的强烈依赖性，容易陷入局部最优解二二.传统优化方法的局限性（传统优化方法的局限性（2）3. 最优性达到的条件太苛刻最优性达到的条件太苛刻问题的函数为问题的函数为凸，可行域为凸；凸，可行域为凸；4. 在非双凸条件下，没有跳出局部最优解的能在非双凸条件下，没有跳出局部最优解的能力。力。 5. 没有跳出局部最优解的能力，是传统优化算没有跳出局部最优解的能力，是传统优化算法的致命弱点。法的致命弱点。三三. .实际问题中对最优化方法的要求实际问题中对最优化方法的要求（1）1.1

8、. 对问题的描述要宽松对问题的描述要宽松( (目标和约束函数目标和约束函数) ) 可以用一段程序来描述可以用一段程序来描述( (程序中带判断、循程序中带判断、循环环) )，函数可以非连续、非凸、非可微、非，函数可以非连续、非凸、非可微、非显式；显式；2. 并不苛求最优解并不苛求最优解通常满意解、理想解就通常满意解、理想解就可以了；可以了；三三. .实际问题中对最优化方法的要求（实际问题中对最优化方法的要求（2 2）3. 计算快速、高效计算快速、高效,可随时终止可随时终止(根据时间定解根据时间定解的质量的质量)；4. 能够处理数据、信息的不确定性能够处理数据、信息的不确定性(如数据的如数据的模糊

9、性，事件的随机性模糊性，事件的随机性)。四四. .智能优化算法的产生与发展（智能优化算法的产生与发展（1 1）智能优化算法的产生一个重要原因是为了改善传统智能优化算法的产生一个重要原因是为了改善传统优化算法局部邻域收索，获得全局最优解。优化算法局部邻域收索，获得全局最优解。1.1975年年holland提出遗传算法提出遗传算法(Genetic Algorithm)2.1977年年Glouer提出禁忌搜索算法提出禁忌搜索算法(Tabn Search)四四. .智能优化算法的产生与发展（智能优化算法的产生与发展（2 2）3. 1982年年Kirkpatrick提出模拟退火算提出模拟退火算 (Sim

10、ulated Annealing)，以可控性概率接受劣解来逃离，以可控性概率接受劣解来逃离局部最优。局部最优。4. 人工神经元网络人工神经元网络5. 1995年年Dorigo提出蚁群算法提出蚁群算法 (Ant Colony Optimization)四四. .智能优化算法的产生与发展（智能优化算法的产生与发展（3 3）6. 1995年年Kennedy & Eherhart提出粒子群优化提出粒子群优化 (Particle Swarm Optimization)7. 其它其它 文化算法文化算法(Cultural Algorithm) 人工生命算法人工生命算法(Artificial-Life Alg

11、orithm)四四. .智能优化算法的产生与发展（智能优化算法的产生与发展（4 4）我们统称以上算法为人工生命计算我们统称以上算法为人工生命计算 (Artificial Life Computation)(Artificial Life Computation)1. 人工生命计算人工生命计算 + 模糊逻辑模糊逻辑 (Fuzzy Logic)=软计算软计算(Soft Computation)2. 人工生命计算人工生命计算 + 进化编程进化编程 = 进化算法进化算法 (Evolutionary computation)五五. .应用前景局限性和研究方向、注意事项（应用前景局限性和研究方向、注意事项

12、（1 1）1. 应用前景十分广阔应用前景十分广阔国民经济的各个领域国民经济的各个领域2. 局限性局限性不能保证最优解，理论上不完备不能保证最优解，理论上不完备五五. .应用前景局限性和研究方向、注意事项（应用前景局限性和研究方向、注意事项（2 2）3. 研究方向及注意事项研究方向及注意事项 以应用为主，扩大面向新问题的应用；不要以应用为主，扩大面向新问题的应用；不要刻意做理论研究，若碰上也不拒绝刻意做理论研究，若碰上也不拒绝; 算法改进表现在以下几个方面：问题的描述、算法改进表现在以下几个方面：问题的描述、编码方法、算法构造及可行性修复策略编码方法、算法构造及可行性修复策略; 要进行大量的上机

13、计算；要进行大量的上机计算；五五. .应用前景局限性和研究方向、注意事项（应用前景局限性和研究方向、注意事项（3 3） 算例的选取，以下算例的说服力降序排列：算例的选取，以下算例的说服力降序排列：网上的测试用例、文献中的例子、实际例子、网上的测试用例、文献中的例子、实际例子、随机产生的例子、自己编的例子随机产生的例子、自己编的例子; 如何检验算法的好坏：比较计算速度、可解如何检验算法的好坏：比较计算速度、可解规模、规模、 (从不同的随机种子出发从不同的随机种子出发)达优率。达优率。TSP问题的概述问题的概述 旅行商问题，即TSP问题（Traveling Salesman Problem）是数学

14、领域中著名问题之一。假设有一个旅行商人要拜访N个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值，这是一个NP难问题File:Tsp By GA.jpg第二部分第二部分 基于自然进化的智能计算技术基于自然进化的智能计算技术 遗传算法遗传算法GA, GA, 免疫优化免疫优化第三部分第三部分 基于群（基于群（swarmswarm）的智能计）的智能计算技术算技术 粒子群优化粒子群优化PSO, PSO, 蚁群优化蚁群优化ACOACO， 捕食搜索捕食搜索PS, PS, 群落选址算法群落选址算法CLACLA

15、1.遗传算法遗传算法(GA)的产生的产生 1975年，年，Holland提出提出GA 著名的书著名的书：Adaptation in Natural and Artificial Systems (中文名称：自然与人工系统的自适应性中文名称：自然与人工系统的自适应性) 后来，后来，DeJong和和Goldberg做了大量工作，使做了大量工作，使GA更加更加完善。完善。一一. .导言（导言（1 1）2.遗传算法遗传算法(GA)的来源：的来源：生物的进化：自然选择、适者生存生物的进化：自然选择、适者生存 生物的遗传和变异生物的遗传和变异(GA)缺点：无人的主动性缺点：无人的主动性 ；解决方法有以下三个：解决方法有以下三个： 定向培育定向培育 随机算法随机算法 网格法网格法一一. .导言（导言（2 2）第四章基于物理自然的智能计算技术第四章基于物理自然的智能计算技术 模拟退火模拟退火(SA), (SA), 禁忌搜索禁忌搜索TS, TS, 神经网络优化神经网络优化 NNNN结语与展望结语与展望 针对实际问题，建立起有效的优化命题是最重要的，智能优化算法选择是其次 智能优化技术有向多目标优化领域发展的趋势 追求优化设计PARETO解，而不是单一的有效解 智能优化技术有向智能鲁棒优化发展的趋势 File:Tsp By GA.jpg课程结束谢谢！