Hybride evolutionäre Algorithmen für Graph-Probleme

Forschungsprojekt P 13602Hybride evolutionäre Algorithmen für Graph-ProblemeGünther RAIDL28.06.1999 In verschiedenen praktischen Bereichen wie z.B. der Entwicklung von Kommunikationsnetzwerken oder dem Design elektronischer Schaltkreise tritt oft das Problem auf, alle Knoten eines gegebenen Graphen auf kürzeste oder kostensparendste Weise zu verbinden. Diese als minimum spanning tree problem (MSTP) bekannte Aufgabe kann normalerweise mit existierenden Algorithmen effizient gelöst werden. In vielen praktischen Fällen sind jedoch unterschiedliche Randbedingungen zu berücksichtigen, die eine Anwendung der klassischen Verfahren und damit eine effiziente Lösbarkeit unmöglich machen. So kann die Anzahl der in einem Knoten mündenden Kanten (der Grad eines Knotens) auf ein bestimmtes Maximum beschränkt sein. Manchmal wird auch verlangt, daß die Länge der Verbindung eines jeden Knotenpaares eine vorgegebene Obergrenze nicht übersteigt oder die Anzahl der auf dieser Verbindung liegenden Zwischenknoten nicht größer als ein bestimmtes Maximum ist. Für derartige Probleme sind keine effizienten exakten Algorithmen, d.h. Algorithmen mit polynomialen Zeitaufwänden, bekannt. Eine dem MSTP ähnliche Aufgabe ist das Steiner-Problem im, Graphen (SPG): Hierbei sind nicht alle Knoten des Graphen, sondern nur eine vorgegebene Teilmenge auf kürzestmögliche Weise zu verbinden. Für dieses Problem ist allgemein bekannt, daß es NP-vollständig ist. Es existieren jedoch Heuristiken und Näherungsverfahren, die relativ gute, annähernd optimale Lösungen in akzeptabler Zeit ermitteln. Sind aber wiederum Randbedingungen, wie sie für das MSTP bereits beschrieben wurden, zu berücksichtigen, so können diese Heuristiken und Näherungsverfahren im allgemeinen nicht eingesetzt werden oder führen zu schlechten Ergebnissen. Vor allem in den letzten Jahren hat sich gezeigt, daß evolutionäre Algorithmen (EAs) für viele komplexe Probleme einen Ansatz darstellen, um in akzeptabler Zeit gute Naherungslösungen zu finden. Wie verschiedene Publikationen belegen, sind EAs grundsätzlich auch für die beschriebenen Graphen-Probleme anwendbar, doch stellen sich hierbei verschiedene Fragen, die die Effizienz wesentlich beeinflussen. Zum Beispiel gibt es sehr unterschiedliche Möglichkeiten, eine potentielle Lösung zum MSTP (SPG), d.h. einen Teilbaum im Graphen, im EA zu repräsentieren. Weiters ist entscheidend, mit welchen Variationsoperatoren aus einer oder mehreren potentiellen Lösungen neue, möglicherweise bessere Lösungen im EA erzeugt werden. Oft bringt auch die Kombination von EAs mit klassischen Heuristiken oder lokalen Optimierungsmethoden (Hybridisierung) entscheidende Vorteile, doch ist unklar, in welcher Weise dies am effizientesten funktioniert. Im Rahmen dieses Projekts soll unter anderem untersucht werden, wie die beschriebenen Randbedingungen am effektivsten berücksichtigt werden können. Bestehende EA-Ansätze für ähnliche Probleme werden hierzu entsprechend adaptiert und verglichen, Ideen zu neuen Ansätzen sollen verwirklicht werden. Vor allem stellt aber auch die Kombination von EAs mit Heuristiken und lokalen Optimierungsmethoden ein zentrales Thema dar. Heuristic-based encoding - eine Art "intelligente" Form, potentielle Lösungen im EA zu repräsentieren - ist hierzu eine vielversprechende Technik, die sich bereits in vorangegangenen Arbeiten für andere Probleme bewährt hat. Die unterschiedlichen Ansätze werden auf Basis zahlreicher Testprobleme charakterisiert und untereinander, aber auch mit traditionellen Optimierungsmethoden verglichen. Generelles Ziel ist es also, für reale Problemstellungen in den Bereichen MSTP und SPG möglichst effiziente Optimierungsmethoden zur näherungsweisen Lösung zu finden. Die Ergebnisse dieses Projekts sollten jedoch auch für die Entwicklung von Strategien zur Lösung anderer kombinatorischer Optimierungsaufgaben von Nutzen sein.