A modification of threshold accepting and its application to the quadratic assignment problem

A modification of threshold accepting and its application to the quadratic assignment problem

0.00 Avg rating0 Votes
Article ID: iaor19961510
Country: Germany
Volume: 17
Issue: 2/3
Start Page Number: 205
End Page Number: 210
Publication Date: Mar 1995
Journal: OR Spektrum
Authors: ,
Keywords: optimization: simulated annealing
Abstract:

In this paper the authors 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, the authors 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, the authors also highlight how varying this number influences the TA-results.

Reviews

Required fields are marked *. Your email address will not be published.