Metaheuristic Algorithms for the Quadratic Assignment Problem

Abstract

This paper presents two meta-heuristic algorithms to solve the quadratic assignment problem. The iterated greedy algorithm has two main components hich are destruction and construction procedures. The algorithm starts from an initial solution and then iterates through a main loop where first a partial candidate solution is obtained by removing a number of solution components from a complete candidate solution. Then a complete solution is reconstructed by inserting the partial solution components in the destructed solution. These simple steps are iterated until some predetermined termination criterion is met. We also present our previous discrete differential evolution algorithm modified for the quadratic assignment problem. The quadratic assignment problem is a classical NP-hard problem and its applications in real life are still considered challenging. The proposed algorithms were evaluated on quadratic assignment problem instances arising from real life problems as well as on a number of benchmark instances from the QAPLIB. The computational results show that the proposed algorithms are superior to the migrating birds optimization algorithm which appeared very recently in the literature. Ultimately 7 out of 8 printed circuit boards (PCB) instances are further improved.