TU Darmstadt / ULB / TUprints

A New Metaheuristic Approach for Stabilizing the Solution Quality of Simulated Annealing and Applications

Güttinger, Dennis (2013)
A New Metaheuristic Approach for Stabilizing the Solution Quality of Simulated Annealing and Applications.
Technische Universität
Ph.D. Thesis, Primary publication

[img]
Preview
Text
doctoralThesis.pdf
Copyright Information: CC BY-NC-ND 2.5 Generic - Creative Commons, Attribution, NonCommercial, NoDerivs .

Download (1MB) | Preview
Item Type: Ph.D. Thesis
Type of entry: Primary publication
Title: A New Metaheuristic Approach for Stabilizing the Solution Quality of Simulated Annealing and Applications
Language: English
Referees: Fürnkranz, Prof. Dr. Johannes ; Weihe, Prof. Dr. Karsten
Date: 1 February 2013
Place of Publication: Darmstadt
Date of oral examination: 31 January 2013
Abstract:

In this work we describe a new metaheuristical approach for global optimization that is based on the simulated annealing algorithm. Within this new approach a preoptimization step with a Greedy strategy is performed to compute an initial solution for the intrinsic iterations of the simulated annealing algorithm. Furthermore, the probability distribution which is used for generation of a new solution candidate is adjusted in a way that candidates in the optimization direction are chosen with a higher probability. We will empirically show the superiority of our metaheuristic for three different combinatorical optimization problems of practical relevance in comparison to other standard techniques that are usually applied to compute solutions of the corresponding problems. Moreover, the dependence of the solution quality on the choice of specific input parameters for simulated annealing can be reduced significantly with our metaheuristic. Finally, we will consider a fourth complex problem class, where our metaheuristic is unable to compute significantly better solutions in comparison to simple local optimization strategies. Consequently, for this problem class local optimization is sufficient for practical applications to determine an adequately good solution near the global optimum.

Alternative Abstract:
Alternative AbstractLanguage

In der vorliegenden Arbeit beschreiben wir ein neues metaheuristisches Verfahren zur globalen Optimierung, welches auf simuliertem Ausglühen basiert. Hierbei wird eine Voroptimierung durch ein Greedy-Verfahren vorgenommen, welches eine initiale Lösung für die eigentlichen Iterationen des simulierten Ausglüh-Algorithmus' berechnet. Außerdem wird die Wahrscheinlichkeitsverteilung mit der ein neuer Lösungskandidat generiert wird angepasst in dem Sinne, dass Kandidaten in Optimierungsrichtung mit einer größeren Wahrscheinlichkeit ausgewählt werden. Für drei verschiedene kombinatorische Optimierungsprobleme aus der Praxis zeigen wir empirisch die Überlegenheit unserer Metaheuristik im Vergleich zu anderen Standardverfahren, die normalerweise zu deren Lösung herangezogen werden. Darüber hinaus kann mit unserer Metaheuristik die Abhängigkeit der Lösungsqualität von der Wahl bestimmter Eingabeparameter des klassischen simulierten Ausglühens signifikant gesenkt werden. Abschließend betrachten wir noch eine vierte komplexe Problemklasse, bei der unsere Metaheuristik im Vergleich zu einfachen lokalen Approximationsverfahren keine signifikanten Lösungsverbesserungen bringt. Folglich reicht bei dieser Problemklasse in der Praxis lokale Optimierung aus, um eine hinreichend gute Lösung nahe des globalen Optimums zu bestimmen.

German
Uncontrolled Keywords: optimization, metaheuristic, simulated annealing, greedy, disaster management, public security, test suite reduction, task allocation, website ranking
Alternative keywords:
Alternative keywordsLanguage
Optimierung, Metaheuristik, Simuliertes Ausglühen, Greedy, Katastrophenmanagement, Öffentliche Sicherheit, Testfolgenreduzierung, Aufgabenzuweisung, Einstufung von WebseitenGerman
URN: urn:nbn:de:tuda-tuprints-32888
Classification DDC: 000 Generalities, computers, information > 000 Generalities
000 Generalities, computers, information > 004 Computer science
Divisions: 20 Department of Computer Science
20 Department of Computer Science > Knowl­edge En­gi­neer­ing
Date Deposited: 15 Feb 2013 09:40
Last Modified: 09 Jul 2020 00:17
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/3288
PPN: 316768472
Export:
Actions (login required)
View Item View Item