Open AccessA 2-Level Iterated Tabu Search Algorithm for the Quadratic Assignment Problem
Author(s) -
Alfonsas Misevičius,
Dovilė Kuznecovaitė
Publication year - 2020
Publication title -
informacijos mokslai
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.128
H-Index - 1
eISSN - 1392-1487
pISSN - 1392-0561
DOI - 10.15388/im.2020.90.52
Subject(s) - tabu search , quadratic assignment problem , guided local search , mathematical optimization , algorithm , iterated function , mutation , quadratic equation , novelty , mathematics , computer science , weapon target assignment problem , combinatorial optimization , mathematical analysis , biochemistry , chemistry , geometry , theology , philosophy , gene
In this paper, a 2-level iterated tabu search (ITS) algorithm for the solution of the quadratic assignment problem (QAP) is considered. The novelty of the proposed ITS algorithm is that the solution mutation procedures are incorporated within the algorithm, which enable to diversify the search process and eliminate the search stagnation, thus increasing the algorithm’s efficiency. In the computational experiments, the algorithm is examined with various implemented variants of the mutation procedures using the QAP test (sample) instances from the library of the QAP instances – QAPLIB. The results of these experiments demonstrate how the different mutation procedures affect and possibly improve the overall performance of the ITS algorithm.