现代优化计算方法课件

现代优化计算方法授课：张彩霞

#四教204#3690caixiazhanggmail现代优化计算方法授课：张彩霞1教材邢文训，谢金星－－《现代优化计算方法》（第二版）清华大学出版社教材邢文训，谢金星－－《现代优化计算方法》（第二版）2主要内容概论（49页）禁忌搜索算法（26页）（tabusearch）模拟退火算法（35页）（simulatedannealing）遗传算法（35页）（geneticalgorithms）蚁群算法（23页）（群体（群集）智能，SwarmIntelligence）人工神经网络（38页）（artificialneuralnetworks）拉格朗日松弛算法（35页）（lagrangeanrelaxation）主要内容概论（49页）3第一章概论组合最优化问题计算复杂性邻域启发式算法第一章概论组合最优化问题4背景传统实际问题的特点

连续性问题——主要以微积分为基础，且问题规模较小传统的优化方法追求准确——精确解理论的完美——结果漂亮主要方法：线性与非线性规划、动态规划、多目标规划、整数规划等；排队论、库存论、对策论、决策论等。传统的评价方法算法收敛性（从极限角度考虑）收敛速度（线性、超线性、二次收敛等）背景传统实际问题的特点5传统运筹学面临新挑战现代问题的特点

离散性问题——主要以组合优化（针对离散问题，定义见后）理论为基础不确定性问题——随机性数学模型半结构或非结构化的问题——计算机模拟、决策支持系统大规模问题——并行计算、大型分解理论、近似理论现代优化方法追求满意——近似解实用性强——解决实际问题现代优化算法的评价方法算法复杂性传统运筹学面临新挑战现代问题的特点61.1组合优化问题

组合优化（combinatorialoptimization）:解决离散问题的优化问题——运筹学分支。通过数学方法的研究去寻找离散事件的最优编排、分组、次序或筛选等，可以涉及信息技术、经济管理、工业工程、交通运输和通信网络等许多方面。数学模型：1.1组合优化问题组合优化（combinatori71.1组合优化问题组合优化问题的三参数表示：

1.1组合优化问题组合优化问题的三参数表示：81.1组合优化问题例10-1背包问题（0-1knapsackproblem）1.1组合优化问题例10-1背包问题（0-1knap91.1组合优化问题1.1组合优化问题101.1组合优化问题例2旅行商问题（TSP,travelingsalesmanproblem）管梅谷教授1960年首先提出，国际上称之为中国邮递员问题。问题描述：一商人去n个城市销货，所有城市走一遍再回到起点，使所走路程最短。1.1组合优化问题例2旅行商问题（TSP,traveli111.1组合优化问题1.1组合优化问题121.1组合优化问题例4装箱问题（binpacking）尺寸为1的箱子有若干个，怎样用最少的箱子装下n个尺寸不超过1的物品，物品集合为：。

