专栏首页程序猿声代码 | 自适应大邻域搜索系列之(2) - ALNS算法主逻辑结构解析
原创

代码 | 自适应大邻域搜索系列之(2) - ALNS算法主逻辑结构解析

00 前言

在上一篇推文中,教大家利用了ALNS的lib库求解了一个TSP问题作为实例。不知道你萌把代码跑起来了没有。那么,今天咱们再接再厉。跑完代码以后,小编再给大家深入讲解具体的代码内容。大家快去搬个小板凳一起过来围观学习吧~

01 总体概述

前排高能预警,在下面的讲解中,会涉及很多C++语言的知识,特别是类与派生这一块的内容,如果C++基础比较薄弱的同学则需要回去(洗洗睡)再好好补一补啦,在这里小编就不再过多科普基础知识了。默认大家都是C++大佬,能一口说出虚函数表是什么的内种……

描述整一个ALNS算法逻辑过程的是一个叫ALNS的C++类。下面对其成员变量和成员函数讲解一下。

1.1 成员变量

//!   当前解。
ISolution* currentSolution;

//! 判断接受准则。
IAcceptanceModule* acceptanceCriterion;

//! ALNS算法运行的相关参数。
ALNS_Parameters* param;

//! destroy和repair方法的管理者。
AOperatorManager* opManager;

//! 最优解的管理者。
IBestSolutionManager* bestSolManager;

//! 局部搜索的管理者。
ILocalSearchManager* lsManager;

//! 自上次重新计算重新的权重以来的迭代次数。
size_t nbIterationsWC;

//! 当前迭代次数。
size_t nbIterations;

//! The current number of iterations without improvement.
size_t nbIterationsWithoutImprovement;

//! The number of iterations without improvement of the current solution.
size_t nbIterationsWithoutImprovementCurrent;

//! The number of iterations without acceptation of a transition.
size_t nbIterationsWithoutTransition;

//! The number of iterations since the last call to a local search
//! operator.
size_t nbIterationsWithoutLocalSearch;

//! 求解的总时间。
clock_t startingTime;

//! 最优解的下界。
double lowerBound;

//! A set containing the hash keys of the encountred solutions.
std::set<long long> knownKeys;

//! 用于计算求解过程的一些状态量。
Statistics stats;

//! 最近一次迭代的状态。
ALNS_Iteration_Status status;

//! 每次迭代完成后需要更新的对象。
std::vector<IUpdatable*> updatableStructures;

//! ALNS实例的名字。
std::string name;

上面的成员变量类型用的都是抽象类的指针,因为在实际写代码的过程中,coder们肯定还要对solution、localsearch等类进行继承和派生,接口重写等。用抽象类的指针好处就是在于当它指向子类对象时也能正确调用。再说明一点,上面的ISolution啊IAcceptanceModule等都是一些抽象类的类型,以后会进行介绍和讲解的,在这里大家知道它代表什么就行了。

1.2 成员函数

//! Constructor.
//! \param name the name of the instance.
//! \param initialSolution the starting solution that is going to be optimized.
//! \param acceptanceCrit the module that determine whether or not a new solution
//! is accepted as the current solution.
//! \param parameters the set of parameters to be use by the ALNS.
//! \param opMan an operator manager.
ALNS(std::string instanceName,
	ISolution& initialSolution,
	IAcceptanceModule& acceptanceCrit,
	 ALNS_Parameters& parameters,
	 AOperatorManager& opMan,
	 IBestSolutionManager& solMan,
	 ILocalSearchManager& lsMan);

//! Destructor.
virtual ~ALNS();

//! This method launch the solving process.
//! \return true if a feasible solution is found,
//! false otherwise.
bool solve();

//! This method seeks if a solution is already known,
//! if not it is added to the set of known solutions.
//! \param sol the solution to be checked.
//! \return true if the solution was unknown, false otherwise.
bool checkAgainstKnownSolution(ISolution& sol);

