组合优化的局部寻优法(3)

《组合优化的局部寻优法(3)》由会员分享，可在线阅读，更多相关《组合优化的局部寻优法(3)（31页珍藏版）》请在金锄头文库上搜索。

1、 1.1.什么是组合最优化什么是组合最优化 （combinatorial optimizationcombinatorial optimization）? ?是通过对数学方法的研究去寻找离散事件 的最优编排、分组、次序或筛选等。其数学 模型描述为：一个组合最优化问题可用三参数（三参数（D D，F F，f f）表示）表示， 其中: D决策变量定义域（是个有限点集）,F可行域f目标函数.组组 合合 最最 优优 化化 问问 题题专题三专题三 组合优化的局部寻优法组合优化的局部寻优法2.2.组合最优化问题的特点及举例组合最优化问题的特点及举例特点特点可行解集为有限点集，因可行解集为有限点集，因此只要将

2、此只要将D D中有限个点逐一判别是否满中有限个点逐一判别是否满足足g(Xg(X) )的约束和比较目标函数值的大小的约束和比较目标函数值的大小即可得到最优解。所以，即可得到最优解。所以，最优解一定存最优解一定存在且可以得到在且可以得到。装箱问题（装箱问题（bin packing bin packing ） 约束机器排序问题约束机器排序问题 （capacitated machine schedulingcapacitated machine scheduling） 0-10-1背包问题（背包问题（knapsack problemknapsack problem）；）；旅行售货员问题旅行售货员问题（

3、TSP, traveling salesman problemTSP, traveling salesman problem）；）；整数线性规划整数线性规划 (integer linear programming )(integer linear programming )；邻邻 域域 概概 念念每一个组合优化问题都可以通过枚 举的方法求得最优解，但枚举是以时间 为代价的，比为TSP问题，以1秒钟计算 机可完成24个城市所有路径枚举为单位 ，列出城市数与计算时间的关系如下：1. 1. 问题的提出：问题的提出：城市 数24252728293031计算 时间1s24s4.3 h4.9 d136.

4、5d10.8 a325 a2610 min当城市数增加至当城市数增加至3030个时，计算时间已达个时，计算时间已达 10.810.8年，已无法接受。年，已无法接受。因此，需要研究相应的算法。若该算法是一个多项式时间算法，则是一个好算法，但遗憾的是，一些组合最优化问题至今还没有找到求最优解的多项式时间算法，而这些组合最优化问题又有很强的实际应用背景，于是人们不得不尝试用一些并不一定可以求出最优解的算法，即启发式算法启发式算法来求解组合最优化问题。2.2.邻域的定义邻域的定义：对于组合优化问题（D,F,f），D上的一个映射 称为一个邻域映射邻域映射，其中2D表示D的所有子集组成的集合，N N（S

5、S）称为）称为S S的邻域的邻域， 称为S的一个邻居。例：四个城市的四个城市的TSPTSP，若定义其邻域映射为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) * * * * * * * * + + + + + + + + + +1 2 3 4 5 6 7 8 9 10图中，x=9为f的全局最优点（最小点），x=5是局部最小点。采用如下邻域定义：则，

6、N(6)=(5,7) 1 1、局部寻优算法、局部寻优算法局部寻优法也许是以最古老的最优化方法(试 错法)为基础的，是解决组合最优化问题最有效 的方法之一，是“爬山法”的离散模拟。局局 部部 寻寻 优优 算算 法法一般局部寻优算法Procedure 局部寻优 Begint:=F中的某个初始起点；while improve(t)“no”,dot:= improve(t);return tend从某个初始可行解tF开始，利用子程序 Improve在它的邻域里搜寻一个更好的解。只要一 个改进的解存在，我们就采用它，并从这新的解 出发重复邻域搜索过程；当我们得到一个局部最 优解时，就停止。为了把这个方法

7、用于具体问题，我们必须做出 数种选择：首先：我们必须决定怎样得到一个初始可行 解。从几个不同的初始起点出发进行局部寻优， 并选取最好的结果，这往往是实用的。在这些情 况下，我们必须决定试验多少个起点以及如何分 配它们。其次：我们必须给所研究的问题选择一个“ 好”的邻域，选择一个搜索它的方法。这些以及类似的一些问题通常是靠经验回答 的。设计有效的局部寻优算法在很大程度上是一 门艺术货郎担问题也叫推销商问题：有n个城市，用1 ，2，n表示，城i, j之间的距离为 dij ，有 一个货郎从城1出发到其他城市一次且仅一次，最 后回到城市1，怎样选择行走路线使总路程最短?货 郎 问 题货郎问题环游f的k

8、交换邻域（k 2）定义为货 郎 问 题1958年，发表了两篇文章用货郎问题k交换局部寻 优法，并且两篇文章都把这个想法与类似于分枝 定界的枚举法结合起来，以便得到最优解。Croes 用了N2,Bock用了N3 1965年,Sherman和Reiter检验了许多不同的领域, 但是是lin首先令人信服地说明了3交换邻域N3的 威力Lin根据经验发现，对于Held和Karp的48城市 问题，一个3最优环游是最优的概率大约是0.05， 因此从100个随机起点出发进行的实验会以0.95的 概率得出最优解。Lin的重要贡献之一：强调使用许多不同的随 机初始解；在货郎问题中使用完全随机的初始环 游是有效的。

