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