AAI现代优化算法

1、第一章 优化计算方法2022-5-16Advanced AI1/33高级人工智能高级人工智能引言引言 优化问题优化问题 传统优化方法传统优化方法 现代优化方法现代优化方法 最优化问题及其分类最优化问题及其分类 函数优化问题函数优化问题 组合优化问题组合优化问题 启发式算法启发式算法 启发式算法的定义启发式算法的定义 启发式算法的分类启发式算法的分类 启发式算法的性能分析启发式算法的性能分析 计算复杂性与计算复杂性与NP完全问题完全问题 计算复杂性的基本概念计算复杂性的基本概念 P,NP,NP-C和和NP-hard 第一章 优化计算方法2022-5-16Advanced AI2/33 n优化技术

2、？优化技术？ 以数学为基础，解决各种工程问题优化解以数学为基础，解决各种工程问题优化解n优化技术的用途优化技术的用途 系统控制系统控制 人工智能人工智能 模式识别模式识别 生产调度生产调度第一章 优化计算方法2022-5-16Advanced AI3/33最优化问题的描述最优化问题的描述最优化问题的数学模型的一般描述：最优化问题的数学模型的一般描述：Dxxgtsxf , 0)( . .)( min第一章 优化计算方法2022-5-16Advanced AI4/33n待解决的问题待解决的问题 连续性问题，以微积分为基础，规模较小连续性问题，以微积分为基础，规模较小n传统的优化方法传统的优化方法

3、理论上的准确与完美，主要方法：线性与非线性理论上的准确与完美，主要方法：线性与非线性规划、动态规划、多目标规划、整数规划等；排规划、动态规划、多目标规划、整数规划等；排队论、库存论、对策论、决策论等。队论、库存论、对策论、决策论等。 n传统的评价方法传统的评价方法 算法收敛性、收敛速度算法收敛性、收敛速度牛顿牛顿第一章 优化计算方法2022-5-16Advanced AI5/33n待解决的问题待解决的问题 离散性、不确定性、大规模离散性、不确定性、大规模n现代的优化方法现代的优化方法 启发式算法（启发式算法（heuristic algorithm） 追求满意（近似解）追求满意（近似解） 实用性

4、强（解决实际工程问题）实用性强（解决实际工程问题） n现代的评价方法现代的评价方法 算法复杂性算法复杂性第一章 优化计算方法2022-5-16Advanced AI6/33n 数学表述数学表述n 难点难点u 高维，多峰值高维，多峰值minminmin : () :()()nSRfSRnfSXf XSXSf Xf X令 为上的有界子集（变量的定义域）为 维实值函数函数 在 域上全局最小化就是寻求点使得在 域上全局最小，即第一章 优化计算方法2022-5-16Advanced AI7/33 Sphere Model其最优状态和最优值为100| ,)(12iniixxXf0)0 , 0 , 0()(

5、min(*fXf第一章 优化计算方法2022-5-16Advanced AI8/33n测试函数 Schwefels Problem其最优状态和最优值为10| , |)(11ininiiixxxXf0)0 , 0 , 0()(min(*fXf第一章 优化计算方法2022-5-16Advanced AI9/33n测试函数 Generalized Rosenbrocks Function其最优状态和最优值为30| , )1 ()(100)(112221iniiiixxxxXf0) 1 , 1 , 1 ()(min(*fXf第一章 优化计算方法2022-5-16Advanced AI10/33n测试函

6、数测试函数 J. D. Schaffer 其最优状态和最优值为其最优状态和最优值为 1)0 , 0()(min(* fXf100| , 5 . 0)(001. 01 5 . 0sin)(2222122212ixxxxxXf第一章 优化计算方法2022-5-16Advanced AI11/33 此函数在距全局最优点大约此函数在距全局最优点大约3.14范围内存在无范围内存在无穷多个局部极小将其包围，并且函数强烈振荡。穷多个局部极小将其包围，并且函数强烈振荡。第一章 优化计算方法2022-5-16Advanced AI12/33有约束的函数优化有约束的函数优化n常用受约束测试函数；常用受约束测试函数

7、； 影响因素：影响因素： （1）曲面拓扑性质，线性或凸函数比无规律的函）曲面拓扑性质，线性或凸函数比无规律的函数更容易求解；数更容易求解； （2）可行区域的疏密程度，通常以可行区域占整）可行区域的疏密程度，通常以可行区域占整个搜索空间的比值来度量；个搜索空间的比值来度量； （3）整体最优解与可行区域最优解之比；）整体最优解与可行区域最优解之比； （4）在最优解处活跃约束的数目，活跃约束数目）在最优解处活跃约束的数目，活跃约束数目越多则最优解离可行区域的边界越近。越多则最优解离可行区域的边界越近。第一章 优化计算方法2022-5-16Advanced AI13/33n数学表述n所属范畴 涉及离散

8、事件的最优编排、分类、次序筛选等问题，涉及离散事件的最优编排、分类、次序筛选等问题，是运筹学的一个重要分支。是运筹学的一个重要分支。 ，构成,21的解空间为所有状态令ns,ss要求寻找最对应的目标函数值为状态,)(iissC。使得优解)(min)(,*iisCsCss第一章 优化计算方法2022-5-16Advanced AI14/33n典型问题典型问题旅行商问题（旅行商问题（Traveling salesman problem, TSP） 给定给定n个城市和两两个城市和两两 城市之间的距离，要城市之间的距离，要 求确定一条经过各城求确定一条经过各城 市当且仅当一次的最市当且仅当一次的最 短路

9、线。短路线。123412181032第一章 优化计算方法2022-5-16Advanced AI15/33n典型问题典型问题旅行商问题（旅行商问题（Traveling salesman problem, TSP） 计算复杂度：指数灾难计算复杂度：指数灾难城市数城市数2425262728293031计算计算时间时间1sec24sec10min4.3hour4.9day136.5day10.8year325year第一章 优化计算方法2022-5-16Advanced AI16/33n典型问题典型问题加工调度问题（加工调度问题（Scheduling problem,如如Flow-shop, Job

10、-shop） Job-shop：n个工件在个工件在m台机器上加工，台机器上加工，Oij：第：第i个个工件在第工件在第j台机器上的操作，台机器上的操作， Tij：相应的操作时间，：相应的操作时间，已知。事先给定各工件在各机器上的加工次序（技已知。事先给定各工件在各机器上的加工次序（技术约束条件），要求确定与技术约束条件相容的各术约束条件），要求确定与技术约束条件相容的各机器上所有工件的加工顺序，使得加工性能指标达机器上所有工件的加工顺序，使得加工性能指标达到最优。到最优。 若各工件技术约束条件相同，转化为若各工件技术约束条件相同，转化为Flow-shop。第一章 优化计算方法2022-5-16A

11、dvanced AI17/33n计算复杂性：可能的排列方式有（计算复杂性：可能的排列方式有（n！）！）m 多目标优化多目标优化 动态性动态性 状态相依状态相依计算资源的占用：时间，空间。计算资源的占用：时间，空间。第一章 优化计算方法2022-5-16Advanced AI18/33n典型问题典型问题01背包问题（背包问题（Knapsack problem） 对于对于n个体积为个体积为ai、价值分别为、价值分别为ci的物品，如何将它的物品，如何将它们装入总体积为们装入总体积为b的背包中，使得所选物品的总价的背包中，使得所选物品的总价值最大。值最大。n1n1Max . . 0,1,1,2,iii

12、iiiic xstc xbxin第一章 优化计算方法2022-5-16Advanced AI19/33n典型问题典型问题装箱问题（装箱问题（Bin packing problem） 有有n个尺寸不超过个尺寸不超过1的物品，有数个尺寸为的物品，有数个尺寸为1的箱子，的箱子，如何将这些物品装入箱子，使得所需箱子的个数最如何将这些物品装入箱子，使得所需箱子的个数最少。少。第一章 优化计算方法2022-5-16Advanced AI20/33n典型问题典型问题图着色问题（图着色问题（Graph coloring problem） 对于对于n个顶点的无环图个顶点的无环图G，要求对其各个顶点进行着色，使，

13、要求对其各个顶点进行着色，使得任意两个相邻的顶点都有不同的颜色，且所用颜色种类得任意两个相邻的顶点都有不同的颜色，且所用颜色种类最少。最少。C1C1C2C3C2ABDCEC1：第一第一种颜色种颜色C2：第二第二种颜色种颜色C3：第三第三种颜色种颜色第一章 优化计算方法2022-5-16Advanced AI21/33n典型问题典型问题聚类问题（聚类问题（Clustering problem） m维空间上的维空间上的n个模式个模式Xi|i=1,2,n，要求聚成，要求聚成k类，使得各类，使得各类本身内的点最相近，如要求类本身内的点最相近，如要求 其中其中Rp为第为第p类的中心，即类的中心，即 其中

14、，其中，p=1,2,k，np为第为第p类中的点数。类中的点数。最小 1)(2nippiRXpnippipnXR1)(/第一章 优化计算方法2022-5-16Advanced AI22/33nBenchmark问题问题 n城市城市TSP问题（问题（n=30，50，75） 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; 7

15、1 71; 74 78; 87 76; 18 40; 13 40; 82 7; 62 32; 58 35; 45 21; 41 26; 44 35; 4 50第一章 优化计算方法2022-5-16Advanced AI23/33n最优算法最优算法 一个问题的最优算法求得该问题每个实例的最优一个问题的最优算法求得该问题每个实例的最优解；解；n启发式算法启发式算法 一个基于直观或经验构造的算法，在可接受的花一个基于直观或经验构造的算法，在可接受的花费（计算时间、占用空间等）下给出待解决优化费（计算时间、占用空间等）下给出待解决优化问题每一个实例的一个可行解，该可行解与最优问题每一个实例的一个可行解

16、，该可行解与最优解的偏离程度不一定事先可以预计。解的偏离程度不一定事先可以预计。第一章 优化计算方法2022-5-16Advanced AI24/33n启发式算法的特点启发式算法的特点 是一种技术；是一种技术； 不能保证所得解的最优性；不能保证所得解的最优性；n启发式算法的发展历史启发式算法的发展历史 20世纪世纪40年代年代起步起步 20世纪世纪6070年代年代被鄙视被鄙视 20世纪世纪70年代年代观点转变观点转变 20世纪世纪80年代至今年代至今研究热潮研究热潮第一章 优化计算方法2022-5-16Advanced AI25/33n例子例子背包问题的贪婪算法（背包问题的贪婪算法（Greed

17、y algorithm） 贪婪算法：采用逐步构造最优解的方法。贪婪算法：采用逐步构造最优解的方法。 在每个阶段，都作出一个看上去最优的决策在每个阶段，都作出一个看上去最优的决策（在一定的标准下）。决策一旦作出，就不可再（在一定的标准下）。决策一旦作出，就不可再更改。作出贪婪决策的依据称为贪婪准则（更改。作出贪婪决策的依据称为贪婪准则（greedy criterion）。）。第一章 优化计算方法2022-5-16Advanced AI26/33n例子例子背包问题的贪婪算法（背包问题的贪婪算法（Greedy algorithm）STEP 1 STEP 2; 1:, 2 , 1knacii记成排列从

18、大到小排列，不妨把对物品以11 10:11STEP2kiikkkia xabxxkkkn若， 则；否则，；当时，停止；否则，重复。第一章 优化计算方法2022-5-16Advanced AI27/33n启发式算法的优点启发式算法的优点 1. 模型误差、数据不精确性、参数估计误差等可能模型误差、数据不精确性、参数估计误差等可能造成最优算法的解比启发式算法的解更差；造成最优算法的解比启发式算法的解更差； 2. 复杂问题无法求得最优算法或最优算法太复杂；复杂问题无法求得最优算法或最优算法太复杂； 3. 简单易行，直观，程序简单。简单易行，直观，程序简单。 n启发式算法的缺点启发式算法的缺点 1. 不

19、能保证最优；不能保证最优； 2. 不稳定；不稳定； 3. 依赖于实际问题、设计者经验。依赖于实际问题、设计者经验。第一章 优化计算方法2022-5-16Advanced AI28/33n简单直观的算法简单直观的算法n数学规划算法数学规划算法n现代优化算法现代优化算法u 禁忌搜索算法禁忌搜索算法u 模拟退火算法模拟退火算法u 遗传算法遗传算法u 人工神经网络人工神经网络u 蚁群算法蚁群算法u 粒子群算法粒子群算法u 混合算法混合算法 特点：特点：基于客观世界中的一些自基于客观世界中的一些自然现象；然现象；建立在计算机迭代计算的建立在计算机迭代计算的基础上；基础上；具有普适性，可解决实际具有普适性

20、，可解决实际应用问题。应用问题。第一章 优化计算方法2022-5-16Advanced AI29/33n评价算法优劣的指标评价算法优劣的指标 算法的复杂性（计算效率）算法的复杂性（计算效率） 解的偏离程度（计算效果）解的偏离程度（计算效果） 算法的稳健性（不同实例、不同时间、不同起点的算法的稳健性（不同实例、不同时间、不同起点的差异）差异）n评价算法优劣的手段评价算法优劣的手段 最坏情况分析（纯理论）最坏情况分析（纯理论） 概率分析（理论分析）概率分析（理论分析） 计算模拟分析（统计特性）计算模拟分析（统计特性）第一章 优化计算方法2022-5-16Advanced AI30/33n时间复杂性和空间复杂性概念时间复杂性和空间复杂性概念 算法算法的时间复杂性的时间复杂性：算法对时间的需要量（加、减、：算法对时间的需要量（加、减、乘、除、比较、读、写等操作的总次数）；乘、除、比较、读、写等操作的总次数）； 算法算法的空间复杂性的空间复杂性：算法对空间的需要量（存储空：算法对空间的需要量（存储空间的大小，二进制位数）；间的大小，二