组合优化的局部寻优法

会计学1组合优化的局部寻优法2.组合最优化问题的特点及举例

特点——可行解集为有限点集，因此只要将D中有限个点逐一判别是否满足g(X)的约束和比较目标函数值的大小即可得到最优解。所以，最优解一定存在且可以得到。第1页/共31页④装箱问题（binpacking）⑤约束机器排序问题（capacitatedmachinescheduling）

①0-1背包问题（knapsackproblem）；②旅行售货员问题（TSP,travelingsalesmanproblem）；③整数线性规划(integerlinearprogramming)；第2页/共31页邻域概念

每一个组合优化问题都可以通过枚举的方法求得最优解，但枚举是以时间为代价的，比为TSP问题，以1秒钟计算机可完成24个城市所有路径枚举为单位，列出城市数与计算时间的关系如下：1.问题的提出：城市数24252728293031计算时间1s24s4.3h4.9d136.5d10.8a325a2610min第3页/共31页

当城市数增加至30个时，计算时间已达10.8年，已无法接受。

因此，需要研究相应的算法。若该算法是一个多项式时间算法，则是一个好算法，但遗憾的是，一些组合最优化问题至今还没有找到求最优解的多项式时间算法，而这些组合最优化问题又有很强的实际应用背景，于是人们不得不尝试用一些并不一定可以求出最优解的算法，即启发式算法来求解组合最优化问题。第4页/共31页2.邻域的定义：

对于组合优化问题（D,F,f），D上的一个映射称为一个邻域映射，其中2D表示D的所有子集组成的集合，N（S）称为S的邻域，称为S的一个邻居。第5页/共31页例：①四个城市的TSP，若定义其邻域映射为S中的两个元素进行对换，记为2-opt，N(S)中共包含S的Cn2个邻居，当S=(1，2，3，4)时，N(S)={(21,3,4),(3,2,1,4),(4,2,3,1),(1,3,2,4)(1,4,3,2),(1,2,4,3)},共C42=6个邻居。

②D为区间[1，10]中的整数点。f(x)***

****

*

*

*

++++++++++

12345678910图中，x=9为f的全局最优点（最小点），x=5是局部最小点。采用如下邻域定义：则，N(6)={(5,7)}

第6页/共31页1、局部寻优算法

局部寻优法也许是以最古老的最优化方法(试错法)为基础的，是解决组合最优化问题最有效的方法之一，是“爬山法”的离散模拟。

局部寻优算法第7页/共31页一般局部寻优算法Procedure局部寻优Begin

t:=F中的某个初始起点；

while

improve(t)≠“no”,do

t:=improve(t);returntend

从某个初始可行解t∈F开始，利用子程序Improve在它的邻域里搜寻一个更好的解。只要一个改进的解存在，我们就采用它，并从这新的解出发重复邻域搜索过程；当我们得到一个局部最优解时，就停止。第8页/共31页

为了把这个方法用于具体问题，我们必须做出数种选择：首先：我们必须决定怎样得到一个初始可行解。从几个不同的初始起点出发进行局部寻优，并选取最好的结果，这往往是实用的。在这些情况下，我们必须决定试验多少个起点以及如何分配它们。其次：我们必须给所研究的问题选择一个“好”的邻域，选择一个搜索它的方法。这些以及类似的一些问题通常是靠经验回答的。设计有效的局部寻优算法在很大程度上是一门艺术第9页/共31页货郎担问题也叫推销商问题：有n个城市，用1，2，…，n表示，城i,j之间的距离为dij，有一个货郎从城1出发到其他城市一次且仅一次，最后回到城市1，怎样选择行走路线使总路程最短?货郎问题第10页/共31页货郎问题环游f的k交换邻域（k≥2）定义为货郎问题1958年，发表了两篇文章用货郎问题k交换局部寻优法，并且两篇文章都把这个想法与类似于分枝定界的枚举法结合起来，以便得到最优解。Croes用了N2,Bock用了N31965年,Sherman和Reiter检验了许多不同的领域,但是是lin首先令人信服地说明了3交换邻域N3的威力第11页/共31页

Lin根据经验发现，对于Held和Karp的48城市问题，一个3最优环游是最优的概率大约是0.05，因此从100个随机起点出发进行的实验会以0.95的概率得出最优解。

Lin的重要贡献之一：强调使用许多不同的随机初始解；在货郎问题中使用完全随机的初始环游是有效的。

Lin的另一贡献是证明了，3最优解比2最优解好得多，但是4最优解比3最优解好不很多，不足以证明附加的运算时间是合算的。

