TU Darmstadt / ULB / TUprints

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

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

[img]
Preview
Text
doctoralThesis.pdf
Available under Creative Commons Attribution Non-commercial No Derivatives, 2.5.

Download (1MB) | Preview
Item Type: Ph.D. Thesis
Title: A New Metaheuristic Approach for Stabilizing the Solution Quality of Simulated Annealing and Applications
Language: English
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
Place of Publication: Darmstadt
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
Classification DDC: 000 Allgemeines, Informatik, Informationswissenschaft > 000 Allgemeines, Wissenschaft
000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik
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: 15 Feb 2013 09:40
URN: urn:nbn:de:tuda-tuprints-32888
Referees: Fürnkranz, Prof. Dr. Johannes and Weihe, Prof. Dr. Karsten
Refereed: 31 January 2013
URI: http://tuprints.ulb.tu-darmstadt.de/id/eprint/3288
Export:
Actions (login required)
View Item View Item

Downloads

Downloads per month over past year