随机算法策略论文关于局部搜索中随机算法策略论文范文参考资料

随机算法策略论文关于局部搜索中随机算法策略论文范文参考资料 文李忠武 摘要：随机局部搜索方法在xx年和xx年分别由Spall和Hoos、Sttzle给出相应的描述，是一种解决计算机科学和运筹学领域中组合最优化问题的元启发式方法。典型的局部搜索方法对邻居的选择有：将变量和值一起选择的方式；先选择一个变量，然后选择它的值的方式；随机选取变量或者变量值，如果能提升评估，那么就接受这个改变等多种变化方式。笔者试从：成对地选择变量变量值来完成最佳改进；将成对选择变量变量值策略进行分割；择参与约束冲突的任意变量并改变它的值；将不再获取约束冲突数据的结构随机地选择一个邻居，然后对于新赋值选择接受还是拒绝四个方面来探讨随机局部搜索的随机算法。 关键词：局部搜索；随机；邻居 迭代最佳改进可以用随机重启和随机游走两种随机方式来跳出局部最小值。在贪婪下降1中，该操作允许上升的移动，这样可以使随机游走跳出局部最小值。局部搜索方法开始时先完整地赋值，即对每一个变量赋一个值，进而试图迭代地提升这套赋值质量，提升的手段包含阶梯性提升、随机性选取或者重新选择一套赋值。随机游走是一个局部随机移动，而随机重启是一个全局随机移动。当问题涉及很多变量时，随机重启消耗代价大。利用随机移动的一种混合贪婪下降法是一类算法的实例，这类算法称为随机局部搜索。 但因搜索空间常常有成千上万的维度，且每一维度都有一个离散的集合，所以很难将算法执行的搜索空间可视化。一些直觉的结果可以从低维度问题收集到。考虑图1中的两个一维搜索空间，在图中想要得到最小值。假设可以通过对当前位置进行向左或向右的一个小的移动来获得邻居位置。为了在搜索空间（a）内寻找全局最小的值，我们希望利用随机重启的贪婪下降法来快速获得这个最优值。一旦随机选择找到了最深的谷中的一点，那么贪婪下降将会快速趋向于全局最小。因为许多随机移动都被要求跳出当前的一个局部极值，所以随机游走法在搜索空间（a）中就不会有很好的效果。但是，随机重启在搜索空间（b）中就会被快速地困在锯齿的峰值上，且不能得到好的结果。可是贪婪下降和随机游走的组织就可以跳出这些局部极值，而且使用一次移动或者两次移动可能就足够跳出这个局部极值。因此，随机游走在搜索空间（b）中就有很好的效果。 以上呈现的局部搜索是没有存储的，在执行的过程中不记录搜索行为。用存储来提升局部搜索的一种简单方法就是禁忌表2，这个禁忌表中存有最近被更改过的变量-变量值。禁忌表的思想是当选择一个新的赋值时，不得选择禁忌表中的变量-变量值。该方法阻止了在一些赋值中不断循环。禁忌表的大小一般是一个小的固定值，而禁忌表的大小也是可以被优化的参数。当禁忌表大小为1时，等价于不允许同样的赋值被立即重新访问。 各种不同算法不同之处在于它们采用了多少工作量来确保最佳改进。举一个极端的情况，算法在选择新赋值时可以确保给出的是相对于所有邻居的最佳改进。另一个极端的情况是，算法随机选取一个新的赋值，并且拒绝使情况更糟的赋值。下面将给出一些典算法，各种算法的不同之处在于它们付出了多少计算工作量来确保完成最佳改进。那个方法能取得最好的效果通常是一个经验问题。 1、常用的改进方法 第一种方法总是成对地选择变量-变量值来完成最佳改进。最朴素的办法就是线性地扫描每个变量和它的每个变量值，然后对比当前的所有变量的赋值决定哪个赋值能使得不被满足的约束数量最少，进而选择一个有产生最佳改进的变量-变量值对，即使这个改进是有负面影响的。当变量数据为n，平均域大小为d，一个赋值的邻居数为r时，这一步复杂度是O(ndr)。 一个更精细的替换策略是设置一个变量-变量值的优先队列。对于任意的变量X，值v在X的域内，并且在当前赋值下变量X没有被赋值为v，那么对就将被填入优先队列。的权重为当前完整赋值的评估减去将X替换为v的完整赋值的评估。也就是说，它包含了每个替换值的评估变化。在每个阶段，算法选择一个最小权重值，这个值则是邻居所能提供的最佳改进。 一旦变量X被赋予一个新值，那么所有变量中有多个权重将被改变，必须重新计算后插入优先队列中。当X被赋予v值时，被更改权重的那些变量是由于这个新值而出现在一个被满足或不被满足约束中的变量。 当变量数为n，平均域大小为d，那一个赋值的邻居数为r时，算法这一步的复杂度是O(log nd+rd log nd)。由于算法在每次都要确保最大的改进，因此在掌握数据的结构方面花费了太多时间。 2、两阶段的选择 一个替换策略是将成对选择变量变量值策略进行分割，首先选择一个变量进行更改，然后再选择一个值。 该算法也有一个变量优先队列，队列*量的权重为变量所参与的冲突约束数。每次算法都选择一个具有最大权重的变量。一个变量被选中，那么这个变量将被赋予一个能最小化约束冲突数的值。作为最新赋值的一个结果，每个变量的约束冲突的值也会发生改变，其余参与到这个冲突的变量的权重也需要被更改。 算法这一步的复杂度是O(log n+r log n)。对比成对地选择最佳变量变量值方法，该算法在每次移动中做的工作量较小，但在固定时间间隔内需要完成更多的移动。尽管这些移动倾向于完成较小的改进，但是在移动数和每次移动的复杂度两者间的权衡需要经验性的评估。 3、任意冲突 相对于选择最佳的移动，一个更为简单的替换策略是选择参与约束冲突的任意变量，并改变它的值。在每一次移动随机任意选择一个参与到不满足约束的变量。该算法将赋予这个变量一个能最小化约束冲突的值。 为了完成这个替换策略，我们需要一个数据结构，用这个结构来表示涉及一个约束冲突的变量集合C。该数据结构应被设计为可以快速选择C中的一个随机成员。当X的值发生改变时，每个包含X的约束都被检查。对于每个变为满足的约束，存在包含在该约束内且不包含在另一个不被满足的约束中的变量，将这些变量从C中删除。检查一个变量是否包含在另一个冲突约束中的方法是掌握每个变量的一组冲突数，这个数在一个约束变为不被满足时将增加，在约束变为被满足时将减少。可以将随机移动、随机重启和禁忌表机制与上述算法组合使用。 4、模拟退火 最后一种方法将不再获取约束冲突数据的结构，取而代之的是随机地选择一个邻居，然后对于新赋值选择接受还是拒绝。 退火是冶金术中的一个过程，在金属慢慢冷却的过程中，使它们达到一个低能量的状态。模拟退火3是一种类似最优化的方法。它用热力学的术语来描述。随机运动对应了高温；在低温条件下则有很小的随机性。模拟退火的执行过程是从在高温下进行随机搜索开始，然后温度慢慢降低，最后到达零度时变成纯贪婪下降。随机性应该倾向于跳出局部极值，并且找到一个低启发值作为邻域；贪婪下降的过程中将导致局部最小。高温条件比低温条件更有可能导致逐步恶化。 模拟退火掌握了当前变量的一个赋值情况。在每一移动中，随机选取一个变量，并且随机选取一个值。如果对该变量的赋值是一个改进或者它没有增加约束冲突数，那么算法接受这个赋值，并依此作为当前的新赋值。另外，算法概率性的接受赋值，这取决于当前的温度和新赋值比当前赋值差了多少。如果当前的改变不被接受，那么当前赋值也不会被改变。 为了控制变化到什么程度是可以被接受的，设定一个正实值的温度T，假设A是当前的一套赋值。假设h(A)是A被最小化的评估值。为了解决约束问题，h通常为约束冲突数。模拟退火随机地选择一个邻居，给出新的赋值A。如果h(A)h(A)，算法接受赋值A，并把其作为新的赋值。否则，这个赋值仅以e(h(A)-h(A)/T这个概率被随机接受。 这样，如果h(A)和h(A)很接近，那么被接受的可能性会更大。如果温度很高，那么指数趋近于0，接受概率则接近1。当温度接近0时，指数接近，且接受概率接近0。 图2中给出不同温度下逐步变差的接受概率。图中，k变差表示h(A)-h(A)=k。例如，如果温度为10（T=10），改变为1-worse(h(a)-h(a)=-1)的接受概率是e-0.10.9。改变为2-worse的接受概率是e-0.20.82。如果温度是1，改变为1worse的接受概率是e-10.37。如果温度是0.1，改变为1-worse的接受概率是e-100.000 05。这个温度下，它本质上仅是一个提升赋值或维持不变的操作。 如果T=10这种情况，温度很高时，算法倾向于接受变差程度很小的移动；不倾向于接受变差程度很大的移动。算法对于改进的移动有轻微的偏好。当温度减少时（例如，当T=1时），尽量变化的移动是有可能的。但是可能性较小。当温度非常小时（例如，当T=0.1时），选择一个变差的移动将非常罕见。 模拟退火需要一个退火计划，这个计划说明在搜索的过程中，温度是怎样下降的。几何冷却法是一个被广泛应用的计划。例如，几何冷却计划开始于温度10，