论文拾萃|用基于邻域分解的启发式算法（NDHA）解决最大化多样性分组问题

一.引言

1.最大化多样性分组问题（MDGP）

最大化多样性分组问题的基本场景是将M个元素分配到G个不相交的分组中，目标是使所有分组的多样性之和最大，其中每个分组的多样性可以定义为这个分组中任意两个元素之间的「距离」之和，而任意两个元素之间的距离则依赖于特定应用场景。

同时，最大化多样性分配问题有两种类型：

• 第一种，等分组最大化多样性问题（MDGP1）。这个问题使每个集合都含有S个元素（S=M/G）
• 第二种，不等分组的最大化多样性问题（MDGP2）。这个问题要求每一个分组g的大小Sg分布于给定的区间 [ag，bg]内（ag<=bg）

「显然，MDGP1是MDGP2的一种特殊情况」

举一个例子：众所周知，当大型程序存储在一个页式存储器上时，由于子程序需要被分配到内存中不同的页面上，我们为了减少页面切换带来的时间开销，所以要最大化在同一个页面上子程序之间的数据传输，这就是一个MDGP问题。

MDGP问题也存在于超大规模集成电路的优化、创造最大多样性的学生（员工）分组等实际问题之中。

「在本文中，我们用一张带非负边权的完全图来表示各元素及其距离」

二.算法内容

1.基本框架

• 第一步，初始化，找到一个初始的可行解
• 第二步，迭代到time limit
  • （1）用扰动算子对当前解进行扰动
  • （2）使用基于邻域分解的变邻域搜索（NDVNS）或禁忌搜索（NDTS）算法对扰动后的解进行优化
  • （3）比较该迭代产生的解和先前的最优解，若更优则进行替换
  • （4）若最优解在该次迭代获得优化，则把扰动强度调整到最小，否则增加扰动强度
• 伪代码：

k为扰动强度，Q为一个常数，用于随机选择使用NDVNS或NDTS

2.解的表达方式

L和U分别表示该集合的上下界

我们用一个n维的数组（x[1——N]）来表示一个可行的解，x[i]=g意味着顶点i已经被分配到了g集合中。

而为了便于理解领域分解的作用方式，我们干脆使用了一个m*Umax的矩阵来表示可行解（如上图的表示方式）

3.分步详解

3.1 初始化

初始化的目的很简单，产生可行的解即可

首先，我们随机把一些点放到各集合里，先满足各集合元素个数的下限

然后，我们把剩下的点随机分配到每个集合里，只要不突破其元素个数上界即可

这样我们便拥有了一个初始解

啪的一下就理解了，很快啊

不过呢，在实际操作中，我们一般会进行贪心优化，让随机产生的初始解更趋近于优解

这里的具体操作在代码注释里有详细说明哦

为了进一步让随机产生的初始解趋近于优解，我们一般依照此方法生成一系列（10个以上）的解，并从中选取最优

3.2基于邻域分解的邻域搜索

3.2.1 邻域和邻域分解

在此算法中，我们定义两类邻域：

• OneMove Neighborhood：在给定的解集S={G1,G2...Gm}之中，在满足各集合上下界的基础上，把Gi里的一个点v移动到集合Gj中去（用 「s ⊕ (v, i, j)」 表示）。在此，我们用N1(s)表示这类邻域（即N1(s)表示当前可以通过OneMove得到的所有新解）。显然，这一类邻域的空间复杂度是O(N*M)。

「我们发现，N1(s)居然可以被分成m(m-1)个不相交子集」

我们把这些不相交的子集叫做邻域块（Neighborhood block），在这一类邻域中，我们用「B1[i] [j] (i,j∈ {1, . . . , m}, i!= j)」,来表示邻域块。

「故有：B1[i] [j]={s ⊕ (v, i, j)}，N1(s) = ∪1≤i!=j≤mB1[i] [j] (s).」

是不是有点懵？这就是本算法中最重要的部分哦——「邻域分解！」

• Swap Neighborhood：交换点v和点u位置，也就是说把点v放到点u所属的集合Gi之中，把点u放到点v所属的集合Gj之中。在此，我们用N2(s)来表示这类邻域。这一类邻域的空间复杂度是O(N*N)。

同理，N2(s)也能被分成m*(m-1)/2个邻域块，用B2[i] [j] (i,j∈ {1, . . . , m}, i!= j)来表示。

（为什么是m*(m-1)/2？留给读者们自己思考哦）

邻域分解有什么用？且再听我一步步介绍给大家

到底是怎么一会事呢

