Ein Lösungsarchiv mit Branch-and-Bound-Erweiterung für das Generalized Minimum Spanning Tree Problem

Abstract

In dieser Arbeit wird ein Algorithmus für das Generalized Minimum Spanning Tree-Problem (GMST) entwickelt. Beim GMST-Problem ist ein vollständiger Graph gegeben, bei dem die Knoten in Cluster partitioniert sind. Als Lösung wird ein Spannbaum gesucht, der von jedem Cluster genau einen Knoten beinhaltet und dessen Kosten minimal sind.<br />Dieses Problem ist NP-schwierig. In dieser Arbeit wird eine Heuristik für dieses Problem entwickelt.<br />Bei diesem Verfahren wird ein Evolutionärer Algorithmus (EA) mit zwei verschiedenen Lösungsarchiven verwendet. Die Lösungsarchive werden dazu benutzt Lösungen zu speichern, um Duplikate zu erkennen und diese in neue Lösungen umzuwandeln. Ein Lösungsarchiv beruht auf der "Ghosh-Kodierung", bei der die ausgewählten Knoten der Cluster einer Lösung gespeichert werden, während das andere Archiv auf der "Pop-Kodierung" beruht, bei der gespeichert wird, welche Cluster in der Lösung verbunden sind.<br />Diese Archive werden in dieser Arbeit durch eine Bounding-Strategie basierend auf dem Branch and Bound Verfahren erweitert. Dabei wird versucht im Archiv an günstigen Positionen geeignete Bounds zu berechnen, die Auskunft darüber geben, wie gut die Lösungen in diesem Bereich des Archivs höchstens sein können. Wird eine Bound gefunden, die schlechter als die beste gefunden Lösung ist, sind diese Lösungen im weiteren Verlauf des Algorithmus uninteressant und werden nicht mehr berücksichtigt. Das führt dazu, dass mehrere Lösungen von vornherein als schlecht erkannt werden können und somit nur Lösungen verfolgt werden, die auch Verbesserungen bringen können.<br />Zusätzlich zu der Bounding-Strategie wird auch noch ein Nearest Neighbour Ansatz verwendet, bei dem beim Anhängen eines Clusters an den Spannbaum die n nächsten Nachbarcluster bevorzugt werden.<br />Am Ende der Arbeit wurden Tests durchgeführt, bei denen die Bounding Strategie in den unterschiedlichen Archiven verwendet wurde. Diese Tests führten zu dem Ergebnis, dass die Bounding Strategie zu einer Verbesserung gegenüber den Archiven ohne Bounding Strategie führt. Der Vergleich zwischen den Archiven hat ergeben, dass die Pop-Variante bessere Ergebnisse liefert als die Gosh-Variante.<br />Die Variante, in der beide Archive gleichzeitig verwendet werden, ist wiederum besser als die anderen beiden Varianten.

In this work, an algorithm for the generalized minimum spanning tree problem (GMST) is developed. Given is a complete graph where the nodes are partitioned into clusters. A solution is a spanning tree which contains exactly one node of each cluster and its costs are minimal.<br />This problem is NP-hard. In this work, a heuristic is developed for this problem.<br />In this method, an evolutionary algorithm (EA) is used with two different solution archives. Using a solution archive, it is possible to store solutions generated by the EA in order to detect duplicates and converts duplicate solutions into new solutions. One solution archive based on the "ghosh-encoding" in which the spanned nodes of each cluster in the solution are stored. The other archive is based on the "pop-encoding" which characterizes the connections between the clusters.<br />These archives are extended by a bounding strategy based on the branch-and-bound technique. They try to calculate appropriate bounds at a convenient positions which give information about how good the solutions in the respective area of the archive can be in the best case.<br />If a bound was found which is worse than the best known solution, the solutions are unattractive in the course of the algorithm and will not be considered. Therefore inferior solutions can be detected at an early stage and only promising solutions that can bring improvements will be pursued.<br />In addition to the bounding strategy a nearest neighbor approach is implemented in which a cluster attached to the spanning tree is preferred among the the n nearest neighboring clusters.<br />Tests were carried out in which the bounding strategy was used in the different variants. These tests led to the conclusion that the bounding strategy leads to an improvement in comparison to the "normal" archives.<br />The comparison between the archives shows that the pop version lead to better results than the gosh version. When both archives are used simultaneously, the results are better than the results of the other two variants.<br />