组合优化问题及算法

MATHEMATICAMODEL制作:龚劬组合优化问题及其算法1组合最优化（combinatorialoptimization)是通过对数学方法的研究去寻找离散事件的最优编排、分组、次序或筛选等，是运筹学(operationsresearch)中的一个重要分支。所研究的问题涉及信息技术、经济管理、工业工程、交通运输、通信网络等领域。该问题可用数学模型描述为：引言其中D表示有限个点组成的集合。21.0-1背包问题设有一个容积为b的背包，n个体积分别为ai(i=1,2,…,n),价值分别为ci(i=1,2,…,n)的物品，如何以最大的价值装包？一些例子32.旅行商问题(TSP，travelingsalesmanproblem)一个商人欲到n个城市推销商品，每两个城市i和j之间的距离为dij，如何选择一条道路使得商人每个城市正好走一遍后回到起点且所走路径最短。一些例子4

3.有约束的机器调度问题(capacitatedmachinescheduling)n个加工量为{di|i=1,2,…,n}的产品在一台机器上加工，机器在第t个时段的工作能力为ct,求完成所有产品加工所需时段数最少的调度方案一些例子

其中xit,T为决策变量,xit=1表示产品i在第t时段加工5

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

7.最大截问题(MCP,MaxCutProblem)8.图的顶点着色问题（GCP,GraphColouringProblem)9.独立集问题（ISP,IndependentSetProblem)10.调度问题(SCP,SchedulingProblem)11.划分问题(PAP,PartitionProblem)12.布局问题（PLP,PlacementProblem)……上述问题都是NP-hard问题，目前人们认为它们不存在求解最优解的多项式时间算法，大规模情形只有尝试用一些近似算法或启发式算法求解。一些例子7邻域概念

对于组合优化问题(D,F,f),D上的一个映射：N:SDN(S)2D称为一个邻域映射，其中2D表示D的所有子集构成的集合，N(S)称为S的邻域。邻域的构造依赖于问题决策变量的表示，邻域的结构在现代化优化算法中起重要作用。启发式算法8邻域概念例如，前面例子2给出的TSP问题模型。由解空间D={x{0,1}n(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)={(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

启发式算法定义

一个基于直观或经验构造的算法，在可接受的花费（计算时间、占用空间等）下给出待解决问题每一个实例的一个可行解，该解与最优解的偏离程度不一定能预计。启发式算法是一种技术，使在可接受的计算开销内寻找最好的解，但不一定能保证所得解的可行性和最优性，甚至多数情况下，无法给出所得解同最优解的近似程度。启发式算法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,…,xn)为贪婪算法所得解，单位体积的价值越大越先放入是贪婪算法的原则。启发式算法14

简单的邻域搜索算法给定组合优化问题，假设其邻域结构已确定，算法为1）任选一个初始解s0F;2)在N(s0)中按某一规则选一s；若f(s)<f(s0),则s0s；否则，N(s0)N(s0)-s;3)若N(s0)=,停止；否则，返回2).启发式算法15算法停止时得到点的性质依赖算法初始解的选取、邻域的结构.只要选好初始点，就一定可以求到最优解。对NP-hard的组合最优化问题，确定这样的初始点非常困难。如何选初始点和如何跳出局部最优值点以达到全局最优点是许多算法的关键。启发式算法16启发式算法的类型1.一步算法（构造型算法）2.改进型算法3.数学规划算法4.解空间松弛算法5.现代化优化算法禁忌搜索（tabusearch),模拟退火（simulatedannealing),遗传算法（geneticalgorithms),人工神经网络(neuralnetworks),蚂蚁算法(antalgorithm).17模拟退火算法1982年，Kirkpatric等将退火思想引入组合优化领域，提出一种解大规模组合优化问题，特别是NP-hard的组合优化问题的有效近似算法——模拟退火算法。它源于对固体退火过程的模拟；采用Metropolis接受准则；并用一组称为冷却进度表的参数控制算法进程，使算法在多项式时间里给出一个近似最优解。固体退火过程的物理图象和统计性质是模拟退火算法的物理背景；Metropolis接受准则使算法跳离局部最优的“陷阱”，而冷却进度表的合理选择是算法应用的前提。18模拟退火算法模拟退火算法的思路：从选定的初始解开始，在借助于控制参数t递减时产生的一系列Markov链中，利用一个新解产生方案和接受准则，重复进行包括“产生新解-计算目标函数差-判断是否接受新解-接受（或舍弃）新解”这四个任务的试验，不断对当前解迭代，使目标函数逼近最优。

19模拟退火算法任选一个初始解x0,xix0,k0,t0

tmax(初始温度）,LkL0(内循环次数初值）；2)l0;3)若l>Lk，则到4）；否则，从邻域N(xi)中随机选一xj,计算fij=f(xj)-f(xi);ll+1;若fij0，则xixj;否则,若exp(-

fij/tk)>random（[0,1)）时，xixj；重复3）；4）tk+1

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

3）冷却进度表的设定22冷却进度表冷却进度表是一组控制算法进程的参数，它包括：1.初始温度t0

=tmax2.温度衰减函数T(t)3.Markov链的长度