Hybrid Algorithm for Solving the Quadratic Assignment Problem

Abstract

The Quadratic Assignment Problem (QAP) is a combinatorial optimization problem; it belongs to the class of NP-hard problems. This problem is applied in various fields such as hospital layout, scheduling parallel production lines and analyzing chemical reactions for organic compounds. In this paper we propose an application of Golden Ball algorithm mixed with Simulated Annealing (GBSA) to solve QAP. This algorithm is based on different concepts of football. The simulated annealing search can be blocked in a local optimum due to the unacceptable movements; our proposed strategy guides the simulated annealing search to escape from the local optima and to explore in an efficient way the search space. To validate the proposed approach, numerous simulations were conducted on 64 instances of QAPLIB to compare GBSA with existing algorithms in the literature of QAP. The obtained numerical results show that the GBSA produces optimal solutions in reasonable time; it has the better computational time. This work demonstrates that our proposed adaptation is effective in solving the quadratic assignment problem.

Keywords

• Combinatorial Optimization
• Golden Ball Algorithm
• Quadratic Assignment Problem
• Simulated Annealing