干货|变邻域搜索(VNS)算法求解Max-Mean Dispersion Problem（附代码及详细注释）
- 2019 年 10 月 8 日
- 筆記
Part
1
Max-Mean Dispersion Problem
对MDP和MMDP还是一头雾水？不要着急，今天就和小编一起解决这三个问题—
什么是MDP和MMDP?
它们有什么用?
怎样解决这两个问题?
1.1
Maximum Diversity Problem
要讨论Max-Mean Dispersion Problem,就要首先了解Maximum Diversity Problem (MDP) 。
MDP是一种用来度量元素中差异的问题，通俗来讲，就是要从一个集合中选择一个子集合，使得子集合中的元素差异最大化。
举个例子，对于生态系统的平衡问题，生态系统的存续与否就在于多样性。假如我们拥有任意两个生物之间的差异值，通过找到具有最大多样性的子集，我们就能方便地建立起可行的生态系统。
又比如说在农业育种中，往往需要在子代中挑选出具有理想多样性的种群，问题就又归结到了在子代中找到最大差异化个体的问题上了。
文章开头的表情包，其实质也是一个MDP。在风险投资中，往往要通过找到差异最大的几个市场来进行投资，避免牵一发而动全身的情况。
例子都是多样性在生活中发挥作用的表现，那么我们应该如何最大化这种多样性呢？这就是MDP要解决的问题了。
更多的应用见下图：
1.2
MDP的数学描述
考虑一个元素的集合
,索引集
。每个元素包含着r个属性，我们可以将一个元素用向量
表示。我们的目标就是从n个元素中选择m个元素，最大化所选择的元素的多样性。为了度量元素之间的多样性，我们定义值
来代表元素i,j之间的距离。这个距离有多种算法，如欧几里得距离，曼哈顿距离等。在这里我们使用最为常用的欧几里得距离。
由此，我们可以定义一组元素的多样性为：
根据这些约定，我们可以通过引入0-1变量的方法，将问题表达为：
1.3
Max-Mean Dispersion Problem
有了对MDP问题的认识，下面我们来看看MMDP。
和MDP要最大化子集的多样性不同，MMDP问题需要最大化子集多样性的平均值。在这里值得注意的一点是，MDP中子集的大小是固定的，是问题给出的。而MMDP中，子集数量的多少需要自己确定。当子集数量确定后，MMDP就转化为了MDP。
还是有些云里雾里？更通俗的讲，假如说问题是在10个人中挑出差异最大的5个人，这自然是一个MDP，但假如说问题是在10个人中挑出几个人，使这几个人的差异最大呢？这时自然不能考虑差异值的和，而是需要考虑差异值的和的平均值，即MMDP了。
我们用一个简单的例子来具体解释MDP和MMDP：
假设给出4个元素A，B，C，D，给出4个元素的距离矩阵如下图：
假如要求是从4个元素中选择3个元素，使它们之间的差异最大，这就是一个MDP。假设选择元素A，B，C，则目标函数的值为1+2+4 = 7.
假如要求是从4个元素中选择任意个元素，使他们之间的平均差异最大，这就是一个MMDP。同样假设选择元素A，B，C，目标函数的值就变为（1+2+4）/ 3 = 7/3。
Part
2
变邻域搜索(VNS)算法再回顾
在之前的推文干货 | 变邻域搜索算法(Variable Neighborhood Search,VNS)超详细一看就懂中，已经对VNS算法有了详细的介绍。
在干货 | 变邻域搜索算法(VNS)求解TSP（附C++详细代码及注释）
中，给出了VNS算法解决问题的实例。
在这里，我们简要地复习下VNS算法的基本内容，详细内容参见以上推文。
2.1
VNS算法介绍
VNS算法的基本思想是在搜索过程中系统地改变邻域结构集来拓展搜索过程，获得局部最优解，再基于此局部最优解重新系统地改变邻域结构集拓展搜索范围找到另一个局部最优解的过程。基本的流程如下图：
正如Hansen在论文Variable neighborhood search Principles and applications一文中提到的，VNS算法本质上还是一种跳出局部最优解的算法。和禁忌搜索与模拟退火算法不同，其算法并不遵循一定的"轨迹"，而是通过shaking动作来跳出当前局部最优解，在不同的邻域中找到其他局部最优解，当且仅当该解优于当前解时进行移动。假如邻域结构可以覆盖整个可行解集，则算法可以找到全局最优解。
Part
3
具体算法介绍
3.1
初始解生成
对于初始解，我们使用贪心的方法来构造。最开始将所有元素都视为已选择，计算出每一元素被移除后，该解目标函数值的提高，不断地移除能提高最多的元素，不断循环，直到不再有元素被移除时目标函数值提高为止。
3.2
邻域动作
我们定义三种邻域动作：
Exchange:从被选择的元素的集合中随机选择元素i，从不被选择的元素的集合中随机选择元素j，交换i,j。
Insert:从不被选择的元素中随机选择元素i，将其从不被选择的元素的集合中移除，并加入到被选择的元素的集合中。
Remove: 从被选择的元素的集合中随机选择元素i，将其从被选择的元素的集合中移除，并加入到不被选择的元素的集合中。
3.3
具体流程
shake函数：我们定义shake函数接受参数k，随机从选择的元素的集合和不被选择的元素的集合中选择k个元素，并交换他们。
通过我们在3.2中定义的邻域动作进行进行搜索，具体流程如下图：
Part
4
代码分享
这里我们分享两份代码，第一份是某位西班牙大佬分享的代码，另一种是小编在他的基础上改编而来的代码，这里展示的是小编实现的版本。在https://github.com/alexfp95/Max-Mean-Dispersion-Problem/tree/master/src中，可以获得西班牙大佬写的版本。
具体实现如下：
import java.io.*; import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; import java.util.Random; class Solution //解的类 { ArrayList<Integer> select_set = new ArrayList<>();//存放点的集合 ArrayList<Integer> unselect_set = new ArrayList<>();//没选择的点 double value; double getValue() { double ans = 0; ArrayList<Integer> new_set = new ArrayList<>(); new_set.addAll(this.select_set); while(new_set.size()!=0) { int i = new_set.get(0); new_set.remove(0); for(Integer j:new_set) { ans+=main.cost_mariax[i][j]; } } ans = ans / this.select_set.size(); return ans; // 返回目标函数值 } double improve_value(int i)//计算返回将这个点转到另一个集合后，value值的改变 { double ans; double last_ans = this.value; Integer I = Integer.valueOf(i); Solution new_solution = new Solution(); new_solution.select_set.addAll(this.select_set); if(this.select_set.contains(i)) { new_solution.select_set.remove(I); new_solution.unselect_set.add(I); ans = new_solution.getValue() - last_ans; } else { new_solution.select_set.remove(I); new_solution.unselect_set.add(I); ans = new_solution.getValue() - last_ans; } return ans; } } abstract class Strategy//策略类，存放算法 { static Solution ini_solution()//初始化一个解，采用贪婪的思想，最开始所有解都在select_set中，随后逐渐减少，每次计算去除点的价值，由大到小，不再有改进 { Solution solution = new Solution(); for(int i=1;i<=main.CODE_NUMBER;i++) solution.select_set.add(i);//开始时所有解都在select_set中 solution.value = solution.getValue();//获得当前解 double best = 0; int id = 0; while(true) { best = 0; for (int i : solution.select_set) { //System.out.println(solution.improve_value(i)); if (best < solution.improve_value(i)) { best = solution.improve_value(i); id = i; } //System.out.println(solution.select_set.size()); } if(best == 0) break; solution.select_set.remove(Integer.valueOf(id));//不断改进 solution.unselect_set.add(Integer.valueOf(id)); solution.value = solution.getValue(); // System.out.println(solution.value); } solution.value = solution.getValue(); return solution; } static Solution exchange(Solution solution)//第一种邻域算子：交换i,j st i在solution中，j不在 { Random r = new Random(); int i = r.nextInt(solution.select_set.size()-1); int j = r.nextInt(solution.unselect_set.size()-1);//在i,j中随机找两点; Integer mid_one = solution.select_set.get(i); Integer mid_two = solution.unselect_set.get(j); solution.select_set.remove(i); solution.unselect_set.remove(j); solution.unselect_set.add(Integer.valueOf(mid_one)); solution.select_set.add(Integer.valueOf(mid_two)); solution.value = solution.getValue(); return solution; } static Solution insert(Solution solution)//第二种邻域算子：将j从没选择的集合中加入到solution中 { Random r = new Random(); int j = r.nextInt(solution.unselect_set.size()-1); int mid = solution.unselect_set.get(j); solution.unselect_set.remove(j); solution.select_set.add(Integer.valueOf(mid)); solution.value = solution.getValue(); return solution; } static Solution remove(Solution solution)//第三种邻域算子：将j从选择的集合中删除 { Random r = new Random(); int j = r.nextInt(solution.select_set.size()-1); int mid = solution.select_set.get(j); solution.unselect_set.add(Integer.valueOf(mid)); solution.value = solution.getValue(); return solution; } public static Solution shake(Solution solution,int k)//shake动作，跳出局部最优 { for(int i=1;i<=k;i++) { solution = exchange(solution); } return solution; } public static Solution Local_Search(Solution solution)//邻域搜索，获得局部最优 { for(int i=1;i<=100;i++) { Solution new_solution = new Solution(); new_solution.select_set.addAll(solution.select_set); new_solution.unselect_set.addAll(solution.unselect_set); new_solution.value = solution.value; if(solution.unselect_set.size()==0) { new_solution = Strategy.remove(solution); } else if(solution.select_set.size()==0) { new_solution = Strategy.remove(solution); } else { Random r = new Random(); double t = r.nextDouble(); if(t>0.6) { new_solution = Strategy.exchange(new_solution); } else if(t>0.3) { new_solution = Strategy.remove(new_solution); } else { new_solution = Strategy.insert(new_solution); } } if(solution.value<new_solution.value) { solution = new_solution; System.out.println(new_solution.value); } } return solution; } public static Solution V_N_Search(Solution solution)//变邻域搜索 { int k = 1; { while(k<=solution.select_set.size())//按照shaking的定义进行shake，不断搜索直到k==被选择的集合的元素个数 { System.out.println(k); Solution new_solution = new Solution(); new_solution.select_set.addAll(solution.select_set); new_solution.unselect_set.addAll(solution.unselect_set); new_solution.value = solution.value; new_solution = shake(new_solution,k); new_solution = Local_Search(new_solution); if(solution.value<new_solution.value) { solution = new_solution; k=1; } else{ k++; } System.out.println(solution.value); } } return solution; } } public class main { static double[][] cost_mariax;//距离矩阵 static int CODE_NUMBER; public static void main(String[] args) { CODE_NUMBER = 150; cost_mariax = new double[CODE_NUMBER+1][CODE_NUMBER+1];//初始化 for(int i=1;i<=CODE_NUMBER;i++) try { FileReader fr = new FileReader("MDPI1_150.txt");//读入数据 BufferedReader br = new BufferedReader(fr); String line = " "; while(true) { line = br.readLine(); if(line.equals("end"))break; String data[] = line.split("t"); cost_mariax[Integer.valueOf(data[0])][Integer.valueOf(data[1])] = Double.valueOf(data[2]); cost_mariax[Integer.valueOf(data[1])][Integer.valueOf(data[0])] = Double.valueOf(data[2]); } } catch(IOException e) { e.printStackTrace(); } for(int i=1;i<=CODE_NUMBER;i++) //初始化 for(int j=1;j<=CODE_NUMBER;j++) { if(i == j) { cost_mariax[i][j] = 0; continue; } } Solution solution = Strategy.ini_solution(); // 初始化解; solution = Strategy.V_N_Search(solution);//VNS搜索 System.out.println(solution.value); System.out.println("当前解为"+solution.value); System.out.println("被选择的点集的大小为" + solution.select_set.size()); } }
结果如图：
欲下载本文相关代码，测试样例，相关论文，请移步留言区
参考文献：
[1]Martí, Rafael, and Fernando Sandoya. “GRASP and Path Relinking for the Equitable Dispersion Problem.” Computers & Operations Research 40.12 (2013): 3091–3099. Crossref. Web.
[2] Hansen, Pierre , and N. Mladenovi . "Variable neighborhood search: Principles and applications." European Journal of Operational Research 130.3(2001):449-467.
[3]Hansen, Pierre, N. Mladenović, and D. Perez-Britos. "Variable Neighborhood Decomposition Search." Journal of Heuristics 7.4(2001):335-350.
-The End-
