组合优化问题及算法.ppt

,MATHEMATICA MODEL,制作: 龚劬,组合优化问题及其算法,-2-,组合最优化（combinatorial optimization)是通过对数学方法的研究去寻找离散事件的最优编排、分组、次序或筛选等，是运筹学(operations research)中的一个重要分支。所研究的问题涉及信息技术、经济管理、工业工程、交通运输、通信网络等领域。该问题可用数学模型描述为：,引言,其中D表示有限个点组成的集合。,-3-,1. 0-1背包问题 设有一个容积为b的背包，n个体积分别为 ai(i=1,2,n),价值分别为ci (i=1,2,n)的物品，如何以最大的价值装包？,一些例子,-4-,2. 旅行商问题(TSP，traveling salesman problem) 一个商人欲到n个城市推销商品，每两个城市i和j之间的距离为dij，如何选择一条道路使得商人每个城市正好走一遍后回到起点且所走路径最短。,一些例子,-5-,3.有约束的机器调度问题(capacitated machine scheduling) n个加工量为di|i=1,2,n的产品在一台机器上加工，机器在第t个时段的工作能力为ct,求完成所有产品加工所需时段数最少的调度方案,一些例子,其中xit,T为决策变量,xit=1表示产品i在第t时段加工,-6-,4. 装箱问题(bin packing) 如何把n个尺寸不超过1的物品装入尺寸为1的箱子，并使所用的箱子个数最少。 5. 二维装箱问题（平面上的套裁问题） 原料的尺寸大于需求的尺寸，需求的品种尺寸可以不同，最终的目标是在满足需求的前提下，使边角余料最小。 6. 车间作业调度问题(job shop scheduling) n个工件，J1,Jn在m台机器M1,M2,Mm上加工。每个工件Ji有ni个工序，Oi1,Oini,第Oij工序的加工时间为pij，必须按工序进行加工且每一工序必须一次加工完成。一台机器在任何时刻最多只能加工一个产品，一个工件不能同时在两台机器上加工，如何安排才能使最后一个完工的工件完工时间最小？,一些例子,-7-,7. 最大截问题(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问题，目前人们认为它们不存在求解最优解的多项式时间算法，大规模情形只有尝试用一些近似算法或启发式算法求解。,一些例子,-8-,邻域概念 对于组合优化问题(D,F,f),D上的一个映射： N:SD N(S)2D 称为一个邻域映射，其中2D表示D的所有子集构成的集合，N(S)称为S的邻域。 邻域的构造依赖于问题决策变量的表示，邻域的结构在现代化优化算法中起重要作用。,启发式算法,-9-,邻域概念 例如，前面例子2给出的TSP问题模型。由解空间 D=x0,1n(n-1)，可以定义它的一种邻域为：,启发式算法,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(k2),-11-,局部最优与全局最优,启发式算法,若s*满足 f(s*)()f(s),其中sN(s*)F, 则称s*为f在F上的局部(local)最小（最大）解。 若s*满足 f(s*)()f(s),其中sF, 则称s*为f在F上的全局(global)最小（最大）解。,-12-,启发式算法,-13-,启发式算法,-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)为贪婪算法所得解，单位体积的价值越大越先放入是贪婪算法的原则。,启发式算法,-15-,简单的邻域搜索算法 给定组合优化问题，假设其邻域结构已确定，算法为 1）任选一个初始解s0F; 2) 在N(s0)中按某一规则选一s；若f(s)f(s0),则s0s；否则，N(s0) N(s0)-s; 3) 若N(s0)=,停止；否则，返回2).,启发式算法,-16-,算法停止时得到点的性质依赖算法初始解的选取、邻域的结构. 只要选好初始点，就一定可以求到最优解。对NP-hard的组合最优化问题，确定这样的初始点非常困难。如何选初始点和如何跳出局部最优值点以达到全局最优点是许多算法的关键。,启发式算法,-17-,启发式算法的类型,1.一步算法（构造型算法） 2.改进型算法 3.数学规划算法 4.解空间松弛算法 5.现代化优化算法 禁忌搜索（tabu search),模拟退火（simulated annealing),遗传算法（genetic algorithms),人工神经网络(neural networks),蚂蚁算法(ant algorithm).,-18-,模拟退火算法,1982年，Kirkpatric等将退火思想引入组合优化领域，提出一种解大规模组合优化问题，特别是NP-hard的组合优化问题的有效近似算法模拟退火算法。它源于对固体退火过程的模拟；采用Metropolis接受准则；并用一组称为冷却进度表的参数控制算法进程，使算法在多项式时间里给出一个近似最优解。 固体退火过程的物理图象和统计性质是模拟退火算法的物理背景；Metropolis接受准则使算法跳离局部最优的“陷阱”，而冷却进度表的合理选择是算法应用的前提。,-19-,模拟退火算法,模拟退火算法的思路：从选定的初始解开始，在借助于控制参数t递减时产生的一系列Markov链中，利用一个新解产生方案和接受准则，重复进行包括“产生新解-计算目标函数差-判断是否接受新解-接受（或舍弃）新解”这四个任务的试验，不断对当前解迭代，使目标函数逼近最优。,-20-,模拟退火算法,任选一个初始解x0,xix0,k 0,t0 tmax(初始温度）,LkL0(内循环次数初值）； 2) l0; 3) 若lLk，则到4）；否则，从邻域N(xi)中随机选一xj,计算fij=f(xj)-f(xi); ll+1;若fij0，则xixj; 否则,若exp(- fij/tk)random（0,1)）时，xixj；重复3）； 4）tk+1T(tk);k k+1；计算Lk，若满足停止条件，终止计算，否则，回到2).,-21-,模拟退火算法的渐近收敛性,已证明，模拟退火算法以1的概率收敛到整体最优解集，但渐近收敛到最优解集须经历无限多次变换。 对最优解任意近似的逼近，对多数组合优化问题都导致比解空间规模大的变换数，从而导致算法的指数时间执行。 解决办法：牺牲保证得到最优解为代价，在多项式时间里，逼近模拟退火算法的渐近收敛状态，返回一个近似最优解。,-22-,模拟退火算法应用的一般要求,数学模型 解空间、目标函数和初始解 2）新解的产生和接受机制 新解产生:当前解经简单变换产生新解（决定了当前解的邻域结构），如对当前解的全部或部分元素进行置换、互换或反演等。 Metropolis接受准则: 3）冷却进度表的设定,-23-,冷却进度表,冷却进度表是一组控制算法进程的参数，它包括： 1.初始温度t0 =tmax 2.温度衰减函数T(t) 3.Markov链的长度Lk 4.终止温度tf（停止准则） 。,-24-,冷却进度表,虽然已经证明模拟退火算法在一定条件下的渐近收敛性。但这并不意味着任意冷却进度表都能确保算法收敛，不合理的冷却进度表会使算法在某些解间“振荡”而不能收敛于某一近似解。 模拟退火算法的最终解质量和CPU时间呈反向关系，很难两全其美，妥善解决办法只有：折中，即在合理的CPU时间里尽量提高最终解的质量。这涉及到冷却进度表所有参数的合理选取。,-25-,冷却进度表的参数设置,1.初始温度t0 的选取 t0 要取得足够大，Johnson等建议通过计算若干次随机变换目标函数平均增量的方法来确定t0的值。,其中， 为上述平均增量， 为初始接受率，一般取0.81之间的数。,-26-,冷却进度表的参数设置,-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为邻域的大小。,-30-,模拟退火算法的优点,高效、健壮、通用、灵活 1）高效性 与局部搜索算法相比，模拟退火算法可望在较短时间里求得更优近似解；允许任意选取初始解，且能得出较优近似解，因此应用该算法解组合优化问题的前期工作量大大减少。 2）健壮性 该算法的实验性能不因组合优化问题实例的不同而蜕变；解的质量和CPU时间均随n的增大而趋于稳定，且不受初始解和随机数序列的影响。,-31-,模拟退火算法的优点,3）通用性和灵活性 该算法能应用于多种组合优化问题，为一个问题编制的程序可有效地用于其他问题。解的质量与CPU时间呈反向关系，针对不同的实例以及不同的解质要求，适当调整冷却进度表的参数值可使算法执行获得最佳的解时关系。,-32-,模拟退火算法的不足和改进途径,主要不足是：返回一个高质近似解的时间花费较多。有如下途径改进算法的实验性能、提高算法的执行效率。 1）增加一个记忆器 给算法增加一个记忆器，使之能记住搜索过程中遇到过的最好结果，当结束时，