//! This method perform one iteration of the ALNS solving
//! process.
void performOneIteration();

//! This method check whether or not the stopping criteria is met.
bool isStoppingCriterionMet();

//! Determine whether or not the new solution is better than the
//! best known solution.
bool isNewBest(ISolution* newSol);

//! \return the number of known solutions.
size_t getNumberKnownSolutions(){return knownKeys.size();};

//! Determine whether or not the new solution should be accepted
//! as the current solution.
bool transitionCurrentSolution(ISolution* newSol);

//! Return a pointer to the best known solution.
IBestSolutionManager* getBestSolutionManager(){return bestSolManager;};

//! Add an object to the list of object to be updated at the end of each
//! iteration of the ALNS.
//! \param up the updatable object to be added.
void addUpdatable(IUpdatable& up){updatableStructures.push_back(&up);};

//! Destroy the manager that have been provided at the construction of
//! the instance.
void end();

ALNS类的成员函数以及参数说明、函数说明等都在注释里面了。这么简单的英文相信大家都能看懂,小编就不作翻译了。

02 具体实现

在看完ALNS类的总体概述以后,我们现在来研究一下各个成员函数的具体实现代码和过程。

2.1 ALNS::构造和析构函数

构造函数主要做的是一些初始化工作,用传进来的参数对成员变量进行初始化,或者直接初始化相关的成员变量等。而析构函数主要做的是清理工作,释放动态申请的堆内存。

//构造
ALNS::ALNS(string instanceName,
		 ISolution& initialSolution,
		 IAcceptanceModule& acceptanceCrit,
		 ALNS_Parameters& parameters,
		 AOperatorManager& opMan,
		 IBestSolutionManager& bestSolMan,
		 ILocalSearchManager& lsMan)
{
	name = instanceName;
	currentSolution = initialSolution.getCopy();
	acceptanceCriterion = &acceptanceCrit;
	param = &parameters;
	lowerBound = -DBL_MAX;
	nbIterationsWC = 0;
	nbIterations = 0;
	nbIterationsWithoutImprovement = 0;
	opManager = &opMan;
	bestSolManager = &bestSolMan;
	lsManager = &lsMan;

	opManager->setStatistics(&stats);

	// We add the initial solution in the best solution manager.
	bestSolManager->isNewBestSolution(initialSolution);

	nbIterationsWithoutImprovementCurrent = 0;

	nbIterationsWithoutTransition = 0;

	nbIterationsWithoutLocalSearch = 0;
}
//析构
ALNS::~ALNS()
{
	delete currentSolution;
}

2.2 ALNS::performOneIteration()

该方法执行一次迭代操作。也是整个流程比较核心的部分。大概过程是先进行destroy操作和进行repair操作,然后判断新解质量。而后看情况要不要使用LocalSearch进行搜索,再用判断接受准则看是否要接受新解。最后更新destroy操作和repair操作的成绩。再做一些状态量的处理等。具体注释我已经标注在代码里了,理解起来不难。

