Ein neues Lösungsarchiv für das Generalized Minimum Spanning Tree-Problem

Abstract

Diese Arbeit behandelt das Generalized Minimum Spanning Tree-Problem (GMST), ein kombinatorisches Optimierungsproblem, das auf dem Minimum Spanning Tree (MST)-Problem basiert. Das GMST ist eine Verallgemeinerung des klassisches MST-Problems, das darin besteht, für einen gegebenen Graphen einen minimalen Spannbaum zu finden. Die Verallgemeinerung besteht darin, für einen gegebenen Graphen einen minimalen Spannbaum zu finden. Für eine kontrete Lösung wird ein Spannbaum gebildet, der aus jedem Cluster genau einen Knoten verwendet.<br />Während das MST in polynomieller Zeit lösbar ist, ist das GMST NP-schwierig.<br />In dieser Arbeit wird ein evolutionärer Algorithmus (EA) verwendet, der ein trie-basiertess Lösungsarchiv, basierend auf zwei verschiedenen Betrachtungsweisen des GMST, verwendet. Die erste Sichtweise besteht darin, die Knoten in den jeweilgen festzulegen. Das das verbleibende Problem dem MST entspricht und somit in polynomieller Zeit gelöst werden kann, kann eine Lösung durch die Angabe der Knoten spezifiziert werden.<br />Die zweite Vorgehensweise ist dann, die globalen Verbindungen zwischen den Clustern festzulegen. Auch hier kann das verbleibende Problem in polynomieller Zeit gelöst werden, und zwar mittels dynamischer Programmierung.<br />In einem Lösungsarchiv können Lösungen gespeichert werden, um einerseits Duplikate zu erkennen, und andererseits eine neue, noch nicht besuchte Lösung zu bekommen. Da ein Lösungsarchiv für die erste Sichtweise bereits implementiert wurde, wurde in dieser Arbeit eines für die zweite Sichtweise entworfen. Diese Lösungsarchiv basiert auf der Sichtweise, die globalen Verbindungen festzulegen. Es werden zwei verschiedene Darstellungen von Spannbäumen verwendet, die diese globalen Kanten repräsentieren, nämlich die Darstellung der Predecessor sowie Prüfernummern. Außerdem wurden die beiden Archive kombiniert, um bessere Lösungen als mit einem alleine zu erhalten Wie die Tests gezeigt haben, konnten mit dem neuen Archiv bessere Lösungen im Vergleich zum EA gefunden werden. Mit der Verwendung beider Archive konnten noch bessere Lösung gefunden werden, wobei diese Version einen größeren Speicherverbrauch aufweist.<br />

This thesis deals with the Generalized Minimum Spanning Tree Problem (GMST), a combinatorial optimization problem based on the Minimum Spanning Tree Problem (MST).<br />The GMST ist a generalization of the classic MST Problem which consists in finding a minimum spanning tree for a given graph. The generalization consists in partitionizing the nodes in clusters. In order to obtain a concrete solution, a spanning tree in formed, which spans exactly one node from each cluster. While the MST is solvable in polynomial time, the GMST is NP-hard.<br />In this thesis, an evolutionary algorithm (EA) is used which is complemented by a trie-based solution archive using two different views of the GMST. The first view is concerned with selecting the node for each cluster. As the remaining problem equals to the MST, the solution can be encoded by specifying the nodes. The second view is concerned with specifying the global edges between the clusters. The remaning problem can be solved using dynamic programming. Using a solution archive, it is possible to store solution generated by the EA in order to detect duplicates and furthermore to convert such duplicates into new solutions which have not yet been examined. As a solution archive for the first view has already been implemented, this thesis in concerned with designing an archive for the second view. This solution archive is based on the view to specify the global edges. Two different encodings of spanning trees are used which represent these global edges, namely the Predecessor-encoding and the Prüfer-encoding.<br />Furthermore both archives have been combined to improve the obtained solutions.<br />As tests have shown, using the archive improves the quality of the solutions compared to the pure EA. Using both archives combined, even better results can be obtained at the expense of a higher memory usage.