前言
上一篇文章中我们具体解剖了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噪声模式会在后面讲到。其他的方法也很简单就不做多解释了。
class AOperator
{
private:
//! Total number of calls during the process.
size_t totalNumberOfCalls;
//! Number of calls since the last evaluation.
size_t nbCallsSinceLastEval;
//! score of the operator.
double score;
//! weight of the operator.
double weight;
//! designation of the operator.
std::string operatorName;
protected:
//! Indicate if the operator is used in noise mode or not.
bool noise;
public:
//! Constructor.
AOperator(std::string name){
operatorName = name;
init();
}
//! Destructor.
virtual ~AOperator(){};
//! Initialize the values of the numbers of calls.
void init()
{
totalNumberOfCalls = 0;
nbCallsSinceLastEval = 0;
score = 0;
weight = 1;
}
//! reset the number of calls since last eval.
void resetNumberOfCalls()
{
nbCallsSinceLastEval = 0;
}
//! Simple getter.
//! \return the total number of calls to the operator since
//! the beginning of the optimization process.
size_t getTotalNumberOfCalls(){return totalNumberOfCalls;};
//! Simple getter.
//! \return the number of calls to this operator since the last
//! evaluation.
size_t getNumberOfCallsSinceLastEvaluation(){return nbCallsSinceLastEval;};
void increaseNumberOfCalls()
{
totalNumberOfCalls++;
nbCallsSinceLastEval++;
}
//! Simple getter.
double getScore() const
{
return score;
}
//! Simple getter.
double getWeight() const
{
return weight;
}
//! resetter.
void resetScore()
{
this->score = 0;
}
//! Simple setter.
void setScore(double s)
{
this->score = s;
}
//! Simple setter.
void setWeight(double weight)
{
this->weight = weight;
}
//! Simple getter.
std::string getName(){return operatorName;};
//! Set noise to true.
void setNoise(){noise=true;};
//! Set noise to false.
void unsetNoise(){noise=false;};
};
2.2 ADestroyOperator
该类主要是继承于上面的AOperator类,然后再此基础上加上Destroy操作的具体实现。它是一个抽象类,需要在后续的应用中重写Destroy操作的方法。
class ADestroyOperator : public AOperator {
protected:
//! The minimum destroy size used.
size_t minimunDestroy;
//! The maximum destroy size used.
size_t maximumDestroy;
public:
//! Constructor.
//! \param mini the minimum destroy size.
//! \param maxi the maximum destroy size.
//! \param s the name of the destroy operator.
ADestroyOperator(size_t mini, size_t maxi, std::string s) : AOperator(s)
{
minimunDestroy = mini;
maximumDestroy = maxi;
}
//! Destructor.
virtual ~ADestroyOperator(){};
//! This function is the one called to destroy a solution.
//! \param sol the solution to be destroyed.
virtual void destroySolution(ISolution& sol)=0;
};
2.3 ARepairOperator
同理,也是由AOperator类派生出来并加上Repair自己的实现方法的类。也是一个抽象类,需要在后续的使用中重写Repair方法。
class ARepairOperator : public AOperator {
public:
ARepairOperator(std::string s) : AOperator(s)
{
}
virtual ~ARepairOperator(){};
virtual void repairSolution(ISolution& sol)=0;
};
03 Destroy和Repair方法管理
对Destroy和Repair方法进行管理的由两个类来实现:AOperatorManager、OperatorManager。其中AOperatorManager是抽象类,只提供接口,OperatorManager继承于AOperatorManager。并对其接口进行实现。
3.1 AOperatorManager
该类抽象了OperatorManager的一些特征,只提供接口。因此成员函数都是纯虚函数。相关方法的说明已经注释在代码里面了。关于保护成员:stats用于保存算法迭代过程中的一些状态量,这个类后续也会讲解的。
class AOperatorManager
{
public:
//! This method selects a destroy operator.
//! \return a destroy operator.
virtual ADestroyOperator& selectDestroyOperator()=0;
//! This method selects a repair operator.
//! \return a repair operator.
virtual ARepairOperator& selectRepairOperator()=0;
virtual void recomputeWeights()=0;
//! Update the scores of the operators.
virtual void updateScores(ADestroyOperator& des, ARepairOperator& rep, ALNS_Iteration_Status& status)=0;
//! Indicate that the optimization process starts.
virtual void startSignal()=0;
//! Destroy the operators registered to this operator manager.
virtual void end()=0;
//! Simple setter.
void setStatistics(Statistics* statistics){stats = statistics;};
protected:
//! A pointer to the instance of the statistics module.
Statistics* stats;
};
3.2 OperatorManager
该类在AOperatorManager基础上也添加了一些自己额外的成员变量和函数方法。具体还是看代码理解吧,挺简单的,没有需要多解释的,我在这多少无益。
class OperatorManager: public AOperatorManager {
private:
//! The set of repair operators.
std::vector<AOperator*> repairOperators;
//! The set of destroy operators.
std::vector<AOperator*> destroyOperators;
//! The sum of the weights of the repair operators.
double sumWeightsRepair;
//! The sum of the weights of the destroy operators.
double sumWeightsDestroy;
//! The paramaters to be used by the ALNS.
ALNS_Parameters* parameters;
//! Indicate whether or not the next operators to be return
//! should be noised or not.
bool noise;
//! A counter that indicates the number of times repair operators with noise have been successfull
double performanceRepairOperatorsWithNoise;
//! A counter that indicates the number of times repair operators without noise have been successfull
double performanceRepairOperatorsWithoutNoise;
//! Use a roulette wheel to select an operator in a vector of operators.
//! \return the selected operator.
AOperator& selectOperator(std::vector<AOperator*>& vecOp, double sumW);
//! Recompute the weight of an operator.
void recomputeWeight(AOperator& op, double& sumW);
public:
//! Constructor
//! \param param the parameters to be used.
OperatorManager(ALNS_Parameters& param);
//! Destructor.
virtual ~OperatorManager();
//! This function recompute the weights of every operator managed by this
//! manager.
void recomputeWeights();
//! This method selects a destroy operator.
//! \return a destroy operator.
ADestroyOperator& selectDestroyOperator();
//! This method selects a repair operator.
//! \return a repair operator.
ARepairOperator& selectRepairOperator();
//! This method adds a repair operator to the list
//! of repair operator managed by this manager.
//! \param repairOperator the repair operator to be added.
void addRepairOperator(ARepairOperator& repairOperator);
//! This method adds a destroy operator to the list
//! of destroy operator managed by this manager.
//! \param destroyOperator the destroy operator to be added.
void addDestroyOperator(ADestroyOperator& destroyOperator);
//! This method run some sanity checks to ensure that it is possible
//! to "safely" use this manager within the ALNS.
void sanityChecks();
//! Update the scores of the operators.
virtual void updateScores(ADestroyOperator& des, ARepairOperator& rep, ALNS_Iteration_Status& status);
//! Indicate that the optimization process starts.
virtual void startSignal();
//! Destroy all the operators registered to this operator.
void end();
};
上面是该类的.h文件,关于其中某些函数方法的实现,小编下面挑一些来重点给大家讲讲,那些以小编的脑瓜子都能理解的代码就省略了,大家应该都能懂……
3.3 OperatorManager具体实现
又到了一大波代码时间,来吧来吧,小板凳准备好,要开始啦~
3.3.1 OperatorManager::recomputeWeight(...)
重新计算单个操作的权重。其有两个参数AOperator& op, double& sumW,其中 op是要重新计算权重的repair或者destroy方法,sumW是其对应集合的权重总和。
这里只讲一个新权重的计算方式就行:
其中:
Rho为设定的[0, 1]之间的参数,PrevWeight表示旧的权重,nbCalls表示在上一次自上一次更新完权重到现在该方法被调用的次数,timeSegmentsIt表示迭代多少次需要重新计算一下权重的迭代次数,currentScore表示旧的成绩。理解了这些就很easy了。
void OperatorManager::recomputeWeight(AOperator& op, double& sumW)
{
double prevWeight = op.getWeight();
sumW -= prevWeight;
double currentScore = op.getScore();
size_t nbCalls = op.getNumberOfCallsSinceLastEvaluation();
double newWeight = (1-parameters->getRho())*prevWeight + parameters->getRho()*(static_cast<double>(nbCalls)/static_cast<double>(parameters->getTimeSegmentsIt()))*currentScore;
// We ensure that the weight is within the bounds.
if(newWeight > parameters->getMaximumWeight())
{
newWeight = parameters->getMaximumWeight();
}
if(newWeight < parameters->getMinimumWeight())
{
newWeight = parameters->getMinimumWeight();
}
sumW += newWeight;
op.setWeight(newWeight);
op.resetScore();
op.resetNumberOfCalls();
}
值得注意的是还有一个OperatorManager::recomputeWeights()成员函数是用于重新计算repair或者destroy方法集合的,它的实现主要也还是调用OperatorManager::recomputeWeight(AOperator& op, double& sumW)方法来实现的。
3.3.2 OperatorManager::selectOperator(...)
相信了解过遗传算法轮盘赌实现过程的小伙伴对这里都不会陌生,当然,并不是说权重大的方法一定会被选中,只是被选中的可能性会大而已。具体过程是先生成一个在0到sumWeight之间的中间权重randomWeightPos ,然后从第一个方法开始用变量cumulSum进行权重累加,直到cumulSum>=randomWeightPos 为止,那么停止累加时最后这个方法就是幸运儿了。
AOperator& OperatorManager::selectOperator(std::vector<AOperator*>& vecOp, double sumW)
{
double randomVal = static_cast<double>(rand())/static_cast<double>(RAND_MAX);
double randomWeightPos = randomVal*sumW;
double cumulSum = 0;
for(size_t i = 0; i < vecOp.size(); i++)
{
cumulSum += vecOp[i]->getWeight();
if(cumulSum >= randomWeightPos)
{
if(noise)
{
vecOp[i]->setNoise();
}
else
{
vecOp[i]->unsetNoise();
}
vecOp[i]->increaseNumberOfCalls();
return *(vecOp[i]);
}
}
assert(false);
return *(vecOp.back());
}
3.3.3 OperatorManager::updateScores(...)
该成员函数用来更新各个Destroy和Repair方法的成绩。参数是Destroy和Repair方法的集合,以及ALNS迭代过程中的各种状态信息。便于说明下面用rScore和dScore分别代表Repair和Destroy方法的成绩。具体实现如下:
- 如果找到新的最优解,rScore+=Sigma1,dScore+=Sigma1。其中Sigma1是设定参数。
- 如果当前解得到改进,rScore+=Sigma2,dScore+=Sigma2。其中Sigma2是设定参数。
- 如果当前解没有得到改进 and 当前解是之前没有出现过的 and 当前解被接受作为新的解了,rScore+=Sigma3,dScore+=Sigma3。其中Sigma3是设定参数。
void OperatorManager::updateScores(ADestroyOperator& des, ARepairOperator& rep, ALNS_Iteration_Status& status)
{
if(status.getNewBestSolution() == ALNS_Iteration_Status::TRUE)
{
rep.setScore(rep.getScore()+parameters->getSigma1());
des.setScore(des.getScore()+parameters->getSigma1());
performanceRepairOperatorsWithNoise += 1;
performanceRepairOperatorsWithoutNoise += 1;
}
if(status.getImproveCurrentSolution() == ALNS_Iteration_Status::TRUE)
{
rep.setScore(rep.getScore()+parameters->getSigma2());
des.setScore(des.getScore()+parameters->getSigma2());
performanceRepairOperatorsWithNoise += 1;
performanceRepairOperatorsWithoutNoise += 1;
}
if(status.getImproveCurrentSolution() == ALNS_Iteration_Status::FALSE
&& status.getAcceptedAsCurrentSolution() == ALNS_Iteration_Status::TRUE
&& status.getAlreadyKnownSolution() == ALNS_Iteration_Status::FALSE)
{
rep.setScore(rep.getScore()+parameters->getSigma3());
des.setScore(des.getScore()+parameters->getSigma3());
performanceRepairOperatorsWithNoise += 1;
performanceRepairOperatorsWithoutNoise += 1;
}
/* OLD VERSION */
/*
if(parameters->getNoise())
{
double randNoise = static_cast<double>(rand())/RAND_MAX;
noise = (randNoise<parameters->getProbabilityOfNoise());
}
*/
/* NEW VERSION */
if(parameters->getNoise())
{
double performanceRepairOperatorsGlobal = 0;
performanceRepairOperatorsGlobal += performanceRepairOperatorsWithNoise;
performanceRepairOperatorsGlobal += performanceRepairOperatorsWithoutNoise;
double randomVal = static_cast<double>(rand())/RAND_MAX;
double randomWeightPos = randomVal*performanceRepairOperatorsGlobal;
noise = (randomWeightPos < performanceRepairOperatorsGlobal);
}
}
至此,差不过难点都讲完了,不知道你萌都understand了吗?
04 小结
好了,以上就是今天的代码内容,别急着走开哦,后面还有好多好多的内容没讲呢。
这是个天坑,希望大家和小编一起努力,共同填完它。哈哈,谢谢各位的至此。
更多运筹优化算法相关内容可以关注公众化【程序猿声】进行获取哦。
网友评论