void ALNS::performOneIteration()
{
    //重新初始化一些状态量。
	status.partialReinit();
    //选择Repair和Destroy方法
	ARepairOperator& repair = opManager->selectRepairOperator();
	ADestroyOperator& destroy = opManager->selectDestroyOperator();

	ISolution* newSolution = currentSolution->getCopy();
    //输出迭代次数等信息。 param->getLogFrequency()获取的是logFrequency变量的值,logFrequency变量表示的意思是每隔多少次输出一下相关信息。
	if(nbIterations % param->getLogFrequency() == 0)
	{
		cout << "[ALNS] it. " << nbIterations << " best sol: " << (*(bestSolManager->begin()))->getObjectiveValue() << " nb known solutions: " << knownKeys.size() << endl;
	}
    //destroy操作
	destroy.destroySolution(*newSolution);
    //更新状态
	status.setAlreadyDestroyed(ALNS_Iteration_Status::TRUE);
	status.setAlreadyRepaired(ALNS_Iteration_Status::FALSE);//未进行repair操作
    //表示newSolution还是status的信息对解进行更新。这里只提供接口,后面应用的时候要具体重写。
	for(vector<IUpdatable*>::iterator it = updatableStructures.begin(); it != updatableStructures.end(); it++)
	{
		(*it)->update(*newSolution,status);
	}
    //进行repair操作
	repair.repairSolution(*newSolution);
	status.setAlreadyRepaired(ALNS_Iteration_Status::TRUE);
    //更新迭代次数
	nbIterations++;
	status.setIterationId(nbIterations);
	nbIterationsWC++;

	double newCost = newSolution->getObjectiveValue();
    //判断新生产的解是不是新的最优解
	isNewBest(newSolution);
    //判断新生成的解之前有没有出现过
	checkAgainstKnownSolution(*newSolution);
    //判断新生成的解和当前解谁更优
	bool betterThanCurrent = (*newSolution)<(*currentSolution);
    //如果新生成的解更优
	if(betterThanCurrent)
	{
		nbIterationsWithoutImprovementCurrent = 0;//清0
		status.setImproveCurrentSolution(ALNS_Iteration_Status::TRUE);
	}
    //否则
	else
	{
		nbIterationsWithoutImprovementCurrent++;
		status.setImproveCurrentSolution(ALNS_Iteration_Status::FALSE);//解没有得到提高
	}
    //更新状态
	status.setNbIterationWithoutImprovementCurrent(nbIterationsWithoutImprovementCurrent);
    //param->getPerformLocalSearch()指出要不要用LocalSearch,然后再用LocalSearch对新生成的解进行搜索。lsManager->useLocalSearch(*newSolution,status)将返回true如果经过LocalSearch之后的解有改进的话。
	if(param->getPerformLocalSearch() && lsManager->useLocalSearch(*newSolution,status))
	{
    //判断LocalSearch之后的新解是不是最优解。
		bestSolManager->isNewBestSolution(*newSolution);
	}
    //判断是否接受当前的解。
	bool transitionAccepted = transitionCurrentSolution(newSolution);
    //如果接受
	if(transitionAccepted)
	{
		status.setAcceptedAsCurrentSolution(ALNS_Iteration_Status::TRUE);
		nbIterationsWithoutTransition = 0;
	}
    //否则
	else
	{
		status.setAcceptedAsCurrentSolution(ALNS_Iteration_Status::FALSE);
		nbIterationsWithoutTransition++;
	}
    //更新信息
	status.setNbIterationWithoutTransition(nbIterationsWithoutTransition);
    //再一次进行LocalSearch操作,以取得更好的效果。
	if(param->getPerformLocalSearch() && lsManager->useLocalSearch(*newSolution,status))
	{
		bestSolManager->isNewBestSolution(*newSolution);
		if(status.getAcceptedAsCurrentSolution() == ALNS_Iteration_Status::TRUE)
		{
			transitionCurrentSolution(newSolution);
		}
	}
    //对destroy,repair方法进行成绩更新。
	opManager->updateScores(destroy,repair,status);

    //记录本次迭代过程的一些信息。
	stats.addEntry(static_cast<double>(clock()-startingTime)/CLOCKS_PER_SEC,nbIterations,destroy.getName(),repair.getName(),newCost,currentSolution->getObjectiveValue(),(*(bestSolManager->begin()))->getObjectiveValue(),knownKeys.size());

    //更新destroy,repair方法的权重。是在进行了一定迭代次数以后才更新的,具体次数由param->getTimeSegmentsIt()获得。
	if(nbIterationsWC % param->getTimeSegmentsIt() == 0)
	{
		opManager->recomputeWeights();
		nbIterationsWC = 0;
	}
    //接口,对解的某些部分再次更新。
	for(vector<IUpdatable*>::iterator it = updatableStructures.begin(); it != updatableStructures.end(); it++)
	{
		(*it)->update(*newSolution,status);
	}
    //如果有需要,将当前解转变成最优解再进行下一次迭代操作。
	currentSolution = bestSolManager->reloadBestSolution(currentSolution,status);

	delete newSolution;
}

