A novel metaheuristic approach for the quadratic assignment problem

Titel in Übersetzung: Ein neuer metaheuristischer Ansatz für das quadratische Zuordnungsproblem

Stefan Christopher Nehl

Publikation: Thesis / Studienabschlussarbeiten und HabilitationsschriftenMasterarbeit

27 Downloads (Pure)

Abstract

Das 1957 von Koopmans und Beckmann eingeführte Quadratische Zuordnungsproblem (QAP) stellt eine der zentralen Herausforderungen in der kombinatorischen Optimierung dar und dient als mathematisches Rückgrat für zahlreiche Anwendungen. Als NP-hard eingestuft, hat es sich als schwer erwiesen, optimale Lösungen für Instanzen größer als 20, zu finden. Überdies zeigt der traditionelle Algorithmus Branch and Bound seine Ineffizienz für dieses Problem, primär aufgrund des Fehlens von guten Schranken für das QAP. Viele schwierige Probleme der kombinatorischen Optimierung, darunter auch das QAP, haben in den vergangenen Jahrzehnten zur Einführung von Metaheuristiken geführt. Zu diesen zählt auch Scatter Search, aus der Familie der evolutionären Algorithmen. Metaheuristiken dienen als übergreifender Rahmen, der in erster Linie dazu entwickelt wurde, den Beschränkungen von Verbesserungsmethoden entgegenzuwirken. Dies geschieht, indem sie suboptimale Züge ermöglichen, um lokale Extrema zu überwinden. Insbesondere die flexible Struktur von Scatter Search ermöglicht die Untersuchung verschiedener Strategien während seiner Ausführung. Die Grundform von Scatter Search enthält eine Diversification Method, eine Improvement Method, eine Reference Set Update Method, eine Subset Generation Method und eine Solution Combination Method. In dieser Arbeit wurden verschiedene Algorithmen für die in Scatter Search verwendeten Methoden analysiert. Weiterhin wurde eine Implementierung von Path Relinking als zusätzliche Solution Generation Method implementiert. Die Idee hinter Path Relinking ist es, Trajektorien zu erkunden, die qualitativ hochwertige Lösungen miteinander verbinden. Die Implementierung erfolgte in C# und folgte der Scatter Search-Architektur, die von Nebro A. et al. 2008 vorgestellt wurde. Zusätzlich zur Implementierung des Frameworks wurden auch parallelisierte Algorithmen implementiert. Zur Vorauswahl der Kombinationen verschiedener Algorithmen, und um die Algorithmen zu vergleichen und die Effizienz einer parallelen Berechnung zu prüfen, wurden Benchmarks durchgeführt. Das Framework Scatter Search wurde über mehrere Instanzen unterschiedlicher Größen getestet. Die Testreihe umfasste zehn Instanzen mit bekannten optimalen Zielfunktionswerten und weitere zehn Instanzen, für die nur eine untere Grenze bekannt ist. Die ersten zehn Instanzen wurden für die endgültige Auswahl des Algorithmus verwendet und halfen bei der Einstellung der Parameter. Jeder Test wurde mit einer vorgegebenen Laufzeit von zehn Minuten durchgeführt. Im ersten Test lieferte der Algorithmus Scatter Search Ergebnisse, welche zwischen 0 und 35 % schlechter als der optimale Zielfunktionswert waren. In einigen Fällen waren die Ergebnisse jedoch um mehr als 100 % schlechter als der optimale Zielfunktionswert. Daher wurden einige Verbesserungen am Scatter Search-Rahmen vorgenommen. Eine davon war eine dynamische Anpassung der Größe der Referenzmenge, wenn nach der Kombinationsmethode keine guten Permutationen gefunden wurden. Dadurch verbesserten sich die Ergebnisse derjenigen Instanzen, die zuvor schlecht abgeschnitten hatten. Nach der Verbesserung wurden die beiden besten Kombinationen von Algorithmen ausgewählt und eine weitere Parameterabstimmung vorgenommen. Nach dem Testen jeder Instanz mit dem Scatter Search Framework lagen die Ergebnisse innerhalb eines Zeitrahmens von zehn Minuten zwischen 0 und 30 %, mit Ausnahmen, über dem Optimum oder der unteren Grenze. Die Modularität des Frameworks erlaubt jedoch eine Kombination verschiedener Algorithmen, was eine Anpassung an spezifische Probleme ermöglicht.
Titel in ÜbersetzungEin neuer metaheuristischer Ansatz für das quadratische Zuordnungsproblem
OriginalspracheEnglisch
QualifikationDipl.-Ing.
Gradverleihende Hochschule
  • Montanuniversität
Betreuer/-in / Berater/-in
  • Staněk, Rostislav, Betreuer (intern)
Datum der Bewilligung20 Okt. 2023
DOIs
PublikationsstatusVeröffentlicht - 2023

Bibliographische Notiz

nicht gesperrt

Schlagwörter

  • Quadratisches Zuordnungsproblem
  • QAP
  • NP-schwer
  • Metaheuristik
  • Scatter Search
  • Path Relinking
  • Evolutionärer Algorithmus

Dieses zitieren