智能优化计算华东理工大学.ppt

智 能 优 化 计 算,华东理工大学自动化系 刘漫丹实验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）在最优解处活跃约束的数目，活跃约束数目越多则最优解离可行区域的边界越近。,1.2.1 函数优化问题,1.2 最优化问题及其分类,智能优化计算,华东理工大学自动化系 2007年,数学表述所属范畴 涉及离散事件的最优编排、分类、次序筛选等问题，是运筹学的一个重要分支。,1.2.2 组合优化问题,1.2 最优化问题及其分类,智能优化计算,华东理工大学自动化系 2007年,典型问题旅行商问题（Traveling salesman problem,TSP）给定n个城市和两两 城市之间的距离，要 求确定一条经过各城 市当且仅当一次的最 短路线。,1.2.2 组合优化问题,1,2,3,4,12,1,8,10,3,2,1.2 最优化问题及其分类,智能优化计算,华东理工大学自动化系 2007年,典型问题旅行商问题（Traveling salesman problem,TSP）计算复杂度：指数灾难,1.2.2 组合优化问题,1.2 最优化问题及其分类,智能优化计算,华东理工大学自动化系 2007年,典型问题加工调度问题（Scheduling problem,如Flow-shop,Job-shop）Job-shop：n个工件在m台机器上加工，Oij：第i个工件在第j台机器上的操作，Tij：相应的操作时间，已知。事先给定各工件在各机器上的加工次序（技术约束条件），要求确定与技术约束条件相容的各机器上所有工件的加工顺序，使得加工性能指标达到最优。若各工件技术约束条件相同，转化为Flow-shop。,1.2.2 组合优化问题,1.2 最优化问题及其分类,智能优化计算,华东理工大学自动化系 2007年,典型问题加工调度问题（Scheduling problem,如Flow-shop,Job-shop）计算复杂性：可能的排列方式有（n！）m 多目标优化 动态性 状态相依,1.2.2 组合优化问题,1.2 最优化问题及其分类,智能优化计算,华东理工大学自动化系 2007年,典型问题01背包问题（Knapsack problem）对于n个体积为ai、价值分别为ci的物品，如何将它们装入总体积为b的背包中，使得所选物品的总价值最大。,1.2.2 组合优化问题,背包问题的贪婪算法,1.2 最优化问题及其分类,智能优化计算,华东理工大学自动化系 2007年,典型问题装箱问题（Bin packing problem）有n个尺寸不超过1的物品，有数个尺寸为1的箱子，如何将这些物品装入箱子，使得所需箱子的个数最少。,1.2.2 组合优化问题,1.2 最优化问题及其分类,智能优化计算,华东理工大学自动化系 2007年,典型问题图着色问题（Graph coloring problem）对于n个顶点的无环图G，要求对其各个顶点进行着色，使得任意两个相邻的顶点都有不同的颜色，且所用颜色种类最少。,1.2.2 组合优化问题,C1：第一种颜色C2：第二种颜色C3：第三种颜色,1.2 最优化问题及其分类,智能优化计算,华东理工大学自动化系 2007年,典型问题聚类问题（Clustering problem）m维空间上的n个模式Xi|i=1,2,n，要求聚成k类，使得各类本身内的点最相近，如要求 其中Rp为第p类的中心，即 其中，p=1,2,k，np为第p类中的点数。,1.2.2 组合优化问题,1.2 最优化问题及其分类,智能优化计算,华东理工大学自动化系 2007年,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 启发式算法,智能优化计算,华东理工大学自动化系 2007年,最优算法 一个问题的最优算法求得该问题每个实例的最优解；启发式算法 一个基于直观或经验构造的算法，在可接受的花费（计算时间、占用空间等）下给出待解决优化问题每一个实例的一个可行解，该可行解与最优解的偏离程度不一定事先可以预计。,1.3.1 启发式算法的定义,1.3 启发式算法,智能优化计算,华东理工大学自动化系 2007年,启发式算法的特点 是一种技术；不能保证所得解的最优性；启发式算法的发展历史 20世纪40年代起步 20世纪6070年代被鄙视 20世纪70年代观点转变 20世纪80年代至今研究热潮,1.3.1 启发式算法的定义,1.3 启发式算法,智能优化计算,华东理工大学自动化系 2007年,例子背包问题的贪婪算法（Greedy algorithm）贪婪算法：采用逐步构造最优解的方法。在每个阶段，都作出一个看上去最优的决策（在一定的标准下）。决策一旦作出，就不可再更改。作出贪婪决策的依据称为贪婪准则（greedy criterion）。,1.3.1 启发式算法的定义,1.3 启发式算法,智能优化计算,华东理工大学自动化系 2007年,例子背包问题的贪婪算法（Greedy algorithm）STEP 1 STEP 2,1.3.1 启发式算法的定义,1.3 启发式算法,智能优化计算,华东理工大学自动化系 2007年,启发式算法的优点 1.模型误差、数据不精确性、参数估计误差等可能造成最优算法的解比启发式算法的解更差；2.复杂问题无法求得最优算法或最优算法太复杂；3.简单易行，直观，程序简单。启发式算法的缺点 1.不能保证最优；2.不稳定；3.依赖于实际问题、设计者经验。,1.3.1 启发式算法的定义,1.3 启发式算法,智能优化计算,华东理工大学自动化系 2007年,简单直观的算法 一步算法：不在两个可行解之间比较，在未终止的迭代过程中，得到的中间解有可能不是可行解；例：背包问题的贪婪算法 改进算法：迭代过程是从一个可行解到另一个可行解变换，通过两个解的比较而选择好的解，直到满足一定的要求为止；例：TSP问题的2opt方法,1.3.2 启发式算法的分类,1.3 启发式算法,智能优化计算,华东理工大学自动化系 2007年,数学规划算法 用连续优化（如线性规划）的方法求解组合优化问题（如整数线性规划模型），其中包括一些启发式规则。基于数学规划的理论。,1.3.2 启发式算法的分类,1.3 启发式算法,智能优化计算,华东理工大学自动化系 2007年,现代优化算法 禁忌搜索算法 模拟退火算法 遗传算法 人工神经网络 蚁群算法 粒子群算法 混合算法,1.3.2 启发式算法的分类,特点：基于客观世界中的一些自然现象；建立在计算机迭代计算的基础上；具有普适性，可解决实际应用问题。,1.3 启发式算法,智能优化计算,华东理工大学自动化系 2007年,评价算法优劣的指标 算法的复杂性（计算效率）解的偏离程度（计算效果）算法的稳健性（不同实例、不同时间、不同起点的差异）评价算法优劣的手段 最坏情况分析（纯理论）概率分析（理论分析）计算模拟分析（统计特性）,1.3.3 启发式算法的性能分析,1.4 计算复杂性与NP完全问题,智能优化计算,华东理工大学自动化系 2007年,时间复杂性和空间复杂性概念 算法的时间复杂性：算法对时间的需要量（加、减、乘、除、比较、读、写等操作的总次数）；算法的空间复杂性：算法对空间的需要量（存储空间的大小，二进制位数）；问题的时间复杂性：所有算法中时间复杂性最小的算法时间复杂性；问题的空间复杂性：所有算法中空间复杂性最小的算法空间复杂性；,1.4.1 计算复杂性的基本概念,1.4 计算复杂性与NP完全问题,智能优化计算,华东理工大学自动化系 2007年,复杂性问题分类 P类、NP类、NP完全类复杂性表示方法 复杂性表示为问题规模n（如TSP的n）的函数，时间复杂性T(n)，关键操作的次数；空间复杂性S(n)，占用的存储单元数量；,1.4.1 计算复杂性的基本概念,1.4 计算复杂性与NP完全问题,智能优化计算,华东理工大学自动化系 2007年,复杂性表示方法 若算法A的时间复杂性为TA(n)=O(p(n)，O(p(n)为复杂性函数p(n)主要项的阶，且p(n)为n的多项式函数，则称算法A为多项式算法。当不存在多项式函数p(n)时，称相应的算法为非多项式时间算法或指数时间算法；随着变量的增加，多项式函数增长的速度比指数函数和非多项式函数增长的速度要慢得多。,1.4.1 计算复杂性的基本概念,1.4 计算复杂性与NP完全问题,智能优化计算,华东理工大学自动化系 2007年,P类问题（deterministic polynomial）具有多项式时间求解算法的问题类 迄今为止，许多组合优化问题都没有找到求最优解的多项式时间算法。NP类问题(Nondeterministic polynomial)定义1 实例是问题的特殊表现，所谓实例就是确定了描述问题特性的所有参数的问题，其中参数值称为数据，这些数据占有计算机的空间称为实例的输入长度。,1.4.2 P,NP,NP-C和NP-hard,1.4 计算复杂性与NP完全问题,智能优化计算,华东理工大学自动化系 2007年,NP类问题(Nondeterministic polynomial)定义2 若一个问题的每个实例只有“是”或“否”两种回答，则称该问题为判定问题。例，TSP的判定问题：给定z，是否存在n个城市的一个排列W，使得f(W)z。满足f(W)z的一个排列W称为判定问题的“是”答案（可行解）。,1.4.2 P,NP,NP-C和NP-hard,1.4 计算复杂性与NP完全问题,智能优化计算,华东理工大学自动化系 2007年,NP类问题(Nondeterministic polynomial)若存在一个多项式 g(x)和一个验证算法 H，对一类判定问题 A 的任何一个“是”的判定实例 I 都存在一个字符串 S 是 I 的“是”回答，满足其输入长度 d(S)不超过 g(d(I)（其中 d(I)为 I 的输入长度），且验证算法验证 S 为 I 的“是”回答的计算时间不超过 g(d(I)，则称判定问题 A 为非多项式确定问题，简称 NP问题。NP类问题是比P问题更为广泛的问题类。,1.4.2 P,NP,NP-C和NP-hard,简单地理解 如果计算工作量在计算数据规模n的多项式（如n，n2，n3等）的范围内，则计算花费的机时是可以接受的，该问题称为P问题；有些问题尚未证实是否属于P类，又未找到有效算法，则称NP问题。,1.4 计算复杂性与NP完全问题,智能优化计算,华东理工大学自动化系 2007年,1.4.2 P,NP,NP-C和NP-hard,1.4 计算复杂性与NP完全问题,智能优化计算,华东理工大学自动化系 2007年,NPC（NP-Complete）和NPhard类问题 Cook在1971年给出并证明了有一类问题具有下述性质（1）这类问题中任何一个问题至今未找出多项式时间算法；（2）如果这类问题中的一个问题存在有多项式时间算法，那么这类问题都有多项式时间的算法，这类问题中的每一个问题称为NP完全问题，这个问题的集合简记NPC。,1.4.2 P,NP,NP-C和NP-hard,NPC（NP-Complete）和NPhard类问题 定义：称判定问题ANP-C，若ANP 且NP中的任何一个问题可多项式规约为问题A。称判定问题A为NPhard，只要上述第二个条件成立。,1.4 计算复杂性与NP完全问题,智能优化计算,华东理工大学自动化系 2007年,1.4.2 P,NP,NP-C和NP-hard,1,2,四类问题的关系 NP-C问题具有重要的实际意义和工程背景:第一个NP完全问题（Cook定理 1971）六个NP完全问题（Karp 1972)更多的NP完全问题1979年：300多个1998年：2000多个 TSP问题、背包问题、装箱问题、Job-shop和Flow-shop问题、集合覆盖问题等均是NP-C问题。,1.4 计算复杂性与NP完全问题,智能优化计算,华东理工大学自动化系 2007年,1.4.2 P,NP,NP-C和NP-hard,第一章 结束,智能优化计算,华东理工大学自动化系 2007年,