组合优化问题及算法课件.ppt

《组合优化问题及算法课件.ppt》由会员分享，可在线阅读，更多相关《组合优化问题及算法课件.ppt（34页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、MATHEMATICA MODEL制作制作:龚劬龚劬组合优化问题组合优化问题及其算法及其算法 组组合合最最优优化化（combinatorial combinatorial optimization)optimization)是是通通过过对对数数学学方方法法的的研研究究去去寻寻找找离离散散事事件件的的最最优优编编排排、分分组组、次次序序或或筛筛选选等等，是是运运筹筹学学(operations operations research)research)中中的的一一个个重重要要分分支支。所所研研究究的的问问题题涉涉及及信信息息技技术术、经经济济管管理理、工工业业工工程程、交交通通运运输输、通通信信网

2、网络络等等领领域域。该该问问题题可可用用数数学学模模型型描述为：描述为：引言引言 其中其中D D表示有限个点组成的集合。表示有限个点组成的集合。2 1.0-1 1.0-1背包问题背包问题 设有一个容积为设有一个容积为b b的背包，的背包，n n个体积分别为个体积分别为a ai i(i(i=1,2,n),=1,2,n),价价值值分分别别为为c ci i (i=1,2,n)(i=1,2,n)的的物物品品，如如何以最大的价值装包？何以最大的价值装包？一些例子一些例子 3 2.2.旅行商问题旅行商问题(TSPTSP，travelingtraveling salesman problem)salesma

3、n problem)一一个个商商人人欲欲到到n n个个城城市市推推销销商商品品，每每两两个个城城市市i i和和j j之之间间的的距距离离为为d dijij，如如何何选选择择一一条条道道路路使使得得商商人人每每个个城城市市正正好好走一遍后回到起点且所走路径最短。走一遍后回到起点且所走路径最短。一些例子一些例子 4 3.3.有有 约约 束束 的的 机机 器器 调调 度度 问问 题题(capacitated capacitated machine machine scheduling)scheduling)n n个个加加工工量量为为 d di i|i|i=1,2,n=1,2,n的的产产品品在在一一台

4、台机机器器上上加加工工，机机器器在在第第t t个个时时段段的的工工作作能能力力为为c ct t,求求完完成成所所有有产产品品加加工工所所需需时时段数最少的调度方案段数最少的调度方案一些例子一些例子 其中其中x xitit,T,T为决策变量为决策变量,x xitit=1=1表示产品表示产品i i在第在第t t时段加工时段加工5 4.4.装箱问题装箱问题(bin packing)bin packing)如如何何把把n n个个尺尺寸寸不不超超过过1 1的的物物品品装装入入尺尺寸寸为为1 1的的箱箱子子，并并使使所所用的箱子个数最少用的箱子个数最少。5.5.二维装箱问题（平面上的套裁问题）二维装箱问题

5、（平面上的套裁问题）原原料料的的尺尺寸寸大大于于需需求求的的尺尺寸寸，需需求求的的品品种种尺尺寸寸可可以以不不同同，最终的目标是在满足需求的前提下，使边角余料最小。最终的目标是在满足需求的前提下，使边角余料最小。6.6.车间作业调度问题车间作业调度问题(job shop scheduling)job shop scheduling)n n个个工工件件，J J1 1,J Jn n在在m m台台机机器器M M1 1,M,M2 2,M,Mm m上上加加工工。每每个个工工件件J Ji i有有n ni i个个工工序序，O Oi1i1,O Oiniini,第第O Oijij工工序序的的加加工工时时间间为为

6、p pijij，必必须须按按工工序序进进行行加加工工且且每每一一工工序序必必须须一一次次加加工工完完成成。一一台台机机器器在在任任何何时时刻刻最最多多只只能能加加工工一一个个产产品品，一一个个工工件件不不能能同同时时在在两两台台机机器器上上加工，如何安排才能使最后一个完工的工件完工时间最小？加工，如何安排才能使最后一个完工的工件完工时间最小？一些例子一些例子 6 7.7.最大截问题最大截问题(MCP,MaxMCP,Max Cut Problem)Cut Problem)8.8.图的顶点着色问题图的顶点着色问题（GCP,GraphGCP,Graph ColouringColouring Prob

