专栏首页数据魔术师代码 | 自适应大邻域搜索系列之(7) - 局部搜索LocalSearch的代码解析

代码 | 自适应大邻域搜索系列之(7) - 局部搜索LocalSearch的代码解析

写在前面

好了小伙伴们我们又见面了,咳咳没错还是我。

不知道你萌接连被

这么多篇代码文章刷屏是什么感受,不过,酸爽归酸爽。

今天咱们依然讲代码哈~不过今天讲的依然很简单,关于局部搜索LocalSearch的代码。

01 总体概述

其实,LocalSearch在本算法中不是必须使用的,用户可以根据需要来选择是否启用这个功能。但是一般情况下,有了LocalSearch以后效果会好一点。

而且本着服务读者的态度(我可以不用,但是小编你不能不讲),就讲讲这个模块吧。和之前讲的几个模块差不多,具体代码也是分成两个部分进行实现的:

  • LocalSearch的定义
  • LocalSearch的管理

LocalSearch的定义用了一个很简单的抽象类ILocalSearch用来提供接口的、而LocalSearch的管理用了ILocalSearchManager、SimpleLocalSearchManager两个类。

其中ILocalSearchManager也是抽象类,而SimpleLocalSearchManager则是继承于ILocalSearchManager并实现了相应的接口。下面对他们进行一一讲解。

02 ILocalSearch

其实这个类只提供了两个纯虚函数作为接口,也是简单得不能再简单了。

performLocalSearch用以执行一次LocalSearch操作。

getName返回该LocalSearch的名字。

 1class ILocalSearch
 2{
 3public:
 4    //! Perform a local search on the solution.
 5    //! \return true if the solution is improved.
 6    virtual bool performLocalSearch(ISolution& sol)=0;
 7
 8    //! \return the name of the local search operator.
 9    virtual std::string getName()=0;
10};

03 ILocalSearchManager

照例,其中ILocalSearchManager和SimpleLocalSearchManager的关系如下:

这个抽象类也非常简单,只有两个接口。

useLocalSearch用以判断是否要使用LocalSearch,而startSignal开始信号,在启动整个算法的时候起到协调作用。

 1class ILocalSearchManager
 2{
 3public:
 4
 5    //! \param sol the solution to be improved.
 6    //! \param status the status of the alns iteration.
 7    //! \return true if the solution has been improved.
 8    virtual bool useLocalSearch(ISolution& sol, ALNS_Iteration_Status& status)=0;
 9
10    //! Indicate that the optimization process starts.
11    virtual void startSignal()=0;
12};

04 SimpleLocalSearchManager

SimpleLocalSearchManager对LocalSearch进行了一定的扩充,加入了addLocalSearchOperator的操作,用以添加LocalSearch。

值得注意的是,该LocalSearchManager管理的可以是多个LocalSearch。

 1class SimpleLocalSearchManager: public ILocalSearchManager {
 2public:
 3
 4    SimpleLocalSearchManager(ALNS_Parameters& parameters){param = &parameters;};
 5
 6    virtual ~SimpleLocalSearchManager(){};
 7
 8    //! \param sol the solution to be improved.
 9    //! \param status the status of the alns iteration.
10    //! \return true if the solution has been improved.
11    virtual bool useLocalSearch(ISolution& sol, ALNS_Iteration_Status& status);
12
13    //! Add a local search operator to the manager.
14    void addLocalSearchOperator(ILocalSearch& ls);
15
16
17    virtual void startSignal(){};
18private:
19    //! A vector containing the local search operators managed by the current instance.
20    std::vector<ILocalSearch*> localSearchOperators;
21
22    //! Parameters of the ALNS.
23    ALNS_Parameters* param;
24};

useLocalSearch和addLocalSearchOperator具体实现代码如下,相信对迭代搜索了解的同学,对下面的过程那是熟悉得不能再熟悉了。

