adaptive large neighbourhood search
v0.2
这是由Ropke和Pisinger设计的（平行）自适应大邻居搜索算法的（平行）自适应大邻居搜索算法的仅C ++的实现。该代码是基于Stefan Ropke与我共享的原始实现的松散。
原始ALNS框架是在本文中开发的：
@article { ropke_2006 ,
title = { An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows } ,
author = { Ropke, Stefan and Pisinger, David } ,
year = 2006 ,
journal = { Transportation Science } ,
volume = 40 ,
number = 4 ,
pages = { 455--472 } ,
doi = { 10.1287/trsc.1050.0135 }
}该实施还包括多个接受标准，因为它们在本文中引入了自适应大型邻里搜索元神经（Preprint）的接受标准的比较。如果您使用此软件，请引用最后一篇论文如下：
@article { ALNS_Acceptance_Criteria ,
title = { A comparison of acceptance criteria for the {Adaptive Large Neighbourhood Search} metaheuristic } ,
author = { Santini, Alberto and Ropke, Stefan and Hvattum, Lars Magnus } ,
journal = { {Journal of Heuristics} } ,
volume = 24 ,
issue = 5 ,
pages = { 783--815 } ,
year = 2018 ,
doi = { 10.1007/s10732-018-9377-x }
}使用doxygen语法在代码中彻底记录了功能。因为这是一个元启发式框架，所以用户必须实现特定于问题的零件。在代码方面，这意味着用户需要提供下面描述的组件。
用户应实施：
getInstanceSize()返回实例的大小（例如，TSP实例中的顶点数）。getCost()返回最小化的成本（例如，TSP巡回赛的长度）。InitialSolutionCreator方案的子类可为问题产生初始解决方案。一旦就位，用户就可以创建PALNS对象的实例。例如：
auto alns = PALNS<TSPInstance, TSPSolution>{instance};其中TSPInstance是对问题实例建模的类，而TSPSolution是对问题解决方案进行建模的类。用户至少必须提供上述功能。例如：
std:: uint32_t TSPInstance::getInstanceSize () const {
return this -> numberOfVertices ;
}
double TSPSolution::getCost () const {
return this -> tourLength ;
}此外，由于ALNS方法从混凝土解决方案开始，因此用户必须提供初始解决方案创建者：
struct TSPRandomSolutionCreator : InitialSolutionCreator<TSPSolution, TSPInstance> {
TSPSolution create_initial_solution ( const TPSInstance& instance, std::mt19937& mt) {
return TSPSolution::shuffled_vertices (mt);
}
}为了可重复性，初始解决方案创建者可以使用ALNS框架传递的伪随机数生成器，类型为std::mt19937 （来自<random> header）。
破坏和修复方法将分别从DestroyMethod和RepairMethod的基本类别得出。从DestroyMethod继承的类应实施两种方法：
void destroy_solution(Solution sol&, std::mt19937& mt) ，它通过参考（如果需要的话）进行解决方案（以及PRNG）并将其拆除。std::unique_ptr<DestroyMethod<Solution>> clone() const ，该const（将unique_ptr返回到基类的DestroyMethod克隆销毁方法。同样，从RepairMethod继承的类应实施：
void repair_solution(Solution& sol, std::mt19937& mt) ，该解决方案通过参考（如果需要的话）进行（破坏的）解决方案（如果需要的话），然后就位进行维修。std::unique_ptr<RepairMethod<Solution>> clone() const ，该const（）将unique_ptr _ptr返回到基础类RepairMethod克隆修复方法。例如：
struct RandomDestroy : public DestroyMethod <TSPSolution> {
void destroy_solution (TSPSolution& solution, std::mt19937& mt) {
std::bernoulli_distribution d ( 0.1 );
for ( const auto & v : solution. visited_vertices ()) {
if ( d (mt)) {
solution. queue_vertex_removal (v);
}
}
solution. remove_queued_vertices ();
}
std::unique_ptr<DestroyMethod<TSPSolution>> clone () const {
return std::make_unique<DestroyMethod<TSPSolution>>();
}
};
struct GreedyRepair : public RepairMethod <TSPSoution> {
void repair_solution (Solution& sol, std::mt19937& mt) {
for ( const auto & v : solution. missing_vertices ()) {
solution. insert_vertex_in_best_position (v);
}
}
std::unique_ptr<RepairMethod<TSPSolution>> clone () const {
return std::make_unique<RepairMethod<TSPSolution>>();
}
};用户可以在使用预定义的接受标准或从基类AcceptanceCriterion中实现自己的继承之间进行选择。在解决方案过程中监视算法并执行非标准操作的一种方便方法是提供从AlgorithmVisitor visitor继承的访问者对象。算法访问者必须实现以下回调：
on_algorithm_start在第一个Alns迭代之前被调用。on_prerun_end在完成前完成时称为（请参见下面的部分参数）。on_iteration_end 。on_many_iters_without_improvement ，在用户定义的连续迭代次数之后被调用，而无需改进最佳解决方案（请参见下面的部分参数）。元启发式框架的所有参数均设置为编辑文件Params.json 。它们如下所述：
prerun-iterations ：算法可以用来尝试自动调整接受参数的初始迭代次数。这不是强制性的，可以设置为零。total-iterations ：对迭代次数的严格限制。timeout-s ：对算法的CPU时间的严格限制。iters-without-improvement-max ：对连续迭代的数量的严格限制，而没有改进最佳解决方案。当陷入平坦的景观情况时，它尽早终止了跑步。iters-without-improvement-alarm ：如果设置，并且如果用户提供了算法访问者，则在此许多连续的迭代之后，我们将称为访问者的on_many_iters_without_improvement方法。用户可以使用此机制尝试逃脱本地Optima。例如，它可以应用更强大的销毁方法或多样化的启发式方法。iterations-without-syncing-threads ：在算法的并行版本中，这是线程不同步信息并像ALNS算法的独立副本一样的迭代次数。线程同步后，共享接受/破坏权重和当前解决方案。prob-return-to-best-known ：在每次迭代中，最著名的解决方案将用这种概率替换当前解决方案。零是一个很好的默认值，但是用户可以设置更高的价值以偏爱强化而不是多元化。acceptance-criterion ：预定义的接受标准之一。可能的值在（未使用的）参数键acceptance-criterion-possible-values中列出。acceptance-params-base ：在算法运行过程中，某些接受参数有所不同。该参数可以花费time ， iterations指定时间限制（ timeout-s ）或迭代限制（ total-iterations ）是否应估算以估算运行何时结束。scores ：这些是用于更新每次迭代时销毁/维修得分的乘数。用户应提供四个乘数：global-bestimprovedaccepted 。decay ）确定上述三个值会影响方法的分数的速度。理智的默认值仅小于1.0，以确保得分变化平稳。parameter-tuning-file ：如果执行参数调整，则是将保存结果的文件名。results-log-basename ：结果文件的Basename。 在以下内容中，我们列出了相对于接受标准的参数。我们敦促用户参考接受标准纸，以更好地了解每个参数的作用，以及以下术语。本文还介绍了解决各种问题的最佳调谐参数。
init-ratio-50p ：解决方案比当前的解决方案在运行开始时以50％的概率接受。end-ratio-50p ：解决方案比当前的解决方案在运行结束时以50％的概率接受。end-ratio-50p-refers-to-initial ：如果设置为true ，则在end-ratio-50p的描述中替换为“初始一个”。换句话说，与初始解决方案相比，与当前解决方案相比，始终评估新解决方案的质量。temperature-decrease-is-linear ：如果为true ，则从开始到末端温度的减小是线性的，否则指数为指数。指数下降是模拟退火文献中的标准，但建议在我们的论文中进行线性减少。reheating ：是否要在一定间隔重新注入温度。reheating-coefficient ：如果reheating是true ，则通过增加温度的数量。reheating-times ：在运行期间增加温度多少次。magic-number-exponent ：Ropke和Pissinger的原始实现的所谓“魔术号”（请参阅上面的参考）。start-threshold ：跑步开始时的阈值。end-threshold ：跑步结束时阈值。threshold-decrease-is-linear ：阈值是在开始值和结束值之间线性（ true ）还是指数（ false ）的阈值。initial-water-level-ratio ：乘数乘以初始溶液的成本，以获得初始水位。water-level-decrease-pct ：每次迭代时水位的降低百分比降低。start-deviation ：运行开始时的最大允许偏差。end-deviation ：运行结束时的最大末端偏差。deviation-decrease-is-linear ：偏差是在开始值和最终值之间呈线性（ true ）还是指数（ false ）。list-size ：晚期吸收率列表的大小。allow-non-worsening ：是否始终接受不加工的新解决方案。initial-water-level-ratio ：乘数乘以初始溶液的成本，以获得初始水位。 gap-to-increase-water-level ：阈值差距以重新施加水位。 water-level-increase-pct ：溶液差的百分比，在增加相期间水位增加。 water-level-decrease-exp-factor ：降低水位时使用的指数因子（我们论文中的三角洲）。start-probability ：运行开始时的接受概率。end-probability ：运行结束时的接受概率。probability-decrease-is-linear ：概率是在开始值和结束值之间线性（ true ）还是指数（ false ）降低。 该软件是根据GNU公共许可证版本3版获得许可的。有关更多信息，请参见文件LICENSE 。
