写在前面
好了小伙伴们我们又见面了，咳咳没错还是我。
不知道你萌接连被
代码 | 自适应大邻域搜索系列之(2) - ALNS算法主逻辑结构解析
代码 | 自适应大邻域搜索系列之(3) - Destroy和Repair方法代码实现解析
代码 | 自适应大邻域搜索系列之(4) - Solution定义和管理的代码实现解析
代码 | 自适应大邻域搜索系列之(5) - ALNS_Iteration_Status和ALNS_Parameters的代码解析
代码 | 自适应大邻域搜索系列之(6) - 判断接受准则SimulatedAnnealing的代码解析
这么多篇代码文章刷屏是什么感受，不过，酸爽归酸爽。
今天咱们依然讲代码哈~不过今天讲的依然很简单，关于局部搜索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 = ¶meters;};
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问题 这篇文章中都能找到代码文件。