ALNS

alns ist eine allgemeine, gut dokumentierte und getestete Implementierung der Adaptive Large Neighbourhood Search (ALNS)-Metaheuristik in Python. ALNS ist ein Algorithmus, mit dem schwierige kombinatorische Optimierungsprobleme gelöst werden können. Der Algorithmus beginnt mit einer Anfangslösung. Dann iteriert der Algorithmus, bis ein Stoppkriterium erfüllt ist. In jeder Iteration werden ein Zerstörungs- und ein Reparaturoperator ausgewählt, die die aktuelle Lösung in eine Kandidatenlösung umwandeln. Diese Kandidatenlösung wird dann anhand eines Akzeptanzkriteriums bewertet und das Betreiberauswahlschema wird basierend auf dem Bewertungsergebnis aktualisiert.

alns installieren

Das alns -Paket hängt von numpy und matplotlib ab. Es kann wie gewohnt installiert werden

 pip install alns

Darüber hinaus können alns mit der optionalen MABWiser-Abhängigkeit installiert werden, um erweiterte Operatorauswahlschemata mithilfe mehrarmiger Bandit-Algorithmen zu ermöglichen:

 pip install alns[mabwiser]

Erste Schritte

Die Dokumentation finden Sie hier. Wenn Sie mit Metaheuristik oder ALNS noch nicht vertraut sind, könnte es für Sie hilfreich sein, die Einführungsseite zu ALNS zu lesen.

Die alns -Bibliothek stellt den ALNS-Algorithmus und verschiedene Akzeptanzkriterien, Bedienerauswahlschemata und Stoppkriterien bereit. Um Ihr eigenes Problem zu lösen, sollten Sie Folgendes bereitstellen:

• Ein Lösungsstatus für Ihr Problem, der eine objective() Funktion implementiert.
• Eine erste Lösung.
• Ein oder mehrere auf Ihr Problem zugeschnittene Zerstörungs- und Reparaturmitarbeiter.

Eine „Schnellstart“-Codevorlage ist hier verfügbar.

Beispiele

Wir stellen mehrere Beispielnotizbücher zur Verfügung, die zeigen, wie die ALNS-Bibliothek verwendet werden kann. Dazu gehören:

• Das Problem des Handlungsreisenden (TSP) hier. Wir lösen eine Instanz von 131 Städten mithilfe sehr einfacher Zerstörungs- und Reparaturheuristiken.
• Das Capacited Vehicle Routing Problem (CVRP) hier. Wir lösen eine Instanz mit 241 Kunden mithilfe einer Kombination aus einem gierigen Reparaturoperator und einem durch Slack induzierten Teilstring-Entfernungs- Zerstörungsoperator.
• Das Cutting-Stock-Problem (CSP) hier. Wir lösen eine Instanz mit 180 Strahlen über 165 verschiedene Größen in nur einer sehr begrenzten Anzahl von Iterationen.
• Hier das Problem der ressourcenbeschränkten Projektplanung (RCPSP). Wir lösen eine Instanz mit 90 Jobs und 4 Ressourcen unter Verwendung verschiedener Operatoren und Erweiterungstechniken aus der Literatur.
• Das Permutation Flow Shop Problem (PFSP) hier. Wir lösen eine Instanz mit 50 Jobs und 20 Maschinen. Darüber hinaus demonstrieren wir mehrere erweiterte Funktionen von ALNS, einschließlich der automatischen Anpassung des Akzeptanzkriteriums und der Hinzufügung einer lokalen Suche für Reparaturbetreiber. Wir zeigen auch, wie man ALNS-Parameter optimieren kann.

Abschließend gibt das Funktionsnotizbuch einen Überblick über die verschiedenen Optionen, die im alns -Paket verfügbar sind. Im Notizbuch verwenden wir diese verschiedenen Optionen, um ein Spielzeug-0/1-Rucksackproblem zu lösen. Das Notizbuch ist ein guter Ausgangspunkt, wenn Sie selbst verschiedene Schemata, Akzeptanz- oder Stoppkriterien anwenden möchten. Es ist hier erhältlich.

Mitwirken

Wir sind sehr dankbar für jeden Beitrag, den Sie bereit sind zu leisten. Bitte schauen Sie hier vorbei, um loszulegen. Wenn Sie eine große Änderung vornehmen möchten, ist es hilfreich, die Änderung zunächst in einer neuen GitHub-Ausgabe zu besprechen. Öffnen Sie gerne eines!

Hilfe bekommen

Fühlen Sie sich frei, hier auf GitHub ein Problem oder einen neuen Diskussionsthread zu eröffnen. Bitte senden Sie uns keine E-Mails mit Fragen, Modellierungsproblemen oder Codebeispielen. Diese lassen sich viel einfacher über GitHub besprechen als per E-Mail. Wenn Sie Ihr Problem oder Ihre Diskussion verfassen, folgen Sie bitte den Anweisungen hier.

So zitieren Sie alns

Wenn Sie alns in Ihrer Forschung verwenden, denken Sie bitte darüber nach, das folgende Papier zu zitieren:

Wouda, NA und L. Lan (2023). ALNS: eine Python-Implementierung der adaptiven Metaheuristik für die große Nachbarschaftssuche. Journal of Open Source Software , 8(81): 5028. https://doi.org/10.21105/joss.05028

Oder verwenden Sie den folgenden BibTeX-Eintrag:

 @article { Wouda_Lan_ALNS_2023 , 
  doi = { 10.21105/joss.05028 } , 
  url = { https://doi.org/10.21105/joss.05028 } , 
  year = { 2023 } , 
  publisher = { The Open Journal } , 
  volume = { 8 } , 
  number = { 81 } , 
  pages = { 5028 } , 
  author = { Niels A. Wouda and Leon Lan } , 
  title = { {ALNS}: a {P}ython implementation of the adaptive large neighbourhood search metaheuristic } , 
  journal = { Journal of Open Source Software } 
}