Lin论文的发表促进了局部寻优法对其他各种问题的应用货郎问题第12页/共31页点1代表岸上的工厂，2至15的每个点各代表气田上的一个钻井平台，每个平台有估计的日产量。我们可以假设每个气田的位置是已知的，问题是选择一棵树，它的边代表管道，通过这些管道收集天然气，并输送到岸上的工厂去。海底天然气管道系统拓扑结构第13页/共31页确定一棵给定树费用的方法：树的每条边代表一个以7个标准直径之一为直径的管道，他们分布在从直径10.75英寸每英里价值70000美元到直径30英寸每英里价值310000美元的范围内。因为我们知道每点的日产量，于是给定一棵树，我们便知道每条边的流量。利用成为锅柄(panhandle)方程的经验公式，对于每种选择的直径确定沿每条边的压差。于是在下面的三个约束条件下选择一些管道直径使费用最小：任意处的最大压强不超过给定的Pmax岸上工厂的输送压强必须至少是给定的Pmin每点集气压强至少是Pmin海底天然气管道系统拓扑结构第14页/共31页使用局部寻优法必须首先选择一个充分小的邻域：容易想到的最自然的邻域：初等树变换依次把每条可能的边加到树上，并依次从生成的圈中去掉每条可能的边。恰好是最小支撑树问题的邻域，大小是O(|V|3)限制邻域：称为Δ交换，定义如下：对于每个点x，找出三个最接近x的点y1,y2,y3,它们在树上与x不相邻。然后搜索由边[x,y1]、[x,y2]和[x,y3]分别确定的各初等树变换。这个邻域的大小是3k|V|，其中k是初等树变换中找到的平均圈长，比|V|要小得多海底天然气管道系统拓扑结构第15页/共31页海底天然气管道系统拓扑结构图中(a)第一次成功的Δ交换后的树(b)12次成功的Δ交换后的局部最优解。20年期间能节省9630000美元看来一定证明方案的很多改进是正确的第16页/共31页问题1：一个邻域或者一类邻域的选择，而这被可行解的自然摄动概念限制着问题2：对于问题大小的一个给定范围，一个大小易处理的自然邻域有一定的强度——即局部寻优法所生成的局部最优解有一定的平均质量。这个强度好像很大程度上依赖于初始可行解质量与生成的局部最优解质量的相关性。强邻域似乎产生质量上很少依赖于初始解质量的局部最优解；而弱邻域却似乎产生质量上与初始解的质量强相关的许多局部最优解。局部寻优法的一些普遍性问题第17页/共31页问题3：搜索邻域的方式。这里有两种极端的方式：一种是先改进，即只要找到一个有利交换，就立即采用它，而不是进一步搜索后再说；另一种是最速下降，即搜索整个邻域，挑选一个费用最低的解。先改进法的显著优点是只有最后一个邻域要搜索遍，因此一般会较快地找到局部最优解。问题4：搜索邻域的顺序。采用由指标导出的某种自然字典序通常是最简单的。不过可以随机安排邻域的顺序，即使从单个初始解出发，也有利于用先改进策略产生随机化的局部最优解。

当邻域的一个固定顺序关系与先改进法的一局部寻优法的一些普遍性问题第18页/共31页起使用时，一个新的邻域搜索可以在这顺序关系的开头重新启动，或者可以从上次搜索停止处继续搜索下去。我们把后一种选择叫做环形搜索法，并用一个计数器确定什么时候找到了一个局部最优解——即什么时候我们绕一个解旋转了360○。环形搜索法大概比重新开始策略有利。问题5：当局部寻优法用于一个最小化问题时，就给出最优费用的一个上界。同样常常很需要有个下界，因为它给我们提供一个近似解与最优解的一个相对偏差界限。局部寻优法的一些普遍性问题第19页/共31页局部寻优法方面用过的改进措施1、先用通常的方法得到一个局部最优解，然后努力进一步改进它。Krone把这样一个两阶段方法用于流水作业车间时间表问题。阶段Ⅰ寻求一些在置换时间表内是局部最优的时间表，而阶段Ⅱ则寻求一些该类之外的交换。Kernighan和Lin还讨论了一个用于图划分的两阶段方法。2、1965年Lin利用过的一个主题是一个称为化简的概念。这是根据观察：一个具体问题中，某些特点会为所有好的解所共有。Lin为求解货郎问题指定的策略是得到数个局部最优解，然后找出他们共有的各条边。把这些边固定下来，从而减少了寻求更多局部最优解的时间局部寻优法的一些普遍性问题第20页/共31页3、同启发方法一样，人们可以赞同完全相反的想法。一旦检查出这类共同特点，我们就禁止用它们，而不是一定用它们。4、[Lk]提到过另外一个想法，他根据的是下述事实：我们找到许多局部最优解时，当中可能有许多解是重复的。而且大部分搜索时间花在检验每个局部最优解的最优性上。检验方法是不成功地搜索它的邻域。用一个表记录以前的到的各局部最优解及其费用，并且随着搜索的进行，对照各局部最优费用检查现在的费用，这就可以避免那种费时的检验。当看到一个解具有局部最优费用时，可以检查它是否等同于某个先前的局部最优解。如果等同的话，则它的最优性检验就能省略。若要全面地节省时间，就必须采用一个有效的算法，进行这种费用检查局部寻优法的一些普遍性问题第21页/共31页局部寻优法与单纯形算法有十分密切的关系；事实上在适当定义的多面体上，可以认为他们是一样的。局部寻优法的几何离散线性子集定义第22页/共31页许多重要的组合最优化问题都是离散线性子集问题货郎问题是个离散线性子集问题。设n是一个完全图G的边数，而F恰好包含G的各环游所对应的那些整数集合。费用向量

就是边的权向量，即距离矩阵的向量表示最小支撑树问题是个离散线性子集问题。此处F恰好包含各支撑树所对应的那些边集合。最短路问题、某些拟阵问题以及另外许多问题都可以表达成离散线性子集问题第23页/共31页

一个可行点可以看作是中的一个点，它的每个坐标i是0或者1分别取决于i在或者不在f中。我们要用f表示这个n维向量，同时也表示集合。于是可以把F看成中单位立方体的顶点集合，其费用是那么选择能使任何点f0∈F成为唯一最优