adaptive large neighbourhood search
v0.2
Dies ist nur eine C ++ -Kuschinformation des (parallelen) adaptiven großen Nachbarhod-Suchalgorithmus, der von Ropke und Pisinger entwickelt wurde. Der Code basiert locker auf der ursprünglichen Implementierung, die Stefan Ropke freundlicherweise mit mir geteilt hat.
Das ursprüngliche ALNS -Framework wurde in diesem Artikel entwickelt:
@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 }
}Diese Implementierung enthält auch mehrere Akzeptanzkriterien, wie sie in dem Papier einen Vergleich der Akzeptanzkriterien für die adaptive große Nachbarschaftssuche Metaheuristic (Preprint) eingeführt wurden. Wenn Sie diese Software verwenden, zitieren Sie bitte dieses letzte Papier wie folgt:
@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 }
}Funktionen werden im Code mit Doxygen -Syntax gründlich dokumentiert. Da dies ein metaheuristisches Framework ist, muss der Benutzer die problemspezifischen Teile implementieren. In Bezug auf den Code bedeutet dies, dass der Benutzer die nachstehend beschriebenen Komponenten bereitstellen muss.
Der Benutzer muss implementieren:
getInstanceSize() , die die Größe der Instanz zurückgibt (z. B. die Anzahl der Scheitelpunkte in einer TSP -Instanz).getCost() die eine Kosten zur Minimierung zurückgibt (z. B. die Länge einer TSP -Tour).InitialSolutionCreator um eine erste Lösung für das Problem zu erzeugen. Sobald dies an Ort ist, kann der Benutzer eine Instanz des PALNS Objekts erstellen. Zum Beispiel:
auto alns = PALNS<TSPInstance, TSPSolution>{instance}; Wenn TSPInstance die Klassenmodellierung der Probleminstanz und TSPSolution ist, ist die Klassenmodellierung der Problemlösung. Der Benutzer muss mindestens die oben genannten Funktionen liefern. Zum Beispiel:
std:: uint32_t TSPInstance::getInstanceSize () const {
return this -> numberOfVertices ;
}
double TSPSolution::getCost () const {
return this -> tourLength ;
}Da die ALNS -Methode mit einer konkreten Lösung beginnt, muss der Benutzer einen ersten Lösungsersteller liefern:
struct TSPRandomSolutionCreator : InitialSolutionCreator<TSPSolution, TSPInstance> {
TSPSolution create_initial_solution ( const TPSInstance& instance, std::mt19937& mt) {
return TSPSolution::shuffled_vertices (mt);
}
} Zur Reproduzierbarkeit kann der Ersteller der anfänglichen Lösung einen Pseudo-Random-Zahlengenerator verwenden, der vom Alns-Framework vom Typ std::mt19937 (aus dem <random> Header) übergeben wurde.
Die Zerstörungs- und Reparaturmethoden ergeben sich jeweils aus Basisklassen DestroyMethod und RepairMethod . Eine Klasse, die von DestroyMethod erbt, muss zwei Methoden implementieren:
void destroy_solution(Solution sol&, std::mt19937& mt) , das eine Lösung durch Referenz (und ein PRNG, falls Sie es benötigen) nimmt und an Ort und Stelle zerstört.std::unique_ptr<DestroyMethod<Solution>> clone() const , das ein unique_ptr zur Basisklasse zurückgibt DestroyMethod klonieren Sie die Zerstörungsmethode. In ähnlicher Weise muss eine Klasse, die von RepairMethod erbt, implementiert:
void repair_solution(Solution& sol, std::mt19937& mt) , die eine (zerstörte) Lösung durch Bezugnahme (und eine PRNG, falls Sie es benötigen) und repariert sie an Ort.std::unique_ptr<RepairMethod<Solution>> clone() const , das ein unique_ptr zur Basisklasse RepairMethod kloniert, die die Reparaturmethode kloniert.Zum Beispiel:
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>>();
}
}; Der Benutzer kann zwischen einer der vordefinierten Akzeptanzkriterien oder der Implementierung seines eigenen Erbens aus der AcceptanceCriterion wählen. Eine praktische Möglichkeit, den Algorithmus zu überwachen und nicht standardmäßige Aktionen während des Lösungsprozesses auszuführen, besteht darin, ein Besucherobjekt bereitzustellen, das von AlgorithmVisitor vererbt wird. Der Algorithmus -Besucher muss die folgenden Rückrufe implementieren:
on_algorithm_start , das vor der ersten ALNS -Iteration aufgerufen wird.on_prerun_end , das aufgerufen wird, wenn die Pre-Run abgeschlossen ist (siehe Abschnittparameter unten).on_iteration_end der am Ende jeder Iteration aufgerufen wird.on_many_iters_without_improvement , der nach einer benutzerdefinierten Anzahl aufeinanderfolgender Iterationen aufgerufen wird, ohne die beste Lösung zu verbessern (siehe Abschnittparameter unten). Alle Parameter des metaheuristischen Frameworks sind Params.json der Bearbeitungsdatei festgelegt. Sie werden unten beschrieben:
prerun-iterations : Die Anzahl der anfänglichen Iterationen, mit denen der Algorithmus versuchen kann, die Akzeptanzparameter automatisch abzustimmen. Dies ist nicht obligatorisch und kann auf Null gesetzt werden.total-iterations : Eine harte Begrenzung der Anzahl der Iterationen.timeout-s : Eine harte Begrenzung der CPU-Zeit des Algorithmus.iters-without-improvement-max : Eine harte Begrenzung der Anzahl der aufeinanderfolgenden Iterationen ohne Verbesserung der besten Lösung. Es beendet den Lauf frühzeitig, wenn es in einer flachen Landschaftssituation steckt.iters-without-improvement-alarm : Wenn gesetzt, und wenn der Benutzer einen Algorithmus-Besucher bereitstellt, werden wir nach vielen aufeinanderfolgenden Iterationen die Methode des Besuchers on_many_iters_without_improvement nennen. Der Benutzer kann diesen Mechanismus verwenden, um der lokalen Optima zu entkommen. Zum Beispiel kann es eine stärkere Zerstörungsmethode oder eine Diversifizierungsheuristik anwenden.iterations-without-syncing-threads : In der parallelen Version des Algorithmus ist dies die Anzahl der Iterationen, bei denen Threads keine Informationen synchronisieren und sich wie unabhängige Kopien des Alns-Algorithmus verhalten. Bei der Threadsynchronisation werden die Akzeptieren/Zerstörergewichte und die aktuelle Lösung geteilt.prob-return-to-best-known : Bei jeder Iteration ersetzt die bekannteste Lösung die aktuelle Lösung durch diese Wahrscheinlichkeit. Null ist ein guter Standard, aber der Benutzer kann einen höheren Wert festlegen, um die Intensivierung gegenüber der Diversifizierung zu bevorzugen.acceptance-criterion : Eines der vordefinierten Akzeptanzkriterien. Mögliche Werte sind in den (nicht verwendeten) Parameterschlüssel acceptance-criterion-possible-values aufgeführt.acceptance-params-base : Einige der Akzeptanzparameter variieren im Verlauf des Algorithmus-Laufs. Dieser Parameter, der die Werte time und iterations übernehmen kann, gibt an, ob die Zeitlimit ( timeout-s ) oder die Iterationengrenze ( total-iterations ) in Betracht gezogen werden sollte, um zu schätzen, wann der Lauf vorbei ist.scores : Dies sind die Multiplikatoren, die zur Aktualisierung der Zerstörungs-/Reparaturwerte bei jeder Iteration verwendet werden. Benutzer sollten vier Multiplikatoren bereitstellen:global-best , wenn die neue Lösung besser ist als die bisher beste Lösung, sonstimproved wenn die neue Lösung besser ist als die aktuelle Lösung, ansonstenaccepted wenn die neue Lösung durch das Akzeptanzkriterium akzeptiert wurde.decay , bestimmt, wie schnell die obigen drei Werte die Bewertungen der Methoden beeinflussen. Ein vernünftiger Standard ist nur etwas weniger als 1,0, um sicherzustellen, dass sich die Ergebnisse reibungslos ändern.parameter-tuning-file : Wenn die Parameterabstimmung durchgeführt wird, ist dies der Dateiname, bei dem die Ergebnisse gespeichert werden.results-log-basename : Basisname für die Ergebnisdateien. Im Folgenden listen wir Parameter in Bezug auf die Akzeptanzkriterien auf. Wir fordern die Benutzer auf, sich auf das Papier von Akzeptanzkriterien zu verweisen, um die Rolle jedes Parameters und die nachstehend verwendete Terminologie besser zu verstehen. Das Papier enthält auch die besten abgestimmten Parameter über eine Vielzahl von Problemen, die gelöst sind.
init-ratio-50p : Lösungen, die so viel schlimmer als die aktuelle Lösungen sind, werden zu Beginn des Laufs mit einer Wahrscheinlichkeit von 50% akzeptiert.end-ratio-50p : Lösungen, die so viel schlimmer als die aktuelle Lösungen mit 50% Wahrscheinlichkeit am Ende des Laufs akzeptiert werden.end-ratio-50p-refers-to-initial : Wenn Sie auf true gesetzt sind, in der Beschreibung des end-ratio-50p ersetzen Sie "aktuelles" durch "initial One". Mit anderen Worten, bewerten Sie immer die Qualität neuer Lösungen im Vergleich zur anfänglichen Lösung und nicht mit der aktuellen Lösung.temperature-decrease-is-linear : Wenn true , ist die Abnahme von Beginn bis zur Endtemperatur linear, ansonsten ist es exponentiell. Eine exponentielle Abnahme ist der Standard in der simulierten Annealing -Literatur, aber in unserem Artikel wird eine lineare Abnahme empfohlen.reheating : Ob Sie die Temperatur in bestimmten Abständen wieder erhöhen sollen.reheating-coefficient : Wie viel ist, wie viel die Temperatur erhöht, wenn reheating true ist.reheating-times : Wie oft, um die Temperatur während des Laufs zu erhöhen.magic-number-exponent : Die sogenannte "magische Nummer" von Ropke und Pisssingers ursprüngliche Implementierung (siehe Referenz oben).start-threshold : Schwelle zu Beginn des Laufs.end-threshold : Schwelle am Ende des Laufs.threshold-decrease-is-linear : Ob der Schwellenwert linear ( true ) oder exponentiell ( false ) zwischen Start- und Endwerten abnimmt.initial-water-level-ratio : Multiplikator mit den Kosten der anfänglichen Lösung, um den anfänglichen Wasserstand zu erhalten.water-level-decrease-pct : prozentuale Abnahme des Wasserspiegels bei jeder Iteration.start-deviation : Maximum erlaubte Abweichung zu Beginn des Laufs.end-deviation : Maximale Endabweichung am Ende des Laufs.deviation-decrease-is-linear : Ob die Abweichung linear ( true ) oder exponentiell ( false ) zwischen den Start- und den Endwerten abnimmt.list-size : Größe der List der späten Akzeptanz.allow-non-worsening : Ob immer eine neue Lösung nicht annimmt.initial-water-level-ratio : Multiplikator mit den Kosten der anfänglichen Lösung, um den anfänglichen Wasserstand zu erhalten. gap-to-increase-water-level : Schwellenlücke zur Wiederaufnahme des Wasserstandes. water-level-increase-pct : Prozentsatz der Lösungsdifferenz, durch die der Wasserstand während der Erhöhungsphasen zunimmt. water-level-decrease-exp-factor : Exponentialfaktor (Delta in unserem Artikel), um den Wasserstand zu verringern.start-probability : Akzeptanzwahrscheinlichkeit zu Beginn des Laufs.end-probability : Akzeptanzwahrscheinlichkeit am Ende des Laufs.probability-decrease-is-linear : Ob die Wahrscheinlichkeit linear ( true ) oder exponentiell ( false ) zwischen den Start- und den Endwerten abnimmt. Diese Software ist unter der GNU Public Lizenz Version 3. lizenziert. Weitere Informationen finden Sie unter der LICENSE .
