代码 | 自适应大邻域搜索系列之(3) - Destroy和Repair方法代码实现解析
代码 | 自适应大邻域搜索系列之(3) - Destroy和Repair方法代码实现解析
写在前面
上一篇文章中我们具体解剖了ALNS类的具体代码实现过程，不过也留下了很多大坑。
接下来的文章基本都是“填坑”了，把各个模块一一展现解析给大家。
不过碍于文章篇幅等原因呢，也不会每一行代码都进行讲解，那些简单的代码就跳过了，相信大家也能一眼就看懂。好了，废话不多说，开始干活吧。
01 照旧总体概述
前面我们提到，ALNS中的重中之重就是Destroy和Repair方法了，在整一个ALNS框架中呢，涉及这俩货的有：
Destroy和Repair方法的具体实现、Destroy和Repair方法管理（包括各个Destroy和Repair方法权重分配、成绩打分、按权重选择哪个Destroy和Repair方法等操作）。
所以在这次的ALNS代码中呢，这俩货的代码实现呢也分为两个模块：
- Destroy和Repair方法具体实现模块
- Destroy和Repair方法管理模块
下面我们将对其进行一一讲解，不知道大家小板凳准备好了没有。
02 Destroy和Repair方法具体实现
关于Destroy和Repair方法，由三个类组成，分别是AOperator、ADestroyOperator、ARepairOperator。它们之间的继承派生关系如下：
下面对其一一讲解。
2.1 AOperator
这是一个基础父类，它抽象了Destroy和Repair方法共有的一些方法和特征（成绩、权重、名称等等），然后Destroy和Repair方法再各自继承于它，实现自己的功能模块。
成员变量已经注释清楚了，关于protected的一个成员noise噪声模式会在后面讲到。其他的方法也很简单就不做多解释了。
1class AOperator
2{
3private:
4 //! Total number of calls during the process.
5 size_t totalNumberOfCalls;
6
7 //! Number of calls since the last evaluation.
8 size_t nbCallsSinceLastEval;
9
10 //! score of the operator.
11 double score;
12
13 //! weight of the operator.
14 double weight;
15
16 //! designation of the operator.
17 std::string operatorName;
18
19protected:
20 //! Indicate if the operator is used in noise mode or not.
21 bool noise;
22public:
23
24 //! Constructor.
25 AOperator(std::string name){
26 operatorName = name;
27 init();
28 }
29
30 //! Destructor.
31 virtual ~AOperator(){};
32
33 //! Initialize the values of the numbers of calls.
34 void init()
35 {
36 totalNumberOfCalls = 0;
37 nbCallsSinceLastEval = 0;
38 score = 0;
39 weight = 1;
40 }
41
42 //! reset the number of calls since last eval.
43 void resetNumberOfCalls()
44 {
45 nbCallsSinceLastEval = 0;
46 }
47
48 //! Simple getter.
49 //! \return the total number of calls to the operator since
50 //! the beginning of the optimization process.
51 size_t getTotalNumberOfCalls(){return totalNumberOfCalls;};
52
53 //! Simple getter.
54 //! \return the number of calls to this operator since the last
55 //! evaluation.
56 size_t getNumberOfCallsSinceLastEvaluation(){return nbCallsSinceLastEval;};
57
58 void increaseNumberOfCalls()
59 {
60 totalNumberOfCalls++;
61 nbCallsSinceLastEval++;
62 }
63
64 //! Simple getter.
65 double getScore() const
66 {
67 return score;
68 }
69
70 //! Simple getter.
71 double getWeight() const
72 {
73 return weight;
74 }
75
76 //! resetter.
77 void resetScore()
78 {
79 this->score = 0;
80 }
81
82 //! Simple setter.
83 void setScore(double s)
84 {
85 this->score = s;
86 }
87
88 //! Simple setter.
89 void setWeight(double weight)
90 {
91 this->weight = weight;
92 }
93
94 //! Simple getter.
95 std::string getName(){return operatorName;};
96
97 //! Set noise to true.
98 void setNoise(){noise=true;};
99
100 //! Set noise to false.
101 void unsetNoise(){noise=false;};
102
103};2.2 ADestroyOperator
该类主要是继承于上面的AOperator类，然后再此基础上加上Destroy操作的具体实现。它是一个抽象类，需要在后续的应用中重写Destroy操作的方法。
1class ADestroyOperator : public AOperator {
2protected:
3 //! The minimum destroy size used.
4 size_t minimunDestroy;
5 //! The maximum destroy size used.
6 size_t maximumDestroy;
7
8public:
9 //! Constructor.
10 //! \param mini the minimum destroy size.
11 //! \param maxi the maximum destroy size.
12 //! \param s the name of the destroy operator.
13 ADestroyOperator(size_t mini, size_t maxi, std::string s) : AOperator(s)
14 {
15 minimunDestroy = mini;
16 maximumDestroy = maxi;
17 }
18
19 //! Destructor.
20 virtual ~ADestroyOperator(){};
21
22 //! This function is the one called to destroy a solution.
23 //! \param sol the solution to be destroyed.
24 virtual void destroySolution(ISolution& sol)=0;
25};2.3 ARepairOperator
同理，也是由AOperator类派生出来并加上Repair自己的实现方法的类。也是一个抽象类，需要在后续的使用中重写Repair方法。
1class ARepairOperator : public AOperator {
2
3public:
4 ARepairOperator(std::string s) : AOperator(s)
5 {
6 }
7
8 virtual ~ARepairOperator(){};
9
10 virtual void repairSolution(ISolution& sol)=0;
11};03 Destroy和Repair方法管理
对Destroy和Repair方法进行管理的由两个类来实现：AOperatorManager、OperatorManager。
其中AOperatorManager是抽象类，只提供接口，OperatorManager继承于AOperatorManager。并对其接口进行实现。然后，接着看代码。
3.1 AOperatorManager
该类抽象了OperatorManager的一些特征，只提供接口。因此成员函数都是纯虚函数。相关方法的说明已经注释在代码里面了。
关于保护成员：stats用于保存算法迭代过程中的一些状态量，这个类后续也会讲解的。
1class AOperatorManager
2{
3public:
4 //! This method selects a destroy operator.
5 //! \return a destroy operator.
6 virtual ADestroyOperator& selectDestroyOperator()=0;
7
8 //! This method selects a repair operator.
9 //! \return a repair operator.
10 virtual ARepairOperator& selectRepairOperator()=0;
11
12 virtual void recomputeWeights()=0;
13
14 //! Update the scores of the operators.
15 virtual void updateScores(ADestroyOperator& des, ARepairOperator& rep, ALNS_Iteration_Status& status)=0;
16
17 //! Indicate that the optimization process starts.
18 virtual void startSignal()=0;
19
20 //! Destroy the operators registered to this operator manager.
21 virtual void end()=0;
22
23 //! Simple setter.
24 void setStatistics(Statistics* statistics){stats = statistics;};
25protected:
26 //! A pointer to the instance of the statistics module.
27 Statistics* stats;
28};3.2 OperatorManager
该类在AOperatorManager基础上也添加了一些自己额外的成员变量和函数方法。具体还是看代码理解吧，挺简单的，没有需要多解释的，我在这多少无益。
1class OperatorManager: public AOperatorManager {
2private:
3 //! The set of repair operators.
4 std::vector<AOperator*> repairOperators;
5
6 //! The set of destroy operators.
7 std::vector<AOperator*> destroyOperators;
8
9 //! The sum of the weights of the repair operators.
10 double sumWeightsRepair;
11
12 //! The sum of the weights of the destroy operators.
13 double sumWeightsDestroy;
14
15 //! The paramaters to be used by the ALNS.
16 ALNS_Parameters* parameters;
17
18 //! Indicate whether or not the next operators to be return
19 //! should be noised or not.
20 bool noise;
21
22 //! A counter that indicates the number of times repair operators with noise have been successfull
23 double performanceRepairOperatorsWithNoise;
24 //! A counter that indicates the number of times repair operators without noise have been successfull
25 double performanceRepairOperatorsWithoutNoise;
26
27
28 //! Use a roulette wheel to select an operator in a vector of operators.
29 //! \return the selected operator.
30 AOperator& selectOperator(std::vector<AOperator*>& vecOp, double sumW);
31
32 //! Recompute the weight of an operator.
33 void recomputeWeight(AOperator& op, double& sumW);
34public:
35 //! Constructor
36 //! \param param the parameters to be used.
37 OperatorManager(ALNS_Parameters& param);
38
39 //! Destructor.
40 virtual ~OperatorManager();
41
42 //! This function recompute the weights of every operator managed by this
43 //! manager.
44 void recomputeWeights();
45
46 //! This method selects a destroy operator.
47 //! \return a destroy operator.
48 ADestroyOperator& selectDestroyOperator();
49
50 //! This method selects a repair operator.
51 //! \return a repair operator.
52 ARepairOperator& selectRepairOperator();
53
54 //! This method adds a repair operator to the list
55 //! of repair operator managed by this manager.
56 //! \param repairOperator the repair operator to be added.
57 void addRepairOperator(ARepairOperator& repairOperator);
58
59 //! This method adds a destroy operator to the list
60 //! of destroy operator managed by this manager.
61 //! \param destroyOperator the destroy operator to be added.
62 void addDestroyOperator(ADestroyOperator& destroyOperator);
63
64 //! This method run some sanity checks to ensure that it is possible
65 //! to "safely" use this manager within the ALNS.
66 void sanityChecks();
67
68 //! Update the scores of the operators.
69 virtual void updateScores(ADestroyOperator& des, ARepairOperator& rep, ALNS_Iteration_Status& status);
70
71 //! Indicate that the optimization process starts.
72 virtual void startSignal();
73
74 //! Destroy all the operators registered to this operator.
75 void end();
76};上面是该类的.h文件，关于其中某些函数方法的实现，小编下面挑一些来重点给大家讲讲，那些以小编的脑瓜子都能理解的代码就省略了，大家应该都能懂……
04 OperatorManager具体实现
又到了一大波代码时间，来吧来吧，小板凳准备好，要开始啦~
4.1 OperatorManager::recomputeWeight()
重新计算单个操作的权重。其有两个参数AOperator& op, double& sumW。
其中 op是要重新计算权重的repair或者destroy方法，sumW是其对应集合的权重总和。这里只讲一个新权重的计算方式就行：
其中：
Rho为设定的[0, 1]之间的参数。
PrevWeight表示旧的权重。
nbCalls表示在上一次自上一次更新完权重到现在该方法被调用的次数。
timeSegmentsIt表示迭代多少次需要重新计算一下权重的迭代次数。
currentScore表示旧的成绩。
理解了这些就很easy了。
1void OperatorManager::recomputeWeight(AOperator& op, double& sumW)
2{
3 double prevWeight = op.getWeight();
4 sumW -= prevWeight;
5 double currentScore = op.getScore();
6 size_t nbCalls = op.getNumberOfCallsSinceLastEvaluation();
7 double newWeight = (1-parameters->getRho())*prevWeight + parameters->getRho()*(static_cast<double>(nbCalls)/static_cast<double>(parameters->getTimeSegmentsIt()))*currentScore;
8 // We ensure that the weight is within the bounds.
9 if(newWeight > parameters->getMaximumWeight())
10 {
11 newWeight = parameters->getMaximumWeight();
12 }
13 if(newWeight < parameters->getMinimumWeight())
14 {
15 newWeight = parameters->getMinimumWeight();
16 }
17
18 sumW += newWeight;
19 op.setWeight(newWeight);
20 op.resetScore();
21 op.resetNumberOfCalls();
22}值得注意的是还有一个OperatorManager::recomputeWeights()成员函数是用于重新计算repair或者destroy方法集合的。
它的实现主要也还是调用OperatorManager::recomputeWeight(AOperator& op, double& sumW)方法来实现的。
4.2 OperatorManager::selectOperator(...)
相信了解过遗传算法轮盘赌实现过程的小伙伴对这里都不会陌生，当然，并不是说权重大的方法一定会被选中，只是被选中的可能性会大而已。
具体过程是先生成一个在0到sumWeight之间的中间权重randomWeightPos ，然后从第一个方法开始用变量cumulSum进行权重累加，直到cumulSum>=randomWeightPos 为止，那么停止累加时最后这个方法就是幸运儿了。
1AOperator& OperatorManager::selectOperator(std::vector<AOperator*>& vecOp, double sumW)
2{
3 double randomVal = static_cast<double>(rand())/static_cast<double>(RAND_MAX);
4 double randomWeightPos = randomVal*sumW;
5 double cumulSum = 0;
6 for(size_t i = 0; i < vecOp.size(); i++)
7 {
8 cumulSum += vecOp[i]->getWeight();
9 if(cumulSum >= randomWeightPos)
10 {
11 if(noise)
12 {
13 vecOp[i]->setNoise();
14 }
15 else
16 {
17 vecOp[i]->unsetNoise();
18 }
19 vecOp[i]->increaseNumberOfCalls();
20 return *(vecOp[i]);
21 }
22 }
23 assert(false);
24 return *(vecOp.back());
25}4.3 OperatorManager::updateScores(...)
该成员函数用来更新各个Destroy和Repair方法的成绩。参数是Destroy和Repair方法的集合，以及ALNS迭代过程中的各种状态信息。
便于说明下面用rScore和dScore分别代表Repair和Destroy方法的成绩。具体实现如下：
1) 如果找到新的最优解，rScore+=Sigma1，dScore+=Sigma1。其中Sigma1是设定参数。
2) 如果当前解得到改进，rScore+=Sigma2，dScore+=Sigma2。其中Sigma2是设定参数。
3) 如果当前解没有得到改进 and 当前解是之前没有出现过的 and 当前解被接受作为新的解了，rScore+=Sigma3，dScore+=Sigma3。其中Sigma3是设定参数。
1void OperatorManager::updateScores(ADestroyOperator& des, ARepairOperator& rep, ALNS_Iteration_Status& status)
2{
3 if(status.getNewBestSolution() == ALNS_Iteration_Status::TRUE)
4 {
5 rep.setScore(rep.getScore()+parameters->getSigma1());
6 des.setScore(des.getScore()+parameters->getSigma1());
7 performanceRepairOperatorsWithNoise += 1;
8 performanceRepairOperatorsWithoutNoise += 1;
9 }
10
11 if(status.getImproveCurrentSolution() == ALNS_Iteration_Status::TRUE)
12 {
13 rep.setScore(rep.getScore()+parameters->getSigma2());
14 des.setScore(des.getScore()+parameters->getSigma2());
15 performanceRepairOperatorsWithNoise += 1;
16 performanceRepairOperatorsWithoutNoise += 1;
17 }
18
19 if(status.getImproveCurrentSolution() == ALNS_Iteration_Status::FALSE
20 && status.getAcceptedAsCurrentSolution() == ALNS_Iteration_Status::TRUE
21 && status.getAlreadyKnownSolution() == ALNS_Iteration_Status::FALSE)
22 {
23 rep.setScore(rep.getScore()+parameters->getSigma3());
24 des.setScore(des.getScore()+parameters->getSigma3());
25 performanceRepairOperatorsWithNoise += 1;
26 performanceRepairOperatorsWithoutNoise += 1;
27 }
28 /* OLD VERSION */
29 /*
30 if(parameters->getNoise())
31 {
32 double randNoise = static_cast<double>(rand())/RAND_MAX;
33 noise = (randNoise<parameters->getProbabilityOfNoise());
34 }
35 */
36 /* NEW VERSION */
37
38 if(parameters->getNoise())
39 {
40 double performanceRepairOperatorsGlobal = 0;
41 performanceRepairOperatorsGlobal += performanceRepairOperatorsWithNoise;
42 performanceRepairOperatorsGlobal += performanceRepairOperatorsWithoutNoise;
43
44 double randomVal = static_cast<double>(rand())/RAND_MAX;
45 double randomWeightPos = randomVal*performanceRepairOperatorsGlobal;
46 noise = (randomWeightPos < performanceRepairOperatorsGlobal);
47 }
48}至此，差不过难点都讲完了，不知道你萌都understand了吗？
05 小结
好了，以上就是今天的代码内容，别急着走开哦，后面还有好多好多的内容没讲呢。
这是个天坑，希望大家和小编一起努力，共同填完它。哈哈，谢谢各位的至此。对了，你萌不会不点赞就走了吧？
END
【如对代码有疑问，可联系小编，可以提供有偿辅导服务】
【有偿辅导纯属个人行为，与团队无关】
精彩文章推荐
干货 | 变邻域搜索算法(VNS)求解TSP（附C++详细代码及注释）
干货 | 变邻域搜索算法(Variable Neighborhood Search,VNS)超详细一看就懂
干货 | 遗传算法(Genetic Algorithm) Java 详细代码及注释
干货 | 遗传算法(Genetic Algorithm) （附代码及注释）
干货|迭代局部搜索算法(Iterated local search)探幽（附C++代码及注释）
干货 | 用模拟退火(SA, Simulated Annealing)算法解决旅行商问题
---The End---
文案 && 编辑：邓发珩
审稿：庄浩城
指导老师： 秦时明岳（华中科技大学管理学院）
如对文中内容有疑问，欢迎交流。PS:部分资料来自网络。
如有需求，可以联系：
秦虎老师（professor.qin@qq.com）
邓发珩 （华中科技大学管理学院本科二年级：2638512393@qq.com、个人公众号：程序猿声）
庄浩城（华中科技大学管理学院本科三年级：1604088003@qq.com）