智能优化方法 Intelligent Optimization Methods

Presentation on theme: "智能优化方法 Intelligent Optimization Methods"— Presentation transcript:

1 智能优化方法 Intelligent Optimization Methods
By Wang Hongfeng PhD ISE, NEU Shenyang, P.R. China

2 课程安排 No.1 导言、伪随机数的产生方法 No.2 禁忌搜索(TS) No.3 模拟退火(SA) No.4 进化算法(GA)
No.5 进化算法(ES, EP, GP,DE)

3 课程安排 No 群体智能算法(PSO) No 群体智能算法(ACO,BFOA,ABC) No 智能优化领域的最新进展

4 课程理解 这是一门关于计算智能的课程 这是一门介绍优化工具的课程 这是一门注重技巧学习的课程 让我们共勉！！！

5 教材 《智能优化方法》 汪定伟 王俊伟 王洪峰等编著 高等教育出版社 中英文文献

6 第一章 导言

7 第一章 导言 〇.最优化的重要性 一.传统优化方法的基本步骤——三步曲 二.传统优化方法的局限性 三.实际问题中对最优化方法的要求
第一章 导言 〇.最优化的重要性 一.传统优化方法的基本步骤——三步曲 二.传统优化方法的局限性 三.实际问题中对最优化方法的要求 四.智能优化算法的产生与发展 五.应用前景局限性和研究方向、注意事项 六.优化领域的新进展 七. 学习这门课程需要具备的基础

8 〇.最优化的重要性（1） 人类的一切活动都是认识世界和改造世界的过程 即： 认识世界 → 改造世界 ↓ ↓ (建模) → (优化)

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

10 〇.最优化的重要性（3） 最优化理论的发展 极值理论 运筹学的兴起(OR)
数学规划：线性规划(LP)；非线性规划(NLP)；动态规划(DP)；马尔可夫规划(MDP) 最优化理论在国民经济中的广泛应用

11 一.传统优化方法的基本步骤—三步曲（1） 如右图所示 选一个初始解 LP：大M法，二阶段法 NLP：任意点或一个内点 开始 选初始解 Y
停止 选初始解 停止判据 改进解 开始 Y N

12 一.传统优化方法的基本步骤—三步曲（2） 停止判据——最优性检验 LP：检验数 当∏≥0时有可能减小 NLP：

13 一.传统优化方法的基本步骤—三步曲（3） 向改进方向移动——改进解 LP：转轴变换（进基、退基） NLP：向负梯度方向移动（共轭梯度方向、牛顿方向）

14 一.传统优化方法的基本步骤—三步曲（4） 停止 选择一个初始解 最优性检验 向改进方向移动 开始 Y N

15 二.传统优化方法的局限性（1） 对问题中目标函数、约束函数有很高的要求——有显式表达，线性、连续、可微，且高阶可微
2. 只从一个初始点出发，难以进行并行、网络计算，难以提高计算效率

16 二.传统优化方法的局限性（2） 最优性达到的条件太苛刻——目标函数为凸，可行域为凸 在非双凸条件下，没有跳出局部最优解的能力

17 三.实际问题中对最优化方法的要求（1） 对问题的描述要宽松（目标和约束函数）——可以用一段程序来描述(程序中带判断、循环)，函数可以非连续、非凸、非可微、非显式 并不苛求最优解——通常满意解、理想解，甚至可行解就可以

18 三.实际问题中对最优化方法的要求（2） 计算快速、高效，可随时终止（根据时间定解的质量）
能够处理数据和信息的不确定性（如数据的模糊性，事件的随机性）

19 四.智能优化算法的产生与发展（1） 基于单点的元启发式算法： 1977年 Glover提出禁忌搜索 (TS)
1982年 Kirkpatrick提出模拟退火(SA) 1995年 Feo提出贪婪随机适应性搜索算法(GRASP) 1995年 Mladenovic提出可变邻域搜索(VNS) 1997年 Voudouris提出导向局域搜索(GLS)

20 四.智能优化算法的产生与发展（1） 进化算法： 1965年 Rechenberg等提出进化策略(ES)
1975年 Holland提出遗传算法(GA) 1995年 Fogel提出进化规划(EP) 1995年 Tackett提出遗传规划(GP) 1995年 Storn等提出差分进化(DE)

21 四.智能优化算法的产生与发展（2） 群体智能算法： 1995年 Kennedy等提出粒子群优化算法(PSO)
1995年 Dorigo提出蚁群算法(ACO) 2002年 Passino提出细菌觅食优化算法(BFOA) 2005年 Karaboga提出人工蜂群算法(ABC)

22 四.智能优化算法的产生与发展（3） 其他智能优化算法： 1994年 Reynolds提出文化算法(CA)
1998年 Linhares提出捕食搜索算法(PS) 2002年 Narayanan提出量子进化算法(QEA) 2004年 Wang提出群落选址算法(CLA)

23 五.应用前景局限性和研究方向、注意事项（1）
应用前景十分广阔 局限性——不能保证最优解，理论上不完备

24 五.应用前景局限性和研究方向、注意事项（2）
研究方向及注意事项 以应用为主，扩大面向新问题的应用；不要刻意做理论研究，若碰上也不拒绝 算法改进表现在以下几个方面：问题的描述、编码方法、算法构造及可行性修复策略 要进行大量的上机计算

25 五.应用前景局限性和研究方向、注意事项（3）
算例的选取 以下算例的说服力降序排列：网上的测试用例、文献中的例子、实际例子、随机产生的例子、自己编的例子 Benchmark的不断发展 如何检验算法的好坏：比较计算速度及消耗、可解规模、 （从不同的随机种子出发）达优率——客观公正与良心！

26 六.优化领域的新进展 随着人们关注的系统越来越复杂，最优化技术也相应不断发展 多目标环境 动态环境 多峰环境

27 六.优化领域的新进展 最优化方法的发展 1940s－1970s：数学规划阶段——目标和约束是解析函数

28 七.学习这门课需要具备的基础 信心、决心、热情 良好的外语能力 较为熟练的计算机编程能力 一定的数学基础