现代优化计算方法ppt课件-79页精品文档

现代优化计算方法授课：张彩霞#四教204#3690caixiazhanggmail教材邢文训，谢金星－－《现代优化计算方法》（第二版）清华大学出版社主要内容1.概论（49页）2.禁忌搜索算法（26页）（tabusearch）3.模拟退火算法（35页）（simulatedannealing）4.遗传算法（35页）（geneticalgorithms）5.蚁群算法（23页）（群体（群集）智能，SwarmIntelligence）6.人工神经网络（38页）（artificialneuralnetworks）7.拉格朗日松弛算法（35页）（lagrangeanrelaxation）第一章概论1.组合最优化问题2.计算复杂性3.邻域4.启发式算法背景传统实际问题的特点连续性问题——主要以微积分为基础，且问题规模较小传统的优化方法追求准确——精确解理论的完美——结果漂亮主要方法：线性与非线性规划、动态规划、多目标规划、整数规划等；排队论、库存论、对策论、决策论等。传统的评价方法算法收敛性（从极限角度考虑）收敛速度（线性、超线性、二次收敛等）传统运筹学面临新挑战现代问题的特点离散性问题——主要以组合优化（针对离散问题，定义见后）理论为基础不确定性问题——随机性数学模型半结构或非结构化的问题——计算机模拟、决策支持系统大规模问题——并行计算、大型分解理论、近似理论现代优化方法追求满意——近似解实用性强——解决实际问题现代优化算法的评价方法算法复杂性1.1组合优化问题组合优化（combinatorialoptimization）:解决离散问题的优化问题——运筹学分支。通过数学方法的研究去寻找离散事件的最优编排、分组、次序或筛选等，可以涉及信息技术、经济管理、工业工程、交通运输和通信网络等许多方面。数学模型：决策变量有限点集约束函数目标函数,.,0)(..)(minDxxgtsxf1.1组合优化问题组合优化问题的三参数表示：.|)(min)(,:::,,0)(,|:),,(FxxfxfFxxFxfxgDxxFDfFD最优解，如果可行解（点）目标函数有限点集可行域决策变量定义域1.1组合优化问题例10-1背包问题（0-1knapsackproblem）装包？问题：如何以最大价值件物品单位价值，第件物品单位体积，第背包容积.,,1:.,,1::niicniiabii1.1组合优化问题.1,0i0i1(1.3).,,1,1,0(1.2),as.t.(1.1)maxn1ii1iniiiniiDxnixbxxc物品，不装第物品装第，其中决策变量包容量限制总价值数学模型：1.1组合优化问题例2旅行商问题（TSP,travelingsalesmanproblem）管梅谷教授1960年首先提出，国际上称之为中国邮递员问题。问题描述：一商人去n个城市销货，所有城市走一遍再回到起点，使所走路程最短。1.1组合优化问题ij1ij1min(1.4)s.t.1.1,2,,,(1.5)i1.1,2,,,ijijijnjnidxxinxjn数学模型：总路长只从城市出来一次,(1.6)1,21,1,2,,,(1.7)0,1,,1,2,,,.(1.8):ij,s:s1,ijijsijijijjxssnsnxijnijdijx只走入城市一次在任意城市子集中不形成回路决策变量其中城市与城市之间的距离集合中元素的个数，走城市和城市0.:,,:,,ijjiijjiijTSPddijTSPddij之间的路径，，不走城市和城市之间的路径对称距离非对称距离)1(}1,0{nnD1.1组合优化问题例4装箱问题（binpacking）尺寸为1的箱子有若干个，怎样用最少的箱子装下n个尺寸不超过1的物品，物品集合为：。12{,,...}naaa1.1组合优化问题11min..1,1,2,,,1,1,2,,,0,1,1,2,,;1,2,,,B:1,0.BibbniibiibibBstxinaxbBxinbBibxib数学模型：其中装下全部物品需要的箱子，第物品装在第个箱子，，第物品不装在第个箱子每个物品都被装箱装在每个箱子的物品总尺寸不能超过箱子的容量例3整数线性规划(integerlinearprogramming)nTZxxbAxtsxc,0..minmnmnRbRARc,,的元素都是整数。cbA,,特点决策变量的定义域和可行解集合都是有限的在问题的规模较小时，用枚举法容易得最优解组合优化问题常用整数规划模型表示由于组合最优化问题的复杂性，很多快速的算法只给出可行解1.2计算复杂性的概念评价算法的好坏——计算时间的多少、解的偏离程度以二进制计算机中的存储和计算为基础理论产生于20世纪70年代例非对称距离TSP问题的算法实现：所有路径枚举。计算时间：n个城市，固定1个为起终点需要(n-1)!个枚举设计算机1秒能完成24个城市的枚举，则城市数与计算时间的关系如下表：1.2计算复杂性的概念城市数2425262728293031计算时间1sec24sec10min4.3hour4.9day136.5day10.8year325year随城市增多，计算时间增加很快。到31个城市时，要计算325年。描述算法的好坏——计算复杂性——讨论计算时间与问题规模之间的关系。以目前二进制计算机中的存储和计算为基础，以理论的形式系统描述，是评估算法性能的基础。1.2计算复杂性的概念问题（problem）：要回答的一般性提问，通常含有若干个满足一定条件的参数（或自由变量）。可以从两方面描述：（1）对所有参数的一般性描述；（2）答案（或解）必须满足的性质。实例（instance）:给问题的所有参数指定具体值，得到问题的一个实例。这些具体值称为数据.1.2计算复杂性的概念数的规模（编码长度）：一个数在计算机中存储时占据的位数实例的规模：)(xl一个实例所有参数数值的规模之和)(Il算法的计算量：算法求解中的加、减、乘、除、比较、读、写等基本运算的总次数)(ICA数的规模正整数x的二进制位数是:(整数到二进制的转换))2,2[1ssx)}1,0{,1(2...220111isssssaaaaaax)(~01aaaxss1)(sxl112212log2sssxxxsx)1(log)(2xxlxxx222log1)1(loglog2实例）和距离实例的规模（城市数例ijdnTSP1.2.1ninjijijdnIl1122}2log{2)1(log)(jidijijdnPPnnIlPnn,022log3)1(3)(log2)1(2课堂练习）的规模（例cbAnm,,,,IP2.2.11.2计算复杂性的概念算法计算量的度量之例——TSP枚举法21,,,(1)!(1)!!;(1)!!(1)!nniinnnnnnnn城市数第一城市为始终点，计算一条路径（,1）长度的基本运算为两两城市间距离的个数求和,共有条路径,求和运算次数为：枚举所有路径进行次比较可得最优路径,基本计算总次数为总计算量:计算量的统计：1.2计算复杂性的概念实例的输入长度：22,,(1)(log12)log12ijijdKLnnKn设对有则（）（）实例的输入长度是n的多项式函数枚举法的基本计算量是n的阶乘函数，随n的增加，比指数函数增加得还快.1.2计算复杂性的概念AAA,()AC(I)()(())()((()))()IlIgxC(I)glICIOglIgx实例实例规模：，算法基本计算总次数：存在函数和一个常数，使得对于该问题的任意实例Ｉ都满足　　　　　　（ＸＸ）则二者关系表示为：的性质决定了算法的性能。控制的函数，且被是))(()()(IlgIlICA算法复杂性分析：由最坏实例的输入规模与算法的计算量之间的关系来衡量算法的好坏。问题复杂性分析1.2计算复杂性的概念定义多项式算法给定问题P，算法A，对一个实例I，存在多项式函数g(x)，使（XX）成立，称算法A对实例I是多项式算法；若存在多项式函数g(x)，使（XX）对问题P的任意实例I都成立，称算法A为解决该问题P的多项式算法.当g(x)为指数函数时，称A为P的指数时间算法。随着变量的增加，多项式函数增长的速度比指数函数增长的速度慢得多nCnC22221011.2计算复杂性的概念利用复杂性分析对组合优化问题归类。定义多项式问题给定一个组合优化问题，若存在一个多项式算法，称该问题为多项式时间可解问题，或简称多项式问题(或P问题).所有多项式问题的集合记为P.例：线性规划是否为多项式问题？是通常将存在多项式时间算法的问题看作是易解问题（EasyProblem），将需要指数时间算法解决的问题看作是难解问题（HardProblem）。为什么把多项式时间复杂性作为易解问题和难解问题的分界线？多项式函数与指数函数的增长率有本质的差别问题规模n多项式函数指数函数log2nnnlog2nn2n32nn!10101121103.321033.21001000102436288001006.64100664.4100001.0E61.3E309.3E1571.3邻域的概念距离空间中，邻域是以一点为中心的一个球体目的：寻找下一个迭代点的邻域。称为。的所有子集组成的集合表示中称为一个邻域映射，其且的子集的一个映射上的一点到），对于组合最优化问题（定义：xxNDxNxxNDxNDDfFDDD)(2),(,2)(:,,示例},|{)(TSP1.3.1,DykxyxyyxNjiijij，定义邻域对例化个位置的值可以发生变最多有kx。中的两个元素进行对换，即定义它的邻域映射为的排列是为问题解的另一种表示法例SoptniiiiiiSDnn2}....,1,2,,...,,|),...,,({TSP1.3.22121局部最优全局最优FxNxxfxf*)(),()(*)(Fxxfxf),()(*)(12345678910＋＋＋＋＋＋＋＋＋＋}1|{)(xyZyxN传统的优化算法可能陷入局部最优点。现代优化算法就是解决如何跳出局部最优点以达到全局最优点。1.4启发式算法_定义启发式算法（heuristicalgorithm）定义1.基于直观或经验构造的算法，在可接受的花费（时间、空间）下，给出待解组合优化问题的每个实例的一个可行解，该可行解与最优解偏差事先不一定可以预计.定义2.启发式算法是一种技术，在可接受的计算费用内寻找最好解，但不保证该解的可行性与最优性，无法描述该解与最优解的近似程度。特点（与传统优化方法不同）：凭直观和经验给出算法；不考虑所得解与最优解的偏离程度.1.4启发式算法_优点优点：（1）有可能比简化数学模型解的误差小；（2）对有些难题，计算时间可接受；（3）可用于某些最优化算法（如分支定界算法）之中的估界；（4）直观易行；（5）速度较快；（6）程序简单，易修改。1.4启发式算法_不足不足：（1）不能保证求得全局最优解；（2）解的精度不稳定，有时好有时坏；（3）算法设计与问题、设计者经验、技术有关，缺乏规律性；（4）不同算法之间难以比较。1.4启发式算法_分类(1)一步算法：不在两个可行解之间比较(2)改进算法（迭代算法）：从一个可行解到另一个可行解变换(3)数学规划算法：主要用连续优化的方法如解空间松弛法1.4启发式算法_分类（4）现代优化算法：80年代初兴起禁忌搜索（tabusearch）模拟退火（simulatedannealing）遗传算法（geneticalgorithms）神经网络（neuralnetwork