专栏首页数据魔术师代码 | 自适应大邻域搜索系列之(4) - Solution定义和管理的代码实现解析

代码 | 自适应大邻域搜索系列之(4) - Solution定义和管理的代码实现解析

写在前面

上一篇文章代码 | 自适应大邻域搜索系列之(3) - Destroy和Repair方法代码实现解析讲解了destroy和repair方法的具体实现代码,好多读者都在喊酸爽和得劲儿……

今天这篇就讲点简单的,关于solution的定义和管理的代码实现,让大家回回神吧……哈哈。

01 总体概述

总所周知的是,每一个算法的最终目标都是求解出一个合理的满足心意的solution。因此对solution的定义和管理基本是每个算法都要涉及的。

在本ALNS代码中呢,也对solution进行了一定的抽象和规范化,提供了一些标准化的接口,同样需要在具体使用中去重写这些接口。

关于solution的处理方式总得来说也由两个模块组成:

  • 关于solution的定义:ISolution抽象类
  • 关于bestSolution的管理: IBestSolutionManager(抽象类)、SimpleBestSolutionManager(派生类)

下面也对其一一进行讲解。

02 ISolution抽象类

该类只是对solution的进行一定的抽象定义,并没有具体实现各个接口,需要coder在后续的使用中重写编写这些接口。

它应该具备的功能看代码就能理解了,注释也写得很详细。

主要包括几个功能:获取目标值、获取目标惩罚值、解是否可行、获取每个solution独一无二的hash值等。 具体代码也很简单:

 1
 2class ISolution
 3{
 4public:
 5    virtual ~ISolution(){};
 6    //! A getter for the value of the objective function.
 7    //! \return the value of the objective function of this solution.
 8    virtual double getObjectiveValue()=0;
 9    //! \return a penalized version of the objective value if the solution
10    //! is infeasible.
11    virtual double getPenalizedObjectiveValue()=0;
12    //! A getter for the feasibility of the current solution.
13    //! \return true if the solution is feasible, false otherwise.
14    virtual bool isFeasible()=0;
15    //! A comparator.
16    //! \return true if this solution is "better" than the solution it is compared to.
17    virtual bool operator<(ISolution&)=0;
18    //! Compute the "distance" between solution.
19    //! This feature can be used as part of the ALNS to favor the
20    //! diversification process. If you do not plan to use this feature
21    //! just implement a method returning 0.
22    virtual int distance(ISolution&)=0;
23    //! This method create a copy of the solution.
24    virtual ISolution* getCopy()=0;
25    //! Compute a hash key of the solution.
26    virtual long long getHash()=0;
27};

03 bestSolution的管理

关于bestSolution的管理有两个类搞定,它们的关系如下:

3.1 IBestSolutionManager

IBestSolutionManager其实也是一个抽象类,它也只是起到提供接口的作用。其中:

isNewBestSolution(ISolution& sol)是判断sol是不是新的最优解。

reloadBestSolution(ISolution* currSol, ALNS_Iteration_Status& status)则根据需要判断是否要将已知的最优解作为当前解。

 1class IBestSolutionManager
 2{
 3public:
 4    //! This method evaluate if a solution is a new best solution, and adds it to the
 5    //! best solution pool in this case.
 6    //! \param sol the solution to be tested.
 7    //! \return true if the solution is a new best solution, false otherwise.
 8    virtual bool isNewBestSolution(ISolution& sol)=0;
 9
10    //! Return a pointer to a best solution.
11    virtual std::list<ISolution*>::iterator begin()=0;
12
13    //! Return a pointer to a best solution.
14    virtual std::list<ISolution*>::iterator end()=0;
15
16    //! This function take care of reloading the best known
17    //! solution, as the current solution, if needed.
18    //! \param currSol a pointer to the current solution.
19    //! \param status the status of the current iteration.
20    //! \return a pointer to the current solution.
21    virtual ISolution* reloadBestSolution(ISolution* currSol, ALNS_Iteration_Status& status)=0;
22};

3.2 SimpleBestSolutionManager

SimpleBestSolutionManager是继承于IBestSolutionManager的。

值得注意的是,它管理的不止是一个BestSolution,而是多个BestSolution的集合(这些BestSolution目标值相同,但是结构不同)。

下面是.h文件的代码:

 1class SimpleBestSolutionManager: public IBestSolutionManager {
 2public:
 3    SimpleBestSolutionManager(ALNS_Parameters& param);
 4
 5    virtual ~SimpleBestSolutionManager();
 6
 7    virtual bool isNewBestSolution(ISolution& sol);
 8
 9    //! Return a pointer to a best solution.
10    std::list<ISolution*>::iterator begin(){return bestSols.begin();};
11
12    //! Return a pointer to a best solution.
13    std::list<ISolution*>::iterator end(){return bestSols.end();};
14
15    //! This function take care of reloading the best known
16    //! solution, as the current solution, if needed.
17    //! \param currSol a pointer to the current solution.
18    //! \param status the status of the current iteration.
19    //! \return a pointer to the current solution.
20    virtual ISolution* reloadBestSolution(ISolution* currSol, ALNS_Iteration_Status& status);
21
22    //! Simple getter.
23    std::list<ISolution*>& getBestSols(){return bestSols;};
24private:
25    std::list<ISolution*> bestSols;
26
27    ALNS_Parameters* parameters;
28
29};

