[Back]

C. Gruber:
"Ein Lösungsarchiv mit Branch-and-Bound-Erweiterung für das Generalized Minimum Spanning Tree Problem";
Supervisor: G. Raidl, B. Hu; Institut für Computergraphik und Algorithmen, 2011; final examination: 2011-09.

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. This problem is NP-hard. In this work, a
heuristic is developed for this problem.
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 an encoding in which the spanned nodes
of each cluster in the solution are stored. The other archive is based on an encoding
which characterizes the connections between the clusters.
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. 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.
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.
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. 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.
iv

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. Dieses Problem ist NP-schwierig. In dieser Arbeit
wird eine Heuristik für dieses Problem entwickelt.
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. Das eine Lösungsarchiv beruht auf einer Kodierung, bei der die
ausgewählten Knoten der Cluster einer Lösung gespeichert werden, während das
andere Archiv auf einer Kodierung beruht, bei der gespeichert wird, welche Cluster
in der Lösung verbunden sind.
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.
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.
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.
Die Variante, in der beide Archive gleichzeitig verwendet werden, ist wiederum
besser als die anderen beiden Varianten.

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