ISSN:
1436-6304
Keywords:
Optimization
;
local search
;
heuristic
;
threshold accepting
;
quadratic assignment problem
;
Optimierung
;
lokale Suchverfahren
;
Heuristik
;
Threshold Accepting
;
Quadratisches Zuordnungsproblem
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
,
Economics
Description / Table of Contents:
Zusammenfassung Im vorliegenden Beitrag wird eine Modifizierung der Threshold Accepting Heuristik von Dueck und Scheuer vorgeschlagen. Anstelle diskreter Schwellenwerte wird eine Schwellenwertfunktion verwendet, die vom Abkühlungsplan beim Simulated Annealing inspiriert ist. Desweiteren ist die Iterationszahl auf jeder Ebene des Verfahrens nunmehr eine Funktion des aktuellen sowie des Ausgangsschwellenwertes. Anhand dieses Vorgehensschemas untersuchen wir den Trade-off von Lösungsqualität und Konvergenzgeschwindigkeit bei verschiedenen Standardbeispielen des bekannten Quadratischen Zuordnungsproblems. Auch die Qualität und Zuverlässigkeit einer Multistart-Version kurzer TA-Läufe wird mit den Ergebnissen ausführlicher Läufe bei gleichen CPU-Zeiten verglichen, um Rückschlüsse auf die sinnvollere Optimierungsstrategie zu erhalten. In der Literatur verwenden unterschiedliche Autoren häufig sehr verschiedene Anzahlen zufälliger Startlösungen in ihren numerischen Experimenten. Wir untersuchen daher auch, wie sich eine Variation dieser Anzahl auf die TA-Ergebnisse auswirkt.
Notes:
Abstract In this paper we propose a modification of the threshold accepting heuristic by Dueck and Scheuer. Instead of using discrete threshold values a threshold function similar to the cooling schedule of simulated annealing is used. Furthermore, the number of iterations during each step of the heuristic is a function of the current and the initial threshold value. Using this scheme, we investigate the trade-off between solution quality and convergence speed on different instances of the well known quadratic assignment problem. In a second set of experiments the results of a multistart-version of TA are compared with the results of unique long runs at identical CPU-requirements to identify the better optimization strategy. Since, generally, in the literature the number of starting solutions for QAP-heuristics appears to be chosen on a rather arbitrary basis, we also highlight how varying this number influences the TA-results.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF01719267
Permalink
