乾貨|變鄰域搜索(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-