adaptive large neighbourhood search
v0.2
これは、RopkeとPisserによって考案された（並列）適応型大型Neighbourhhod検索アルゴリズムのヘッダーのみの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 }
}この実装には、適応的な大型近隣検索メタリスティック（プレリント）の受け入れ基準の比較を論文で紹介したため、複数の受け入れ基準も含まれています。このソフトウェアを使用する場合は、次のようにこの最後の論文を引用してください。
@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()で実装します。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);
}
}再現性のために、最初のソリューション作成者は、 std::mt19937のタイプのALNSフレームワークで渡された擬似ランダム数ジェネレーターを使用できます（ <random>ヘッダーから）。
破壊および修復方法は、それぞれ基本クラスDestroyMethodおよびRepairMethodから派生します。 DestroyMethodから継承するクラスは、2つの方法を実装するものとします。
void destroy_solution(Solution sol&, std::mt19937& mt)は、参照（および必要に応じてPRNG）によって解決策を取り、その場所に破壊します。std::unique_ptr<DestroyMethod<Solution>> clone() constは、 unique_ptrベースクラスDestroyMethodに戻し、破壊方法をクローニングします。同様に、 RepairMethodから継承するクラスは、次のことを実装するものとします。
void repair_solution(Solution& sol, std::mt19937& mt)は、参照（および必要に応じてPRNG）によって（破壊された）ソリューションを採取し、その場所に修理します。std::unique_ptr<RepairMethod<Solution>> clone() const 、修理方法をクローニングするベースクラスのRepairMethodにunique_ptr _ptrを返します。例えば：
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から継承する訪問者オブジェクトを提供することです。アルゴリズムの訪問者は、次のコールバックを実装する必要があります。
on_algorithm_startは、最初のalnsイテレーションの前に呼び出されます。on_prerun_endは、プリランが終了したときに呼び出されます（以下のセクションパラメーターを参照）。on_iteration_end 。on_many_iters_without_improvement最適なソリューションを改善することなく、ユーザー定義の連続反復の数の後に呼び出されます（以下のセクションパラメーターを参照）。Metaheuristic Frameworkのすべてのパラメーターは、編集ファイルParams.jsonに設定されています。以下に説明します。
prerun-iterations ：アルゴリズムが受け入れパラメーターを自動調整しようと試みるために使用できる初期反復の数。これは強制的ではなく、ゼロに設定できます。total-iterations ：反復回数の厳しい制限。timeout-s ：アルゴリズムのCPU時間の厳しい制限。iters-without-improvement-max ：最良のソリューションを改善することなく、連続した繰り返しの数の厳しい制限。フラットな風景の状況で立ち往生したとき、それは早期に実行を終了します。iters-without-improvement-alarm ：設定されている場合、およびユーザーがアルゴリズムの訪問者を提供する場合、この多くの連続した反復の後、訪問者のon_many_iters_without_improvementメソッドを呼び出します。ユーザーはこのメカニズムを使用して、ローカルオプティマを逃れようとすることができます。たとえば、より強力な破壊方法、または多様化ヒューリスティックを適用できます。iterations-without-syncing-threads ：アルゴリズムの並列バージョンでは、これはスレッドが情報を同期せず、ALNSアルゴリズムの独立したコピーのように振る舞わない反復の数です。スレッドの同期により、ウェイトを受け入れる/破壊する現在のソリューションが共有されます。prob-return-to-best-known ：各反復で、最も既知のソリューションは、現在のソリューションをこの確率に置き換えます。 Zeroは優れたデフォルトですが、ユーザーは多様化よりも強化を支持するために高い値を設定できます。acceptance-criterion ：事前定義された受け入れ基準の1つ。考えられる値は、（未使用の）パラメーターキーアacceptance-criterion-possible-valuesにリストされています。acceptance-params-base ：Acceptanceパラメーターの一部は、アルゴリズムの実行中に異なります。このパラメーターは、 timeがかかり、 iterations時間制限（ timeout-s ）または反復制限（ total-iterations ）を検討して、実行が終了する時期を推定する必要があるかどうかを指定します。scores ：これらは、各反復で破壊/修理スコアを更新するために使用される乗数です。ユーザーは4つの乗数を提供する必要があります。global-bestimprovedaccepted 。decayは、上記の3つの値がメソッドのスコアにどれだけ速く影響するかを決定します。正気なデフォルトは、スコアがスムーズに変化することを確認するために、1.0未満です。parameter-tuning-file ：パラメーターチューニングを実行する場合、これは結果が保存されるファイル名です。results-log-basename ：結果ファイルのベースネーム。 以下では、受け入れ基準を比較してパラメーターをリストします。私たちは、各パラメーターの役割と以下で使用される用語をよりよく理解するために、受け入れ基準論文を参照することをユーザーに促します。このペーパーは、さまざまな問題が解決された場合に最適なパラメーターを提示します。
init-ratio-50p ：ソリューション現在のものよりもはるかに悪いものは、実行の開始時に50％の確率で受け入れられています。end-ratio-50p ：ソリューション現在のものよりもはるかに悪いものは、実行の終了時に50％の確率で受け入れられています。end-ratio-50p-refers-to-initial ： trueに設定されている場合、 end-ratio-50pの説明では、「現在の」を「初期One」に置き換えます。言い換えれば、現在のソリューションではなく、初期ソリューションと比較して、新しいソリューションの品質を常に評価します。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参照してください。
