首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >代码 | 自适应大邻域搜索系列之(5) - Status和Parameters的代码解析

代码 | 自适应大邻域搜索系列之(5) - Status和Parameters的代码解析

原创
作者头像
短短的路走走停停
修改2019-05-14 18:17:49
4510
修改2019-05-14 18:17:49
举报
文章被收录于专栏:程序猿声程序猿声

前言

上一篇推文说了,后面的代码难度直线下降,各位小伙伴可以放去n的100次方心了。今天讲讲一些细枝末节,就是前面一直有提到的参数和一些状态的记录代码。这个简单啦,小编也不作过多解释了。大家直接看代码都能看懂,不过小编还是会把逻辑结构给大家梳理出来的。好了,开始干活。

01 ALNS_Iteration_Status

这个类,咳咳,不是抽象类了哈。主要用来记录ALNS迭代过程中的一些中间变量和状态等。主要是成员变量,成员函数都是简单的getter(获取成员变量的接口)或者setter(设置成员变量的接口)。所以这里就把成员变量贴出来好了,各个变量记录的内容注释也写得很详细,小编就不做多赘述以免扰乱了大家看代码的心。

private:

	//! Id of the iteration corresponding to this status.
	size_t iterationId;

	//! Number of iteration since the last improvement of the BKS
	size_t nbIterationWithoutImprovement;

	//! Number of iteration since the last improvement of the BKS
	//! or the last reload of the best known solution.
	size_t nbIterationWithoutImprovementSinceLastReload;

	//! Number of iterations since the last improvement of the current
	//! solution.
	size_t nbIterationWithoutImprovementCurrent;

	//! Number of iterations without transition.
	size_t nbIterationWithoutTransition;

	//! Indicate if a new best solution has been obtained.
	State newBestSolution;

	//! Indicate if the new solution has been accepted as the
	//! current solution.
	State acceptedAsCurrentSolution;

	//! Indicate if the new solution is already known.
	State alreadyKnownSolution;

	//! Indicate if the new solution improve the current solution.
	State improveCurrentSolution;

	//! Indicate if a local search operator has been used.
	State localSearchUsed;

	//! Indicate if solution has been improved by local search.
	State improveByLocalSearch;

	//! Indicate if the solution has already been repaired.
	State alreadyRepaired;

	//! Indicate if the new solution has already been destroyed.
	State alreadyDestroyed;

};

02 ALNS_Parameters

该类是ALNS运行过程中的一些参数设置,和上面的ALNS_Iteration_Status差不多,主要功能集中在成员变量上,成员函数都是简单的getter(获取成员变量的接口)或者setter(设置成员变量的接口)。照例把成员变量贴出来吧~

public:

	//! Enumeration representing the various kind of stopping criteria.
	//! MAX_IT: the maximum number of iterations.
	//! MAX_RT: the maximum run time.
	//! MAX_IT_NO_IMP: the maximum number of iterations without improvement.
	//! ALL: a mix of the MAX_IT, MAX_RT and MAX_IT_NO_IMP.
	enum StoppingCriteria {
		MAX_IT,
		MAX_RT,
		MAX_IT_NO_IMP,
		ALL
	};

	//! An enumeration listing a set of packaged AcceptanceModule Implementation.
	enum AcceptanceCriterioKind {
		SA
	};
