数学建模——组合优化问题及算法

1、1-2- 组合最优化（组合最优化（combinatorial optimization)combinatorial optimization)是通过是通过对数学方法的研究去寻找离散事件的最优编排、分组、次对数学方法的研究去寻找离散事件的最优编排、分组、次序或筛选等，是运筹学序或筛选等，是运筹学( (operations research)operations research)中的一个中的一个重要分支。所研究的问题涉及信息技术、经济管理、工业重要分支。所研究的问题涉及信息技术、经济管理、工业工程、交通运输、通信网络等领域。该问题可用数学模型工程、交通运输、通信网络等领域。该问题可用数学模型描述

2、为：描述为：Dxxgtsxf 0)(. .)(min 其中其中D D表示有限个点组成的集合。表示有限个点组成的集合。-3- 1. 0-1 1. 0-1背包问题背包问题 设有一个容积为设有一个容积为b b的背包，的背包，n n个体积分别为个体积分别为a ai i(i=1,2,n),(i=1,2,n),价值分别为价值分别为c ci i (i=1,2,n) (i=1,2,n)的物品，如的物品，如何以最大的价值装包？何以最大的价值装包？ nixbxatsxciniiiniii, 1,1 , 0. .max11-4- 2. 2. 旅行商问题旅行商问题( (TSPTSP，traveling salesma

3、n problem)traveling salesman problem) 一个商人欲到一个商人欲到n n个城市推销商品，每两个城市个城市推销商品，每两个城市i i和和j j之之间的距离为间的距离为d dijij，如何选择一条道路使得商人每个城市正如何选择一条道路使得商人每个城市正好走一遍后回到起点且所走路径最短。好走一遍后回到起点且所走路径最短。., 1,1 , 0, 2 , 1, 2|2, 1|, 1, 1, 1, 1. .min,11jinjixnSnSSxnjxnixtsxdijSjiijniijnjijnjiijij-5- 3. 3.有约束的机器调度问题有约束的机器调度问题( (ca

4、pacitated machine capacitated machine scheduling)scheduling) n n个加工量为个加工量为 d di i|i=1,2,n|i=1,2,n的产品在一台机器上加工，的产品在一台机器上加工，机器在第机器在第t t个时段的工作能力为个时段的工作能力为c ct t, ,求完成所有产品加工所需时求完成所有产品加工所需时段数最少的调度方案段数最少的调度方案TtnixTtcxdnixtsTitnititiTtit, 2 , 1, 1,1 , 0,2 , 1, 1, 1. .min11 其中其中x xitit,T,T为决策变量为决策变量,x,xitit=

5、1=1表示产品表示产品i i在第在第t t时段加工时段加工-6- 4. 4. 装箱问题装箱问题( (bin packing)bin packing) 如何把如何把n n个尺寸不超过个尺寸不超过1 1的物品装入尺寸为的物品装入尺寸为1 1的箱子，并使所的箱子，并使所用的箱子个数最少用的箱子个数最少。 5. 5. 二维装箱问题（平面上的套裁问题）二维装箱问题（平面上的套裁问题） 原料的尺寸大于需求的尺寸，需求的品种尺寸可以不同，原料的尺寸大于需求的尺寸，需求的品种尺寸可以不同，最终的目标是在满足需求的前提下，使边角余料最小。最终的目标是在满足需求的前提下，使边角余料最小。 6. 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工序的加工时间为工序的加工时间为p pijij，必须必须按工序进行加工且每一工序必须一次加工完成。一台机器在任按工序进行加工且每一工序必须一次加工完成。一台机器在任何时刻最多只能加工一个产品，一个工件不能同时在两台机器何时刻最多只能加工一个产品，一

7、个工件不能同时在两台机器上加工，如何安排才能使最后一个完工的工件完工时间最小？上加工，如何安排才能使最后一个完工的工件完工时间最小？-7- 7. 7. 最大截问题最大截问题( (MCP,Max Cut Problem)MCP,Max Cut Problem) 8. 8. 图的顶点着色问题图的顶点着色问题（GCP,Graph Colouring Problem)GCP,Graph Colouring Problem) 9. 9. 独立集问题（独立集问题（ISP,Independent Set Problem)ISP,Independent Set Problem) 10. 10.调度问题调度问题

8、( (SCP,Scheduling Problem)SCP,Scheduling Problem) 11. 11.划分问题划分问题( (PAP,Partition Problem)PAP,Partition Problem) 12. 12.布局问题（布局问题（PLP, Placement Problem) PLP, Placement Problem) 上述问题都是上述问题都是NP-hardNP-hard问题，目前人们认为它们不存在问题，目前人们认为它们不存在求解最优解的多项式时间算法，大规模情形只有尝试用一求解最优解的多项式时间算法，大规模情形只有尝试用一些近似算法或启发式算法求解。些近似算

