论文拾萃 | 邻域分解驱动的变邻域搜索算法(NDVNS)求解容量限制分群问题(CCP)(附C++代码)

1.引言

聚类问题(Clustering problems)是一类将多个数分为固定或可变数目的多个组，使其在满足一定限制条件并且实现某些目标的问题。例如半监督图聚类、生物网络领域的限制图聚类、图划分、P-中心选址问题和P-中位问题。

容量限制分群问题[Capacitated clustering problem(CCP)]是典型的聚类问题，有广泛的应用空间。该问题可以描述如下：

给定一个完全权重图以及正常数，\ce{V = {v_1, v_2, . . . , v_N }} 是图的N个顶点，代表条边的集合，是边的权重的集合，是顶点的权重。

问题的目标是将顶点集合分成个不相交的集合\ce{C_1, C_2, . . . , C_K} ，使得每个集合内的顶点权重之和位于给定的区间\ce{[L, U]} 内，同时最大化同一个集合内的边权重之和。

以上图为例：

其中，分区数，所有点的权重，\ce{[L, U] = [3, 4]} ，对每个分区，分区内的点权和均在区间\ce{[L, U]} 内。目标即为使图中标红的边的权重之和最大。

换句话说，要把14个人分成4组开展工作，每组最少3人，最多4人。两人之间的合作默契程度可以量化为一个值，只有在两人在同一组时这个值才有效。我们的目标就是让这个有效值的和最大。

2.NDVNS算法流程

NDVNS是邻域分解驱动的变邻域搜索算法 (Neighborhood decomposition-driven variable neighborhood search)的缩写，流程如下：

1. 生成随机初始解并初始化扰动强度；
2. 用局部优化，同时将作为当前最优解；
3. 以目前的扰动强度对进行扰动得到；
4. 用局部优化；
5. 综合与，与的有效边权和之比以及距离函数计算值，结合参数计算优化效果（详见2.4），若更优则将作为当前解，并进而比较和的有效边权和，若的更大则将作为当前最优解；
6. 以概率性方式，结合参数调整扰动强度；
7. 若时间允许，返回到第3步，否则结束运算； 的伪代码如下：

2.1 生成随机初始解

1. 使所有分区的点权和不小于下界 1.1 选取权重最大的顶点 1.2 随机选择点权和小于下界的分区 1.3 判断放入后分区点权和是否越界，若不越界则放入，若越界则回到1.2 1.4 回到1.1直至所有分区的点权和不小于下界
2. 使所有顶点都进入分区 2.1 选取权重最大的顶点 2.2 随机选择点权和小于上界的分区 2.3 判断放入后分区点权和是否越界，若不越界则放入，若越界则回到2.2 2.4 回到2.1直至所有顶点都进入某个分区

2.2

为邻域分解驱动的变邻域下降法(neighborhood decomposition-driven variable neighborhood descent method)的缩写。

细心的你肯定发现了，在刚才的流程中有一个下标2或3(下记为)，区别就体现在引入局部优化()的种类数。下面介绍算法中包含的3种算法(下记为)。

以下是的基本框架：

1. 随机选取两个分区和作为起始分区；
2. 若满足以下三个条件：1、点权和不小于下界；2、点权和不大于上界；3、两个分区不同且适合进行下文提到的“优化”操作，则进行下一步，否则直接跳到步骤4；
3. 逐个选取和中的若干个顶点，若将这些点交换位置后，点权和与点权和不越界，且有效边权和增加，则将这些点交换位置（不妨将这个交换的过程称作一次“优化”），更新状态矩阵。

在这里停顿一下，这里的状态矩阵是一个关键点。

该矩阵记录两个分区之间是否适合进行“优化”操作。以上文为例，在和两个分区之间进行“优化”操作后，就标记为不适合进行“优化”操作（若为使用swap算子的还需标记，详见下文）。同时，由于两个分区都发生了变化，矩阵中其它有关两个分区的部分都更新为适合进行“优化”操作。这样一来，一方面，优化操作便集中在适合进行“优化”操作的两个分区中，减少了重复计算，另一方面，多次迭代的方式也尽可能使分区得到优化。

回到刚才的过程中。

对于：

1. 在步骤3中的点的选取遍历结束后或当步骤2中两个区间不满足条件时，变为（若大于分区数则变为1），重复步骤2的过程，直至由遍历到为止。
2. 在步骤4中的分区遍历结束后，变为（若大于分区数则变为1），重复步骤2的过程，直至由遍历到为止。
3. 若以上过程中有过任何一次“优化”操作，则回到步骤1再次重新随机选取两个分区和作为起始分区，否则优化结束；

