组合优化问题及算法

《组合优化问题及算法》由会员分享，可在线阅读，更多相关《组合优化问题及算法（34页珍藏版）》请在金锄头文库上搜索。

1、MATHEMATICA MODEL制作制作: : 龚劬龚劬组合优化问题组合优化问题 及其算法及其算法 1组合最优化（combinatorial optimization)是通过 对数学方法的研究去寻找离散事件的最优编排、分组、次 序或筛选等，是运筹学(operations research)中的一个 重要分支。所研究的问题涉及信息技术、经济管理、工业 工程、交通运输、通信网络等领域。该问题可用数学模型 描述为：引言 其中D表示有限个点组成的集合。21. 0-1背包问题设有一个容积为b的背包，n个体积分别为ai(i=1,2,n),价值分别为ci (i=1,2,n)的物品，如 何以最大的价值装包？

2、 一些例子 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个尺寸不超过

3、1的物品装入尺寸为1的箱子，并使所 用的箱子个数最少。5. 二维装箱问题（平面上的套裁问题）原料的尺寸大于需求的尺寸，需求的品种尺寸可以不同， 最终的目标是在满足需求的前提下，使边角余料最小。6. 车间作业调度问题(job shop scheduling)n个工件，J1,Jn在m台机器M1,M2,Mm上加工。每个工件 Ji有ni个工序，Oi1,Oini,第Oij工序的加工时间为pij，必须按 工序进行加工且每一工序必须一次加工完成。一台机器在任何 时刻最多只能加工一个产品，一个工件不能同时在两台机器上 加工，如何安排才能使最后一个完工的工件完工时间最小？一些例子 67. 最大截问题(MCP,M

4、ax 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

5、称为一个邻域映射，其中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)

6、=(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启发式算法定义 一个基于直观或经验构造的算法，在可接受 的花费（计算时间、占用空间等）下给出待解决 问题每一个实例的一个可行解，该解与最优解的 偏离程度不一定能预计。启发式算法是一种技术，使在可接

7、受的计算 开销内寻找最好的解，但不一定能保证所得解的 可行性和最优性，甚至多数情况下，无法给出所 得解同最优解的近似程度。 启发式算法 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,x

8、n)为贪婪算法所得解，单位体积的价值越 大越先放入是贪婪算法的原则。启发式算法 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模拟退火算法的渐近收

9、敛性 已证明，模拟退火算法以1的概率收敛到整体 最优解集，但渐近收敛到最优解集须经历无限多 次变换。对最优解任意近似的逼近，对多数组合优化 问题都导致比解空间规模大的变换数，从而导致 算法的指数时间执行。解决办法：牺牲保证得到最优解为代价，在 多项式时间里，逼近模拟退火算法的渐近收敛状 态，返回一个近似最优解。21模拟退火算法应用的一般要求1) 数学模型解空间、目标函数和初始解 2）新解的产生和接受机制 新解产生:当前解经简单变换产生新解（决定 了当前解的邻域结构），如对当前解的全部 或部分元素进行置换、互换或反演等。 Metropolis接受准则:3）冷却进度表的设定22冷却进度表 冷却进度

10、表是一组控制算法进程的参数 ，它包括：1.初始温度t0 =tmax2.温度衰减函数T(t)3.Markov链的长度Lk4.终止温度tf（停止准则） 。23冷却进度表 虽然已经证明模拟退火算法在一定条件 下的渐近收敛性。但这并不意味着任意冷却 进度表都能确保算法收敛，不合理的冷却进 度表会使算法在某些解间“振荡”而不能收 敛于某一近似解。模拟退火算法的最终解质量和CPU时间呈 反向关系，很难两全其美，妥善解决办法只 有：折中，即在合理的CPU时间里尽量提高最 终解的质量。这涉及到冷却进度表所有参数 的合理选取。 24冷却进度表的参数设置 1.初始温度t0 的选取t0 要取得足够大，Johnson

11、等建议通过 计算若干次随机变换目标函数平均增量的方 法来确定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应

12、尽量小，随着温度的渐 渐下降，Lk逐步增大。 27冷却进度表的参数设置 3.Markov链的长度Lk的选取 2）由接受和拒绝的比率来控制Lk实现的第一种方法是实现的第一种方法是：给定一个充分大的 长度上限U和一个接受次数指标R,当接受次数等 于R时，此温度不再迭代而使温度下降。实现的第二种方法是实现的第二种方法是：给定一个接受比率 指标R,长度上限U和下限L,当迭代次数超过L时 ，若接受次数与迭代次数的比率不小于R时，此 温度不再迭代而使温度下降，否则，一直迭代 到上限步数U。28冷却进度表的参数设置 4.终止温度tf（停止准则）的选取 1）零度法 2）循环总数控制法 3）基于不改进规则的控制

13、法 4）接受概率控制法3）和4）的实现：在一个温度和给定的迭代次 数内，没有改进当前的局部最优解或接受概率都小 于一个给定的比较小的数f,则停止运算. 5）邻域法 当 时，停止计算。f0,f1分别为一个邻 域内的局部最优和次最优，N为邻域的大小。 29模拟退火算法的优点 高效、健壮、通用、灵活1）高效性与局部搜索算法相比，模拟退火算法可望在 较短时间里求得更优近似解；允许任意选取初始 解，且能得出较优近似解，因此应用该算法解组 合优化问题的前期工作量大大减少。2）健壮性该算法的实验性能不因组合优化问题实例的不同而 蜕变；解的质量和CPU时间均随n的增大而趋于稳 定，且不受初始解和随机数序列的影

14、响。30模拟退火算法的优点 3）通用性和灵活性该算法能应用于多种组合优化问题，为一个 问题编制的程序可有效地用于其他问题。解的质 量与CPU时间呈反向关系，针对不同的实例以及不 同的解质要求，适当调整冷却进度表的参数值可 使算法执行获得最佳的解时关系。31模拟退火算法的不足和改进途径 主要不足是：返回一个高质近似解的时间 花费较多。有如下途径改进算法的实验性能、 提高算法的执行效率。 1）增加一个记忆器 给算法增加一个记忆器，使之能记住搜索 过程中遇到过的最好结果，当结束时，将最终 解与记忆器中的解比较，取较优者作为最后结 果。 2）增加返回搜索在有记忆的模拟退火算法后链接一个局部 搜索算法。 32参考书1.刑文训 谢金星,现代优化计算方法,清华大学出版社,2001年；2.张颖 刘艳秋, 软计算方法,科学出版社,2002年；3.王晓东, 算法设计与分析,清华大学出版社,2003年.4.(美) Zbigniew Michalewicz,等著,曹宏庆等译,如何求解问题_现代启发式方法,中国水利水电出版社,2003返回返回33The End34