Wolf, M. (2009). Ein Lösungsarchiv-unterstützter evolutionärer Algorithmus für das GMST-Problem [Diploma Thesis, Technische Universität Wien]. reposiTUm. http://hdl.handle.net/20.500.12708/186093
E186 - Institut für Computergraphik und Algorithmen
-
Date (published):
2009
-
Number of Pages:
62
-
Keywords:
Lösungsarchiv; GMST; Evolutionäre Algorithmen; Generalized Minimum Spanning Tree
de
solution archive; GMST; evolutionary algorithms; Generalized Minimum Spanning Tree
en
Abstract:
Das Generalized Minimum Spanning Tree (GMST)-Problem ist ein NP-schweres kombinatorisches 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.<br />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.<br />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.<br />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.<br />Unter anderem wird eine Variante vorgestellt, bei der mehrere Tries verwendet werden, von denen jeder nur einen Teil der Lösung enthält.<br />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.<br />
de
The Generalized Minimum Spanning Tree (GMST) problem is an NP-hard combinatorial 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.<br />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.<br />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.<br />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.<br />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.
en
Additional information:
Abweichender Titel laut Übersetzung der Verfasserin/des Verfassers Zsfassung in engl. Sprache