《组合优化的局部寻优法》由会员分享，可在线阅读，更多相关《组合优化的局部寻优法（31页珍藏版）》请在金锄头文库上搜索。
1、1.什么是组合最优化 （combinatorial optimization）?,是通过对数学方法的研究去寻找离散事件的最优编排、分组、次序或筛选等。其数学模型描述为：,一个组合最优化问题可用三参数（D，F，f）表示， 其中: D决策变量定义域（是个有限点集）, F可行域 f目标函数.,专题三 组合优化的局部寻优法,2.组合最优化问题的特点及举例,特点可行解集为有限点集，因此只要将D中有限个点逐一判别是否满足g(X)的约束和比较目标函数值的大小即可得到最优解。所以，最优解一定存在且可以得到。,装箱问题（bin packing ）,约束机器排序问题 （capacitated machine sc
2、heduling）,0-1背包问题（knapsack problem）；,旅行售货员问题 （TSP, traveling salesman problem）；,整数线性规划 (integer linear programming )；,每一个组合优化问题都可以通过枚举的方法求得最优解，但枚举是以时间为代价的，比为TSP问题，以1秒钟计算机可完成24个城市所有路径枚举为单位，列出城市数与计算时间的关系如下：,1. 问题的提出：,当城市数增加至30个时，计算时间已达10.8年，已无法接受。,因此，需要研究相应的算法。若该算法是一个多项式时间算法，则是一个好算法，但遗憾的是，一些组合最优化问题至今还
3、没有找到求最优解的多项式时间算法，而这些组合最优化问题又有很强的实际应用背景，于是人们不得不尝试用一些并不一定可以求出最优解的算法，即启发式算法来求解组合最优化问题。,2.邻域的定义：,对于组合优化问题（D,F,f），D上的一个映射 称为一个邻域映射，其中2D表示D的所有子集组成的集合，N（S）称为S的邻域， 称为S的一个邻居。,例：四个城市的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),
4、共C42=6个邻居。,D为区间1，10中的整数点。,f(x) * * * * * * * * * * + + + + + + + + + + 1 2 3 4 5 6 7 8 9 10,图中，x=9为f的全局最优点（最小点），x=5是局部最小点。,1、局部寻优算法,局部寻优法也许是以最古老的最优化方法(试错法)为基础的，是解决组合最优化问题最有效的方法之一，是“爬山法”的离散模拟。,一般局部寻优算法 Procedure 局部寻优 Begin t:=F中的某个初始起点； while improve(t)“no”,do t:= improve(t); return t end,从某个初始可行解tF开
5、始，利用子程序Improve在它的邻域里搜寻一个更好的解。只要一个改进的解存在，我们就采用它，并从这新的解出发重复邻域搜索过程；当我们得到一个局部最优解时，就停止。,为了把这个方法用于具体问题，我们必须做出数种选择： 首先：我们必须决定怎样得到一个初始可行解。从几个不同的初始起点出发进行局部寻优，并选取最好的结果，这往往是实用的。在这些情况下，我们必须决定试验多少个起点以及如何分配它们。 其次：我们必须给所研究的问题选择一个“好”的邻域，选择一个搜索它的方法。 这些以及类似的一些问题通常是靠经验回答的。设计有效的局部寻优算法在很大程度上是一门艺术,货郎担问题也叫推销商问题：有n个城市，用1，2
6、，n表示，城i, j之间的距离为 dij ，有一个货郎从城1出发到其他城市一次且仅一次，最后回到城市1，怎样选择行走路线使总路程最短?,货郎问题环游f的k交换邻域（k 2）定义为,1958年，发表了两篇文章用货郎问题k交换局部寻优法，并且两篇文章都把这个想法与类似于分枝定界的枚举法结合起来，以便得到最优解。Croes用了N2,Bock用了N3 1965年,Sherman和Reiter检验了许多不同的领域,但是是lin首先令人信服地说明了3交换邻域N3的威力,Lin根据经验发现，对于Held和Karp的48城市问题，一个3最优环游是最优的概率大约是0.05，因此从100个随机起点出发进行的实验会
7、以0.95的概率得出最优解。 Lin的重要贡献之一：强调使用许多不同的随机初始解；在货郎问题中使用完全随机的初始环游是有效的。 Lin的另一贡献是证明了，3最优解比2最优解好得多，但是4最优解比3最优解好不很多，不足以证明附加的运算时间是合算的。 Lin论文的发表促进了局部寻优法对其他各种问题的应用,点1代表岸上的工厂，2至15的每个点各代表气田上的一个钻井平台，每个平台有估计的日产量。我们可以假设每个气田的位置是已知的，问题是选择一棵树，它的边代表管道，通过这些管道收集天然气，并输送到岸上的工厂去。,确定一棵给定树费用的方法： 树的每条边代表一个以7个标准直径之一为直径的管道，他们分布在从直
8、径10.75英寸每英里价值70000美元到直径30英寸每英里价值310000美元的范围内。因为我们知道每点的日产量，于是给定一棵树，我们便知道每条边的流量。利用成为锅柄(panhandle)方程的经验公式，对于每种选择的直径确定沿每条边的压差。于是在下面的三个约束条件下选择一些管道直径使费用最小： 任意处的最大压强不超过给定的Pmax 岸上工厂的输送压强必须至少是给定的Pmin 每点集气压强至少是Pmin,使用局部寻优法必须首先选择一个充分小的邻域： 容易想到的最自然的邻域：初等树变换 依次把每条可能的边加到树上，并依次从生成的圈中去掉每条可能的边。恰好是最小支撑树问题的邻域，大小是O(|V|
9、3) 限制邻域：称为交换，定义如下： 对于每个点x，找出三个最接近x的点y1,y2,y3,它们在树上与x不相邻。然后搜索由边x,y1、 x,y2和x,y3分别确定的各初等树变换。这个邻域的大小是3k|V|，其中k是初等树变换中找到的平均圈长，比|V|要小得多,图中(a)第一次成功的交换后的树(b)12次成功的交换后的局部最优解。20年期间能节省9630000美元看来一定证明方案的很多改进是正确的,问题1：一个邻域或者一类邻域的选择，而这被可行解的自然摄动概念限制着 问题2：对于问题大小的一个给定范围，一个大小易处理的自然邻域有一定的强度即局部寻优法所生成的局部最优解有一定的平均质量。这个强度好
10、像很大程度上依赖于初始可行解质量与生成的局部最优解质量的相关性。强邻域似乎产生质量上很少依赖于初始解质量的局部最优解；而弱邻域却似乎产生质量上与初始解的质量强相关的许多局部最优解。,问题3：搜索邻域的方式。这里有两种极端的方式：一种是先改进，即只要找到一个有利交换，就立即采用它，而不是进一步搜索后再说；另一种是最速下降，即搜索整个邻域，挑选一个费用最低的解。先改进法的显著优点是只有最后一个邻域要搜索遍，因此一般会较快地找到局部最优解。 问题4：搜索邻域的顺序。采用由指标导出的某种自然字典序通常是最简单的。不过可以随机安排邻域的顺序，即使从单个初始解出发，也有利于用先改进策略产生随机化的局部最优
11、解。 当邻域的一个固定顺序关系与先改进法的一,起使用时，一个新的邻域搜索可以在这顺序关系的开头重新启动，或者可以从上次搜索停止处继续搜索下去。我们把后一种选择叫做环形搜索法，并用一个计数器确定什么时候找到了一个局部最优解即什么时候我们绕一个解旋转了360。环形搜索法大概比重新开始策略有利。 问题5：当局部寻优法用于一个最小化问题时，就给出最优费用的一个上界。同样常常很需要有个下界，因为它给我们提供一个近似解与最优解的一个相对偏差界限。,局部寻优法方面用过的改进措施 1、先用通常的方法得到一个局部最优解，然后努力进一步改进它。Krone把这样一个两阶段方法用于流水作业车间时间表问题。阶段寻求一些
12、在置换时间表内是局部最优的时间表，而阶段则寻求一些该类之外的交换。Kernighan和Lin还讨论了一个用于图划分的两阶段方法。 2、1965年Lin利用过的一个主题是一个称为化简的概念。这是根据观察：一个具体问题中，某些特点会为所有好的解所共有。Lin为求解货郎问题指定的策略是得到数个局部最优解，然后找出他们共有的各条边。把这些边固定下来，从而减少了寻求更多局部最优解的时间,3、同启发方法一样，人们可以赞同完全相反的想法。一旦检查出这类共同特点，我们就禁止用它们，而不是一定用它们。 4、Lk提到过另外一个想法，他根据的是下述事实：我们找到许多局部最优解时，当中可能有许多解是重复的。而且大部分
13、搜索时间花在检验每个局部最优解的最优性上。检验方法是不成功地搜索它的邻域。用一个表记录以前的到的各局部最优解及其费用，并且随着搜索的进行，对照各局部最优费用检查现在的费用，这就可以避免那种费时的检验。当看到一个解具有局部最优费用时，可以检查它是否等同于某个先前的局部最优解。如果等同的话，则它的最优性检验就能省略。若要全面地节省时间，就必须采用一个有效的算法，进行这种费用检查,局部寻优法与单纯形算法有十分密切的关系；事实上在适当定义的多面体上，可以认为他们是一样的。,离散线性子集定义,许多重要的组合最优化问题都是离散线性子集问题,货郎问题是个离散线性子集问题。设n是一个完全图G的边数，而F恰好包
14、含G的各环游所对应的那些整数集合。费用向量 就是边的权向量，即距离矩阵的向量表示,最小支撑树问题是个离散线性子集问题。此处F恰好包含各支撑树所对应的那些边集合。,最短路问题、某些拟阵问题以及另外许多问题都可以表达成离散线性子集问题,给LP1增加一些松弛变量，把这个问题划到Rn+m中去，得到可行集合是F2Rn+m的标准形式LP2,把F1和F2的连接性联系起来的引理,定理1,定理2,我们以一个稍悲观的注释来结束这一章。这个注释使人们不再抱有这样的希望：对于货郎问题，即一个多面体NP-完备最优化问题，我们找到一个像单纯形算法那样快速迭代的局部寻优算法。但是我们不应忘记，局部寻优法可能是这类问题的一个很有效的启发式方法。事实上它经常是最适用的。,