7、lem)Problem)9.9.独立集问题（独立集问题（ISP,IndependentISP,Independent Set Problem)Set Problem)10.10.调度问题调度问题(SCP,SchedulingSCP,Scheduling Problem)Problem)11.11.划分问题划分问题(PAP,PartitionPAP,Partition Problem)Problem)12.12.布局问题（布局问题（PLP,Placement Problem)PLP,Placement Problem)上上述述问问题题都都是是NP-hardNP-hard问问题题，目目前前人人们们

8、认认为为它它们们不不存存在在求求解解最最优优解解的的多多项项式式时时间间算算法法，大大规规模模情情形形只只有有尝尝试试用用一一些近似算法或启发式算法求解。些近似算法或启发式算法求解。一些例子一些例子 7邻域概念邻域概念 对于组合优化问题对于组合优化问题(D,F,f),DD,F,f),D上的一个映射：上的一个映射：N:S N:S D D N(S)N(S)2 2D D称称为为一一个个邻邻域域映映射射，其其中中2 2D D表表示示D D的的所所有有子子集集构构成的集合，成的集合，N(S)N(S)称为称为S S的邻域。的邻域。邻邻域域的的构构造造依依赖赖于于问问题题决决策策变变量量的的表表示示，邻邻域

9、的结构在现代化优化算法中起重要作用。域的结构在现代化优化算法中起重要作用。启发式算法启发式算法 8邻域概念邻域概念例如，前面例子例如，前面例子2 2给出的给出的TSPTSP问题模型。由解空间问题模型。由解空间D=xD=x 0,10,1n n(n-1)(n-1)，可以定义它的一种邻域为：可以定义它的一种邻域为：启发式算法启发式算法 k k为一个正整数。为一个正整数。TSPTSP问题解的另一种表示法为问题解的另一种表示法为D=S=(iD=S=(i1 1,i,i2 2,i,in n)是是1,2,1,2,n n的一个排列的一个排列 9邻域概念邻域概念启发式算法启发式算法 TSP TSP问题解的另一种表

10、示法为问题解的另一种表示法为D=S=(iD=S=(i1 1,i,i2 2,i,in n)是是1,2,1,2,n n的一个排列的一个排列 可可以以定定义义它它的的邻邻域域映映射射为为2-2-optopt，即即S S中中的的两两个个元素对换。元素对换。如如4 4个个城城市市的的TSPTSP问问题题，当当S=(1,2,3,4)S=(1,2,3,4)时时，N(S)=(2,1,3,4),(3,2,1,4),(4,2,3,1),(1,3,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).2,4),(1,4,3,2),(1,2,

11、4,3).类似可定义类似可定义k-opt(kk-opt(k 2)2)10局部最优与全局最优局部最优与全局最优启发式算法启发式算法 若若s*s*满足满足 f(s*)f(s*)()f(s),)f(s),其中其中s s N(s*)N(s*)F,F,则称则称s*s*为为f f在在F F上的局部上的局部(local)local)最小（最大）解。最小（最大）解。若若s*s*满足满足 f(s*)f(s*)()f(s),)f(s),其中其中s s F,F,则则称称s*s*为为f f在在F F上上的的全全局局(global)global)最最小小（最最大大）解。解。11 启发式算法定义启发式算法定义 一一个个基

12、基于于直直观观或或经经验验构构造造的的算算法法，在在可可接接受受的的花花费费（计计算算时时间间、占占用用空空间间等等）下下给给出出待待解解决决问问题题每每一一个个实实例例的的一一个个可可行行解解，该该解解与与最最优优解解的的偏离程度不一定能预计。偏离程度不一定能预计。启启发发式式算算法法是是一一种种技技术术，使使在在可可接接受受的的计计算算开开销销内内寻寻找找最最好好的的解解，但但不不一一定定能能保保证证所所得得解解的的可可行行性性和和最最优优性性，甚甚至至多多数数情情况况下下，无无法法给给出出所所得解同最优解的近似程度。得解同最优解的近似程度。启发式算法启发式算法 12近似算法定义近似算法定