2.3 ALNS::checkAgainstKnownSolution(ISolution& sol)

检查该解是否是之前出现过的解。主要原理是利用一个解的哈希表,所有第一次出现的解都会生成一个唯一的哈希值存于哈希表中。将传入解的哈希值在哈希表中进行匹配,如果存在,那么这个解之前已经出现过了,否则就是独一无二的新解。

bool ALNS::checkAgainstKnownSolution(ISolution& sol)
{
	bool notKnownSolution = false;
	long long keySol = sol.getHash();
    //哈希值匹配
	if(knownKeys.find(keySol) == knownKeys.end())
	{
		notKnownSolution = true;
		knownKeys.insert(keySol);
	}
    //之前已经出现过的解。
	if(!notKnownSolution)
	{
		status.setAlreadyKnownSolution(ALNS_Iteration_Status::TRUE);
	}
    //全新的解,之前没有出现过。
	else
	{
		status.setAlreadyKnownSolution(ALNS_Iteration_Status::FALSE);
	}
	return notKnownSolution;
}

2.4 ALNS::isNewBest(ISolution* newSol)

用来判断解是否为新的最优解,并做出相应的设置。

bool ALNS::isNewBest(ISolution* newSol)
{
    //如果是新的最优解
	if(bestSolManager->isNewBestSolution(*newSol))
	{
		status.setNewBestSolution(ALNS_Iteration_Status::TRUE);
		nbIterationsWithoutImprovement = 0;
		status.setNbIterationWithoutImprovement(nbIterationsWithoutImprovement);
		status.setNbIterationWithoutImprovementSinceLastReload(0);
		return true;
	}
    //如果不是。
	else
	{
		status.setNewBestSolution(ALNS_Iteration_Status::FALSE);
		nbIterationsWithoutImprovement++;
		status.setNbIterationWithoutImprovement(nbIterationsWithoutImprovement);
		status.setNbIterationWithoutImprovementSinceLastReload(status.getNbIterationWithoutImprovementSinceLastReload()+1);
		return false;
	}
}

2.5 ALNS::transitionCurrentSolution(ISolution* newSol)

利用判断准则判断是否要接受当前的解作为新的解。

bool ALNS::transitionCurrentSolution(ISolution* newSol)
{
    //如果接受。
	if(acceptanceCriterion->transitionAccepted(*bestSolManager,*currentSolution,*newSol,status))
	{
		delete currentSolution;
		currentSolution = newSol->getCopy();
		return true;
	}
    //不接受,原来解不变,什么也不做。
	else
	{
		return false;
	}
}

2.6 ALNS::isStoppingCriterionMet()

判断算法迭代是否遇到终止条件。各种条件说明已经注释在代码:

bool ALNS::isStoppingCriterionMet()
{
    //是否找到最优可行解。
	if((*(bestSolManager->begin()))->isFeasible() && (*(bestSolManager->begin()))->getObjectiveValue() == lowerBound)
	{
		return true;
	}
	else
	{
		switch(param->getStopCrit())
		{
            //是否达到最大迭代次数。
			case ALNS_Parameters::MAX_IT: {
				return nbIterations >= param->getMaxNbIterations();
			}
            //是否达到最大限制运行时间。
			case ALNS_Parameters::MAX_RT: {
				clock_t currentTime = clock();
				double elapsed = (static_cast<double>(currentTime - startingTime)) / CLOCKS_PER_SEC;
				return elapsed >= param->getMaxRunningTime();
			}
            //the maximum number of iterations without improvement. 
			case ALNS_Parameters::MAX_IT_NO_IMP: {
				return nbIterationsWithoutImprovement >= param->getMaxNbIterationsNoImp();
			}
           //a mix of the MAX_IT, MAX_RT and MAX_IT_NO_IMP.
			case ALNS_Parameters::ALL: {
				if(nbIterations >= param->getMaxNbIterations())
				{
					return true;
				}
				if(nbIterationsWithoutImprovement >= param->getMaxNbIterationsNoImp())
				{
					return true;
				}
				clock_t currentTime = clock();
				double elapsed = (static_cast<double>(currentTime - startingTime)) / CLOCKS_PER_SEC;
				if(elapsed >= param->getMaxRunningTime())
				{
					return true;
				}
				return false;
			}

			default: {
				assert(false);
				return false;
			}
		}
	}

}

