Adaptive iterated local search for quadratic assignment problem

作     者：Mohamed Saifullah Hussin Mohammad Aizat Basir 

作者机构：Faculty of Ocean Engineering Technology and Informatics Universiti Malaysia Terengganu 20130 Kuala Nerus Terengganu Malaysia 

出 版 物：《AIP Conference Proceedings》 

年 卷 期：2024年第2905卷第1期

学科分类：07[理学] 0702[理学-物理学] 

摘      要：Iterated Local Search (ILS) is one of the classical metaheuristics that is frequently used for solving the Quadratic Assignment Problem (QAP), a commonly studied NP-hard combinatorial optimization problem. Despite the effectiveness shown by the ILS when solving the QAP, many possible enhancements can still be implemented, based on studies conducted on other combinatorial problems, for example vertex coloring problem, vehicle routing problem, network design optimization, and many others. Among possible approaches for improving the ILS are by implementing adaptive ILS and multi-start strategy. Adaptive ILS is implemented by dynamically changing the perturbation strength of ILS during the run, which focus on developing a robust algorithm that can solve a wide range of instances. Multi-start strategy on the other hand, focus on applying restart or diversification during ILS run to prevent early stagnation. Adaptive ILS with frequent and large perturbation strength change has shown the best overall result when it has obtained the lowest deviation to the best-known solution compared to others. Implementation of Multi-start strategy showed bad performance, except on Taillard75e instance, in which it frequently found the best-known solution compared to others. Both adaptive and multi-start strategy have shown interesting results that may be further studied for ILS improvement.