组合优化问题及算法

MATHEMATICAMODEL制作:龚劬组合优化问题及其算法-2-组合最优化（combinatorialoptimization)是通过对数学方法的研究去寻找离散事件的最优编排、分组、次序或筛选等，是运筹学(operationsresearch)中的一个重要分支。所研究的问题涉及信息技术、经济管理、工业工程、交通运输、通信网络等领域。该问题可用数学模型描述为：引言Dxxgtsxf0)(..)(min其中D表示有限个点组成的集合。-3-1.0-1背包问题设有一个容积为b的背包，n个体积分别为ai(i=1,2,…,n),价值分别为ci(i=1,2,…,n)的物品，如何以最大的价值装包？一些例子nixbxatsxciniiiniii,,1},1,0{..max11-4-2.旅行商问题(TSP，travelingsalesmanproblem)一个商人欲到n个城市推销商品，每两个城市i和j之间的距离为dij，如何选择一条道路使得商人每个城市正好走一遍后回到起点且所走路径最短。一些例子.,,,1,},1,0{},,2,1{,2||2,1||,,1,1,,1,1..min,11jinjixnSnSSxnjxnixtsxdijSjiijniijnjijnjiijij-5-3.有约束的机器调度问题(capacitatedmachinescheduling)n个加工量为{di|i=1,2,…,n}的产品在一台机器上加工，机器在第t个时段的工作能力为ct,求完成所有产品加工所需时段数最少的调度方案一些例子TtnixTtcxdnixtsTitnititiTtit,,2,1,,,1},1,0{,2,1,,,1,1..min11其中xit,T为决策变量,xit=1表示产品i在第t时段加工-6-4.装箱问题(binpacking)如何把n个尺寸不超过1的物品装入尺寸为1的箱子，并使所用的箱子个数最少。5.二维装箱问题（平面上的套裁问题）原料的尺寸大于需求的尺寸，需求的品种尺寸可以不同，最终的目标是在满足需求的前提下，使边角余料最小。6.车间作业调度问题(jobshopscheduling)n个工件，J1,…,Jn在m台机器M1,M2,…,Mm上加工。每个工件Ji有ni个工序，Oi1,…,Oini,第Oij工序的加工时间为pij，必须按工序进行加工且每一工序必须一次加工完成。一台机器在任何时刻最多只能加工一个产品，一个工件不能同时在两台机器上加工，如何安排才能使最后一个完工的工件完工时间最小？一些例子-7-7.最大截问题(MCP,MaxCutProblem)8.图的顶点着色问题（GCP,GraphColouringProblem)9.独立集问题（ISP,IndependentSetProblem)10.调度问题(SCP,SchedulingProblem)11.划分问题(PAP,PartitionProblem)12.布局问题（PLP,PlacementProblem)……上述问题都是NP-hard问题，目前人们认为它们不存在求解最优解的多项式时间算法，大规模情形只有尝试用一些近似算法或启发式算法求解。一些例子-8-邻域概念对于组合优化问题(D,F,f),D上的一个映射：N:SDN(S)2D称为一个邻域映射，其中2D表示D的所有子集构成的集合，N(S)称为S的邻域。邻域的构造依赖于问题决策变量的表示，邻域的结构在现代化优化算法中起重要作用。启发式算法-9-邻域概念例如，前面例子2给出的TSP问题模型。由解空间D={x{0,1}n(n-1)}，可以定义它的一种邻域为：启发式算法jiijijDykxyxyyxN,},||||{)(k为一个正整数。TSP问题解的另一种表示法为D={S=(i1,i2,…,in)是1,2,…,n的一个排列}-10-邻域概念启发式算法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(k2)-11-局部最优与全局最优启发式算法若s*满足f(s*)()f(s),其中sN(s*)F,则称s*为f在F上的局部(local)最小（最大）解。若s*满足f(s*)()f(s),其中sF,则称s*为f在F上的全局(global)最小（最大）解。-12-启发式算法定义一个基于直观或经验构造的算法，在可接受的花费（计算时间、占用空间等）下给出待解决问题每一个实例的一个可行解，该解与最优解的偏离程度不一定能预计。启发式算法是一种技术，使在可接受的计算开销内寻找最好的解，但不一定能保证所得解的可行性和最优性，甚至多数情况下，无法给出所得解同最优解的近似程度。启发式算法-13-近似算法定义记问题A的任何一个实例I的最优解和启发式算法H解的目标值分别为zopt(I)和zH(I),若对某个正数0，有|zH(I)-zopt(I)||zopt(I)|，IA则称H是A的近似算法。启发式算法-14-背包问题的贪婪算法1）将物品以ci/ai（单位体积的价值）由大到小的顺序排列，不妨把排列记为{1,2,…,n},k:=1;2）若，则xk=1;否则xk=0,k:=k+1;3)当k=n+1时，停止；否则，转2).(x1,x2,…,xn)为贪婪算法所得解，单位体积的价值越大越先放入是贪婪算法的原则。启发式算法11kikiibdxd-15-简单的邻域搜索算法给定组合优化问题，假设其邻域结构已确定，算法为1）任选一个初始解s0F;2)在N(s0)中按某一规则选一s；若f(s)f(s0),则s0s；否则，N(s0)N(s0)-s;3)若N(s0)=,停止；否则，返回2).启发式算法-16-算法停止时得到点的性质依赖算法初始解的选取、邻域的结构.只要选好初始点，就一定可以求到最优解。对NP-hard的组合最优化问题，确定这样的初始点非常困难。如何选初始点和如何跳出局部最优值点以达到全局最优点是许多算法的关键。启发式算法-17-启发式算法的类型1.一步算法（构造型算法）2.改进型算法3.数学规划算法4.解空间松弛算法5.现代化优化算法禁忌搜索（tabusearch),模拟退火（simulatedannealing),遗传算法（geneticalgorithms),人工神经网络(neuralnetworks),蚂蚁算法(antalgorithm).-18-模拟退火算法1982年，Kirkpatric等将退火思想引入组合优化领域，提出一种解大规模组合优化问题，特别是NP-hard的组合优化问题的有效近似算法——模拟退火算法。它源于对固体退火过程的模拟；采用Metropolis接受准则；并用一组称为冷却进度表的参数控制算法进程，使算法在多项式时间里给出一个近似最优解。固体退火过程的物理图象和统计性质是模拟退火算法的物理背景；Metropolis接受准则使算法跳离局部最优的“陷阱”，而冷却进度表的合理选择是算法应用的前提。-19-模拟退火算法模拟退火算法的思路：从选定的初始解开始，在借助于控制参数t递减时产生的一系列Markov链中，利用一个新解产生方案和接受准则，重复进行包括“产生新解-计算目标函数差-判断是否接受新解-接受（或舍弃）新解”这四个任务的试验，不断对当前解迭代，使目标函数逼近最优。-20-模拟退火算法1)任选一个初始解x0,xix0,k0,t0tmax(初始温度）,LkL0(内循环次数初值）；2)l0;3)若lLk，则到4）；否则，从邻域N(xi)中随机选一xj,计算fij=f(xj)-f(xi);ll+1;若fij0，则xixj;否则,若exp(-fij/tk)random（[0,1)）时，xixj；重复3）；4）tk+1T(tk);kk+1；计算Lk，若满足停止条件，终止计算，否则，回到2).-21-模拟退火算法的渐近收敛性已证明，模拟退火算法以1的概率收敛到整体最优解集，但渐近收敛到最优解集须经历无限多次变换。对最优解任意近似的逼近，对多数组合优化问题都导致比解空间规模大的变换数，从而导致算法的指数时间执行。解决办法：牺牲保证得到最优解为代价，在多项式时间里，逼近模拟退火算法的渐近收敛状态，返回一个近似最优解。-22-模拟退火算法应用的一般要求1)数学模型解空间、目标函数和初始解2）新解的产生和接受机制新解产生:当前解经简单变换产生新解（决定了当前解的邻域结构），如对当前解的全部或部分元素进行置换、互换或反演等。Metropolis接受准则:3）冷却进度表的设定0)/exp(01ftffP-23-冷却进度表冷却进度表是一组控制算法进程的参数，它包括：1.初始温度t0=tmax2.温度衰减函数T(t)3.Markov链的长度Lk4.终止温度tf（停止准则）。-24-冷却进度表虽然已经证明模拟退火算法在一定条件下的渐近收敛性。但这并不意味着任意冷却进度表都能确保算法收敛，不合理的冷却进度表会使算法在某些解间“振荡”而不能收敛于某一近似解。模拟退火算法的最终解质量和CPU时间呈反向关系，很难两全其美，妥善解决办法只有：折中，即在合理的CPU时间里尽量提高最终解的质量。这涉及到冷却进度表所有参数的合理选取。-25-冷却进度表的参数设置1.初始温度t0的选取t0要取得足够大，Johnson等建议通过计算若干次随机变换目标函数平均增量的方法来确定t0的值。)ln(100ft其中，为上述平均增量，为初始接受率，一般取0.81之间的数。f0-26-冷却进度表的参数设置2.温度衰减函数T(t)的选取一个常用的温度衰减函数是,2,1,0,1kttkk其中，取为0.50.99之间的数。Skiscim等人固定控制参数值的衰减步数K,把区间[0,t0]划分为K个小区间，把温度衰减函数取为KktKkKtk,,2,1,0-27-冷却进度表的参数设置3.Markov链的长度Lk的选取1）固定长度Lk通常取为问题规模n的一个多项式函数。如，Kirkpatric等Lk=n或100n,Aars等Lk=邻域规模2）由接受和拒绝的比率来控制Lk当温度很高时，Lk应尽量小，随着温度的渐渐下降，Lk逐步增大。-28-冷却进度表的参数设置3.Markov链的长度Lk的选取2）由接受和拒绝的比率来控制Lk实现的第一种方法是：给定一个充分大的长度上限U和一个接受次数指标R,当接受次数等于R时，此温度不再迭代而使温度下降。实现的第二种方法是：给定一个接受比率指标R,长度上限U和下限L,当迭代次数超过L时，若接受次数与迭代次数的比率不小于R时，此温度不再迭代而使温度下降，否则，一直迭代到上限步数U。-29-冷却进度表的参数设置4.终止温度tf（停止准则）的选取1）零度法2）循环总数控制法3）基于不改进规则的控制法4）接受概率控制法3）和4）的实现：在一个温度和给定的迭代次数内，没有改进当前的局部最优解或接受概率都小于一个给定的比较小的数f,则停止运算.5）邻域法当时，停止计算。f0,f1分别为一个邻域内的局部最优和次最优，N为邻域的大小。Ntff1)exp(01-30-模拟退火算法的优点高效、健壮、通用、灵活1）高效性与局部搜索算法相比，模拟退火算法可望在较短时间里求得更优近似解；允许任意选取初始解，且能得出较优近似解，因此应用该算法解组合优化问题的前期工作量大大减少。2）健壮性该算法的实验性能不因组合优化问题实例的不同而蜕变；解的质量和CPU时间均随n的增大而趋于稳定，且不受初始解和随机数序列的影响。-31-模拟退火算法的优点3）通用性和灵活性