13、义 记记问问题题A A的的任任何何一一个个实实例例I I的的最最优优解解和和启启发发式式算算法法H H解解的的目目标标值值分分别别为为z zoptopt(I(I)和和z zH H(I(I),),若若对对某某个正数个正数0 0，有，有|z zH H(I)-z(I)-zoptopt(I(I)|)|z zoptopt(I)|(I)|，I I A A则称则称H H是是A A的的 近似算法。近似算法。启发式算法启发式算法 13 背包问题的贪婪算法背包问题的贪婪算法1 1）将将物物品品以以c ci i/a/ai i（单单位位体体积积的的价价值值）由由大大到到小小的的顺顺序序排列，不妨把排列记为排列，不妨把

14、排列记为1,2,1,2,n,kn,k:=1;:=1;2 2）若若 ，则，则x xk k=1;=1;否则否则x xk k=0,k:=k+1;=0,k:=k+1;3)3)当当k=n+1k=n+1时，停止；否则，转时，停止；否则，转2).2).(x x1 1,x,x2 2,x xn n)为为贪贪婪婪算算法法所所得得解解，单单位位体体积积的的价价值值越越大越先放入是贪婪算法的原则。大越先放入是贪婪算法的原则。启发式算法启发式算法 14 简单的邻域搜索算法 给给定定组组合合优优化化问问题题，假假设设其其邻邻域域结结构构已已确确定定，算法为算法为1 1）任选一个初始解）任选一个初始解s s0 0 F;F;

15、2)2)在在N(sN(s0 0)中中按按某某一一规规则则选选一一s s；若若f(sf(s)f(s)lL Lk k，则则到到4 4）；否否则则，从从邻邻域域N(xN(xi i)中中随随机机选选一一x xj j,计计算算 f fijij=f(xf(xj j)-f(x)-f(xi i););l ll+1;l+1;若若 f fijij 0 0，则则x xi ix xj j;否否则则,若若exp(-exp(-f fijij/t/tk k)random)random（0,1)0,1)）时，时，x xi ix xj j；重复重复3 3）；）；4)4)4 4）t tk+1k+1T(tT(tT(tT(tk k

16、k k);k;k k+1k+1；计计算算L Lk k，若若满满足足停停停停止止止止条条条条件件件件，终止计算，否则，回到，终止计算，否则，回到2).2).20模拟退火算法的渐近收敛性模拟退火算法的渐近收敛性 已已证证明明，模模拟拟退退火火算算法法以以1 1的的概概率率收收敛敛到到整整体体最最优优解解集集，但但渐渐近近收收敛敛到到最最优优解解集集须须经经历历无无限限多多次变换。次变换。对对最最优优解解任任意意近近似似的的逼逼近近，对对多多数数组组合合优优化化问问题题都都导导致致比比解解空空间间规规模模大大的的变变换换数数，从从而而导导致致算法的指数时间执行。算法的指数时间执行。解解决决办办法法：

17、牺牺牲牲保保证证得得到到最最优优解解为为代代价价，在在多多项项式式时时间间里里，逼逼近近模模拟拟退退火火算算法法的的渐渐近近收收敛敛状状态，返回一个近似最优解。态，返回一个近似最优解。21模拟退火算法应用的一般要求模拟退火算法应用的一般要求1)1)数学模型数学模型2)2)解空间、目标函数和初始解解空间、目标函数和初始解2 2）新解的产生和接受机制）新解的产生和接受机制新解产生新解产生:当前解经简单变换产生新解（决定当前解经简单变换产生新解（决定了当前解的邻域结构），如对当前解的全部了当前解的邻域结构），如对当前解的全部或部分元素进行置换、互换或反演等。或部分元素进行置换、互换或反演等。Metr