特别是improvement 变量的复位操作(如果有改进,那么接着搜索下去,直到最大迭代次数为止,如果没有改进就不搜索了。)addLocalSearchOperator就不需要讲解了吧~

 1bool SimpleLocalSearchManager::useLocalSearch(ISolution& sol, ALNS_Iteration_Status& status)
 2{
 3    if(status.getNewBestSolution()!=ALNS_Iteration_Status::TRUE
 4        || status.getAcceptedAsCurrentSolution()!=ALNS_Iteration_Status::UNKNOWN)
 5    {
 6        return false;
 7    }
 8    else
 9    {
10        status.setLocalSearchUsed(ALNS_Iteration_Status::TRUE);
11        bool improvement;
12        do
13        {
14            improvement = false;
15            for(size_t i = 0; i < localSearchOperators.size(); i++)
16            {
17                improvement = localSearchOperators[i]->performLocalSearch(sol)||improvement;
18            }
19        }while(improvement);
20        if(improvement)
21        {
22            status.setImproveByLocalSearch(ALNS_Iteration_Status::TRUE);
23            return true;
24        }
25        else
26        {
27            status.setImproveByLocalSearch(ALNS_Iteration_Status::FALSE);
28            return false;
29        }
30    }
31}
32
33void SimpleLocalSearchManager::addLocalSearchOperator(ILocalSearch& ls)
34{
35    //TODO find out why the set.find() == set.end() does not work.
36    bool ok = true;
37    for(size_t i=0; i< param->getForbidenLsOperators().size() && ok; i++)
38    {
39        if(param->getForbidenLsOperators()[i] == ls.getName())
40        {
41            std::cout << "NO " << ls.getName() << std::endl;
42            ok = false;
43        }
44    }
45    if(ok)
46    {
47        localSearchOperators.push_back(&ls);
48    }
49
50}

05 小结

差不多到此整个ALNS框架已经讲得差不多了,相信大家在看了这么多代码以后,心里早已经有了一个数了。

下面几篇推文将为大家展现一个实例,怎么在该框架的基础上定制自己的代码求解相应的问题。为了演示,还是给大家实例一个TSP问题的求解过程哈。谢谢!

最后做个小小说明:整个系列所有的代码在 代码 | 自适应大邻域搜索系列之(1) - 使用ALNS代码框架求解TSP问题 这篇文章中都能找到代码文件。

---The End---

文案 && 编辑:邓发珩

审稿:庄浩城

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

本文分享自微信公众号 - 数据魔术师(data-magician)

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

原始发表时间:2019-04-01

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【Android休眠】之PowerKey唤醒源实现【转】

    转自:https://blog.csdn.net/u013686019/article/details/53677531

    用户3033338
  • tftp--实现服务器与客户端的下载与上传【转】

    转自:https://blog.csdn.net/xiaopangzi313/article/details/9122975

    用户3033338
  • 手动跟踪函数的调用过程【转】

    转自:https://blog.csdn.net/ccjjnn19890720/article/details/6871036/

    用户3033338
  • SpringBoot实用小知识之Maven中dependencys和dependencymanagement区别

      利用pom管理引用包时,如果是单项目的话就直接在dependencies引用了,若有一个大工程项目里面包含多个子模块,则为了所有项目模块包的版本统一和好管理...

    欢醉
  • C++ 之虚函数的实现原理

    c++的多态使用虚函数实现,通过“晚绑定”,使程序在运行的时候,根据对象的类型去执行对应的虚函数。

    用户1215536
  • linux驱动 之 module_init解析 (上)【转】

    转自:https://blog.csdn.net/Richard_LiuJH/article/details/45669207

    用户3033338
  • 内核模块中filp->open对文件的读写【转】

    转自:http://guiltcool.blog.chinaunix.net/uid-9950859-id-98917.html

    用户3033338
  • Linux内核很吊之 module_init解析 (下)【转】

    转自:https://blog.csdn.net/richard_liujh/article/details/46758073

    用户3033338
  • 用户态与内核态 & 文件流与文件描述符 简介【转】

    转自:https://www.cnblogs.com/Jimmy1988/p/7479856.html

    用户3033338
  • input子系统 KeyPad-Touch上报数据格式与机制【转】

    转自:https://www.cnblogs.com/0822vaj/p/4185634.html

    用户3033338

扫码关注云+社区

领取腾讯云代金券