写在前面
上一篇文章代码 | 自适应大邻域搜索系列之(3) - Destroy和Repair方法代码实现解析讲解了destroy和repair方法的具体实现代码，好多读者都在喊酸爽和得劲儿……
今天这篇就讲点简单的，关于solution的定义和管理的代码实现，让大家回回神吧……哈哈。
01 总体概述
总所周知的是，每一个算法的最终目标都是求解出一个合理的满足心意的solution。因此对solution的定义和管理基本是每个算法都要涉及的。
在本ALNS代码中呢，也对solution进行了一定的抽象和规范化，提供了一些标准化的接口，同样需要在具体使用中去重写这些接口。
关于solution的处理方式总得来说也由两个模块组成：
- 关于solution的定义：ISolution抽象类
- 关于bestSolution的管理： IBestSolutionManager(抽象类)、SimpleBestSolutionManager(派生类)
下面也对其一一进行讲解。
02 ISolution抽象类
该类只是对solution的进行一定的抽象定义，并没有具体实现各个接口，需要coder在后续的使用中重写编写这些接口。
它应该具备的功能看代码就能理解了，注释也写得很详细。
主要包括几个功能：获取目标值、获取目标惩罚值、解是否可行、获取每个solution独一无二的hash值等。 具体代码也很简单：
代码语言：javascript复制 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)则根据需要判断是否要将已知的最优解作为当前解。
代码语言：javascript复制 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文件的代码：
代码语言：javascript复制 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的状态，返回最优解集合中最后一个解或者返回当前解。
代码语言：javascript复制 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---
文案 && 编辑：邓发珩
审稿：庄浩城
指导老师： 秦时明岳（华中科技大学管理学院）