protected:
	//! Maximum number of iterations performed by the ALNS.
	size_t maxNbIterations;

	//! Maximum running time of the ALNS.
	double maxRunningTime;

	//! Maximum number of iterations without any improvement.
	size_t maxNbIterationsNoImp;

	//! Which stopping criterion should be used.
	StoppingCriteria stopCrit;

	//! Indicate if noise should be used.
	bool noise;

	//! Indicate after how many iterations should the scores of
	//! the operators be recomputed.
	size_t timeSegmentsIt;

	//! Indicate the number of iterations that should be performed
	//! before reinitialization of the scores of the operators.
	size_t nbItBeforeReinit;

	//! score adjustment parameter in case the last remove-insert
	//! operation resulted in a new global best solution
	int sigma1;

	//! score adjustment parameter in case that the last remove-insert
	//! operation resulted in a solution that has not been accepted before and
	//! the objective value is better than the objective value of current solution
	int sigma2;

	//! score adjustment parameter in case that the last remove-insert
	//! operation resulted in a solution that has not been accepted before and such
	//! that the score objective value is worse than the one of current solution but
	//! the solution was accepted.
	int sigma3;

	//! reaction factor 0 <= rho <= 1 for the update of the weights of the
	//! operators.
	double rho;

	//! The minimum possible weight for an operator.
	double minimumWeight;

	//! The maximum possible weight for an operator.
	double maximumWeight;

	//! Indicates the probability of using noised operators.
	double probabilityOfNoise;

	//! Kind of acceptance criterion used.
	AcceptanceCriterioKind acKind;

	//! patht to the configuration file of the acceptance criterion.
	std::string acPath;

	//! path to the file where the global stats have to be saved.
	std::string statsGlobPath;

	//! path to the file where the operators stats have to be saved.
	std::string statsOpPath;

	//! Indicate every each iteration logging is done. 不懂看后面。
	int logFrequency;

	//! A set of forbidden operators. 不懂看后面。
	std::vector<std::string> forbidenOperators;

	//! A set of forbidden local search operators. 不懂看后面。
	std::vector<std::string> forbidenLsOperators;

	//! The minimum percentage of the solution destroyed by the destroy operators.
	int minDestroyPerc;

	//! The maximum percentage of the solution destroyed by the destroy operators.
	int maxDestroyPerc;

	//! Indicate after how many iterations without improvement
	//! does the best known solution is reloaded.
	size_t reloadFrequency;

	//! Indicate if local search should be used.
	bool performLocalSearch;

	//! When the optimization process start, the parameters
	//! should not be modified. lock is set to true when the
	//! optimization begin. If the setter of the value
	//! of one parameter is called while lock is true, an
	//! error is raised.
	bool lock;

};

不过有几个变量大家看了注释可能还不太明白是干嘛用的。在这里再解释一下。

logFrequency,隔多少次迭代输出一下当前的信息。直接给大家上两个图让大家心领神会一下:

  1. logFrequency = 1
  2. logFrequency = 100

懂了吧。

forbidenOperators是禁止的某些repair和destroy方法的集合,学过禁忌搜索的都知道这意味着什么,有些repair和destroy方法效果太差劲了,所以我们把它们给ban掉。

forbidenLsOperators和forbidenOperators差不多,不过它是禁止的某些LocalSearch方法的集合,效果太差嘛。。。

03 再论ALNS_Parameters

关于ALNS_Parameters它的大部分成员函数是简单的getter(获取成员变量的接口)或者setter(设置成员变量的接口)。但其CPP文件中,还有一个函数是从xml文件读取相应参数的。代码就不具体介绍了,主要是xml文件操作的一些api的使用,有现成的lib库,感兴趣的同学了解一下。

至于为什么用xml文件呢?其实直接把参数写死在程序里面也是可以的,不过读取xml文件获取相应的参数更符合标准,在实际生产中也更方便实用而已。

04 小结

至此,整一个ALNS模块已经讲得差不多了,不知道大家都看懂了没有。看不懂的话可以多看几遍,很多地方也只是小编个人的理解,不一定正确,如果你觉得你有更好的想法,也可以联系小编一起讨论。

后面再出多几篇估计就差不多了。把判断接受准则讲讲,把局部搜索讲讲就差不多可以了。最后谢谢大家一路过来的支持哈。

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

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

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

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

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 前言
  • 01 ALNS_Iteration_Status
  • 02 ALNS_Parameters
  • 03 再论ALNS_Parameters
  • 04 小结
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档