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 。