2.7 ALNS::solve()

开始ALNS算法的迭代过程。这是将上面的模块组装起来,然后跑算法求解的过程了。

bool ALNS::solve()
{
	startingTime = clock();
	param->setLock();
	acceptanceCriterion->startSignal();
	opManager->startSignal();
	stats.setStart();
    //如果没有遇到终止条件,那么将一次次迭代下去。
	while(!isStoppingCriterionMet())
	{
		performOneIteration();
	}
    //获取运行结果,返回解是否可行。
	string pathGlob = param->getStatsGlobPath();
	pathGlob += name;
	pathGlob += ".txt";
	string pathOp = param->getStatsOpPath();
	pathOp += name;
	pathOp += ".txt";
	stats.generateStatsFile(pathGlob,pathOp);
	return (*(bestSolManager->begin()))->isFeasible();
}

03 小结

至此,ALNS主逻辑的代码已经讲完了,大家还是以整体为重点,整体把握为主。

细枝末节我们后期还会讲的。并且……后面还有一大波代码有得大家酸爽。

不过还是先把碗里的吃完吧~咱们下期代码再见!

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • C++ 标准库之 iomanip 、操作符 ios::fixed 以及 setprecision 使用的惨痛教训经验总结

    本菜鸡自从退役之后就再也没怎么敲过 C++ 代码,在 C++ 语言下,求解关于浮点数类型的问题时,之前有碰到类似的情况,但是似乎都没有卡这块的数据,基本上用一个...

    Angel_Kitty
  • JavaScript和Java的区别?

    它是运行在浏览器中的一种脚本语言,在web页面中,Javascript可谓是无所不能:

    葆宁
  • Linux 多进程通信开发(六): 共享内存

    版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/briblue/article/details/891...

    Frank909
  • Linux命令(63)——nm令

    nm命令是GNU Binutils二进制工具集的一员,用于显示目标文件中的符号。如果没有为nm命令指出目标文件,则nm假定目标文件是a.out。

    Dabelv
  • 字节跳动凉面(抖音C++)(问题+解答)

    本科大四。 在字节官网投了简历,过了一天突然收到hr电话,问我工作倾向于北京还是上海,我说上海,然后hr说把我简历转给抖音上海hr....又过了一天(清明节前一...

    牛客网
  • 只有程序员才看得懂的段子!

    一程序员去面试,面试官问:“你毕业才两年,这三年工作经验是怎么来的?!”程序员答:“加班。”

    加米谷大数据
  • Linux命令(65)——ld命令

    ld命令是二进制工具集GNU Binutils的一员,是GNU链接器,用于将目标文件与库链接为可执行程序或库文件。

    Dabelv
  • Protocol Buffers(1):序列化、编译与使用

    Protocol Buffers docs:https://developers.google.com/protocol-buffers/docs/overvi...

    李拜六不开鑫
  • 百度面试两板斧:手写算法问基础

    17年7月份,我参加了百度的实习生面试,随后在百度开始了半年的实习生活,18年7月份,我参加了百度的校招提前批面试,由于可以同时参加百度多个部门的提前批面试,结...

    黄小斜
  • 五大人工智能流行编程语言对比,只要学会一种绝对不亏!

    就像大多数软件应用程序的开发一样,开发人员也在使用多种语言来编写人工智能项目,但是现在还没有任何一种完美的编程语言是可以完全速配人工智能项目的。

    一墨编程学习

扫码关注云+社区

领取腾讯云代金券