 |
    |
Ruin and Recreate Principle Based Approach for the Quadratic Assignment Problem
Alfonsas Misevicius
Kaunas University of Technology,
Department of Practical Informatics,
Studentu St. 50-400a,
LT-3031 Kaunas, Lithuania
misevi@soften.ktu.lt
Abstract. In this paper, we propose an algorithm based on so-called ruin and recreate (R&R) principle. The R&R approach is conceptual simple but at the same time powerful meta-heuristic for combinatorial optimization problems. The main components of this method are a ruin (mutation) procedure and a recreate (improvement) procedure. We have applied the R&R principle based algorithm for a well-known combinatorial optimization problem, the quadratic assignment problem (QAP). We tested this algorithm on a number of instances from the library of the QAP instances – QAPLIB. The results obtained from the experiments show that the proposed approach appears to be significantly superior to a "pure" tabu search on real-life and real-life like QAP instances.
LNCS 2723, p. 598 ff.
lncs@springer.de
© Springer-Verlag Berlin Heidelberg 2003