《《现代优化计算方法》PPT课件》由会员分享，可在线阅读，更多相关《《现代优化计算方法》PPT课件（78页珍藏版）》请在金锄头文库上搜索。
1、 现代优化计算方法现代优化计算方法授课：张授课：张 彩彩 霞霞 #四教四教204# 教教 材材n邢文训，谢金星邢文训，谢金星现代优化计算方法现代优化计算方法（第二版）（第二版） 清华大学出版社清华大学出版社主要内容主要内容1.概论（概论（49页）页）2.禁忌搜索算法（禁忌搜索算法（26页）页）（tabu search）3.模拟退火算法（模拟退火算法（35页）页） （simulated annealing）4.遗传算法（遗传算法（35页）页） （genetic algorithms）5.蚁群算法（蚁群算法（23页）页） （群体（群集）智能，Swarm Intelligence） 6.人工神经网络
2、（人工神经网络（38页）页） （artificial neural networks）7.拉格朗日松弛算法（拉格朗日松弛算法（35页）页） （lagrangean relaxation）第一章第一章 概论概论1.组合最优化问题组合最优化问题2.计算复杂性计算复杂性3.邻域邻域4.启发式算法启发式算法背背 景景n传统实际问题的特点传统实际问题的特点 连续性问题连续性问题主要以微积分为基础，且问题规模较小主要以微积分为基础，且问题规模较小n传统的传统的优化方法优化方法 追求准确追求准确精确解精确解 理论的完美理论的完美结果漂亮结果漂亮 主要方法：线性与非线性规划、动态规划、多目标规划、整主要方法：
3、线性与非线性规划、动态规划、多目标规划、整数规划等；排队论、库存论、对策论、决策论等。数规划等；排队论、库存论、对策论、决策论等。n传统的传统的评价方法评价方法 算法收敛性（从极限角度考虑）算法收敛性（从极限角度考虑） 收敛速度（线性、超线性、二次收敛等）收敛速度（线性、超线性、二次收敛等）传统运筹学面临新挑战传统运筹学面临新挑战n现代问题的特点现代问题的特点 离散性问题离散性问题主要以组合优化（针对离散问题，定义见主要以组合优化（针对离散问题，定义见后）理论为基础后）理论为基础 不确定性问题不确定性问题随机性数学模型随机性数学模型 半结构或非结构化的问题半结构或非结构化的问题计算机模拟、决策
4、支持系统计算机模拟、决策支持系统 大规模问题大规模问题并行计算、大型分解理论、近似理论并行计算、大型分解理论、近似理论n现代现代优化方法优化方法 追求满意追求满意近似解近似解 实用性强实用性强解决实际问题解决实际问题n现代优化算法的现代优化算法的评价方法评价方法 算法复杂性算法复杂性1.1 组合优化问题组合优化问题 组合优化组合优化（combinatorial optimization）:解决解决离散问题的优化问题离散问题的优化问题运筹学分支。通过数学方运筹学分支。通过数学方法的研究去寻找离散事件的最优编排、分组、次序法的研究去寻找离散事件的最优编排、分组、次序或筛选等，可以涉及信息技术、经济
5、管理或筛选等，可以涉及信息技术、经济管理、工业工、工业工程程、交通运输和通信网络等许多方面。、交通运输和通信网络等许多方面。 数学模型：数学模型：1.1 组合优化问题组合优化问题组合优化问题的组合优化问题的三参数三参数表示：表示： 1.1 组合优化问题组合优化问题n例例1 0-1背包问题（背包问题（0-1 knapsack problem）1.1 组合优化问题组合优化问题1.1 组合优化问题组合优化问题n例例2 旅行商问题旅行商问题（TSP,traveling salesman problem） 管梅谷教授管梅谷教授1960年首先提出，国际上称年首先提出，国际上称之为中国邮递员问题。之为中国邮
6、递员问题。 问题描述：一商人去问题描述：一商人去n个城市销货，所有个城市销货，所有城市走一遍再回到起点，使所走路程最城市走一遍再回到起点，使所走路程最短。短。1.1 组合优化问题组合优化问题1.1 组合优化问题组合优化问题例例4 装箱问题（装箱问题（bin packing） 尺寸为尺寸为1的箱子有若干个，怎样用最少的的箱子有若干个，怎样用最少的箱子装下箱子装下n个尺寸不超过个尺寸不超过1 的物品，物品的物品，物品集合为：集合为： 。 1.1 组合优化问题组合优化问题每个物品都被装箱每个物品都被装箱装在每个箱子的物品装在每个箱子的物品总尺寸不能超过箱子总尺寸不能超过箱子的容量的容量例3 整数线性
7、规划(integer linear programming)特特 点点n决策变量的定义域和可行解集合都是决策变量的定义域和可行解集合都是有有限的限的n在问题的规模较小时，用在问题的规模较小时，用枚举法枚举法容易得容易得最优解最优解n组合优化问题常用组合优化问题常用整数规划模型整数规划模型表示表示n由于组合最优化问题的复杂性，很多快由于组合最优化问题的复杂性，很多快速的算法只给出可行解速的算法只给出可行解1.2 计算复杂性的概念计算复杂性的概念n评价算法的好坏评价算法的好坏计算时间计算时间的多少、解的的多少、解的偏离偏离程程度度n以二进制计算机中的存储和计算为基础以二进制计算机中的存储和计算为基
8、础n理论产生于理论产生于20世纪世纪70年代年代n例例 非对称距离非对称距离TSP问题的算法实现：所有问题的算法实现：所有路径路径枚举枚举。n计算时间计算时间：n个城市，固定个城市，固定1个为起终点需要个为起终点需要(n-1)!个枚举个枚举 设设计算机计算机1秒能完成秒能完成24个城市的枚举，则城市数与个城市的枚举，则城市数与计算时间的关系如下表：计算时间的关系如下表：1.2 计算复杂性的概念计算复杂性的概念城市数城市数2425262728293031计算时计算时间间1sec24sec10min4.3hour4.9day136.5day10.8year325year随城市增多，计算时间增加很快
9、。随城市增多，计算时间增加很快。到到31个城市时，要计算个城市时，要计算325年。年。描述算法的好坏描述算法的好坏计算复杂性计算复杂性讨论讨论计算时间与问题规计算时间与问题规模模之间的关系。以目前二进制计算机中的存储和计算为基础，之间的关系。以目前二进制计算机中的存储和计算为基础，以理论的形式系统描述，是评估算法性能的基础。以理论的形式系统描述，是评估算法性能的基础。1.2 计算复杂性的概念计算复杂性的概念n问题（问题（problem）：）：要回答的一般性提问，通常含有要回答的一般性提问，通常含有若干个满足一定条件的参数（或自由变量）。可以从若干个满足一定条件的参数（或自由变量）。可以从两方面
10、描述：两方面描述： （1）对所有参数的一般性描述；）对所有参数的一般性描述； （2）答案（或解）必须满足的性质。）答案（或解）必须满足的性质。n实例（实例（instance）:给问题的所有参数指定具体值，得给问题的所有参数指定具体值，得到问题的一个实例。这些具体值称为到问题的一个实例。这些具体值称为数据数据.1.2 计算复杂性的概念计算复杂性的概念数的数的规模规模（编码长度）（编码长度） ：一个数在计算机中存储时占据的一个数在计算机中存储时占据的位数位数实例的实例的规模规模：一个实例所有参数数值的规模之和一个实例所有参数数值的规模之和算法的算法的计算量计算量：算法求解中的加、减、乘、除、比较、
11、算法求解中的加、减、乘、除、比较、读、写等基本运算的总次数读、写等基本运算的总次数数的数的规模规模n正整数正整数x的二进制位数是的二进制位数是:(整数整数到二进制的转换到二进制的转换)实例实例课课 堂堂 练练 习习1.2 计算复杂性的概念计算复杂性的概念n算法计算量的度量之例算法计算量的度量之例TSP枚举枚举法法计算量的统计：计算量的统计：1.2 计算复杂性的概念计算复杂性的概念n实例的输入长度实例的输入长度：n实例的输入长度是实例的输入长度是n的的多项式函数多项式函数n枚举法的基本计算量是枚举法的基本计算量是n的的阶乘函数阶乘函数， 随随n的增加，比的增加，比指数函数指数函数增加得还快增加得
12、还快.1.2 计算复杂性的概念计算复杂性的概念算法复杂性分析：由最坏实例的输入规模与算法的计算量之算法复杂性分析：由最坏实例的输入规模与算法的计算量之间的关系来衡量算法的好坏。间的关系来衡量算法的好坏。问题复杂性分析问题复杂性分析1.2 计算复杂性的概念计算复杂性的概念定义定义 多项式算法多项式算法给定问题给定问题P，算法算法A，对对一个一个实例实例I，存在存在多项式多项式函数函数g(x)，使（使（XX ）成立，称）成立，称算法算法A对实例对实例I是是多项式算法多项式算法；若存在多项式函数若存在多项式函数g(x)，使（使（XX）对问题）对问题P的的任任意意实例实例I都成立，称都成立，称算法算法
13、A为解决该问题为解决该问题P的多项的多项式算法式算法.当当g(x)为指数函数时，称为指数函数时，称A为为P的指数时间算法。的指数时间算法。随着变量的增加，多项式函数增长的速度比指数随着变量的增加，多项式函数增长的速度比指数函数增长的速度慢得多函数增长的速度慢得多1.2 计算复杂性的概念计算复杂性的概念n利用复杂性分析对组合优化问题归类。利用复杂性分析对组合优化问题归类。n定义定义多项式问题多项式问题 给定一个组合优化问题，若给定一个组合优化问题，若存在存在一个多项式一个多项式算法，称该问题为多项式时间可解问题，或算法，称该问题为多项式时间可解问题，或简称简称多项式问题多项式问题(或或P问题问题
14、). 所有多项式问所有多项式问题的集合记为题的集合记为P.n例：线性规划是否为多项式问题？例：线性规划是否为多项式问题？ 是是n通常将存在多项式时间算法的问题看作通常将存在多项式时间算法的问题看作是是易解问题易解问题（Easy Problem），将需要），将需要指数时间算法解决的问题看作是指数时间算法解决的问题看作是难解问难解问题题（Hard Problem）。）。 为什么把多项式时间复杂性作为易解问题和为什么把多项式时间复杂性作为易解问题和难解问题的分界线？难解问题的分界线？多项式函数与指数函数的增长率有本质的差别多项式函数与指数函数的增长率有本质的差别问题规模n多项式函数指数函数log2n
15、nnlog2nn2n32nn!10101121103.32 1033.21001000 1024 36288001006.64 100 664.4 100001.0E61.3E309.3E1571.3 邻域的概念邻域的概念n距离空间中，邻域是以一点为中心的一距离空间中，邻域是以一点为中心的一个球体个球体n目的：寻找下一个迭代点目的：寻找下一个迭代点示例n局部最优n全局最优1 2 3 4 5 6 7 8 9 10n传统的优化算法传统的优化算法可能陷入局部最优点。可能陷入局部最优点。n现代优化算法就是解决现代优化算法就是解决如何跳出如何跳出局部最局部最优点以达到全局最优点。优点以达到全局最优点。1
16、.4 启发式算法启发式算法_定义定义n启发式算法（启发式算法（heuristic algorithm）n定义定义1. 基于基于直观或经验直观或经验构造的算法，在可接受的花构造的算法，在可接受的花费（时间、空间）下，给出待解组合优化问题的每费（时间、空间）下，给出待解组合优化问题的每个实例的一个个实例的一个可行解可行解，该可行解与最优解偏差事先，该可行解与最优解偏差事先不一定可以预计不一定可以预计.n定义定义2. 启发式算法是一种技术，在可接受的计算费启发式算法是一种技术，在可接受的计算费用内寻找最好解，但不保证该解的可行性与最优性，用内寻找最好解，但不保证该解的可行性与最优性，无法描述该解与最
17、优解的近似程度。无法描述该解与最优解的近似程度。n特点（与传统优化方法不同）：特点（与传统优化方法不同）：凭凭直观和经验直观和经验给出给出算法；算法；不考虑不考虑所得解与最优解的所得解与最优解的偏离程度偏离程度.1.4 启发式算法启发式算法_优点优点 优点：优点：（1）有可能比简化数学模型解的误差小；）有可能比简化数学模型解的误差小；（2）对有些难题，计算时间可接受；）对有些难题，计算时间可接受；（3）可用于某些最优化算法（如分支定界算）可用于某些最优化算法（如分支定界算 法）之中的估界；法）之中的估界；（4）直观易行；）直观易行；（5）速度较快；）速度较快；（6）程序简单，易修改。）程序简单
18、，易修改。1.4 启发式算法启发式算法_不足不足不足：不足：（1）不能保证求得全局最优解；）不能保证求得全局最优解；（2）解的精度不稳定，有时好有时坏；）解的精度不稳定，有时好有时坏；（3）算法设计与问题、设计者经验、技术）算法设计与问题、设计者经验、技术 有关，缺乏规律性；有关，缺乏规律性；（4）不同算法之间难以比较。）不同算法之间难以比较。1.4 启发式算法启发式算法_分类分类 (1) 一步算法：不在两个可行解之间比较一步算法：不在两个可行解之间比较 (2) 改进算法（迭代算法）：从一个可行解到另一个可行改进算法（迭代算法）：从一个可行解到另一个可行解变换解变换 (3) 数学规划算法：主要
19、用连续优化的方法数学规划算法：主要用连续优化的方法 如解空间松弛法如解空间松弛法 1.4 启发式算法启发式算法_分类分类（4）现代优化算法：）现代优化算法： 80年代初兴起年代初兴起n禁忌搜索（禁忌搜索（tabu search）n模拟退火（模拟退火（simulated annealing）n遗传算法（遗传算法（genetic algorithms）n神经网络（神经网络（neural networks）n蚂蚁算法（蚂蚁算法（Ant Algorithm，群体（群集）群体（群集）智能，智能，Swarm Intelligence）（5 5）其他算法：）其他算法： 多种启发式算法的集成多种启发式算法的集
20、成. . 理论上难以理论上难以区分目标值区分目标值的优劣的优劣1.4启发式算法启发式算法_性能分析性能分析n评价指标：评价指标：1.算法的复杂性（计算效率）算法的复杂性（计算效率）2.解的偏离程度（计算效果）解的偏离程度（计算效果）3.算法的鲁棒性算法的鲁棒性n评价手段：评价手段：1.最坏情形分析最坏情形分析2.概率分析概率分析3.计算模拟分析计算模拟分析1.4启发式算法启发式算法_性能分析性能分析全局优化启发式算法的特点全局优化启发式算法的特点n在一些限定条件下，理论上可以收敛到在一些限定条件下，理论上可以收敛到全局最优。全局最优。n但付出的计算时间可能无法接受。但付出的计算时间可能无法接受
21、。n在限定计算时间后，无法保证收敛到全在限定计算时间后，无法保证收敛到全局最优。局最优。n随着计算时间的增加，算法的解越来越随着计算时间的增加，算法的解越来越好。好。n策略策略1：集中集中 集中搜索，求得局部最优解集中搜索，求得局部最优解n策略策略2：扩散扩散 扩大搜索区域，达到全局最优解扩大搜索区域，达到全局最优解第二章第二章 禁忌搜索算法（禁忌搜索算法（ Tabu Search）Glover 1986禁忌禁忌：禁止重复前面的工作：禁止重复前面的工作禁忌表禁忌表：记录已经到达过的局部最优解：记录已经到达过的局部最优解或或达到局部最优的过程。达到局部最优的过程。2.1 局部搜索局部搜索是是停止
22、停止否否是是否否例例2.1.1 五个城市的对称五个城市的对称TSP1.全邻域搜索全邻域搜索2.随机搜索随机搜索陷入局部最优解！陷入局部最优解！例例2.1.2四城市非对称四城市非对称TSP特特 点点n依赖于依赖于初始点初始点的选取和的选取和邻域邻域的结构的结构选取选取足够多足够多的初始点的初始点2.2 禁忌搜索禁忌搜索n基本思想基本思想： 标记标记已得到的局部最优解或求解的过程，已得到的局部最优解或求解的过程，并在进一步的迭代中并在进一步的迭代中避开避开这些局部最优这些局部最优解或过程。解或过程。禁忌搜索算法禁忌搜索算法停止准则停止准则结果结果是是否否1.禁忌对象禁忌对象：被禁的变化元素：被禁的
23、变化元素2.禁忌长度禁忌长度：被禁对象不允许选取的：被禁对象不允许选取的迭代次数迭代次数3.候选集合候选集合的构成：的构成：邻域邻域中的邻居组成中的邻居组成4.评价函数评价函数的构造：赋予候选集合中每个元素一个的构造：赋予候选集合中每个元素一个实数值实数值，通常是目标，通常是目标函数。函数。5.特赦规则特赦规则6.记忆频率信息记忆频率信息7.终止规则终止规则 禁禁忌忌表表技术问题技术问题n n禁忌对象如何选取？禁忌对象如何选取？禁忌对象如何选取？禁忌对象如何选取？n n禁忌长度禁忌长度禁忌长度禁忌长度短短短短会造成循环，会造成循环，会造成循环，会造成循环，长长长长会造成算法的记忆会造成算法的记
24、忆会造成算法的记忆会造成算法的记忆存储量增加存储量增加存储量增加存储量增加n n被禁对象能否被禁对象能否被禁对象能否被禁对象能否解禁解禁解禁解禁？n n候选集合的确定候选集合的确定候选集合的确定候选集合的确定n n评价函数的构造评价函数的构造评价函数的构造评价函数的构造n n终止规则终止规则终止规则终止规则n n。例例2.2.1 四城市非对称四城市非对称TSP的的距离矩阵距离矩阵例例2.2.2 禁忌长度从禁忌长度从3变到变到2禁忌对象禁忌对象：被禁的：被禁的变化元素变化元素1.解的简单变化解的简单变化2.向量分量的变化向量分量的变化3.目标值变化目标值变化解的简单变化解的简单变化n从一个解变化
25、到另一个解从一个解变化到另一个解例例2.3.4(例例2.1.1) 五个城市的对称五个城市的对称TSP向量分量的变化向量分量的变化n对解向量的每个分量进行变化对解向量的每个分量进行变化例例2.3.1 0-1背包问题背包问题例例2.3.2 TSP问题问题例例2.3.5(例例2.1.1) 五个城市的对称五个城市的对称TSP目标值变化目标值变化等值线等值线例例2.3.3例例2.3.6(例例2.1.1) 五个城市的对称五个城市的对称TSPn解的简单变化解的简单变化比比解的分量变化解的分量变化和和目标值目标值变化变化的受禁忌范围要小的受禁忌范围要小禁忌长度禁忌长度n被禁对象被禁对象x不允许选取的不允许选取
26、的迭代次数迭代次数t tabu(x)=ttabu(x)=t-1tabu(x)=0特赦规则特赦规则n让一些禁忌对象重新可选：让一些禁忌对象重新可选：1. 候选集中的全部对象都被禁忌候选集中的全部对象都被禁忌2. 一对象被禁，但若解禁后其当前最优值将下降一对象被禁，但若解禁后其当前最优值将下降例例2.3.7 五个城市的非对称五个城市的非对称TSP1.基于评价值的规则基于评价值的规则2.基于最小错误的规则基于最小错误的规则3.基于影响力的规则基于影响力的规则选评价值最小的解禁选评价值最小的解禁关注影响大的变化关注影响大的变化候选集合的确定候选集合的确定n由邻域中的邻居组成由邻域中的邻居组成1.从邻域
27、中从邻域中所有邻居所有邻居中选择若干个目标值或中选择若干个目标值或评价值最佳的邻居评价值最佳的邻居2.从邻域中的从邻域中的一部分邻居一部分邻居中选择若干个目标中选择若干个目标值或评价值最佳的邻居值或评价值最佳的邻居3.随机选取随机选取评价函数评价函数n赋予候选集合中每个元素一个赋予候选集合中每个元素一个实数值实数值，以此选取下一步的以此选取下一步的替代点替代点目标函数目标函数1.直接直接评价函数：含目标函数评价函数：含目标函数2.间接间接评价函数：尽量反映目标函数的特性评价函数：尽量反映目标函数的特性CLPS：约束批量计划与调度：约束批量计划与调度记忆频率信息记忆频率信息n记忆信息的出现频率记
28、忆信息的出现频率解集合、被禁对象、目标值集合解集合、被禁对象、目标值集合动态控制禁忌的长度动态控制禁忌的长度1.一个元素或一个序列重复出现，可以增加禁忌长一个元素或一个序列重复出现，可以增加禁忌长度度2.一个序列的目标值变化较小时，有必要增加序列一个序列的目标值变化较小时，有必要增加序列每个对象的禁忌长度。每个对象的禁忌长度。3.一个最佳的目标值出现的频率很高，可认为是最一个最佳的目标值出现的频率很高，可认为是最优值而终止优值而终止终止规则终止规则1.确定步数确定步数终止：迭代次数超过一定的值终止：迭代次数超过一定的值2.频率频率控制原则：解的频率超过一定的值控制原则：解的频率超过一定的值3.
29、目标目标控制原则：在一定步长内，最优值不变控制原则：在一定步长内，最优值不变4.目标值目标值偏离程度偏离程度原则：与下界差小于一定的原则：与下界差小于一定的值值应用案例：应用案例：图节点着色图节点着色问题问题对于图着色的研究是从对于图着色的研究是从m可着色性问题的可着色性问题的著名特例著名特例四色问题四色问题开始的。开始的。这个问题要求这个问题要求证明平面或球面上的任何地图的证明平面或球面上的任何地图的所有区域都至多可用所有区域都至多可用四种颜色四种颜色来着色来着色，并使任何两个有一段公共边界的并使任何两个有一段公共边界的相邻相邻区域区域没有相同没有相同的颜色。的颜色。 例例2.4.1AEDCB用禁忌搜索算法求得无向图的用禁忌搜索算法求得无向图的一个最小划分一个最小划分n定义函数：n目标函数：目标函数：n解的形式解的形式n邻域邻域n禁忌对象禁忌对象n特赦规则特赦规则n终止规则终止规则禁忌搜索算法禁忌搜索算法停止准则停止准则结果结果是是否否P70作业作业 P766
