智能优化计算.ppt

1、智 能 优 化 计 算,叶洪涛yehongtao,课程定位 解决的问题：优化问题 解决的方法：智能方法 数学工具 实用方法 考核方式 交一篇文献综述（4-8页）A4 纸，五号字体，左边装钉，由各班学习委员6月22日上午10点交4D303。 综述的写法和格式请参考例子，请在公共信箱中下载 dkxdsp 密码：dkxyht,智能优化计算,内容安排 智能算法在污水处理系统中的应用研究 最优化问题概述 遗传算法(Genetic Algorithm),智能优化计算,第一章 绪论,智能优化计算,1.1 引言 1.1.1 优化问题 1.1.2 传统优化方法 1.1.3 现代优化方法

2、 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,智能优化计算,1.1 引言,智能优化计算,优化技术？ 以数学为基础，解决各种工程问题优化解 优化技术的用途 系统控制 人工智能 模式识别 生产调度 ,1.1.1 优化问题,1.1 引言,智能优化计算,最优化问题的描述 最优化问题的数学模型的一般描述：,1.1.1 优化问题,1.1 引言,

3、智能优化计算,待解决的问题 连续性问题，以微积分为基础，规模较小 传统的优化方法 理论上的准确与完美，主要方法：线性与非线性规划、动态规划、多目标规划、整数规划等；排队论、库存论、对策论、决策论等。 传统的评价方法 算法收敛性、收敛速度,1.1.2 传统优化方法,1.1 引言,智能优化计算,待解决的问题 离散性、不确定性、大规模 现代的优化方法 启发式算法（heuristic algorithm） 追求满意（近似解） 实用性强（解决实际工程问题） 现代的评价方法 算法复杂性,1.1.3 现代优化方法,1.2 最优化问题及其分类（函数优化和组合优化）,智能优化计算,数学表述 难点 高维 多峰值,

4、1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,测试函数（Benchmark问题） （1）Sphere Model 其最优状态和最优值为,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,测试函数 （2）Schwefels Problem 2.22 其最优状态和最优值为,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,测试函数 （3）Schwefels Problem 1.2 其最优状态和最优值为,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,测试函数 （4）Schwefels Problem 2.21 其最优状态

5、和最优值为,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,测试函数 （5）Generalized Rosenbrocks Function 其最优状态和最优值为,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,测试函数 （6）Step Function 其最优状态和最优值为,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,测试函数 （6）Step Function,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,测试函数 （7）Quartic Function i.e. Niose 其最优状态和最优值为,1.2.

6、1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,测试函数 （8）Generalized Schwefels Problem 2.26 其最优状态和最优值为,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,测试函数 （8）Generalized Schwefels Problem 2.26,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,测试函数 （9）Generalized Rastrigins Function 其最优状态和最优值为,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,测试函数 （10）Ackleys Fun

7、ction 其最优状态和最优值为,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,测试函数 （10）Ackleys Function,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,测试函数 （11）Generalized Griewank Function 其最优状态和最优值为,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,测试函数 （11）Generalized Griewank Function,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,测试函数 （12）Generalized Penalized F

8、unction 其最优状态和最优值为,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,测试函数 其中，,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,测试函数 （13）Generalized Penalized Function 其最优状态和最优值为,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,测试函数 （14）Shekels Foxholes Function 其最优状态和最优值为,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,测试函数 其中，,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优

9、化计算,测试函数 （15）Kowaliks Function 其最优状态和最优值为,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,测试函数 其中，,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,测试函数 （16）Six-Hump Camel-Back Function 其最优状态和最优值为,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,测试函数 （17）Branin Function 其最优状态和最优值为,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,测试函数 （18）Goldstein-Price Fun

10、ction 其最优状态和最优值为,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,测试函数 （19）Hartmans Function 其最优状态和最优值为,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,测试函数 其中，,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,测试函数 （20）Hartmans Function 其最优状态和最优值为,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,测试函数 其中，,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,测试函数 （21）Shekels Fa

11、mily m分别取5，7和10，其最优状态和最优值为,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,测试函数 其中，,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,测试函数 （22）J. D. Schaffer 其最优状态和最优值为,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,测试函数 （22）J. D. Schaffer 此函数在距全局最优点大约3.14范围内存在无穷多个局部极小将其包围，并且函数强烈振荡。,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,有约束的函数优化 常用受约束测试函数； 影响因素：

12、 （1）曲面拓扑性质，线性或凸函数比无规律的函数更容易求解； （2）可行区域的疏密程度，通常以可行区域占整个搜索空间的比值来度量；,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,有约束的函数优化 常用受约束测试函数； 影响因素： （3）整体最优解与可行区域最优解之比； （4）在最优解处活跃约束的数目，活跃约束数目越多则最优解离可行区域的边界越近。,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,数学表述 所属范畴 涉及离散事件的最优编排、分类、次序筛选等问题，是运筹学的一个重要分支。,1.2.2 组合优化问题,1.2 最优化问题及其分类,智能优化计算,