18、opolisMetropolis接受准则接受准则:3 3）冷却进度表的设定）冷却进度表的设定22冷却进度表冷却进度表 冷却进度表是一组控制算法进程的参数，冷却进度表是一组控制算法进程的参数，它包括：它包括：1.1.初始温度初始温度t t0 0=tmaxtmax2.2.温度衰减函数温度衰减函数T(tT(t)3.Markov3.Markov链的长度链的长度L Lk k4.4.终止温度终止温度t tf f（停止准则）（停止准则）。23冷却进度表冷却进度表 虽然已经证明模拟退火算法在一定条件虽然已经证明模拟退火算法在一定条件下的渐近收敛性。但这并不意味着任意下的渐近收敛性。但这并不意味着任意冷却冷却进

19、度表都能确保算法收敛进度表都能确保算法收敛，不合理的冷却进不合理的冷却进度表会使算法在某些解间度表会使算法在某些解间“振荡振荡”而不能收而不能收敛于某一近似解。敛于某一近似解。模拟退火算法的最终解质量和模拟退火算法的最终解质量和CPUCPU时间呈时间呈反向关系，很难两全其美，妥善解决办法只反向关系，很难两全其美，妥善解决办法只有：折中，即在合理的有：折中，即在合理的CPUCPU时间里尽量提高最时间里尽量提高最终解的质量。这涉及到冷却进度表所有参数终解的质量。这涉及到冷却进度表所有参数的合理选取。的合理选取。24冷却进度表的参数设置冷却进度表的参数设置 1.1.初始温度初始温度t t0 0的选取

20、的选取 t t0 0 要取得足够大，要取得足够大，JohnsonJohnson等建议通过等建议通过计算若干次随机变换目标函数平均增量的方计算若干次随机变换目标函数平均增量的方法来确定法来确定t t0 0的值。的值。其中，其中，为上述平均增量，为上述平均增量，为初始接受率，为初始接受率，一般取一般取0.80.8 1 1之间的数。之间的数。25冷却进度表的参数设置冷却进度表的参数设置 2.2.温度衰减函数温度衰减函数T(tT(t)的选取的选取 一个常用的温度衰减函数是温度衰减函数是其中，取为0.5 0.990.99之间的数。之间的数。SkiscimSkiscim等人固定控制参数值的衰减步数等人固定

21、控制参数值的衰减步数K,K,把区间把区间0,0,t t0 0 划分为划分为K K个小区间，把温度个小区间，把温度衰减函数取为衰减函数取为26冷却进度表的参数设置冷却进度表的参数设置 3.Markov3.Markov链的长度链的长度L Lk k的选取的选取1 1）固定长度固定长度 L Lk k通常取为问题规模通常取为问题规模 n n的一个多项式函数。的一个多项式函数。如，如，KirkpatricKirkpatric等等 L Lk k=n=n或或100100n,n,AarsAars等等 L Lk k=邻域规模邻域规模 2 2）由接受和拒绝的比率来控制）由接受和拒绝的比率来控制L Lk k 当温度很

22、高时，当温度很高时，L Lk k应尽量小，随着温度的渐应尽量小，随着温度的渐渐下降，渐下降，L Lk k逐步增大。逐步增大。27冷却进度表的参数设置冷却进度表的参数设置 3.Markov3.Markov链的长度链的长度L Lk k的选取的选取2 2）由接受和拒绝的比率来控制）由接受和拒绝的比率来控制L Lk k 实现的第一种方法是实现的第一种方法是实现的第一种方法是实现的第一种方法是：给定一个充分大的：给定一个充分大的长度上限长度上限U U和一个接受次数指标和一个接受次数指标R,R,当接受次数等当接受次数等于于R R时，此温度不再迭代而使温度下降。时，此温度不再迭代而使温度下降。实现的第二种方

23、法是实现的第二种方法是实现的第二种方法是实现的第二种方法是：给定一个接受比率：给定一个接受比率指标指标R,R,长度上限长度上限U U和下限和下限L,L,当迭代次数超过当迭代次数超过L L时，时，若接受次数与迭代次数的比率不小于若接受次数与迭代次数的比率不小于R R时，此温时，此温度不再迭代而使温度下降，否则，一直迭代到度不再迭代而使温度下降，否则，一直迭代到上限步数上限步数U U。28冷却进度表的参数设置冷却进度表的参数设置 4.4.终止温度终止温度t tf f（停止准则）的选取（停止准则）的选取1 1）零度法零度法2 2）循环总数控制法）循环总数控制法3 3）基于不改进规则的控制法）基于不改

24、进规则的控制法4 4）接受概率控制法）接受概率控制法 3 3）和）和4 4）的实现：在一个温度和给定的迭代次）的实现：在一个温度和给定的迭代次数内，没有改进当前的局部最优解或接受概率都小数内，没有改进当前的局部最优解或接受概率都小于一个给定的比较小的数于一个给定的比较小的数 f f,则停止运算则停止运算.5 5）邻域法）邻域法当当 时，停止计算。时，停止计算。f f0 0,f,f1 1分别为一个邻分别为一个邻域内的局部最优和次最优，域内的局部最优和次最优，N N为邻域的大小。为邻域的大小。29模拟退火算法的优点模拟退火算法的优点 高效、健壮、通用、灵活高效、健壮、通用、灵活1 1）高效性）高效

25、性 与与局局部部搜搜索索算算法法相相比比，模模拟拟退退火火算算法法可可望望在在较较短短时时间间里里求求得得更更优优近近似似解解；允允许许任任意意选选取取初初始始解解，且且能能得得出出较较优优近近似似解解，因因此此应应用用该该算算法法解解组组合优化问题的前期工作量大大减少。合优化问题的前期工作量大大减少。2 2）健壮性健壮性 该该算算法法的的实实验验性性能能不不因因组组合合优优化化问问题题实实例例的的不不同同而而蜕蜕变变；解解的的质质量量和和CPUCPU时时间间均均随随n n的的增增大大而而趋趋于于稳稳定，且不受初始解和随机数序列的影响。定，且不受初始解和随机数序列的影响。30模拟退火算法的优点

26、模拟退火算法的优点 3 3）通用性和灵活性）通用性和灵活性 该该算算法法能能应应用用于于多多种种组组合合优优化化问问题题，为为一一个个问问题题编编制制的的程程序序可可有有效效地地用用于于其其他他问问题题。解解的的质质量量与与CPUCPU时时间间呈呈反反向向关关系系，针针对对不不同同的的实实例例以以及及不不同同的的解解质质要要求求，适适当当调调整整冷冷却却进进度度表表的的参参数数值值可可使算法执行获得最佳的解时关系。使算法执行获得最佳的解时关系。31模拟退火算法的不足和改进途径模拟退火算法的不足和改进途径 主要不足是：返回一个高质近似解的时间主要不足是：返回一个高质近似解的时间花费较多。有如下途

27、径改进算法的实验性能、花费较多。有如下途径改进算法的实验性能、提高算法的执行效率。提高算法的执行效率。1 1）增加一个记忆器）增加一个记忆器 给算法增加一个记忆器，使之能记住搜索给算法增加一个记忆器，使之能记住搜索过程中遇到过的最好结果，当结束时，将最终过程中遇到过的最好结果，当结束时，将最终解与记忆器中的解比较，取较优者作为最后结解与记忆器中的解比较，取较优者作为最后结果。果。2 2）增加返回搜索）增加返回搜索 在有记忆的模拟退火算法后链接一个局部在有记忆的模拟退火算法后链接一个局部搜索算法。搜索算法。32参考书参考书1.刑文训 谢金星,现代优化计算方法,清华大学出版社,2001年；2.张颖 刘艳秋,软计算方法,科学出版社,2002年；3.王晓东,算法设计与分析,清华大学出版社,2003年.4.(美)Zbigniew Michalewicz,等著,曹宏庆等译,如何求解问题_现代启发式方法,中国水利水电出版社,2003返回返回返回返回33The End34