智 能 优 化 计 算,华东理工大学自动化系 刘漫丹 实验15楼221 64253078,课程名称 智能优化计算 教师联系方式 办公地点：实验十五楼221，Tel：64253078 E-mail： 课件下载： http:/e- (password) 上课时间地点 周二 34节，八/210 周四 56节，八/307,智能优化计算,华东理工大学自动化系 2007年,课程定位 解决的问题：优化问题 解决的方法：智能方法 数学工具 实用方法 考核方式 课堂讨论（抽签）或报告 作业（编程，2次）,智能优化计算,华东理工大学自动化系 2007年,内容安排 最优化问题概述 禁忌搜索算法(Tabu search) 模拟退火算法(Simulated Annealing) 遗传算法(Genetic Algorithm) 神经网络优化算法(Neural Network) 群智能算法，包括蚁群算法(Ant Colony Optimization)、粒子群算法(Particle Swarm Optimization) 广义领域搜索算法及其统一结构 课堂讨论及作业,智能优化计算,华东理工大学自动化系 2007年,参考书 1 邢文训, 谢金星. 现代优化计算方法. 北京: 清华大学出版社, 2005. 2 王凌. 智能优化算法及其应用. 北京: 清华大学出版社, 2001. 3 阎平凡, 张长水. 人工神经网络与模拟进化计算. 北京: 清华大学出版社, 2005.,智能优化计算,华东理工大学自动化系 2007年,参考书 4王小平, 曹立明. 遗传算法理论、应用与软件实现. 西安: 西安交通大学出版社, 2002. 5黄席樾等. 现代智能算法理论及应用. 北京：科学出版社, 2005. 6高尚, 杨静宇. 群智能算法及其应用. 北京: 中国水利水电出版社, 2006.,智能优化计算,华东理工大学自动化系 2007年,第一章 绪论,智能优化计算,华东理工大学自动化系 2007年,1.1 引言 1.1.1 优化问题 1.1.2 传统优化方法 1.1.3 现代优化方法 1.2 最优化问题及其分类 1.2.1 函数优化问题 1.2.2 组合优化问题 1.3 启发式算法 1.3.1 启发式算法的定义 1.3.2 启发式算法的分类 1.3.3 启发式算法的性能分析 1.4 计算复杂性与NP完全问题 1.4.1 计算复杂性的基本概念 1.4.2 P,NP,NP-C和NP-hard,智能优化计算,华东理工大学自动化系 2007年,1.1 引言,智能优化计算,华东理工大学自动化系 2007年,优化技术？ 以数学为基础，解决各种工程问题优化解 优化技术的用途 系统控制 人工智能 模式识别 生产调度 ,1.1.1 优化问题,1.1 引言,智能优化计算,华东理工大学自动化系 2007年,最优化问题的描述 最优化问题的数学模型的一般描述：,1.1.1 优化问题,1.1 引言,智能优化计算,华东理工大学自动化系 2007年,待解决的问题 连续性问题，以微积分为基础，规模较小 传统的优化方法 理论上的准确与完美，主要方法：线性与非线性规划、动态规划、多目标规划、整数规划等；排队论、库存论、对策论、决策论等。 传统的评价方法 算法收敛性、收敛速度,1.1.2 传统优化方法,1.1 引言,智能优化计算,华东理工大学自动化系 2007年,待解决的问题 离散性、不确定性、大规模 现代的优化方法 启发式算法（heuristic algorithm） 追求满意（近似解） 实用性强（解决实际工程问题） 现代的评价方法 算法复杂性,1.1.3 现代优化方法,1.2 最优化问题及其分类（函数优化和组合优化）,智能优化计算,华东理工大学自动化系 2007年,数学表述 难点 高维 多峰值,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,华东理工大学自动化系 2007年,测试函数（Benchmark问题） （1）Sphere Model 其最优状态和最优值为,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,华东理工大学自动化系 2007年,测试函数 （2）Schwefels Problem 2.22 其最优状态和最优值为,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,华东理工大学自动化系 2007年,测试函数 （3）Schwefels Problem 1.2 其最优状态和最优值为,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,华东理工大学自动化系 2007年,测试函数 （4）Schwefels Problem 2.21 其最优状态和最优值为,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,华东理工大学自动化系 2007年,测试函数 （5）Generalized Rosenbrocks Function 其最优状态和最优值为,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,华东理工大学自动化系 2007年,测试函数 （6）Step Function 其最优状态和最优值为,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,华东理工大学自动化系 2007年,测试函数 （6）Step Function,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,华东理工大学自动化系 2007年,测试函数 （7）Quartic Function i.e. Niose 其最优状态和最优值为,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,华东理工大学自动化系 2007年,测试函数 （8）Generalized Schwefels Problem 2.26 其最优状态和最优值为,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,华东理工大学自动化系 2007年,测试函数 （8）Generalized Schwefels Problem 2.26,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,华东理工大学自动化系 2007年,测试函数 （9）Generalized Rastrigins Function 其最优状态和最优值为,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,华东理工大学自动化系 2007年,测试函数 （10）Ackleys Function 其最优状态和最优值为,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,华东理工大学自动化系 2007年,测试函数 （10）Ackleys Function,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,华东理工大学自动化系 2007年,测试函数 （11）Generalized Griewank Function 其最优状态和最优值为,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,华东理工大学自动化系 2007年,测试函数 （11）Generalized Griewank Function,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,华东理工大学自动化系 2007年,测试函数 （12）Generalized Penalized Function 其最优状态和最优值为,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,华东理工大学自动化系 2007年,测试函数 其中，,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,华东理工大学自动化系 2007年,测试函数 （13）Generalized Penalized Function 其最优状态和最优值为,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,华东理工大学自动化系 2007年,测试函数 （14）Shekels Foxholes Function 其最优状态和最优值为,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,华东理工大学自动化系 2007年,测试函数 其中，,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,华东理工大学自动化系 2007年,测试函数 （15）Kowaliks Function 其最优状态和最优值为,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,华东理工大学自动化系 2007年,测试函数 其中，,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,华东理工大学自动化系 2007年,测试函数 （16）Six-Hump Camel-Back Function 其最优状态和最优值为,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,华东理工大学自动化系 2007年,测试函数 （17）Branin Function 其最优状态和最优值为,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,华东理工大学自动化系 2007年,测试函数 （18）Goldstein-Price Function 其最优状态和最优值为,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,华东理工大学自动化系 2007年,测试函数 （19）Hartmans Function 其最优状态和最优值为,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,华东理工大学自动化系 2007年,测试函数 其中，,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,华东理工大学自动化系 2007年,测试函数 （20）Hartmans Function 其最优状态和最优值为,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,华东理工大学自动化系 2007年,测试函数 其中，,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,华东理工大学自动化系 2007年,测试函数 （21）Shekels Family m分别取5，7和10，其最优状态和最优值为,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,华东理工大学自动化系 2007年,测试函数 其中，,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,华东理工大学自动化系 2007年,测试函数 （22）J. D. Schaffer 其最优状态和最优值为,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,华东理工大学自动化系 2007年,测试函数 （22）J. D. Schaffer 此函数在距全局最优点大约3.14范围内存在无穷多个局部极小将其包围，并且函数强烈振荡。,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,华东理工大学自动化系 2007年,有约束的函数优化 常用受约束测试函数； 影响因素： （1）曲面拓扑性质，线性或凸函数比无规律的函数更容易求解； （2）可行区域的疏密程度，通常以可行区域占整个搜索空间的比值来度量；,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,华东理工大学自动化系 2007年,有约束的函数优化 常用受约束测试函数； 影响因素： （3）整体最优解与可行区域最优解之比； （4）在最优解处活跃约束的数目，活跃约束数目越多则最