《智能优化计算》PPT课件.ppt
智 能 优 化 计 算,叶洪涛,课程定位 解决的问题：优化问题 解决的方法：智能方法 数学工具 实用方法考核方式 交一篇文献综述（4-8页）A4 纸，五号字体，左边装钉，由各班学习委员6月22日上午10点交4D303。综述的写法和格式请参考例子，请在公共信箱中下载 密码：dkxyht,智能优化计算,内容安排 智能算法在污水处理系统中的应用研究 最优化问题概述 遗传算法(Genetic Algorithm),智能优化计算,第一章 绪论,智能优化计算,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,智能优化计算,1.1 引言,智能优化计算,优化技术？以数学为基础，解决各种工程问题优化解优化技术的用途 系统控制 人工智能 模式识别 生产调度,1.1.1 优化问题,1.1 引言,智能优化计算,最优化问题的描述 最优化问题的数学模型的一般描述：,1.1.1 优化问题,1.1 引言,智能优化计算,待解决的问题 连续性问题，以微积分为基础，规模较小传统的优化方法 理论上的准确与完美，主要方法：线性与非线性规划、动态规划、多目标规划、整数规划等；排队论、库存论、对策论、决策论等。传统的评价方法 算法收敛性、收敛速度,1.1.2 传统优化方法,1.1 引言,智能优化计算,待解决的问题 离散性、不确定性、大规模现代的优化方法 启发式算法（heuristic algorithm）追求满意（近似解）实用性强（解决实际工程问题）现代的评价方法 算法复杂性,1.1.3 现代优化方法,1.2 最优化问题及其分类（函数优化和组合优化）,智能优化计算,数学表述难点 高维 多峰值,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 其最优状态和最优值为,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.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 Function 其最优状态和最优值为,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 Function 其最优状态和最优值为,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 最优化问题及其分类,智能优化计算,测试函数（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 Function 其最优状态和最优值为,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 Family 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 最优化问题及其分类,智能优化计算,有约束的函数优化 常用受约束测试函数；影响因素：（1）曲面拓扑性质，线性或凸函数比无规律的函数更容易求解；（2）可行区域的疏密程度，通常以可行区域占整个搜索空间的比值来度量；,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,有约束的函数优化 常用受约束测试函数；影响因素：（3）整体最优解与可行区域最优解之比；（4）在最优解处活跃约束的数目，活跃约束数目越多则最优解离可行区域的边界越近。,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,数学表述所属范畴 涉及离散事件的最优编排、分类、次序筛选等问题，是运筹学的一个重要分支。,1.2.2 组合优化问题,1.2 最优化问题及其分类,智能优化计算,典型问题旅行商问题（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台机器上加工，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背包问题（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，要求对其各个顶点进行着色，使得任意两个相邻的顶点都有不同的颜色，且所用颜色种类最少。,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问题 Car 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;58 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 启发式算法,智能优化计算,例子背包问题的贪婪算法（Greedy algorithm）STEP 1 STEP 2,1.3.1 启发式算法的定义,1.3 启发式算法,智能优化计算,启发式算法的优点 1.模型误差、数据不精确性、参数估计误差等可能造成最优算法的解比启发式算法的解更差；2.复杂问题无法求得最优算法或最优算法太复杂；3.简单易行，直观，程序简单。启发式算法的缺点 1.不能保证最优；2.不稳定；3.依赖于实际问题、设计者经验。,1.3.1 启发式算法的定义,1.3 启发式算法,智能优化计算,简单直观的算法 一步算法：不在两个可行解之间比较，在未终止的迭代过程中，得到的中间解有可能不是可行解；例：背包问题的贪婪算法 改进算法：迭代过程是从一个可行解到另一个可行解变换，通过两个解的比较而选择好的解，直到满足一定的要求为止；例：TSP问题的2opt方法,1.3.2 启发式算法的分类,1.3 启发式算法,智能优化计算,数学规划算法 用连续优化（如线性规划）的方法求解组合优化问题（如整数线性规划模型），其中包括一些启发式规则。基于数学规划的理论。,1.3.2 启发式算法的分类,1.3 启发式算法,智能优化计算,现代优化算法 禁忌搜索算法 模拟退火算法 遗传算法 人工神经网络 蚁群算法 粒子群算法 混合算法,1.3.2 启发式算法的分类,特点：基于客观世界中的一些自然现象；建立在计算机迭代计算的基础上；具有普适性，可解决实际应用问题。,
