Max-Mean Dispersion Problem
image
对MDP和MMDP还是一头雾水？不要着急，今天就和小编一起解决这三个问题—
什么是MDP和MMDP?
它们有什么用?
怎样解决这两个问题?
Maximum Diversity Problem
要讨论Max-Mean Dispersion Problem,就要首先了解** Maximum Diversity Problem (MDP) **。
MDP是一种用来度量元素中差异的问题，通俗来讲，就是要从一个集合中选择一个子集合，使得子集合中的元素差异最大化。
举个例子，对于生态系统的平衡问题，生态系统的存续与否就在于多样性。假如我们拥有任意两个生物之间的差异值，通过找到具有最大多样性的子集，我们就能方便地建立起可行的生态系统。
又比如说在农业育种中，往往需要在子代中挑选出具有理想多样性的种群，问题就又归结到了在子代中找到最大差异化个体的问题上了。
文章开头的表情包，其实质也是一个MDP。在风险投资中，往往要通过找到差异最大的几个市场来进行投资，避免牵一发而动全身的情况。
例子都是多样性在生活中发挥作用的表现，那么我们应该如何最大化这种多样性呢？这就是MDP要解决的问题了。
更多的应用见下图：
image
1.2
MDP的数学描述 考虑一个元素的集合
image
,索引集
image
。每个元素包含着r个属性，我们可以将一个元素用向量
image
表示。我们的目标就是从n个元素中选择m个元素，最大化所选择的元素的多样性。为了度量元素之间的多样性，我们定义值
image
来代表元素i,j之间的距离。这个距离有多种算法，如欧几里得距离，曼哈顿距离等。在这里我们使用最为常用的欧几里得距离。
image
由此，我们可以定义一组元素的多样性为：
image
根据这些约定，我们可以通过引入0-1变量的方法，将问题表达为：
image
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个元素的距离矩阵如下图：
image
假如要求是从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算法的基本思想是在搜索过程中系统地改变邻域结构集来拓展搜索过程，获得局部最优解，再基于此局部最优解重新系统地改变邻域结构集拓展搜索范围找到另一个局部最优解的过程。基本的流程如下图：
image
正如Hansen在论文Variable neighborhood search Principles and applications一文中提到的，VNS算法本质上还是一种跳出局部最优解的算法。和禁忌搜索与模拟退火算法不同，其算法并不遵循一定的"轨迹"，而是通过shaking动作来跳出当前局部最优解，在不同的邻域中找到其他局部最优解，当且仅当该解优于当前解时进行移动。假如邻域结构可以覆盖整个可行解集，则算法可以找到全局最优解。
具体算法介绍
初始解生成
对于初始解，我们使用贪心的方法来构造。最开始将所有元素都视为已选择，计算出每一元素被移除后，该解目标函数值的提高，不断地移除能提高最多的元素，不断循环，直到不再有元素被移除时目标函数值提高为止。
3.2
邻域动作
我们定义三种邻域动作：
Exchange:从被选择的元素的集合中随机选择元素i，从不被选择的元素的集合中随机选择元素j，交换i,j。
Insert:从不被选择的元素中随机选择元素i，将其从不被选择的元素的集合中移除，并加入到被选择的元素的集合中。
Remove: 从被选择的元素的集合中随机选择元素i，将其从被选择的元素的集合中移除，并加入到不被选择的元素的集合中。
3.3
具体流程
shake函数：我们定义shake函数接受参数k，随机从选择的元素的集合和不被选择的元素的集合中选择k个元素，并交换他们。
通过我们在3.2中定义的邻域动作进行进行搜索，具体流程如下图：
image
代码分享
这里我们分享两份代码，第一份是某位西班牙大佬分享的代码，另一种是小编在他的基础上改编而来的代码，这里展示的是小编实现的版本。在https://github.com/alexfp95/Max-Mean-Dispersion-Problem/tree/master/src中，可以获得西班牙大佬写的版本。
结果如图：
image
参考文献：
[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.
有问题欢迎交流：作者邮箱1642940680@qq.com
网友评论