【运筹优化】元启发式算法详解：变邻域搜索算法（Variable Neighborhood Search，VNS）+ 案例讲解&代码实现

可变邻域搜索(VNS)是一种元启发式算法，该算法基于邻域系统变化的思想，在下降阶段寻找局部最优解，在扰动阶段走出相应的谷值。最初设计用于组合优化问题的近似解，它被扩展到处理混合整数规划、非线性规划，以及最近的混合整数非线性规划。此外，VNS已被用作自动化或计算机辅助图论的工具。这导致了该领域超过1500个猜想的发现，并自动证明了其中的一半以上。这与许多不同的数学家对大约400个这样的猜想所做的独立

WSKH0929

7084人浏览 · 2023-06-01 16:07:18

WSKH0929 · 2023-06-01 16:07:18 发布

一、介绍

可变邻域搜索(VNS)是一种元启发式算法，该算法基于邻域系统变化的思想，在下降阶段寻找局部最优解，在扰动阶段走出相应的谷值。

最初设计用于组合优化问题的近似解，它被扩展到处理混合整数规划、非线性规划，以及最近的混合整数非线性规划。

此外，VNS已被用作自动化或计算机辅助图论的工具。这导致了该领域超过1500个猜想的发现，并自动证明了其中的一半以上。这与许多不同的数学家对大约400个这样的猜想所做的独立的证明形成了对比。

本博客组织如下：

第二节中，我们将介绍VNS的基本方案，即可变邻域下降(VND)、简化VNS (RVNS)、基本VNS (BVNS)和广义VNS (GVNS)
两个重要的扩展出现在第三节：偏斜VNS和可变邻域分解搜索（VNDS）。
第四节讨论了最近进一步的发展，称为公式空间搜索(FSS)。本文的其余部分描述了VNS在几类大规模和复杂优化问题中的应用，这些应用已被证明是特别成功的。
第五节专门介绍原始双VNS (PD-VNS)及其在定位和聚类问题中的应用。
寻找具有VNS的大型混合整数线性规划的可行解将在第六节中讨论。
第七节介绍了在连续全局优化中应用VNS的方法。
用VNS求解混合整数非线性规划的更困难的情况将在八节中考虑。
将VNS应用于图论本身(而不仅仅是图上定义的特定优化问题)将在第九节中讨论。
第十节给出了简短的结论。

二、基本方案

确定性优化问题可以表述为：

在这里插入图片描述

令 $N_k(k=1,...,k_{max})$ 是一个预先定义好的有限数量的邻域结构集合。 $N_k(x)$ 是解 $x$ 的第 $k$ 个邻域解集合。

大多数的局部搜索启发式算法仅仅使用一个邻域结构，即 $k_{max}=1$ 。

令最优解 $x_{opt}$ (或全局最小值)是达到最小值的可行解。

