专栏首页程序猿声干货|变邻域搜索(VNS)算法求解Max-Mean Dispersion Problem(附代码及详细注释)

干货|变邻域搜索(VNS)算法求解Max-Mean Dispersion Problem(附代码及详细注释)

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-

本文分享自微信公众号 - 程序猿声(ProgramDream)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-09-25

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Creator MVVM方案—为人生节省时间!

    核心脚本文件存放在 assets\Script\modelView 路径,要使用必须全部引入

    张晓衡
  • 英雄之舞—凌波微步

    本文主要介绍使用async.js优雅地控制Cocos异步动画,文中有较多的代码与gif演示,为了获得更佳体验建议在电脑上阅读,如果当下没有环境,建议看代码时用横...

    张晓衡
  • java之Lambda表达式

    上面的一段代码和之前的除了参数传递方式不同,其他都一样,第一段代码用匿名内部类的方式实现参数传递,第二段代码用Lambda表达式实现参数传递。

    用代码征服天下
  • python接口自动化(二十八)--html测试 报告——下(详解)

      五一小长假已经结束了,想必大家都吃饱喝足玩好了,那就继续学习吧。一天不学习,自己知道;两天不学习,对手知道;三天不学习,大家知道;一周不学习,智商输给猪。好...

    北京-宏哥
  • java多线程超详细总结

    第一步:定义Thread类的之类,并重写run方法,该run方法的方法体就代表了线程需要执行的任务

    用代码征服天下
  • java之集合那些事

    1、Hash Set和 TreeSet是Set的两个典型实现,到底如何选择 Hash Set和 Tree Set呢? HashSet的性能总是比 TreeSet...

    用代码征服天下
  • async.js在Cocos Creator中的应用

    有网友在公众号上提问题,使用async.js在微信小游戏环境报错,由于Shawn这段时间有点懒癌发作,没有即时回复留言,已经超过48小时回复不了,在此表示歉意,...

    张晓衡
  • java泛型

    集合有一个特点——当你把对象丢进集合中,集合就会“忘记”这个对象的类型,而把它当做Object类型来处理。这样当程序员不小心将不同类型的数据丢进同一个集合中时...

    用代码征服天下
  • GLSL ES 语言—变量数值类型

    GLSL ES 要求你具体指明变量的数据类型: <类型> <变量名> 如 vec4 a_position。 在进行赋值操作(=)时,等号左右两侧的数据类型必须一...

    张晓衡
  • python接口自动化(二十九)--html测试报告通过邮件发出去——上(详解)

      前边几篇,已经教小伙伴们掌握了如何生成HTML的测试报告,那么生成测试报告,我们也不能放在那里不管了,这样即使你报告在漂亮,领导也看不到。因此如果想向领导汇...

    北京-宏哥

扫码关注云+社区

领取腾讯云代金券