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

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.

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.