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.
| Typ des Eintrags: |
Dissertation
|
| Erschienen: |
2013 |
| Autor(en): |
Güttinger, Dennis |
| Art des Eintrags: |
Erstveröffentlichung |
| Titel: |
A New Metaheuristic Approach for Stabilizing the Solution Quality of Simulated Annealing and Applications |
| Sprache: |
Englisch |
| Referenten: |
Fürnkranz, Prof. Dr. Johannes ; Weihe, Prof. Dr. Karsten |
| Publikationsjahr: |
1 Februar 2013 |
| Ort: |
Darmstadt, Germany |
|
Datum der mündlichen Prüfung: |
31 Januar 2013 |
| URL / URN: |
http://tuprints.ulb.tu-darmstadt.de/3288/ |
| Kurzbeschreibung (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. |
|
Alternatives oder übersetztes Abstract: |
|
Alternatives Abstract | Sprache |
|---|
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. | Deutsch |
|
| Freie Schlagworte: |
optimization, metaheuristic, simulated annealing, greedy, disaster management, public security, test suite reduction, task allocation, website ranking |
| Schlagworte: |
| Einzelne Schlagworte | Sprache |
|---|
| Optimierung, Metaheuristik, Simuliertes Ausglühen, Greedy, Katastrophenmanagement, Öffentliche Sicherheit, Testfolgenreduzierung, Aufgabenzuweisung, Einstufung von Webseiten | Deutsch |
|
| URN: |
urn:nbn:de:tuda-tuprints-32888 |
| Sachgruppe der Dewey Dezimalklassifikatin (DDC): |
000 Allgemeines, Informatik, Informationswissenschaft > 000 Allgemeines, Wissenschaft
000 Allgemeines, Informatik, Informationswissenschaft > 004 Informatik |
| Fachbereich(e)/-gebiet(e): |
20 Fachbereich Informatik
20 Fachbereich Informatik > Knowledge Engineering |
| Hinterlegungsdatum: |
18 Mär 2013 16:25 |
| Letzte Änderung: |
21 Mär 2013 10:08 |
| PPN: |
|
| Referenten: |
Fürnkranz, Prof. Dr. Johannes ; Weihe, Prof. Dr. Karsten |
|
Datum der mündlichen Prüfung / Verteidigung / mdl. Prüfung: |
31 Januar 2013 |
| Schlagworte: |
| Einzelne Schlagworte | Sprache |
|---|
| Optimierung, Metaheuristik, Simuliertes Ausglühen, Greedy, Katastrophenmanagement, Öffentliche Sicherheit, Testfolgenreduzierung, Aufgabenzuweisung, Einstufung von Webseiten | Deutsch |
|
| Export: |
|
| Suche nach Titel in: |
TUfind oder in Google |
 |
Redaktionelle Details anzeigen |
Drucken
Impressum