Chapter 12 Variable Neighborhood Search

定义：变邻域搜索算法（VNS）就是一种改进型的局部搜索算法。它利用不同的动作构成的邻域结构进行交替搜索，在集中性和疏散性之间达到很好的平衡。其思想可以概括为“变则通”。
变邻域搜索算法依赖于以下事实：

• 一个邻域结构的局部最优解不一定是另一个邻域结构的局部最优解。
• 全局最优解是所有可能邻域的局部最优解。
• 对于许多问题，不同领域的局部最优解互相非常接近（这一点表明，局部最优解蕴含着全局最优解的信息，但并不知道蕴含了什么信息）

  不同算法的比较

  名词解释

  VND: variable neiborhoods descent
  VNS: variable neiborhood search
  RVNS: reduced VNS
  basic VNS
  general VNS
  SVNS: skewed VNS
  VNDS: varaible neiborhood decomposition search
  MSSC: minimum sum-of-square clustering

  算法要素对比

  | 算法 | 策略 | 问题 | | —- | —- | —- | | VND:
  variable neiborhoods descent | 1）如果解是随机生成的则使用first improvement;
  2）如果解是通过一些启发式规则生成的，则使用best improvement | (i) What complexity do the different moves have?
  (ii) What is the best order in applying them?
  (iii) Are the moves considered sufficient to ensure a thorough exploration of the region containingx?
  (iv) How precise a solution is desired? | | RVNS: reduced VNS | 邻域往往是嵌套的 | 1. which direction to go?
  2. how far ?
  3. how should one modify moves if they are not successful? | | Basic and General VNS | 当问题的约束过多时，尤其当可行域是分离的时，
  - 限制在可行域内搜索可能约束过强
  - 使用拉格朗日乘子法（将一些约束放入到目标函数中），可能导致搜索到不可行解
  - 一个可行的方法是，惩罚不可行性
  | - 为了搜索到全局最优解或者近似全局最优解，哪些性质是邻域结构必须的？
  - 为了方便实施，一般使用嵌套结构，如对于TSP问题，定义，然后迭代次，获得邻域，邻域的大小逐渐增大
  - 邻域的哪些性质有利于找到近似最优解？
  - 邻域是否应该互相嵌套？否则应该怎样排序？
  - 邻域的理想大小是多少？
  | | SVNS: skewed VNS | 步骤2.d中，用，其中是和之间的距离，允许解跳到一个距离较远但是不那么好的解，然后进一步搜索，能提高解跳出局部最优的能力。
  | 使用SVNS需要考虑两个问题：1）所考虑的问题是否有一个非平滑凸（roughly convex）的目标函数，或者是几个相隔很远的山谷（valley）；2）如何选择。
  解决方法：首先使用VNS的多起点版本（比如随机设置VNS的初始解，并且运行一小段时间），然后观察每个局部最优解是聚集在一起，还是比较分散。更进一步，我们可以绘制所有局部最优解与最好的解之间的函数值差异和距离差异，从而确定的取值。 | | VNDS:
  varaible neiborhood decomposition search | 将问题分解为多个子问题，每个邻域解决一个子问题 | |

伪代码对比

使用VNS的步骤

• 增加对问题的理解：生成一个简单的数值例子，并花一些时间手动解决它，尽量理解为什么这个问题是困难的，以及为什么要使用启发式算法。
• 阅读文献：
• 测试例子或数据：步骤1，使用生成的数值例子，搜集文献中的大规模算例测试算法。步骤2，通过均匀分布等函数生成一些算例
• 数据结构：寻找合理的数据结构
• 初始解：方法1）随机生成；方法2）使用一些贪婪规则，推荐使用方法2
• 目标函数：生成一个评估解的目标函数的程序
• 震动（shaking）：这是VNS的关键。
• 局部搜索：
  • 设计局部搜索算法：使用一些现成的局部启发是搜索方法，或者通过drop, add, swap, interchange等方法组合出一个新的局部搜索算法
  • 评估解，利用搜索的特性，提高评估解的目标函数的效率

• 比较：

  其他建议

• 比较first improvement 和 best improvement：以往的研究表明，如果解是随机生成的，则使用first improvement;如果解是通过一些启发式规则生成的，则使用best improvement

• 减少邻域：1）识别出现最优解可能性高的邻域；2）设计能够在邻域中找到一个好的解的方法
• 强化震动：1）研究解对微小震动的敏感度；2）在VNS中，平衡集中性和多样性的算子在shaking中。比如，随机选择一个邻域，往往会导致解过于分散，这时，一些intensify shalking 可以增强局部搜索能力（如k-interchange，neiborhood may be reduced by repeating k times random add followed by best drop moves）
• VND:分析几个可能的邻域结构，评估他们的大小，排序（比如使用VND代替局部搜索从而获得VNS)
• 参数实验：在VNS中唯一的参数是,1）通过反复试验，寻找最佳值；2）根据具体问题，确定参数值，如p-medium问题中,MSSC问题中，

针对某个具体问题的邻域（计划实现该问题的算法）

可行的研究方向

• 第一个研究方向：研究基础VNS的强化，以及提高各个步骤效率的方法
  • 初始化
  • 邻域结构（inventory of neiborhoods)：研究现有文献中的启发式方法和使用的数据结构对设计新的邻域结构大有好处
  • 邻域分布：研究在局部搜索阶段和震荡阶段的邻域的分布。In particular, the trade-off between increased work in the descent, which provides better local optima, and in shaking which leads to better valleys should be focused upon.
  • 辅助测试（ancillary test）：研究每种邻域（操作）对结果提升的贡献，找出关键邻域（操作）
• 第二个研究方向：更改基础VNS
  • 记忆的使用：禁忌搜索算法和其他元启发式算法已经充分使用了记忆的，对于VNS的挑战时，在引入记忆的同时保持算法的简洁。其中一个有效的方法是reactive VNS，如Braisy(2001)在求解VRPTW问题时，如果某些约束很难被满足，那么解就会更频繁的惩罚违反这些约束的解。
  • 并行VNS：1）在VND中，并行使用局部搜索。2）将探索每个当前解的邻域的过程分配到不同进程；3）在VNDS中，将每个子问题分配到一个进程中
  • 混合：将VNS与其他元启发式算法混合

研究方法建议

搜索与选题相关的文献，需要注意的点

• 评估选题的难度：问题的复杂度，它是否是NP-hard问题，是否是强NP-hard问题
• 评估文献中算法的性能的标准：是否有标准测试集，最大的测试集的求解情况
• 评估文献中启发式算法：有哪些元启发式算法应用于这个问题了，就没饿规模的算例而言，算法的性能如何（求解时间，求解误差）

• 文献中的算法的步骤是什么样的，邻域结构如何设计的，代码是否公开

  评估元启发式算法的要素

• 1）简洁性，2）精确性，3）一致性，4）效率，5）有效性，6）鲁棒性，7）用户友好性，8）创新性

  解和邻域的特性

• 一个邻域结构的局部最优解不一定是另一个邻域结构的局部最优解。

• 全局最优解是所有可能邻域的局部最优解。
• 对于许多问题，不同领域的局部最优解互相非常接近（这一点表明，局部最优解蕴含着全局最优解的信息，但并不知道蕴含了什么信息）

参考资料

• 变邻域搜索算法(Variable Neighborhood Search)
• Burke E K , Kendall G . Search Methodologies || Variable Neighborhood Search[J]. 2014, 10.1007/978-1-4614-6940-7(Chapter 12):313-337.