如果 $x∈N_k(x')$ 不存在令 $f (x) < f (x^{'})$ 的解，则称 $x^{'} \in X$ 是关于 $N_k$ 的 $(3.1)$ 的局部最小值。

元启发式(基于局部搜索过程)在找到第一个局部最小值后，尝试通过其他方式继续搜索。

VNS则基于三个简单的事实：

事实1：一个邻域结构的局部最小解 $x^{'}$ ，对另一个邻域结构不一定如此；
事实2：全局最小值是所有可能邻域结构的局部最小值；
事实3：在许多问题中，不同邻域结构的局部极小值与局部极小值之间的距离相对较近

最后这一点是经验性的，它意味着局部最优常常提供一些关于全局最优的信息。

例如，在两个解决方案中可能有几个变量共享相同的值。由于这些变量通常不能提前确定，因此应该对局部最优的邻域进行有组织的研究，直到找到更好的解决方案。

为了通过使用多个邻域来解决(3.1)，事实1 - 3可以以三种不同的方式使用：(1)确定性;(2)随机;(3)既有确定性又有随机性。

我们首先在算法1中检查将在VNS框架中使用的解移动和邻域变化函数。

$N e i g hb or h oo d C han g e (x, x^{'}, k)$ 将在位值 $f (x)$ 与从第 $k$ 个邻域(行1)获得的新值 $f (x^{'})$ 进行比较。如果获得改进，则更新在位值(行2)，并将 $k$ 返回到初始值(行3)。否则，考虑下一个邻域(行4)。

在这里插入图片描述
下面我们讨论变邻域下降和简化变邻域搜索，然后在此基础上构建基本和一般变邻域搜索的框架：

(i) 可变邻域下降(Variable Neighborhood Descent，VND)方法(算法2)以确定性的方式进行邻域的改变。这些邻域记为 $N_k( k = 1,…, k_{max})$ 。

在这里插入图片描述
大多数局部搜索启发式算法使用一个或两个邻域来改进当前解决方案，但是最终解决方案应该是所有邻域的局部最小值解，因此，与单个邻域结构相比，采用更多的邻域更有可能达到全局最优解。

(ii) 从 $N_k(x)$ 中随机选择一个点，而不尝试从该点下降，得到 RVNS (Reduced VNS) 方法。相反，将新点的目标值与现有点的目标值进行比较，并在改进的情况下进行更新。我们还假设已经选择了一个停止条件，例如允许的最大CPU时间 $t_{max}$ ，或者两个改进之间的最大迭代次数。为了简化算法的描述，我们在下面总是使用 $t_{max}$ 。因此，RVNS(算法3)使用两个参数： $t_{max}$ 和 $k_{max}$ 。

在这里插入图片描述

第4行中的 $S hak e (x, k)$ 函数从 $x$ 的第 $k$ 个邻域随机生成一个点 $x^{'}$ ，即 $x'∈N_k(x)$ 。在算法4中给出，其中假设 $N_k(x)$ 中的点编号为 ${x^1,..., x^{|N_k(x)|}\}$ 。请注意，震动操作中的邻域结构使用了不同的符号，因为这些通常与VND中使用的符号不同。

在这里插入图片描述
RVNS对于局部搜索成本很高的大型实例非常有用。它也可以用于在分解之前找到大型问题的初始解决方案。

据观察，参数 $k_{max}$ 的最佳值通常是 $2$ 或 $3$ 。此外，两次改进之间的最大迭代次数通常用作停止条件。RVNS类似于蒙特卡罗方法，但更具系统性。

(iii) 基本VNS (Basic VNS, BVNS)方法结合了邻域的确定性和随机变化。确定性部分用局部搜索启发式表示。它包括：

(1) 选择一个初始解 $x$
(2) 找到一个从 $x$ 下降的方向(在一个邻域 $N (x)$ 内)
(3) 沿着这个方向移动到 $N (x)$ 内 $f (x)$ 的最小值。如果没有下降方向，则启发式停止；否则迭代

通常使用最陡下降方向，也称为最佳改进方向。另请参阅算法2，其中在VND的每个邻域中使用最佳改进。这在算法5中进行了总结，其中我们假设给出了初始解 $x$ 。输出由局部最小值(也用 $x$ 表示)及其值组成。

在这里插入图片描述

由于最陡下降法可能很耗时，所以另一种方法是使用首次下降法(或首次改进法)。然后系统地枚举点 $x^i∈N(x)$ ，一旦找到下降方向就进行移动。算法6对此进行了总结。

在这里插入图片描述
BVNS的随机相位(见算法7)由从震动操作的第 $k$ 邻域随机选择点 $x^{'}$ 表示。请注意,在步骤5中随机生成点 $x^{'}$ ，以避免在确定性规则中可能发生的循环。

在这里插入图片描述

(iv) 一般VNS（General VNS）。请注意，局部搜索步骤(BVNS算法7中的第6行)也可以被VND(算法2)所取代。这种通用VNS (VNS/VND)方法已经导致了文献中报道的一些最成功的应用。一般VNS (GVNS)概述在下面的算法8中。注意邻域 ${N_1,...,N_{l_{max}}\}$ 用于 VND 步骤，而不同的邻域序列 ${N_1,...,N_{k_{max}}\}$ 适用于震动步骤。

在这里插入图片描述

三、一些扩展

(i) 倾斜 VNS (Skewed VNS，SVNS)方法解决了探索远离现有解决方案的山谷的问题。事实上，一旦在一个大地区找到了最佳解决方案，就必须走很远的路才能得到一个改进的解决方案。在遥远的邻域中随机抽取的解可能与现有的解有很大的不同，然后VNS可能在某种程度上退化为多起点启发式(其中从随机生成的解迭代下降，这是低效的)。因此，必须对与现任者的距离进行补偿，为此提出了一种称为倾斜VNS (SVNS)的方案。其步骤在算法9、10和11中给出。SVNS中的 $Kee pB es t (x, x^{'})$ 函数(算法9)仅保留最佳解决方案 $x$ 和 $x^{'}$ 。 $N e i g hb or h oo d C han g e S$ 函数(算法10)执行SVNS的移动和邻居更改。

在这里插入图片描述

SVNS利用函数 $ρ (x, x^{''})$ 来测量当前解 $x$ 和局部最优解 $x^{''}$ 之间的距离。用于定义 $N_k$ 的距离函数也可用于此目的。当 $f (x^{''})$ 大于 $f (x)$ 但不能太大(否则总是会离开 $x$ )时，必须选择参数 $α$ 以允许向远离 $x$ 的谷移动。在每种情况下，实验都可以找到 $α$ 的良好值。此外，为了避免从 $x$ 到接近解的频繁移动，当 $ρ (x, x^{''})$ 很小时，可以取较小的 $α$ 值。更复杂的 $α ρ (x, x^{''})$ 函数的选择可以通过一些学习过程（机器学习）来完成。

在这里插入图片描述

(ii) 变量邻域分解搜索(Variable neighborhood decomposition search, VNDS)方法在对问题进行分解的基础上，将基本VNS扩展为两级VNS方案。它在算法12中给出，其中 $t_d$ 是一个附加参数，表示Basic VNS(第5行)解决分解(较小规模)问题所允许的运行时间。

在这里插入图片描述
为了便于表示，但又不失一般性，我们假设解 $x$ 表示一组属性。在步骤4中，我们用 $y$ 表示在 $x^{'}$ 中存在但不存在于 $\ x ) x (即y = x' \backslash x)$ 中的 $k$ 个解属性的集合。在步骤5中，我们在 $y$ 空间中找到局部最优 $y^{'}$ ；然后用 $x^{''}$ 表示整个空间 $\ y ) ∪ y ′ ) x (x''= (x' \backslash y)∪y')$ 的对应解。我们注意到在新解中利用一些边界效应可以显著提高解的质量。这就是为什么在步骤6中，使用 $x^{''}$ 作为初始解在整个空间 $x$ 中找到局部最优 $x^{''}$ 的原因。如果这很耗时，那么至少应该执行一些局部搜索迭代。

VNDS可以被看作是在VNS框架中嵌入经典的逐次逼近方案(至少从60年代开始就被用于组合优化）。

四、在VNS内改变配方

解决优化问题的传统方法是考虑给定的公式，并以某种方式通过其可行集 $x$ 进行搜索。鉴于相同的问题通常可以用不同的方式进行表述，因此可以扩展搜索范例，以包括从一个公式到另一个公式的跳转。

每个公式都应该适合一些传统的搜索方法，它的“局部搜索”完全在这个公式中工作，并从某个初始解开始产生最终解。在一种公式中找到的任何解都应该很容易地转化为它在任何其他公式中的等效解。

然后，我们可以通过使用由前者的局部搜索得到的解作为后者的局部搜索的初始解，从一个公式移动到另一个公式。当然，这种策略只有在不同形式的本地搜索表现不同时才有用。这里我们讨论两种这样的可能性。

4.1 基于变邻域的公式空间搜索

略

在这里插入图片描述

4.2 变公式搜索

略

五、原始对偶VNS

对于大多数现代试探法，最优解和获得的近似解之间的差值并不精确。如果可以找到目标的下限函数值。为此，标准的方法是根据问题的数学规划公式，放松原始变量的完整性条件。

然而，当问题的维度很大时，即使是宽松的问题也不可能被标准的商业解决者精确地解决。因此，启发式地解决对偶松弛问题似乎也是一个好主意。以这种方式，我们得到了原始启发式性能的保证界限。

如果我们想在分支定界框架内得到精确解，下一个困难就出现了，因为拥有松弛对偶的近似值不允许我们以简单的方式分支，例如通过利用互补松弛条件。因此，对偶的精确值是必要的。于是学者们提出了一种获得保证界和精确解的一般方法，称为原始对偶VNS (PD-VNS)。它在算法16中给出。

在这里插入图片描述
在第一阶段，一个基于VNS的启发式程序被用来获得一个接近最优的解决方案。

在第二阶段，目标是找到松弛对偶问题的精确解。求解松弛对偶分三个阶段完成：
(1)使用原始启发式解和补充松弛条件找到初始对偶解(通常不可行)
(2)通过将VNS应用于对偶的无约束非线性形式来寻找可行解
(3)使用在对偶变量上应用“窗口”的定制“滑动单纯形”算法，从找到的初始可行解开始精确地求解对偶，从而大大减小了问题的大小。在所有测试的问题上，包括比文献中以前报道的大得多的例子，该程序能够在合理的计算时间内找到精确的对偶解。

在第三和最后阶段，分别从第一阶段的启发式原始解和第二阶段的精确对偶解获得严格的上界和下界，应用标准分支定界算法来寻找原始问题的最优解。

每当在分支树的节点处获得新的整数解时，用对偶滑动单纯形法更新下界，并更新上界。通过这种方式，对于统一的固定成本，有可能精确地解决规模高达7000个设施×7000个用户的问题实例，甚至15000个设施×15000个用户的问题实例。

六、求解混合整数线性规划的VNS

略

七、连续全局优化的可变邻域搜索

略

八、可变邻域编程(VNP):自动编程的VNS

略

九、Discovery Science

略

十、总结

提出并讨论了变邻域搜索的一般方案。为了评估与VNS相关的研究进展，我们需要一个元启发式的可取属性列表。

简单性：元启发式应该基于一个简单明了的原则，这个原则应该广泛适用
严谨：元启发式的步骤应该用严谨的数学术语来表述，独立于可能是灵感最初来源的物理或生物类比
连贯性：为解决特定问题而开发的所有启发式步骤都应该自然地遵循元启发式原则
有效性：对特定问题的启发应该为所有已知的或至少是最现实的情况提供最优或接近最优的解决方案。最好是，他们应该为大多数已知解决方案的基准问题找到最优解决方案
效率：针对特定问题的启发式算法应该花费适度的计算时间来提供最优或接近最优的解决方案，或者比最先进的解决方案更好的解决方案
鲁棒性：元启发式算法的性能应该在各种情况下都是一致的，也就是说，不仅仅是对一些训练集进行微调，而在其他地方并不那么好
用户友好性：元启发式应该表达清楚，易于理解，最重要的是，易于使用。这意味着它应该有尽可能少的参数，最好没有
创新：元启发法的原理或由此衍生的启发法的效率和有效性应该导致新类型的应用
一般性：元启发式应该对各种各样的问题产生好的结果
交互性：元启发式应该允许用户结合他的知识来改进解决过程
多重性：元启发式应该能够产生几个接近最优的解决方案，用户可以从中进行选择

我们试图在这里表明，VNS在很大程度上拥有所有上述性质。这个框架导致了启发式，这是解决许多问题的最佳方法之一。人们对VNS的兴趣正在迅速增长。每年发表的关于这一主题的论文越来越多就证明了这一点。20年前，只有几个；15年前，大概十几个；10年前50篇左右，2016年250多篇。

图3.8显示了关于VNS和其他最著名的元试探法的论文数量的平行增长。数据是通过使用Scopus搜索工具获得的，查找术语“可变邻域搜索”(VNS)和“元启发式搜索”(MH)。图3.8显示了这些术语在该数据库的论文摘要中出现的次数。使用的年份是从2000年到2017年，但2017年只包括前6个月(从1月到6月)。为了便于比较，用MH的论文数除以4。

在这里插入图片描述