13、典型问题旅行商问题（Traveling salesman problem, TSP） 给定n个城市和两两 城市之间的距离，要 求确定一条经过各城 市当且仅当一次的最 短路线。,1.2.2 组合优化问题,1,2,3,4,12,1,8,10,3,2,1.2 最优化问题及其分类,智能优化计算,典型问题旅行商问题（Traveling salesman problem, TSP） 计算复杂度：指数灾难,1.2.2 组合优化问题,1.2 最优化问题及其分类,智能优化计算,典型问题加工调度问题（Scheduling problem,如Flow-shop, Job-shop） Job-shop：n个工件在m台

14、机器上加工，Oij：第i个工件在第j台机器上的操作， Tij：相应的操作时间，已知。事先给定各工件在各机器上的加工次序（技术约束条件），要求确定与技术约束条件相容的各机器上所有工件的加工顺序，使得加工性能指标达到最优。 若各工件技术约束条件相同，转化为Flow-shop。,1.2.2 组合优化问题,1.2 最优化问题及其分类,智能优化计算,典型问题加工调度问题（Scheduling problem,如Flow-shop, Job-shop） 计算复杂性：可能的排列方式有（n！）m 多目标优化 动态性 状态相依,1.2.2 组合优化问题,1.2 最优化问题及其分类,智能优化计算,典型问题01背包

15、问题（Knapsack problem） 对于n个体积为ai、价值分别为ci的物品，如何将它们装入总体积为b的背包中，使得所选物品的总价值最大。,1.2.2 组合优化问题,背包问题的贪婪算法,1.2 最优化问题及其分类,智能优化计算,典型问题装箱问题（Bin packing problem） 有n个尺寸不超过1的物品，有数个尺寸为1的箱子，如何将这些物品装入箱子，使得所需箱子的个数最少。,1.2.2 组合优化问题,1.2 最优化问题及其分类,智能优化计算,典型问题图着色问题（Graph coloring problem） 对于n个顶点的无环图G，要求对其各个顶点进行着色，使得任意两个相邻的顶点

16、都有不同的颜色，且所用颜色种类最少。,1.2.2 组合优化问题,C1：第一种颜色 C2：第二种颜色 C3：第三种颜色,1.2 最优化问题及其分类,智能优化计算,典型问题聚类问题（Clustering problem） m维空间上的n个模式Xi|i=1,2,n，要求聚成k类，使得各类本身内的点最相近，如要求 其中Rp为第p类的中心，即 其中，p=1,2,k，np为第p类中的点数。,1.2.2 组合优化问题,1.2 最优化问题及其分类,智能优化计算,Benchmark问题 n城市TSP问题（n=30，50，75） Hopfield-10城市TSP问题 Grotschel-442城市TSP问题 Ca

17、r n Flow-shop问题（n=1,2,8） Rec n Flow-shop问题（n=1,3,5,39,41） FT n or MT n Job-shop问题（n=6,10,20） LA n Job-shop问题（n=1,6,11,16,21,26,31,36）,1.2.2 组合优化问题,30城市TSP问题（d*=423.741 by D B Fogel） 41 94; 37 84; 54 67; 25 62; 7 64; 2 99; 68 58; 71 44; 54 62; 83 69; 64 60; 18 54; 22 60; 83 46; 91 38; 25 38; 24 42; 5

18、8 69; 71 71; 74 78; 87 76; 18 40; 13 40; 82 7; 62 32; 58 35; 45 21; 41 26; 44 35; 4 50,1.3 启发式算法,智能优化计算,最优算法 一个问题的最优算法求得该问题每个实例的最优解； 启发式算法 一个基于直观或经验构造的算法，在可接受的花费（计算时间、占用空间等）下给出待解决优化问题每一个实例的一个可行解，该可行解与最优解的偏离程度不一定事先可以预计。,1.3.1 启发式算法的定义,1.3 启发式算法,智能优化计算,启发式算法的特点 是一种技术； 不能保证所得解的最优性； 启发式算法的发展历史 20世纪40年代起步 20世纪6070年代被鄙视 20世纪70年代观点转变 20世纪80年代至今研究热潮,1.3.1 启发式算法的定义,1.3 启发式算法,智能优化计算,例子背包问题的贪婪算法（Greedy algorithm） 贪婪算法：采用逐步构造最优解的方法。 在每个阶段，都作出一个看上去最优的决策（在一定的标准下）。决策一旦作出，就不可再更改。作出贪婪决策的依据称为贪婪准则（greedy criterion）。,1.3.1 启发式算法的定义,1.3 启发式算法,智能优化计算,例子背