[Zurück]

M. Wolf:
"Ein lösungsarchiv-unterstützter evolutionärer algorithmus für das generalized minimum spanning tree-problem";
Betreuer/in(nen): G. Raidl, B. Hu; Institute of Computer Graphics and Algorithms, 2009.

Das Generalized Minimum Spanning Tree (GMST)-Problem ist ein Optimierungsproblem. Gegeben ist ein Graph, dessen Knoten in Cluster eingeteilt sind, und gesucht wird ein minimaler Spannbaum, wobei aus jedem Cluster genau ein Knoten gewählt werden muss.
In dieser Arbeit wird ein evolutionärer Algorithmus verwendet, um dieses Problem zu behandeln. Ein Problem von derartigen Algorithmen sind die häufig mehrfach auftretenden Lösungen. Die gleiche Lösung mehrmals zu evaluieren, kostet unnötig Zeit. Deshalb wird zur Verbesserung des Algorithmus ein Lösungsarchiv basierend auf einer Trie-Struktur verwendet.
Alle generierten Lösungen werden in dieses Archiv gespeichert. Stellt man dabei fest, dass die Lösung schon vorhanden ist, kann sie auf effiziente Weise in eine neue, garantiert noch nicht untersuchte Lösung umgewandelt werden. Auf diese Art können in der gleichen Laufzeit mehr unterschiedliche Lösungen untersucht werden.
Derartige Lösungsarchive wurden bislang nur bei Problemen angewendet, deren Lösungen als Bitstrings repräsentiert wurden. Das ist beim GMSTP nicht möglich, weswegen der Trie eine andere Struktur hat, die zusätzliche Überlegungen bezüglich des Speicherplatzes nötig macht. Unter anderem wird eine Variante vorgestellt, bei der mehrere Tries verwendet werden, von denen jeder nur einen Teil der Lösung enthält.
Es zeigt sich, dass mit Hilfe dieses Archivs bei vielen Instanzen bessere Lösungen gefunden werden können. Weiter verbessert werden können die Ergebnisse durch eine Optimierung, die auf einer alternativen Repräsentation von Lösungen basiert.

Abstract
The Generalized Minimum Spanning Tree (GMST) problem is an optimization problem. Given a graph whose node set is partitioned into clusters, the goal is to find a minimum spanning tree that contains exactly one node from each cluster.
In this work an evolutionary algorithm is used to solve the GMSTP. One problem with this kind of algorithms is the frequently appearing duplicate solutions. Evaluating the same solution multiple times wastes time while offering no new information. For this reason, a solution archive based on a trie structure is used to improve the algorithm.
Every newly generated solution is stored in this archive. If the solution is already present, it can be efficiently converted into one that is guaranteed to be new and not yet evaluated. This allows the algorithm to evaluate more unique solutions using the same runtime.
Until now, solution archives of this type have only been applied to problems whose solutions are represented as bit strings. Since this is not possible for the GMSTP, it leads to a different structure for the trie and requires additional considerations concerning memory usage. A variant using multiple tries is also introduced, where each individual trie stores only partial solutions.
The results show that this archive can lead to better solutions for many instances. Additionally, a different kind of optimization based on an alternate representation of solutions can further improve solutions.

http://publik.tuwien.ac.at/files/PubDat_176845.pdf