Autoren:	Steitz, Wolfgang
Titel:	Problem-specific design of metaheuristics for constrained spanning tree problems
Online-Publikationsdatum:	26-Feb-2013
Erscheinungsdatum:	2013
Sprache des Dokuments:	Englisch
Zusammenfassung/Abstract:	When designing metaheuristic optimization methods, there is a trade-off between application range and effectiveness. For large real-world instances of combinatorial optimization problems out-of-the-box metaheuristics often fail, and optimization methods need to be adapted to the problem at hand. Knowledge about the structure of high-quality solutions can be exploited by introducing a so called bias into one of the components of the metaheuristic used. These problem-specific adaptations allow to increase search performance. This thesis analyzes the characteristics of high-quality solutions for three constrained spanning tree problems: the optimal communication spanning tree problem, the quadratic minimum spanning tree problem and the bounded diameter minimum spanning tree problem. Several relevant tree properties, that should be explored when analyzing a constrained spanning tree problem, are identified. Based on the gained insights on the structure of high-quality solutions, efficient and robust solution approaches are designed for each of the three problems. Experimental studies analyze the performance of the developed approaches compared to the current state-of-the-art. Bei dem Entwurf von metaheuristischen Optimierungsmethoden besteht ein Zielkonflikt zwischen Anwendungsbreite und Effektivität. Für große anwendungsnahe Instanzen von kombinatorischen Optimierungsproblemen funktionieren Standard-Metaheuristiken für gewöhnlich nicht besonders gut. Um bessere Ergebnisse zu erzielen muss die Optimierungsmethode an das zu optimierende Problem angepasst werden. Wissen über die Struktur guter Lösungen kann genutzt werden indem ein sogenannter Bias in den Komponenten der Metaheuristik integriert wird. Diese problemspezifischen Anpassungen erlauben es die Leistungsfähigkeit zu steigern. In dieser Arbeit werden die Charakteristika von qualitativ hochwertigen Lösungen dreier Spannbaumproblemen mit unterschiedlichen Nebenbedingungen untersucht: das Optimal Communication Spanning Tree Problem, das Quadratic Minimum Spanning Tree Problem und das Bounded Diameter Minimum Spanning Tree Problem. Verschiedene relevante Eigenschaften von Spannbäumen werden identifiziert, welche untersucht werden sollten wenn ein Spannbaumproblem analysiert wird. Basierend auf den gewonnenen Erkenntnissen bezüglich der Struktur qualitativ hochwertiger Lösungen, werden effiziente und robuste Lösungsverfahren für jedes der Probleme entwickelt. Experimentelle Studien analysieren die Leistungsfähigkeit der entwickelten Ansätze im Vergleich zu den bisher erfolgreichsten Verfahren.
DDC-Sachgruppe:	004 Informatik 004 Data processing
Veröffentlichende Institution:	Johannes Gutenberg-Universität Mainz
Organisationseinheit:	FB 03 Rechts- und Wirtschaftswissenschaften
Veröffentlichungsort:	Mainz
ROR:	https://ror.org/023b0x485
DOI:	http://doi.org/10.25358/openscience-4731
URN:	urn:nbn:de:hebis:77-32803
Version:	Original work
Publikationstyp:	Dissertation
Nutzungsrechte:	Urheberrechtsschutz
Informationen zu den Nutzungsrechten:	https://rightsstatements.org/vocab/InC/1.0/
Umfang:	128 S.
Enthalten in den Sammlungen:	JGU-Publikationen