A modified simulated annealing algorithm for the quadratic assignment problem

A modified simulated annealing algorithm for the quadratic assignment problem

0.00 Avg rating0 Votes
Article ID: iaor20042283
Country: Lithuania
Volume: 14
Issue: 4
Start Page Number: 497
End Page Number: 514
Publication Date: Dec 2003
Journal: Informatica
Authors:
Keywords: programming: quadratic
Abstract:

The quadratic assessment problem (QAP) is one of the well-known combinatorial optimization problems and is known for its various applications. In this paper, we propose a modified simulated annealing algorithm for the QAP–M-SA-QAP. The novelty of the proposed algorithm is an advanced formula of calculation of the initial and final temperatures, as well as an original cooling schedule with oscillation, i.e., periodical decreasing and increasing of the temperature. In addition, in order to improve the results obtained, the simulated annealing algorithm is combined with a tabu search approach based algorithm. We tested our algorithm on a number of instances from the library of the QAP instances – QAPLIB. The results obtained from the experiments show that the proposed algorithm appears to be superior to earlier versions of the simulated annealing for the QAP. The power of M-SA-QAP is also corroborated by the fact that the new best known solution was found for the one of the largest QAP instances – THO150.

Reviews

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