邻域分解之后，我们就要有请~熟悉的朋友——「状态矩阵！」

学过动态规划的小伙伴们都已经被这个名字折磨得不轻了罢

闲篇儿不扯，进入正题：

• 对于N1(s)：

给定一个m*m的二进制矩阵M1，其中M1[i] [j] (1 ≤ i != j ≤ m)与B1[i] [j]对应。

（显然，这个矩阵对角线上的值与本算法无关，因为B1[i] [i]必然是个空集）

如果B1[i] [j]先前已被搜索过，并且我们的解未能在其中得到优化，那么我们就把M1[i] [j]赋值为0，否则赋值为1

• 对于N2(s)： 两个字，「同理」。

只不过由于M2[i] [j]是一个关于对角线对称的矩形，所以所有关于M2[i] [j]的操作必然要作用于B2[j] [i]

所以M2[i] [j]和M2[j] [i]需要同时被赋值

为什么？因为这是swap。

特别地，当搜索正在进行时，M1[i] [j]，M2[i] [j]和M2[j] [i]的值暂时都是0，在找到更优的解之后才被更新为1

「同时，如果在某个邻域块里我们的解被优化了：」

M1[i] [q] (or M2[i] [q]for N2),

M1[q] [i] (or M2[q] [i]for N2),

M1[j] [q] (or M2[j] [q]for N2),

M1[q] [j] (or M2[q] [j]for N2),

(1 ≤ q ≤ m)

这些区块都需要被搜索一遍，若有优化便更新为1！

如图：（蓝色区块代表正在进行搜索的邻域块，紫色代表着需要被搜索，可能被更新成1的邻域块）

「在这之后，只需要搜索状态矩阵中值为1的区块所对应的邻域块即可，其他的都可以跳过」

打住。

凭什么是这些区块的值被更新？

因为仔细对照先前对于状态矩阵和邻域块的定义，发现只有紫色区块对应的邻域块会被解的更新所影响。

3.2.1.ex：小小的总结一下

1. 邻域分解的进行基于以下事实：MDGP问题是被定义为m个分组的子目标的总和，由此产生的邻域块有着较好的独立性。
2. 邻域分解在状态矩阵的帮助下帮助我们跳过了没有希望产生更优解的邻域块，避免了大量冗余的无意义搜索，由此也就大大加快了运算速度

3.2.2NDVNS

做好准备之后，VNS似乎也没有那么狰狞了 什么？VNS是什么？

直接上伪代码罢。

NDVNS

3.2.3 NDTS

就算是禁忌搜索似乎也不是那么难懂 什么？你不知道禁忌搜索是什么？

如图，NDTS里加入了一个常数μ，使得B2[i] [j] (s)始终有μ的概率被包含在邻域N2(s)之中，不管其所对应的状态矩阵是1还是0，这样一来就避免了由于邻域N2(s)实在太小而导致的算法效率降低。

「经过研究，在本算法中μ=0.05」

NDTS

3.2.4 扰动函数

众所周知，在所有的启发式算法里都需要一个扰动函数来跳出局部最优陷阱，顺便还能增加一些搜索的多样性。

本算法里就是随机挑两个点出来swap一下就行。

扰动函数

三.优势总结——NDHA好处都有啥，谁说对了——

关于NDHA介绍了这么多，它真的厉害吗？

不厉害我给你讲这么多干啥？

话不多说我们直接上图：

相比于目前最先进的几种算法，NDHA在最佳目标值和平均目标值上都有着较大优势，尤其是在m比较大时

总结一下NDHA的强大之处：

1. 使用两种启发式搜索算法，以一定的概率交替进行，加强了算法的稳定性
2. 创造性地提出了「邻域分解」策略，大大提高了算法速度，同时，该策略也可以被应用于解决其他相关的MDGP或者分群问题
3. 真的很快。尤其是当数据较大时，运算速度带来的精度优势尤其明显

四.参考文献

【1】Xiangjing Lai, Jin-Kao Hao, Zhang-Hua Fu Dong Yue "Neighborhood decomposition based variable neighborhood scarch and tabu search for maximally diverse grouping"，European Joural of Operational Research July 2020 .

【2】谢龙恩《求解最大化多样性分组问题的一种混合算法》.

欲下载相关代码，请移步留言区

-The End-

文案&代码注释&排版：黄锐扬（华中科技大学管理学院本科一年级）

指导老师：秦虎老师 （华中科技大学管理学院）

如对文中内容有疑问，欢迎交流。PS：部分资料来自网络。