代码 | 自适应大邻域搜索系列之(3) - Destroy和Repair方法代码实现解析

2023-10-08 00:32

本文主要是介绍代码 | 自适应大邻域搜索系列之(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。它们之间的继承派生关系如下:
1240

下面对其一一讲解。

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 successfulldouble performanceRepairOperatorsWithNoise;//! A counter that indicates the number of times repair operators without noise have been successfulldouble 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是其对应集合的权重总和。
这里只讲一个新权重的计算方式就行:
1240
其中:
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方法的成绩。具体实现如下:

  1. 如果找到新的最优解,rScore+=Sigma1,dScore+=Sigma1。其中Sigma1是设定参数。
  2. 如果当前解得到改进,rScore+=Sigma2,dScore+=Sigma2。其中Sigma2是设定参数。
  3. 如果当前解没有得到改进 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 小结

好了,以上就是今天的代码内容,别急着走开哦,后面还有好多好多的内容没讲呢。
这是个天坑,希望大家和小编一起努力,共同填完它。哈哈,谢谢各位的至此。

posted @ 2019-03-23 19:04 短短的路走走停停 阅读( ...) 评论( ...) 编辑 收藏

这篇关于代码 | 自适应大邻域搜索系列之(3) - Destroy和Repair方法代码实现解析的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/161492

相关文章

网页解析 lxml 库--实战

lxml库使用流程 lxml 是 Python 的第三方解析库,完全使用 Python 语言编写,它对 XPath表达式提供了良好的支 持,因此能够了高效地解析 HTML/XML 文档。本节讲解如何通过 lxml 库解析 HTML 文档。 pip install lxml lxm| 库提供了一个 etree 模块,该模块专门用来解析 HTML/XML 文档,下面来介绍一下 lxml 库

Spring Security 从入门到进阶系列教程

Spring Security 入门系列 《保护 Web 应用的安全》 《Spring-Security-入门(一):登录与退出》 《Spring-Security-入门(二):基于数据库验证》 《Spring-Security-入门(三):密码加密》 《Spring-Security-入门(四):自定义-Filter》 《Spring-Security-入门(五):在 Sprin

hdu1043(八数码问题,广搜 + hash(实现状态压缩) )

利用康拓展开将一个排列映射成一个自然数,然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

认识、理解、分类——acm之搜索

普通搜索方法有两种:1、广度优先搜索;2、深度优先搜索; 更多搜索方法: 3、双向广度优先搜索; 4、启发式搜索(包括A*算法等); 搜索通常会用到的知识点:状态压缩(位压缩,利用hash思想压缩)。

hdu1240、hdu1253(三维搜索题)

1、从后往前输入,(x,y,z); 2、从下往上输入,(y , z, x); 3、从左往右输入,(z,x,y); hdu1240代码如下: #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#inc

【C++】_list常用方法解析及模拟实现

相信自己的力量,只要对自己始终保持信心,尽自己最大努力去完成任何事,就算事情最终结果是失败了,努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一:什么是list? •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二:list常用接口 •🌰1.默认成员函数 🔥构造函数(⭐) 🔥析构函数 •🌰2.list对象

【Prometheus】PromQL向量匹配实现不同标签的向量数据进行运算

✨✨ 欢迎大家来到景天科技苑✨✨ 🎈🎈 养成好习惯,先赞后看哦~🎈🎈 🏆 作者简介:景天科技苑 🏆《头衔》:大厂架构师,华为云开发者社区专家博主,阿里云开发者社区专家博主,CSDN全栈领域优质创作者,掘金优秀博主,51CTO博客专家等。 🏆《博客》:Python全栈,前后端开发,小程序开发,人工智能,js逆向,App逆向,网络系统安全,数据分析,Django,fastapi

活用c4d官方开发文档查询代码

当你问AI助手比如豆包,如何用python禁止掉xpresso标签时候,它会提示到 这时候要用到两个东西。https://developers.maxon.net/论坛搜索和开发文档 比如这里我就在官方找到正确的id描述 然后我就把参数标签换过来

让树莓派智能语音助手实现定时提醒功能

最初的时候是想直接在rasa 的chatbot上实现,因为rasa本身是带有remindschedule模块的。不过经过一番折腾后,忽然发现,chatbot上实现的定时,语音助手不一定会有响应。因为,我目前语音助手的代码设置了长时间无应答会结束对话,这样一来,chatbot定时提醒的触发就不会被语音助手获悉。那怎么让语音助手也具有定时提醒功能呢? 我最后选择的方法是用threading.Time

Android实现任意版本设置默认的锁屏壁纸和桌面壁纸(两张壁纸可不一致)

客户有些需求需要设置默认壁纸和锁屏壁纸  在默认情况下 这两个壁纸是相同的  如果需要默认的锁屏壁纸和桌面壁纸不一样 需要额外修改 Android13实现 替换默认桌面壁纸: 将图片文件替换frameworks/base/core/res/res/drawable-nodpi/default_wallpaper.*  (注意不能是bmp格式) 替换默认锁屏壁纸: 将图片资源放入vendo