TU Darmstadt / ULB / TUbiblio

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.
Darmstadt, Germany, TU Darmstadt, [Online-Edition: http://tuprints.ulb.tu-darmstadt.de/3288/],
[Ph.D. Thesis]

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.

Item Type: Ph.D. Thesis
Erschienen: 2013
Creators: Güttinger, Dennis
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.

Place of Publication: Darmstadt, Germany
Uncontrolled Keywords: optimization, metaheuristic, simulated annealing, greedy, disaster management, public security, test suite reduction, task allocation, website ranking
Divisions: 20 Department of Computer Science
20 Department of Computer Science > Knowl­edge En­gi­neer­ing
Date Deposited: 18 Mar 2013 16:25
Official URL: http://tuprints.ulb.tu-darmstadt.de/3288/
URN: urn:nbn:de:tuda-tuprints-32888
License: Creative Commons: Attribution-No Derivative Works 3.0
Referees: Fürnkranz, Prof. Dr. Johannes and Weihe, Prof. Dr. Karsten
Refereed / Verteidigung / mdl. Prüfung: 31 January 2013
Alternative keywords:
Alternative keywordsLanguage
Optimierung, Metaheuristik, Simuliertes Ausglühen, Greedy, Katastrophenmanagement, Öffentliche Sicherheit, Testfolgenreduzierung, Aufgabenzuweisung, Einstufung von WebseitenGerman
Alternative Abstract:
Alternative abstract Language
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
Export:

Optionen (nur für Redakteure)

View Item View Item