1.1组合优化问题例4装箱问题（binpacking131.1组合优化问题每个物品都被装箱装在每个箱子的物品总尺寸不能超过箱子的容量1.1组合优化问题每个物品都被装箱装在每个箱子的物品总尺寸14例3整数线性规划(integerlinearprogramming)例3整数线性规划(integerlinearprog15特点决策变量的定义域和可行解集合都是有限的在问题的规模较小时，用枚举法容易得最优解组合优化问题常用整数规划模型表示由于组合最优化问题的复杂性，很多快速的算法只给出可行解特点决策变量的定义域和可行解集合都是有限的161.2计算复杂性的概念评价算法的好坏——计算时间的多少、解的偏离程度以二进制计算机中的存储和计算为基础理论产生于20世纪70年代例非对称距离TSP问题的算法实现：所有路径枚举。计算时间：n个城市，固定1个为起终点需要(n-1)!个枚举设计算机1秒能完成24个城市的枚举，则城市数与计算时间的关系如下表：1.2计算复杂性的概念评价算法的好坏——计算时间的多少、解171.2计算复杂性的概念城市数2425262728293031计算时间1sec24sec10min4.3hour4.9day136.5day10.8year325year随城市增多，计算时间增加很快。到31个城市时，要计算325年。描述算法的好坏——计算复杂性——讨论计算时间与问题规模之间的关系。以目前二进制计算机中的存储和计算为基础，以理论的形式系统描述，是评估算法性能的基础。1.2计算复杂性的概念城市数242526272829303181.2计算复杂性的概念问题（problem）：要回答的一般性提问，通常含有若干个满足一定条件的参数（或自由变量）。可以从两方面描述：（1）对所有参数的一般性描述；（2）答案（或解）必须满足的性质。实例（instance）:给问题的所有参数指定具体值，得到问题的一个实例。这些具体值称为数据.1.2计算复杂性的概念问题（problem）：要回答的一般191.2计算复杂性的概念数的规模（编码长度）：一个数在计算机中存储时占据的位数实例的规模：一个实例所有参数数值的规模之和算法的计算量：算法求解中的加、减、乘、除、比较、读、写等基本运算的总次数1.2计算复杂性的概念数的规模（编码长度）：一个数在计算20数的规模正整数x的二进制位数是:(整数到二进制的转换)数的规模正整数x的二进制位数是:(整数到二进制的转换)21实例实例22课堂练习课堂练习231.2计算复杂性的概念算法计算量的度量之例——TSP枚举法计算量的统计：1.2计算复杂性的概念算法计算量的度量之例——TSP枚举法241.2计算复杂性的概念实例的输入长度：实例的输入长度是n的多项式函数枚举法的基本计算量是n的阶乘函数，随n的增加，比指数函数增加得还快.1.2计算复杂性的概念实例的输入长度：实例的输入长度是n的251.2计算复杂性的概念算法复杂性分析：由最坏实例的输入规模与算法的计算量之间的关系来衡量算法的好坏。问题复杂性分析1.2计算复杂性的概念算法复杂性分析：由最坏实例的输入规模261.2计算复杂性的概念定义

多项式算法给定问题P，算法A，对一个实例I，存在多项式函数g(x)，使（XX）成立，称算法A对实例I是多项式算法；若存在多项式函数g(x)，使（XX）对问题P的任意实例I都成立，称算法A为解决该问题P的多项式算法.当g(x)为指数函数时，称A为P的指数时间算法。随着变量的增加，多项式函数增长的速度比指数函数增长的速度慢得多1.2计算复杂性的概念定义多项式算法随着变量的增加，多项271.2计算复杂性的概念利用复杂性分析对组合优化问题归类。定义多项式问题给定一个组合优化问题，若存在一个多项式算法，称该问题为多项式时间可解问题，或简称多项式问题(或P问题).所有多项式问题的集合记为P.例：线性规划是否为多项式问题？是1.2计算复杂性的概念利用复杂性分析对组合优化问题归类。是28通常将存在多项式时间算法的问题看作是易解问题（EasyProblem），将需要指数时间算法解决的问题看作是难解问题（HardProblem）。通常将存在多项式时间算法的问题看作是易解问题（EasyPr29为什么把多项式时间复杂性作为易解问题和难解问题的分界线？多项式函数与指数函数的增长率有本质的差别问题规模n多项式函数指数函数log2nnnlog2nn2n32nn!10101121103.321033.21001000102436288001006.64100664.4100001.0E61.3E309.3E157为什么把多项式时间复杂性作为易解问题和难解问题的分界301.3邻域的概念距离空间中，邻域是以一点为中心的一个球体目的：寻找下一个迭代点1.3邻域的概念距离空间中，邻域是以一点为中心的一个球体31示例示例32局部最优全局最优12345678910＋＋＋＋＋＋＋＋＋＋局部最优12345678910＋＋33传统的优化算法可能陷入局部最优点。现代优化算法就是解决如何跳出局部最优点以达到全局最优点。传统的优化算法可能陷入局部最优点。341.4启发式算法_定义启发式算法（heuristicalgorithm）定义1.基于直观或经验构造的算法，在可接受的花费（时间、空间）下，给出待解组合优化问题的每个实例的一个可行解，该可行解与最优解偏差事先不一定可以预计.定义2.启发式算法是一种技术，在可接受的计算费用内寻找最好解，但不保证该解的可行性与最优性，无法描述该解与最优解的近似程度。特点（与传统优化方法不同）：凭直观和经验给出算法；不考虑所得解与最优解的偏离程度.1.4启发式算法_定义启发式算法（heuristical351.4启发式算法_优点

优点：（1）有可能比简化数学模型解的误差小；（2）对有些难题，计算时间可接受；（3）可用于某些最优化算法（如分支定界算法）之中的估界；（4）直观易行；（5）速度较快；（6）程序简单，易修改。1.4启发式算法_优点优点：361.4启发式算法_不足不足：（1）不能保证求得全局最优解；（2）解的精度不稳定，有时好有时坏；（3）算法设计与问题、设计者经验、技术有关，缺乏规律性；（4）不同算法之间难以比较。1.4启发式算法_不足不足：371.4启发式算法_分类(1)一步算法：不在两个可行解之间比较(2)改进算法（迭代算法）：从一个可行解到另一个可行解变换(3)数学规划算法：主要用连续优化的方法如解空间松弛法

1.4启发式算法_分类(1)一步算法：不在两个可行解381.4启发式算法_分类（4）现代优化算法：80年代初兴起禁忌搜索（tabusearch）模拟退火（simulatedannealing）遗传算法（geneticalgorithms）神经网络（neuralnetworks）蚂蚁算法（AntAlgorithm，群体（群集）智能，SwarmIntelligence）（5）其他算法：多种启发式算法的集成.理论上难以区分目标值的优劣1.4启发式算法_分类（4）现代优化算法：理论上难以区分目391.4启发式算法_性能分析评价指标：算法的复杂性（计算效率）解的偏离程度（计算效果）算法的鲁棒性1.4启发式算法_性能分析评价指标：40评价手段：最坏情形分析概率分析计算模拟分析1.4启发式算法_性能分析评价手段：1.4启发式算法_性能分析41全局优化启发式算法的特点在一些限定条件下，理论上可以收敛到全局最优。但付出的计算时间可能无法接受。在限定计算时间后，无法保证收敛到全局最优。随着计算时间的增加，算法的解越来越好。全局优化启发式算法的特点在一些限定条件下，理论上可以收敛到全42策略1：集中集中搜索，求得局部最优解策略2：扩散扩大搜索区域，达到全局最优解策略1：集中43第二章禁忌搜索算法（TabuSearch）Glover1986禁忌：禁止重复前面的工作禁忌表：记录已经到达过的局部最优解或达到局部最优的过程。第二章禁忌搜索算法（TabuSearch）Glove442.1局部搜索是停止否是否2.1局部搜索是停止否是否45例2.1.1五个城市的对称TSP全邻域搜索随机搜索例2.1.1五个城市的对称TSP全邻域搜索46陷入局部最优解！例2.1.2四城市非对称TSP陷入局部最优解！例2.1.2四城市非对称TSP47特点依赖于初始点的选取和邻域的结构选取足够多的初始点特点依赖于初始点的选取和邻域的结构选取足够多的初始点482.2禁忌搜索基本思想：

标记已得到的局部最优解或求解的过程，并在进一步的迭代中避开这些局部最优解或过程。2.2禁忌搜索基本思想：49禁忌搜索算法停止准则结果是否禁忌搜索算法停止准则结果是否50禁忌对象：被禁的变化元素禁忌长度：被禁对象不允许选取的迭代次数候选集合的构成：邻域中的邻居组成评价函数的构造：赋予候选集合中每个元素一个实数值，通常是目标函数。特赦规则记忆频率信息终止规则

禁忌表禁忌对象：被禁的变化元素禁忌表51技术问题禁忌对象如何选取？禁忌长度短会造成循环，长会造成算法的记忆存储量增加被禁对象能否解禁？候选集合的确定评价函数的构造终止规则。。。。。。技术问题禁忌对象如何选取？52例2.2.1四城市非对称TSP的距离矩阵例2.2.1四城市非对称TSP的距离矩阵53例2.2.2禁忌长度从3变到2例2.2.2禁忌长度从3变到254禁忌对象：被禁的变化元素解的简单变化向量分量的变化目标值变化禁忌对象：被禁的变化元素解的简单变化55解的简单变化从一个解变化到另一个解解的简单变化从一个解变化到另一个解56例2.3.4(例2.1.1)五个城市的对称TSP例2.3.4(例2.1.1)五个城市的对称TSP57向量分量的变化

对解向量的每个分量进行变化例2.3.10-1背包问题例2.3.2TSP问题向量分量的变化

对解向量的每个分量进行变化例2.3.1058例2.3.5(例2.1.1)五个城市的对称TSP例2.3.5(例2.1.1)五个城市的对称TSP59目标值变化等值线例2.3.3目标值变化等值线例2.3.360例2.3.6(例2.1.1)五个城市的对称TSP例2.3.6(例2.1.1)五个城市的对称TSP61解的简单变化比解的分量变化和目标值变化的受禁忌范围要小解的简单变化比解的分量变化和目标值变化的受禁忌范围要小62禁忌长度被禁对象x不允许选取的迭代次数ttabu(x)=ttabu(x)=t-1…tabu(x)=0禁忌长度被禁对象x不允许选取的迭代次数ttabu(x63特赦规则让一些禁忌对象重新可选：候选集中的全部对象都被禁忌一对象被禁，但若解禁后其当前最优值将下降特赦规则让一些禁忌对象重新可选：候选集中的全部对象都被禁忌64例2.3.7五个城市的非对称TSP例2.3.7五个城市的非对称TSP65基于评价值的规则基于最小错误的规则基于影响力的规则选评价值最小的解禁关注影响大的变化基于评价值的规则选评价值最小的解禁关注影响大的变化66候选集合的确定由邻域中的邻居组成从邻域中所有邻居中选择若干个目标值或评价值最佳的邻居从邻域中的一部分邻居中选择若干个目标值或评价值最佳的邻居随机选取候选集合的确定由邻域中的邻居组成从邻域中所有邻居中选择若干个67评价函数赋予候选集合