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

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

前言

好了小伙伴们我们又见面了，咳咳没错还是我。不知道你萌接连被这么多篇代码文章刷屏是什么感受，不过，酸爽归酸爽。今天咱们依然讲代码哈~不过今天讲的依然很简单，关于局部搜索LocalSearch的代码。

01 总体概述

其实，LocalSearch在本算法中不是必须使用的，用户可以根据需要来选择是否启用这个功能。但是一般情况下，有了LocalSearch以后效果会好一点。而且本着服务读者的态度（我可以不用，但是小编你不能不讲），就讲讲这个模块吧。和之前讲的几个模块差不多，具体代码也是分成两个部分进行实现的：

LocalSearch的定义
LocalSearch的管理

LocalSearch的定义用了一个很简单的抽象类ILocalSearch用来提供接口的、而LocalSearch的管理用了ILocalSearchManager、SimpleLocalSearchManager两个类，其中ILocalSearchManager也是抽象类，而SimpleLocalSearchManager则是继承于ILocalSearchManager并实现了相应的接口。下面对他们进行一一讲解。

02 ILocalSearch

其实这个类只提供了两个纯虚函数作为接口，也是简单得不能再简单了，performLocalSearch用以执行一次LocalSearch操作，getName返回该LocalSearch的名字。

class ILocalSearch { public: //! Perform a local search on the solution. //! \return true if the solution is improved. virtual bool performLocalSearch(ISolution& sol)=0;//! \return the name of the local search operator. virtual std::string getName()=0; };

03 ILocalSearchManager

这个抽象类也非常简单，只有两个接口。useLocalSearch用以判断是否要使用LocalSearch，而startSignal开始信号，在启动整个算法的时候起到协调作用。

class ILocalSearchManager { public://! \param sol the solution to be improved. //! \param status the status of the alns iteration. //! \return true if the solution has been improved. virtual bool useLocalSearch(ISolution& sol, ALNS_Iteration_Status& status)=0;//! Indicate that the optimization process starts. virtual void startSignal()=0; };

04 SimpleLocalSearchManager

SimpleLocalSearchManager对LocalSearch进行了一定的扩充，加入了addLocalSearchOperator的操作，用以添加LocalSearch。值得注意的是，该LocalSearchManager管理的可以是多个LocalSearch。

class SimpleLocalSearchManager: public ILocalSearchManager { public:SimpleLocalSearchManager(ALNS_Parameters& parameters){param = &parameters;};virtual ~SimpleLocalSearchManager(){};//! \param sol the solution to be improved. //! \param status the status of the alns iteration. //! \return true if the solution has been improved. virtual bool useLocalSearch(ISolution& sol, ALNS_Iteration_Status& status);//! Add a local search operator to the manager. void addLocalSearchOperator(ILocalSearch& ls);virtual void startSignal(){}; private: //! A vector containing the local search operators managed by the current instance. std::vector<ILocalSearch*> localSearchOperators;//! Parameters of the ALNS. ALNS_Parameters* param; };

useLocalSearch和addLocalSearchOperator具体实现代码如下，相信对迭代搜索了解的同学，对下面的过程那是熟悉得不能再熟悉了，特别是improvement 变量的复位操作（如果有改进，那么接着搜索下去，直到最大迭代次数为止，如果没有改进就不搜索了。）addLocalSearchOperator就不需要讲解了吧~

bool SimpleLocalSearchManager::useLocalSearch(ISolution& sol, ALNS_Iteration_Status& status) { if(status.getNewBestSolution()!=ALNS_Iteration_Status::TRUE || status.getAcceptedAsCurrentSolution()!=ALNS_Iteration_Status::UNKNOWN) { return false; } else { status.setLocalSearchUsed(ALNS_Iteration_Status::TRUE); bool improvement; do { improvement = false; for(size_t i = 0; i < localSearchOperators.size(); i++) { improvement = localSearchOperators[i]->performLocalSearch(sol)||improvement; } }while(improvement); if(improvement) { status.setImproveByLocalSearch(ALNS_Iteration_Status::TRUE); return true; } else { status.setImproveByLocalSearch(ALNS_Iteration_Status::FALSE); return false; } } }void SimpleLocalSearchManager::addLocalSearchOperator(ILocalSearch& ls) { //TODO find out why the set.find() == set.end() does not work. bool ok = true; for(size_t i=0; i< param->getForbidenLsOperators().size() && ok; i++) { if(param->getForbidenLsOperators()[i] == ls.getName()) { std::cout << "NO " << ls.getName() << std::endl; ok = false; } } if(ok) { localSearchOperators.push_back(&ls); }}