9、Lin的另一贡献是证明了，3最优解比2最优解 好得多，但是4最优解比3最优解好不很多，不足 以证明附加的运算时间是合算的。Lin论文的发表促进了局部寻优法对其他各种 问题的应用货 郎 问 题点1代表岸上的工厂，2至15的每个点各代表 气田上的一个钻井平台，每个平台有估计的日产 量。我们可以假设每个气田的位置是已知的，问 题是选择一棵树，它的边代表管道，通过这些管 道收集天然气，并输送到岸上的工厂去。海底天然气管道系统拓扑结 构确定一棵给定树费用的方法：树的每条边代表一个以7个标准直径之一为直 径的管道，他们分布在从直径10.75英寸每英里价 值70000美元到直径30英寸每英里价值310000

10、美元 的范围内。因为我们知道每点的日产量，于是给 定一棵树，我们便知道每条边的流量。利用成为 锅柄(panhandle)方程的经验公式，对于每种选择 的直径确定沿每条边的压差。于是在下面的三个 约束条件下选择一些管道直径使费用最小：a) 任意处的最大压强不超过给定的Pmaxb) 岸上工厂的输送压强必须至少是给定的Pminc) 每点集气压强至少是Pmin海底天然气管道系统拓扑结 构使用局部寻优法必须首先选择一个充分小的邻域 ：容易想到的最自然的邻域：初等树变换依次把每条可能的边加到树上，并依次从生成的 圈中去掉每条可能的边。恰好是最小支撑树问题 的邻域，大小是O(|V|3)限制邻域：称为交换，定

11、义如下：对于每个点x，找出三个最接近x的点y1,y2,y3,它 们在树上与x不相邻。然后搜索由边x,y1、 x,y2和x,y3分别确定的各初等树变换。这个邻 域的大小是3k|V|，其中k是初等树变换中找到的 平均圈长，比|V|要小得多海底天然气管道系统拓扑结 构海底天然气管道系统拓扑结 构图中(a)第一次成功 的交换后的树 (b)12次成功的交 换后的局部最优解 。20年期间能节省 9630000美元看来一 定证明方案的很多 改进是正确的问题1：一个邻域或者一类邻域的选择，而这被可 行解的自然摄动概念限制着问题2：对于问题大小的一个给定范围，一个大小 易处理的自然邻域有一定的强度即局部寻优 法

12、所生成的局部最优解有一定的平均质量。这个 强度好像很大程度上依赖于初始可行解质量与生 成的局部最优解质量的相关性。强邻域似乎产生 质量上很少依赖于初始解质量的局部最优解；而 弱邻域却似乎产生质量上与初始解的质量强相关 的许多局部最优解。局部寻优法的一些普遍性问 题问题3：搜索邻域的方式。这里有两种极端的方式 ：一种是先改进，即只要找到一个有利交换，就 立即采用它，而不是进一步搜索后再说；另一种 是最速下降，即搜索整个邻域，挑选一个费用最 低的解。先改进法的显著优点是只有最后一个邻 域要搜索遍，因此一般会较快地找到局部最优解 。问题4：搜索邻域的顺序。采用由指标导出的某种 自然字典序通常是最简单

13、的。不过可以随机安排 邻域的顺序，即使从单个初始解出发，也有利于 用先改进策略产生随机化的局部最优解。当邻域的一个固定顺序关系与先改进法的一局部寻优法的一些普遍性问 题起使用时，一个新的邻域搜索可以在这顺序关系 的开头重新启动，或者可以从上次搜索停止处继 续搜索下去。我们把后一种选择叫做环形搜索法 ，并用一个计数器确定什么时候找到了一个局部 最优解即什么时候我们绕一个解旋转了360。环形搜索法大概比重新开始策略有利。问题5：当局部寻优法用于一个最小化问题时，就 给出最优费用的一个上界。同样常常很需要有个 下界，因为它给我们提供一个近似解与最优解的 一个相对偏差界限。局部寻优法的一些普遍性问 题

14、局部寻优法方面用过的改进措施1、先用通常的方法得到一个局部最优解，然后努 力进一步改进它。Krone把这样一个两阶段方法用 于流水作业车间时间表问题。阶段寻求一些在 置换时间表内是局部最优的时间表，而阶段则 寻求一些该类之外的交换。Kernighan和Lin还讨 论了一个用于图划分的两阶段方法。2、1965年Lin利用过的一个主题是一个称为化简 的概念。这是根据观察：一个具体问题中，某些 特点会为所有好的解所共有。Lin为求解货郎问题 指定的策略是得到数个局部最优解，然后找出他 们共有的各条边。把这些边固定下来，从而减少 了寻求更多局部最优解的时间局部寻优法的一些普遍性问 题3、同启发方法一样

15、，人们可以赞同完全相反的想 法。一旦检查出这类共同特点，我们就禁止用它 们，而不是一定用它们。4、Lk提到过另外一个想法，他根据的是下述事 实：我们找到许多局部最优解时，当中可能有许 多解是重复的。而且大部分搜索时间花在检验每 个局部最优解的最优性上。检验方法是不成功地 搜索它的邻域。用一个表记录以前的到的各局部 最优解及其费用，并且随着搜索的进行，对照各 局部最优费用检查现在的费用，这就可以避免那 种费时的检验。当看到一个解具有局部最优费用 时，可以检查它是否等同于某个先前的局部最优 解。如果等同的话，则它的最优性检验就能省略 。若要全面地节省时间，就必须采用一个有效的 算法，进行这种费用检查局部寻优法的一些普遍性问 题局部寻优法与单纯形算法有十分密切的关系 ；事实上在适当定义的多面体上，可以认为他们 是一样的。局 部 寻 优 法 的 几 何离散线性子集定义许多重要的组合最优化问题都是离散线性子集问题货郎问题是个离散线性子集问题。设n是一个完全 图G的边数，而F恰好包含G的各环游所对应的那些 整数集合。费用向量 就是边的权向量，即距离 矩阵的向量表示最小支撑树问题是个