局部搜索中随机算法策略探讨

《局部搜索中随机算法策略探讨》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、局部搜索中随机算法策略探讨摘要：随机局部搜索方法在2003年和2004年分别由Spall和Hoos、Stutzle给岀相应的描述，是一种解决计算机科学和运筹学领域中组合最优化问题的元启发式方法。典型的局部搜索方法对邻居的选择有：将变量和值一起选择的方式；先选择一个变量，然后选择它的值的方式；随机选取变量或者变量值，如果能提升评估，那么就接受这个改变等多种变化方式。笔者试从：成对地选择变量一变量值来完成最佳改进；将成对选择变量一变量值策略进行分割；择参与约束冲突的任意变量并改变它的值；将不再获取约束冲突数据的结构随机地选择一个邻居，然后对于新赋值选择接受还是拒绝四个方面来探讨随机局部搜索的随机

2、算法。关键词：局部搜索；随机；邻居迭代最佳改进可以用随机重启和随机游走两种随机方式来跳出局部最小值。在贪婪下降⑴中，该操作允许上升的移动，这样可以使随机游走跳出局部最小值。局部搜索方法开始时先完整地赋值，即对每一个变量赋一个值，进而试图迭代地提升这套赋值质量，提升的手段包含阶梯性提升、随机性选取或者重新选择一套赋值。随机游走是一个局部随机移动，而随机重启是一个全局随机移动。当问题涉及很多变量时，随机重启消耗代价大。利用随机移动的一种混合贪婪下降法是一类算法的实例，这类算法称为随机局部搜索。但因搜索空间常常有成千上万的维度，且每一维度都有一个离散的集合，所以很难将算法执行的搜索空间可视化。一些

3、直觉的结果可以从低维度问题收集到。考虑图1屮的两个一维搜索空间，在图屮想要得到最小值。假设可以通过对当前位置进行向左或向右的一个小的移动来获得邻居位置。为了在搜索空间(a)内寻找全局最小的值，我们希望利用随机重启的贪婪下降法来快速获得这个最优值。一旦随机选择找到了最深的谷中的一点，那么贪婪下降将会快速趋向于全局最小。因为许多随机移动都被要求跳出当前的一个局部极值，所以随机游走法在搜索空间(a)中就不会有很好的效果。但是，随机重启在搜索空间(b)中就会被快速地困在锯齿的峰值上，且不能得到好的结果。可是贪婪下降和随机游走的组织就可以跳出这些局部极值，而且使用一次移动或者两次移动可能就足够跳岀这个

4、局部极值。因此，随机游走在搜索空间(b)中就有很好的效果。以上呈现的局部搜索是没有存储的，在执行的过程中不记录搜索行为。用存储來提升局部搜索的…种简单方法就是禁忌表[2],这个禁忌表中存有最近被更改过的变量-变量值。禁忌表的思想是当选择一个新的赋值时，不得选择禁忌表中的变量•变量值。该方法阻止了在一些赋值中不断循环。禁忌表的大小一般是一个小的固定值，而禁忌表的大小也是可以被优化的参数。当禁忌表大小为4时，等价于不允许同样的赋值被立即重新访问。各种不同算法不同之处在于它们采用了多少工作量来确保最佳改进。举一个极端的情况，算法在选择新赋值时可以确保给出的是相对于所有邻居的最佳改进。另一个极端的情

5、况是，算法随机选取一个新的赋值，并且拒绝使情况更糟的赋值。下面将给出一些典算法，各种算法的不同之处在于它们付出了多少计算工作量来确保完成最佳改进。那个方法能取得最好的效果通常是一个经验问题。1、常用的改进方法第一种方法总是成对地选择变量■变量值来完成最佳改进。最朴素的办法就是线性地扫描每个变量和它的每个变量值，然后对比当前的所有变量的赋值决定哪个赋值能使得不被满足的约束数量最少，进而选择一个有产生最佳改进的变量-变量值对，即使这个改进是有负面影响的。当变量数据为n,平均域大小为d,—个赋值的邻居数为r时，这一步复杂度是O(ndr)o一个更精细的替换策略是设置一个变量•变量值的优先队列。对于任

6、意的变量X,值v在X的域内，并且在当前赋值下变量X没有被赋值为v,那么vX,v＞对就将被填入优先队列。＜X,v＞的权重为当前完整赋值的评估减去将X替换为v的完整赋值的评估。也就是说，它包含了每个替换值的评估变化。在每个阶段，算法选择一个最小权重值，这个值则是邻居所能提供的最佳改进。一旦变量X被赋予一个新值，那么所有变量中有多个权重将被改变，必须重新计算后插入优先队列中。当X被赋予v值时，被更改权重的那些变量是由于这个新值而出现在一个被满足或不被满足约束中的变量。当变量数为n,平均域大小为d,那一个赋值的邻居数为r时，算法这一步的复杂度是O(lognd+rdlognd)。由于算法在每次都要确保

7、最大的改进，因此在掌握数据的结构方面花费了太多时间。2、两阶段的选择一个替换策略是将成对选择变量一变量值策略进行分割，首先选择一个变量进行更改，然后再选择一个值。该算法也有一个变量优先队列，队列中变量的权重为变量所参与的冲突约束数。每次算法都选择一个具有最大权重的变量。一个变量被选中，那么这个变量将被赋予一个能最小化约束冲突数的值。作为最新赋值的一个结果，每个变量的约束冲突的值也会发生改变，其余参与到这个冲突