《组合优化问题及算法.pptx》由会员分享，可在线阅读，更多相关《组合优化问题及算法.pptx（34页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、-1-组合最优化（combinatorial optimization)是通过对数学方法的研究去寻找离散事件的最优编排、分组、次序或筛选等，是运筹学(operations research)中的一个重要分支。所研究的问题涉及信息技术、经济管理、工业工程、交通运输、通信网络等领域。该问题可用数学模型描述为：引言引言 其中D表示有限个点组成的集合。第1页/共34页-2-1.0-1背包问题 设有一个容积为b的背包，n个体积分别为ai(i=1,2,n),价值分别为ci(i=1,2,n)的物品，如何以最大的价值装包？一些例子一些例子 第2页/共34页-3-2.旅行商问题(TSP，traveling sa
2、lesman problem)一个商人欲到n个城市推销商品，每两个城市i和j之间的距离为dij，如何选择一条道路使得商人每个城市正好走一遍后回到起点且所走路径最短。一些例子一些例子 第3页/共34页-4-3.有 约 束 的 机 器 调 度 问 题(capacitated machine scheduling)n个加工量为di|i=1,2,n的产品在一台机器上加工，机器在第t个时段的工作能力为ct,求完成所有产品加工所需时段数最少的调度方案一些例子一些例子 其中xit,T为决策变量,xit=1表示产品i在第t时段加工第4页/共34页-5-4.装箱问题(bin packing)如何把n个尺寸不超过
3、1的物品装入尺寸为1的箱子，并使所用的箱子个数最少。5.二维装箱问题（平面上的套裁问题）原料的尺寸大于需求的尺寸，需求的品种尺寸可以不同，最终的目标是在满足需求的前提下，使边角余料最小。6.车间作业调度问题(job shop scheduling)n个工件，J1,Jn在m台机器M1,M2,Mm上加工。每个工件Ji有ni个工序，Oi1,Oini,第Oij工序的加工时间为pij，必须按工序进行加工且每一工序必须一次加工完成。一台机器在任何时刻最多只能加工一个产品，一个工件不能同时在两台机器上加工，如何安排才能使最后一个完工的工件完工时间最小？一些例子一些例子 第5页/共34页-6-7.最大截问题(
4、MCP,Max Cut Problem)8.图的顶点着色问题（GCP,Graph Colouring Problem)9.独立集问题（ISP,Independent Set Problem)10.调度问题(SCP,Scheduling Problem)11.划分问题(PAP,Partition Problem)12.布局问题（PLP,Placement Problem)上述问题都是NP-hard问题，目前人们认为它们不存在求解最优解的多项式时间算法，大规模情形只有尝试用一些近似算法或启发式算法求解。一些例子一些例子 第6页/共34页-7-邻域概念 对于组合优化问题(D,F,f),D上的一个映射
5、：N:SD N(S)2D称为一个邻域映射，其中2D表示D的所有子集构成的集合，N(S)称为S的邻域。邻域的构造依赖于问题决策变量的表示，邻域的结构在现代化优化算法中起重要作用。启发式算法启发式算法 第7页/共34页-8-邻域概念例如，前面例子2给出的TSP问题模型。由解空间D=x0,1n(n-1)，可以定义它的一种邻域为：启发式算法启发式算法 k为一个正整数。TSP问题解的另一种表示法为D=S=(i1,i2,in)是1,2,n的一个排列第8页/共34页-9-邻域概念启发式算法启发式算法 TSP问题解的另一种表示法为D=S=(i1,i2,in)是1,2,n的一个排列可以定义它的邻域映射为2-op
6、t，即S中的两个元素对换。如4个城市的TSP问题，当S=(1,2,3,4)时，N(S)=(2,1,3,4),(3,2,1,4),(4,2,3,1),(1,3,2,4),(1,4,3,2),(1,2,4,3).类似可定义k-opt(k2)第9页/共34页-10-局部最优与全局最优启发式算法启发式算法 若s*满足 f(s*)()f(s),其中sN(s*)F,则称s*为f在F上的局部(local)最小（最大）解。若s*满足 f(s*)()f(s),其中sF,则称s*为f在F上的全局(global)最小（最大）解。第10页/共34页-11-启发式算法定义 一个基于直观或经验构造的算法，在可接受的花费（
7、计算时间、占用空间等）下给出待解决问题每一个实例的一个可行解，该解与最优解的偏离程度不一定能预计。启发式算法是一种技术，使在可接受的计算开销内寻找最好的解，但不一定能保证所得解的可行性和最优性，甚至多数情况下，无法给出所得解同最优解的近似程度。启发式算法启发式算法 第11页/共34页-12-近似算法定义 记问题A的任何一个实例I的最优解和启发式算法H解的目标值分别为zopt(I)和zH(I),若对某个正数0，有|zH(I)-zopt(I)|zopt(I)|，IA则称H是A的近似算法。启发式算法启发式算法 第12页/共34页-13-背包问题的贪婪算法1）将物品以ci/ai（单位体积的价值）由大到
8、小的顺序排列，不妨把排列记为1,2,n,k:=1;2）若 ，则xk=1;否则xk=0,k:=k+1;3)当k=n+1时，停止；否则，转2).(x1,x2,xn)为贪婪算法所得解，单位体积的价值越大越先放入是贪婪算法的原则。启发式算法启发式算法 第13页/共34页-14-简单的邻域搜索算法 给定组合优化问题，假设其邻域结构已确定，算法为1）任选一个初始解s0F;2)在N(s0)中按某一规则选一s；若f(s)Lk，则到4）；否则，从邻域N(xi)中随机选一xj,计算fij=f(xj)-f(xi);ll+1;若fij0，则xixj;否则,若exp(-fij/tk)random（0,1)）时，xixj
9、；重复3）；4）tk+1T(tT(tk k);k k+1；计算Lk，若满足停停止止条条件件，终止计算，否则，回到2).第19页/共34页-20-模拟退火算法的渐近收敛性模拟退火算法的渐近收敛性 已证明，模拟退火算法以1的概率收敛到整体最优解集，但渐近收敛到最优解集须经历无限多次变换。对最优解任意近似的逼近，对多数组合优化问题都导致比解空间规模大的变换数，从而导致算法的指数时间执行。解决办法：牺牲保证得到最优解为代价，在多项式时间里，逼近模拟退火算法的渐近收敛状态，返回一个近似最优解。第20页/共34页-21-模拟退火算法应用的一般要求模拟退火算法应用的一般要求1)数学模型 解空间、目标函数和初
10、始解2）新解的产生和接受机制新解产生:当前解经简单变换产生新解（决定了当前解的邻域结构），如对当前解的全部或部分元素进行置换、互换或反演等。Metropolis接受准则:3）冷却进度表的设定第21页/共34页-22-冷却进度表冷却进度表 冷却进度表是一组控制算法进程的参数，它包括：1.初始温度t0=tmax2.温度衰减函数T(t)3.Markov链的长度Lk4.终止温度tf（停止准则）。第22页/共34页-23-冷却进度表冷却进度表 虽然已经证明模拟退火算法在一定条件下的渐近收敛性。但这并不意味着任意冷却进度表都能确保算法收敛，不合理的冷却进度表会使算法在某些解间“振荡”而不能收敛于某一近似解
11、。模拟退火算法的最终解质量和CPU时间呈反向关系，很难两全其美，妥善解决办法只有：折中，即在合理的CPU时间里尽量提高最终解的质量。这涉及到冷却进度表所有参数的合理选取。第23页/共34页-24-冷却进度表的参数设置冷却进度表的参数设置 1.初始温度t0的选取 t0 要取得足够大，Johnson等建议通过计算若干次随机变换目标函数平均增量的方法来确定t0的值。其中，为上述平均增量，为初始接受率，一般取0.81之间的数。第24页/共34页-25-冷却进度表的参数设置冷却进度表的参数设置 2.温度衰减函数T(t)的选取 一个常用的温度衰减函数是其中，取为0.5 0.99之间的数。Skiscim等人
12、固定控制参数值的衰减步数K,把区间0,t0划分为K个小区间，把温度衰减函数取为第25页/共34页-26-冷却进度表的参数设置冷却进度表的参数设置 3.Markov链的长度Lk的选取1）固定长度 Lk通常取为问题规模 n的一个多项式函数。如，Kirkpatric等 Lk=n或100n,Aars等 Lk=邻域规模 2）由接受和拒绝的比率来控制Lk 当温度很高时，Lk应尽量小，随着温度的渐渐下降，Lk逐步增大。第26页/共34页-27-冷却进度表的参数设置冷却进度表的参数设置 3.Markov链的长度Lk的选取2）由接受和拒绝的比率来控制Lk 实现的第一种方法是实现的第一种方法是：给定一个充分大的长
13、度上限U和一个接受次数指标R,当接受次数等于R时，此温度不再迭代而使温度下降。实现的第二种方法是实现的第二种方法是：给定一个接受比率指标R,长度上限U和下限L,当迭代次数超过L时，若接受次数与迭代次数的比率不小于R时，此温度不再迭代而使温度下降，否则，一直迭代到上限步数U。第27页/共34页-28-冷却进度表的参数设置冷却进度表的参数设置 4.终止温度tf（停止准则）的选取1）零度法2）循环总数控制法3）基于不改进规则的控制法4）接受概率控制法 3）和4）的实现：在一个温度和给定的迭代次数内，没有改进当前的局部最优解或接受概率都小于一个给定的比较小的数f,则停止运算.5）邻域法当 时，停止计算
14、。f0,f1分别为一个邻域内的局部最优和次最优，N为邻域的大小。第28页/共34页-29-模拟退火算法的优点模拟退火算法的优点 高效、健壮、通用、灵活1）高效性 与局部搜索算法相比，模拟退火算法可望在较短时间里求得更优近似解；允许任意选取初始解，且能得出较优近似解，因此应用该算法解组合优化问题的前期工作量大大减少。2）健壮性 该算法的实验性能不因组合优化问题实例的不同而蜕变；解的质量和CPU时间均随n的增大而趋于稳定，且不受初始解和随机数序列的影响。第29页/共34页-30-模拟退火算法的优点模拟退火算法的优点 3）通用性和灵活性 该算法能应用于多种组合优化问题，为一个问题编制的程序可有效地用
15、于其他问题。解的质量与CPU时间呈反向关系，针对不同的实例以及不同的解质要求，适当调整冷却进度表的参数值可使算法执行获得最佳的解时关系。第30页/共34页-31-模拟退火算法的不足和改进途径模拟退火算法的不足和改进途径 主要不足是：返回一个高质近似解的时间花费较多。有如下途径改进算法的实验性能、提高算法的执行效率。1）增加一个记忆器 给算法增加一个记忆器，使之能记住搜索过程中遇到过的最好结果，当结束时，将最终解与记忆器中的解比较，取较优者作为最后结果。2）增加返回搜索 在有记忆的模拟退火算法后链接一个局部搜索算法。第31页/共34页-32-参考书参考书1.刑文训 谢金星,现代优化计算方法,清华大学出版社,2001年；2.张颖 刘艳秋,软计算方法,科学出版社,2002年；3.王晓东,算法设计与分析,清华大学出版社,2003年.4.(美)Zbigniew Michalewicz,等著,曹宏庆等译,如何求解问题_现代启发式方法,中国水利水电出版社,2003返回返回第32页/共34页-33-The End第33页/共34页-34-感谢您的观看！第34页/共34页