Lösungsarchive für Evolutionäre Kombinatorische Optimierung

In diesem Projekt befassen wir uns mit einer Erweiterung für Genetische Algorithmen (GAs) und Memetischen Algorithmen (MAs), nämlich dem vollständigen Lösungsarchiv. Eine bekannte Schwäche von GAs (MAs) liegt darin, dass bereits betrachtete Lösungen während der Optimierung erneut evaluiert werden können. Im Allgemeinen macht dies keinen Sinn und verschwendet wertvolle Zeit, die besser genutzt werden könnte. Das Lösungsarchiv speichert alle betrachtete Lösungen in einer kompakten Datenstruktur. Für neu generierte Lösungen wird zuerst überprüft, ob sie bereits betrachtet wurden. Gegebenenfalls konvertiert eine effiziente Transformationsoperation die Duplikate mittels kleinen Modifikationen in garantiert neue, unbesuchte Lösungen. Die Transformation ist das zentrale Feature, das diesen neuen Ansatz von Techniken wie klassischem Populationsmanagement und Caching von Lösungen unterscheidet. Bezüglich Datenstruktur für das Archiv sind Varianten von Tries unsere primäre Wahl, welche bisher vorwiegend in Wörterbuchapplikationen eingesetzt wurden um große Mengen von Wörtern zu speichern. Sie ermöglichen es die essenziellen Einfüge-, Such- und Transformationsoperationen in konstanter Laufzeit in Bezug auf die Anzahl der gespeicherten Lösungen zu implementieren. Zusätzlich zur Basisfunktionalität befassen wir uns mit erweiterten Techniken wie Bounding- Strategien zum Einschränken des Suchraums, heuristisch geleiteten Transformationen und Methoden, um die Skalierbarkeit zu verbessern. Wir betrachten als Anwendungsfälle drei kombinatorische Optimierungsprobleme, um die problemspezifische Umsetzung und die Auswirkung des Lösungsarchivs zu untersuchen: das generalisierte minimale Spannbaumproblem, das probabilistische Handlungsreisendenproblem, und das diskrete (r|p)-Centroid Problem. Diese Probleme benutzen verschiedene direkte, indirekte bzw. unvollständige Lösungsrepräsentationen basierend auf Bit- und Integervektoren, Permutationen und Baumstrukturen, sowie Verbesserungs- und Reparaturtechniken. Neben GAs ist das Archiv auch für andere Metaheuristiken vielversprechend, daher wird auch die Verwendungsmöglichkeit für Variable Neighborhood Search, Simulated Annealing, Tabu Search, Large Neighborhood Search und Ant Colony Optimization untersucht. Das Lösungsarchiv in GAs kann als eine Kombination von Populationsmanagement, intelligenter Mutation und einer Hybridisierung mit Branch-and-Bound Konzepten betrachtet werden. Richtig eingesetzt kann das Problem von Duplikaten endlich effizient gelöst werden, ohne dabei die Struktur des GAs grundlegend verändern zu müssen. Aus theoretischer Sicht verwandelt dieses Konzept GAs in vollständige Optimierungsmethoden, die in begrenzter Zeit garantiert optimale Lösungen finden. In der Praxis erwarten wir, dass dieses Verfahren vor allem für komplexe Optimierungs-probleme mit kompakten Lösungsrepräsentationen und/oder teurer Evaluierung bzw. Dekodierung eines Genotyps wesentliche Vorteile im Sinne einer signifikanten Leistungssteigerung bringt. Existierende Vorarbeiten können bereits das große Potential des Verfahrens belegen.

Dieses Projekt behandelt eine neue Kombination von exakten und heuristischen Lösungsansätzen zur besseren Lösung schwerer kombinatorischer Optimierungsprobleme (COPs). Solche Probleme treten häufig in den Bereichen der Transportlogistik, Routenplanung, Telekommunikation, Terminplanung, Standortplanung, und in viele weiteren auf. Grundsätzliches Ziel solcher Probleme ist es, eine gültige Lösung aus einer sehr großen Menge an Möglichkeiten zu finden, die eine gegebene Zielfunktion, wie etwa Kosten, Zeit oder Profit, minimiert bzw. maximiert. In vielen Fällen sind diese Problemstellungen sehr schwierig und können daher i.A. nicht effizient gelöst werden. Algorithmen, die garantiert eine optimale Lösung finden, wie zum Beispiel Tree Search, können auf Grund ihrer hohen Laufzeit oft nicht mehr angewandt werden. Besonders wenn die Größe der Probleminstanz wächst müssen andere Lösungsansätze in Betracht gezogen werden. Metaheuristiken sind Verfahren, die häufig in relativ kurzer Laufzeit Lösungen finden, die sehr gut aber nicht notwendigerweise optimal sind. Beispielsweise sind evolutionäre Algorithmen, die im Fokus dieses Projekts standen, von der Natur inspirierte Metaheuristiken mit einem breiten Anwendungsspektrum. Ein bekannter Nachteil dieser Methoden ist allerdings, dass das Fehlen eines Langzeitgedächtnisses über den Suchverlauf oft zu unnötigen Re-evaluierungen von Kandidatenlösungen, einem Verlust der Diversität, und vorzeitiger Konvergenz führt. Diese Aspekte beeinträchtigen die Effektivität der Optimierung oft erheblich.Um diesen Problemen entgegenzuwirken haben wir uns in diesem Projekt auf die Kombination von Tree Search und evolutionären Algorithmen mittels sogenannten vollständigen Lösungsarchiven konzentriert. Ein solches Lösungsarchiv speichert alle generierten Lösungskandidaten in einer effizienten Baum-Datenstruktur und verhindert dadurch Duplikate. Immer wenn eine potentielle Duplikatlösung erkannt wird, wird diese in eine garantiert neue und üblicherweise ähnliche Lösung direkt vom Archiv konvertiert. Wendet man dieses Lösungsarchiv innerhalb einer Metaheuristik an, wird diese dadurch grundsätzlich zu einem vollständigen, exakten Lösungsverfahren, welches eine optimale Lösung bei genügend langer Laufzeit garantiert findet. In der Praxis wird ein solches optimales Lösen aber immer noch nur für kleine Probleminstanzen möglich sein und die hybride Metaheuristik i.A. früher abgebrochen werden. Speziell in diesen Situationen kann das Archiv die Performance der Metaheuristik jedoch erheblich steigern. Im Zuge dieses Projekts haben wir solche Lösungsarchive im Detail untersucht, diese mit fortgeschrittenen Methoden erweitert, und ihren Einfluss auf evolutionäre Algorithmen für zwei Klassen praxisrelevanten COPs für kompetitive Standort- und Routenplanung studiert.Die Ergebnisse auf diesen Problemen zeigten, dass vollständige Lösungsarchive in der Lage sind, die Performanz von evolutionären Algorithmen bzw. allgemeiner Metaheuristiken für COPs mit einer kompakten Lösungsrepräsentation und zeitaufwändigen Evaluierungsfunktion erheblich zu steigern. Durch sorgfältiges Design können Erweiterungen des Lösungsarchivs, die die Baumstruktur ausnutzen, zu weiteren signifikanten Verbesserungen führen. Nicht zuletzt führte dieses Projekt auch zu neuen, leistungsfähigeren state-of-the-art Lösungsverfahren für die betrachteten Problemstellungen in den Bereichen der kompetitiven Standort- und Routenplanung.