前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >代码 | 自适应大邻域搜索系列之(7) - 局部搜索LocalSearch的代码解析

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

作者头像
短短的路走走停停
发布2019-05-14 17:25:17
5030
发布2019-05-14 17:25:17
举报
文章被收录于专栏:程序猿声
今天咱们依然讲代码哈~不过今天讲的依然很简单,关于局部搜索LocalSearch的代码。

01 总体概述

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

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

  • LocalSearch的定义
  • LocalSearch的管理

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

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

02 ILocalSearch

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

performLocalSearch用以执行一次LocalSearch操作。

getName返回该LocalSearch的名字。

代码语言:javascript
复制
 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开始信号,在启动整个算法的时候起到协调作用。

代码语言:javascript
复制
 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。

代码语言:javascript
复制
 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就不需要讲解了吧~

代码语言:javascript
复制
 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问题 这篇文章中都能找到代码文件。

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-04-16,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 程序猿声 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档