对于：

1. 若步骤3进行了 “优化”操作，则优化结束并返回值1；否则，在步骤3中的点的选取遍历结束后，变为（若大于分区数则变为1），重复步骤2的过程，直至由遍历到为止。
2. 在步骤4中的分区遍历结束后，变为（若大于分区数则变为1），重复步骤2的过程，直至由遍历到为止。
3. 若以上过程中没有进行 “优化”操作，则优化结束并返回值0；

3种不同算法的区别在于选取和中的顶点的方式不同：

第一种，只在中选取1个顶点，即将这个顶点移动到中；

第二种，在和中各选取1个顶点，即将这个两顶点交换；

第三种，在中选取2个顶点，在中选取1个顶点，将二者交换；

对于，基本框架如下：

1、对解进行优化；

2、对解进行优化；

3、若对解进行优化时返回值1，即解仍可被优化，则返回步骤1，否则优化结束；

而就像是的加强版，因为它用上了全部三种优化，基本框架如下：

1. ；
2. 对解进行优化；
3. 若对解进行优化时返回值1，即解仍可被优化，则返回步骤1，否则优化结束；

显然，耗时较多得多，因此在整个算法中只进行一次优化，而视时间限制进行若干次优化。

2.3 扰动

扰动强度最小值为，最大值为 (顶点数除以分区数)，初始值为最小值。

回顾主算法步骤5：

"综合 与 ， 与 的有效边权和 之比以及距离函数计算值，结合参数 计算优化效果，若 更优则将 作为当前解 ，并进而比较 和 的有效边权和 ，若 的更大则将 作为当前最优解 "

其中包含三种情况，并分别对应的三种调整方式：

1. 优于当前解，且的有效边权和比的大：调整为最小值1；
2. 优于当前解，但的有效边权和比的小：的几率调整为最小值1，的几率调整为；
3. 不优于当前解：调整为，若大于最大值则调整为最小值1；

扰动过程为：随机选取两个不同分区的顶点，若交换后两分区点权和均不越界，则交换两顶点，共交换次。

2.4 距离函数

回顾主算法步骤5：

"综合 与 ， 与 的有效边权和 之比以及距离函数计算值，结合参数 计算优化效果，若 更优则将 作为当前解 "

综合的方法如下：

记与有效边权和之比为，对于解和的距离函数的返回值为；

记与有效边权和之比为，对于解和的距离函数的返回值为；

满足以下任意一条则表示更优：

1. ；
2. ；

距离函数如下:

对于两个解和，引入两个量、。其中，为原本位于同一分区的两个顶点变为位于不同分区的情况数目与原本位于不同分区的两个顶点变为位于同一分区的情况数目之和。为两个顶点原本位于同一分区或在中位于同一分区的情况数目之和（同时满足算一次）。这句话确实很长但是真心不好改成短句，希望同学们能够耐心理解。

引入变量，即为距离函数返回值。

对该距离函数的完整论述可参考文末给出的三篇论文。

最后提一下，参数和都是经过数十个样本测试后调整出的数值，默认，。

以上即为的全部内容，你看明白了吗？

源代码链接（或点击阅读原文）

⬇️

https://leria-info.univ-angers.fr/~jinkao.hao/NDVNS.html

参考文献：

原论文：

[1] "Neighborhood decomposition-driven variable neighborhood search for capacitated clustering", Xiangjing Lai, Jin-Kao Hao, Zhang-Hua Fu, Dong Yue, Computers & Operations Research, Volume 134, October 2021.

距离函数：

[2] "Solving the maximally diverse grouping problem by skewed general variable neighborhood search", Jack Brimberg, Nenad Mladenović, Dragan Urošević, Information Sciences, Volume 295, February 2015, Pages 650-675.

[3] "Partition-distance: A problem and class of perfect graphs arising in clustering", Dan Gusfield, Information Processing Letters, Volume 82, Issue 3, May 2002, Pages 159-164.

[4] "An efficient algorithm for computing the distance between close partitions", Daniel Cosmin Porumbel, Jin Kao Hao, Pascale Kuntz, Discrete Applied Mathematics, Volume 159, Issue 1, January 2011, Pages 53-59.

-The End-

文案&代码&排版：吕其乐（华中科技大学管理学院本科一年级）

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

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