9、法或启发式算法求解。 -8-邻域概念邻域概念 对于组合优化问题对于组合优化问题( (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-邻域概念邻域概念例如，前面例子例如，前面例子2 2给出的给出的TSPTSP问题

10、模型。由解空间问题模型。由解空间D=xD=x 0,10,1n n (n-1)(n-1) ，可以定义它的一种邻域为：可以定义它的一种邻域为：jiijijDykxyxyyxN,|)( k k为一个正整数。为一个正整数。TSPTSP问题解的另一种表示法为问题解的另一种表示法为D=S=(iD=S=(i1 1,i,i2 2,i,in n) )是是1,2,1,2,n n的一个排列的一个排列 -10-邻域概念邻域概念 TSP TSP问题解的另一种表示法为问题解的另一种表示法为D=S=(iD=S=(i1 1,i,i2 2,i,in n) )是是1,2,1,2,n n的一个排列的一个排列 可以定义它的邻域映射为

11、可以定义它的邻域映射为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,4,3). 类似可定义类似可定义k-opt(kk-opt(k 2)2)-11-局部最优与全局最优局部最优与全局最优 若若s s* *满足满足 f(s f

12、(s* *) ) ( ( )f(s),)f(s),其中其中s s N(sN(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)最小（最大）最小（最大）解。解。-12- 启发式算法定义启发式算法定义 一个基于直观或经验构造的算法，在可接受一个基于直观或经验构造的算法，在可接受的花费（计算时间、占用空间等）下

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

14、法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的的 近似算法。近似算法。-14- 1 1）将物品以）将物品以c ci i/a/ai i（单位体积的价值）由大到小的顺单位体积的价值）由大到小的顺序排列，不妨把排列记为序排列，不妨把排列记为1,2,1,2,n,k:=1;n,k:=1;2 2）若若 ，则，则x xk k=1;=1;否则否则x xk k=0,k

15、:=k+1;=0,k:=k+1;3) 3) 当当k=n+1k=n+1时，停止；否则，转时，停止；否则，转2).2).( (x x1 1,x,x2 2,x,xn n) )为贪婪算法所得解，单位体积的价值越为贪婪算法所得解，单位体积的价值越大越先放入是贪婪算法的原则。大越先放入是贪婪算法的原则。11kikiibdxd-15- 给定组合优化问题，假设其邻域结构已确给定组合优化问题，假设其邻域结构已确定，算法为定，算法为1 1）任选一个初始解）任选一个初始解s s0 0 F;F;2) 2) 在在N(sN(s0 0) )中按某一规则选一中按某一规则选一s s；若若f(s)f(sf(s)LlLk k，则到

16、则到4 4）；否则，从邻域）；否则，从邻域N(xN(xi i) )中随机中随机选一选一x xj j, ,计算计算 f fijij=f(x=f(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）t tk+1k+1;k ;k k+1k+1；计算计算L Lk k，若满足若满足，终止计算，否则，回到，终止计算，否则，回到2).2).-21- 已

17、证明，模拟退火算法以已证明，模拟退火算法以1 1的概率收敛到整体的概率收敛到整体最优解集，但渐近收敛到最优解集须经历无限多最优解集，但渐近收敛到最优解集须经历无限多次变换。次变换。 对最优解任意近似的逼近，对多数组合优化对最优解任意近似的逼近，对多数组合优化问题都导致比解空间规模大的变换数，从而导致问题都导致比解空间规模大的变换数，从而导致算法的指数时间执行。算法的指数时间执行。 解决办法：牺牲保证得到最优解为代价，在解决办法：牺牲保证得到最优解为代价，在多项式时间里，逼近模拟退火算法的渐近收敛状多项式时间里，逼近模拟退火算法的渐近收敛状态，返回一个近似最优解。态，返回一个近似最优解。-22-

18、数学模型数学模型 解空间、目标函数和初始解解空间、目标函数和初始解2 2）新解的产生和接受机制）新解的产生和接受机制新解产生新解产生: :当前解经简单变换产生新解（决定当前解经简单变换产生新解（决定了当前解的邻域结构），如对当前解的全部了当前解的邻域结构），如对当前解的全部或部分元素进行置换、互换或反演等。或部分元素进行置换、互换或反演等。MetropolisMetropolis接受准则接受准则: : 3 3）冷却进度表的设定）冷却进度表的设定0)/exp(01ftffP-23- 冷却进度表是一组控制算法进程的参数，冷却进度表是一组控制算法进程的参数，它包括：它包括：1.1.初始温度初始温度t

19、 t0 0 =tmax=tmax2.2.温度衰减函数温度衰减函数T(t)T(t)3.Markov3.Markov链的长度链的长度L Lk k4.4.终止温度终止温度t tf f（停止准则）（停止准则） 。-24- 虽然已经证明模拟退火算法在一定条件虽然已经证明模拟退火算法在一定条件下的渐近收敛性。但这并不意味着任意下的渐近收敛性。但这并不意味着任意冷却冷却进度表都能确保算法收敛进度表都能确保算法收敛，不合理的冷却进不合理的冷却进度表会使算法在某些解间度表会使算法在某些解间“振荡振荡”而不能收而不能收敛于某一近似解。敛于某一近似解。 模拟退火算法的最终解质量和模拟退火算法的最终解质量和CPUCP

20、U时间呈时间呈反向关系，很难两全其美，妥善解决办法只反向关系，很难两全其美，妥善解决办法只有：折中，即在合理的有：折中，即在合理的CPUCPU时间里尽量提高最时间里尽量提高最终解的质量。这涉及到冷却进度表所有参数终解的质量。这涉及到冷却进度表所有参数的合理选取。的合理选取。 -25-1.1.初始温度初始温度t t0 0 的选取的选取 t t0 0 要取得足够大，要取得足够大，JohnsonJohnson等建议通过等建议通过计算若干次随机变换目标函数平均增量的方计算若干次随机变换目标函数平均增量的方法来确定法来确定t t0 0的值。的值。)ln(100ft其中，其中， 为上述平均增量，为上述平均

21、增量， 为初始接受率，为初始接受率，一般取一般取0.80.8 1 1之间的数。之间的数。f0-26-2.2.温度衰减函数温度衰减函数T(t)T(t)的选取的选取 一个常用的温度衰减函数是温度衰减函数是, 2 , 1 , 0,1kttkk其中，取为0.5 0.990.99之间的数。之间的数。 SkiscimSkiscim等人固定控制参数值的衰减步等人固定控制参数值的衰减步数数K,K, 把区间把区间0,0,t t0 0 划分为划分为K K个小区间，把温个小区间，把温度衰减函数取为度衰减函数取为KktKkKtk, 2 , 1,0-27-3.Markov3.Markov链的长度链的长度L Lk k的选

22、取的选取1 1）固定长度固定长度 L Lk k通常取为问题规模通常取为问题规模 n n的一个多项式函数。的一个多项式函数。如，如，KirkpatricKirkpatric等等 L Lk k=n=n或或100100n,n, Aars Aars等等 L Lk k= =邻域规模邻域规模 2 2）由接受和拒绝的比率来控制）由接受和拒绝的比率来控制L Lk k 当温度很高时，当温度很高时，L Lk k应尽量小，随着温度的应尽量小，随着温度的渐渐下降，渐渐下降，L Lk k逐步增大。逐步增大。 -28-3.Markov3.Markov链的长度链的长度L Lk k的选取的选取2 2）由接受和拒绝的比率来控制

23、）由接受和拒绝的比率来控制L Lk k ：给定一个充分大的：给定一个充分大的长度上限长度上限U U和一个接受次数指标和一个接受次数指标R,R,当接受次数等当接受次数等于于R R时，此温度不再迭代而使温度下降。时，此温度不再迭代而使温度下降。 ：给定一个接受比率：给定一个接受比率指标指标R,R,长度上限长度上限U U和下限和下限L,L,当迭代次数超过当迭代次数超过L L时时，若接受次数与迭代次数的比率不小于，若接受次数与迭代次数的比率不小于R R时，此时，此温度不再迭代而使温度下降，否则，一直迭代温度不再迭代而使温度下降，否则，一直迭代到上限步数到上限步数U U。-29-4.4.终止温度终止温度

24、t tf f（停止准则）的选取（停止准则）的选取1 1）零度法零度法2 2）循环总数控制法）循环总数控制法3 3）基于不改进规则的控制法）基于不改进规则的控制法4 4）接受概率控制法）接受概率控制法 3 3）和）和4 4）的实现：在一个温度和给定的迭代次）的实现：在一个温度和给定的迭代次数内，没有改进当前的局部最优解或接受概率都小数内，没有改进当前的局部最优解或接受概率都小于一个给定的比较小的数于一个给定的比较小的数 f f, ,则停止运算则停止运算. .5 5）邻域法）邻域法当当 时，停止计算。时，停止计算。f f0 0,f,f1 1分别为一个分别为一个邻域内的局部最优和次最优，邻域内的局部最优和次最优，N N为邻域的大小。为邻域的大小。Ntff1)exp(01-30- 高效、健壮、通用、灵活高效、健壮、通用、灵活1 1）高效性）高效性 与局部搜索算法相比，模拟退火算法可望在与局部搜索算法相比，模拟退火算法可望在较短时间里求得更优近似解；允许任意选取初始较短时间里求得更优近似解；允许任意选取初始解，且能得出较优近似解，因此应用该算法解组解，且能得出较优近似解，因此应用该算法解组合优化问题的前期工作量大大减少。合优化问题的前期工作量大大减少。2 2）健壮性健壮性