Please use this identifier to cite or link to this item: http://doi.org/10.25358/openscience-4731
Full metadata record
DC FieldValueLanguage
dc.contributor.authorSteitz, Wolfgang
dc.date.accessioned2013-02-26T15:23:44Z
dc.date.available2013-02-26T16:23:44Z
dc.date.issued2013
dc.identifier.urihttps://openscience.ub.uni-mainz.de/handle/20.500.12030/4733-
dc.description.abstractWhen 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.en_GB
dc.description.abstractBei 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.de_DE
dc.language.isoeng
dc.rightsInCopyrightde_DE
dc.rights.urihttps://rightsstatements.org/vocab/InC/1.0/
dc.subject.ddc004 Informatikde_DE
dc.subject.ddc004 Data processingen_GB
dc.titleProblem-specific design of metaheuristics for constrained spanning tree problemsen_GB
dc.typeDissertationde_DE
dc.identifier.urnurn:nbn:de:hebis:77-32803
dc.identifier.doihttp://doi.org/10.25358/openscience-4731-
jgu.type.dinitypedoctoralThesis
jgu.type.versionOriginal worken_GB
jgu.type.resourceText
jgu.description.extent128 S.
jgu.organisation.departmentFB 03 Rechts- und Wirtschaftswissenschaften-
jgu.organisation.year2012
jgu.organisation.number2300-
jgu.organisation.nameJohannes Gutenberg-Universität Mainz-
jgu.rights.accessrightsopenAccess-
jgu.organisation.placeMainz-
jgu.subject.ddccode004
opus.date.accessioned2013-02-26T15:23:44Z
opus.date.modified2013-02-26T15:41:01Z
opus.date.available2013-02-26T16:23:44
opus.subject.dfgcode00-000
opus.subject.otherOptimierung, Heuristiken, Spannbäume, Kombinatorische Optimierungde_DE
opus.subject.otherOptimization, Heuristics, spanning tree, combinatorial optimizationen_GB
opus.organisation.stringFB 03: Rechts- und Wirtschaftswissenschaften: Abteilung Wirtschaftswissenschaftende_DE
opus.identifier.opusid3280
opus.institute.number0302
opus.metadataonlyfalse
opus.type.contenttypeDissertationde_DE
opus.type.contenttypeDissertationen_GB
jgu.organisation.rorhttps://ror.org/023b0x485
Appears in collections:JGU-Publikationen

Files in This Item:
  File Description SizeFormat
Thumbnail
3280.pdf819.91 kBAdobe PDFView/Open