可变邻域搜索技术的原理及应用.rar

可变邻域搜索技术的原理及应用
作者：Pierre Hansen, Nenad Mladenovic
摘要：
一个可能的随机系统的邻域搜索算法的系统改变为组合问题和全局最优解问题产生一个简单而且有效的直接推断法，它被称为可变邻域搜索法（VNS）。我们为了这个目的介绍一种能够被任何局部搜索算法作为子程序容易实施的基本方案，他的功用已经在解决一些传统组合全局最优化问题得到阐明。此外，它的一些扩展也被建议用来解决大的问题场合：在逐步近似法中使用VNS产生了一个被称为可变邻域分解搜索法的二级VNS(VNDS)；修改基本方案去开发脱离限制的简单领域产生了一种有效歪斜的VNS(SNVS)直接推理法。最后，我们将在VNS的帮助下展示如何稳定继承父代的算法，和讨论用各种方法在图线理论下去使用VNS，如说明，证明或者给出线索去证实如何证明猜想，在那种超启发式没有出现而之前却已经被运用。
关键词：启发式，超启发式；可变邻域搜索技术；VNS
1绪论
从很早开始启发式已经在解决大量的实际问题中得到广泛使用。确实模仿综合问题经常产生困难的问题。这类问题在最差的事情中很难处理，但在一般事情或者研究中也许不是这样。然而，现在一大套工具对正确地解决他们很有用（分支界限，剖面，分解，拉格朗日缓和，直代遗传，…）可能不能够去解决很大的问题，从而给了启发式一个回复。此外，这些可以被以下的图解，启发式可能在准确的算法中非常的有用。
启发式另一个有用发面是局部搜索。它的处理是从初始化的局部次序解决，这样改善每一次客观因素的价值，直到找出最优解。近些年，许多超启发式被提了出来，这个方案扩大了各种方式而且可以避免陷入局部最优解从而失去意义（见【56】）这些超启发式，例如：适应的 交叉开始【4】，各种深度搜索【47，55】，模拟退火【42】，禁忌搜索技术（TS）[23-27,30],领会【14】还有如遗传搜索技术【38】与蚂蚁群体【11】，在许多实际文章中已经引起了很大的改良。
在这篇文章里，我们调查了相关未调查的接近接近启发式的设计：在搜索中邻域的变化。用系统的这个想法或者稍多点，也就是，只有邻域搜索技术导致一种新的超启发式，它具有广泛的可适用性。我们称这种逼近可变邻域搜索技术（VNS）.与其它基于邻域搜索技术方法相反，VNS不沿着一定轨道但向着远的附近可行域搜索解答，还从这个解答跳向新的解答，只要而且只能是逼近最优解，这种方法的可行域的有力特征将被保持并被用来获得更接近最优解的解答，举例来说，就是很多变量都已经得到最佳解。此外，邻域搜索程序是被再三的用来获得临近较优解的，从而获得最优解。这个程序也或许使用于个别领域，因此，要构建不同的邻域组织去完成系统的搜索，这就需要一个方法找出任意两个解答之间的差距，也就是需要提供一定的如米制的（或类似米制）解答空间，然后引导附近邻域接近这个空间。在下一个运用部分，我们解答这类特殊问题当作每一个被认为的难题。