再回过头来看看.cpp文件的实现代码,也很简单,讲讲两个函数的实现方式就好了。

isNewBestSolution(ISolution& sol)做的可不只是简单判断这么简单:

如果sol和最优解集合中的某个相同,那么返回false。 如果sol的目标值>最优解集合中的解的目标值,返回false。 如果sol的目标值<最优解集合中的某个解的目标值,那么将该最优解从集合中移除。 最后如果没有返回false,将sol加入最优解集合。

reloadBestSolution(ISolution* currSol, ALNS_Iteration_Status& status)根据status的状态,返回最优解集合中最后一个解或者返回当前解。

 1bool SimpleBestSolutionManager::isNewBestSolution(ISolution& sol)
 2{
 3    for(list<ISolution*>::iterator it = bestSols.begin(); it != bestSols.end(); it++)
 4    {
 5        ISolution& currentSol = *(*it);
 6        if(currentSol<sol)
 7        {
 8            return false;
 9        }
10        else if(sol<currentSol)
11        {
12            delete *it;
13            it = bestSols.erase(it);
14            if(it == bestSols.end())
15            {
16                break;
17            }
18        }
19        else if(currentSol.getHash() == sol.getHash())
20        {
21            return false;
22        }
23    }
24    ISolution* copy = sol.getCopy();
25    bestSols.push_back(copy);
26    return true;
27}
28
29ISolution* SimpleBestSolutionManager::reloadBestSolution(ISolution* currSol, ALNS_Iteration_Status& status)
30{
31    if(status.getNbIterationWithoutImprovementSinceLastReload() > 0 &&
32       ((status.getNbIterationWithoutImprovementSinceLastReload() % parameters->getReloadFrequency()) == 0))
33    {
34        status.setNbIterationWithoutImprovementSinceLastReload(0);
35        delete currSol;
36        return bestSols.back()->getCopy();
37    }
38    else
39    {
40        return currSol;
41    }
42}

04 小结

好了,以上就是今天的内容,是不是特别简单呢?相信在克服之前两篇文章的读者来说,后面都是一马平川、一帆风顺了。哈哈。

---The End---

文案 && 编辑:邓发珩

审稿:庄浩城

指导老师: 秦时明岳(华中科技大学管理学院)

本文分享自微信公众号 - 数据魔术师(data-magician),作者:邓发珩

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

原始发表时间:2019-03-11

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

我来说两句

0 条评论
登录 后参与评论

相关文章

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

    要讨论Max-Mean Dispersion Problem,就要首先了解Maximum Diversity Problem (MDP) 。

    用户1621951
  • 从小白到年薪10万+,优秀的数据分析能力如何速成?

    用户1621951
  • 干货|自适应大邻域搜索(ALNS)算法求解带时间窗的车辆路径规划问题(附JAVA代码)

    有关ALNS概念的介绍,公众号内已经有相关内容了,这里稍提一下,有疑惑的同学可以参考往期内容:

    用户1621951
  • 代码 | 自适应大邻域搜索系列之(4) - Solution定义和管理的代码实现解析

    上一篇讲解了destroy和repair方法的具体实现代码,好多读者都在喊酸爽和得劲儿……今天这篇就讲点简单的,关于solution的定义和管理的代码实现,让大...

    短短的路走走停停
  • HDU 2586 How far away ?

    Problem Description There are n houses in the village and some bidirectional r...

    attack
  • CodeFores 665D Simple Subset(贪心)

    D. Simple Subset time limit per test 1 second memory limit per test 256 me...

    ShenduCC
  • BZOJ4364: [IOI2014]wall砖墙(线段树)

    但实际上因为这题只需要输出最后的操作序列,那么我们只维护最大最小值的覆盖标记即可。

    attack
  • (int),Int32.Parse,Convert.ToInt3…

    (int)是一种被称为强制转换的显示转换。源变量和目标变量必须是兼容的(必须都是int类型的)。并且有丢失数据的风险。因为目标变量的类型大小小于源变量。

    Dabelv
  • BZOJ3083: 遥远的国度(树链剖分)

    以下图片来自(https://blog.csdn.net/lcomyn/article/details/45718295)

    attack
  • BZOJ2683: 简单题(cdq分治 树状数组)

    你有一个N*N的棋盘,每个格子内有一个整数,初始时的时候全部为0,现在需要维护两种操作:

    attack

扫码关注云+社区

领取腾讯云代金券