Hybrid Algorithm for Solving the Quadratic Assignment Problem

Author
Keywords
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.
Year of Publication
2019
Journal
International Journal of Interactive Multimedia and Artificial Intelligence
Volume
5
Issue
Special Issue on Artificial Intelligence Applications
Number
4
Number of Pages
68-74
Date Published
03/2019
ISSN Number
1989-1660
Citation Key
URL
DOI
Attachment