A Bandit-Inspired Memetic Algorithm for Quadratic Assignment Problems

Abstract

In this thesis a new metaheuristic for combinatorial optimization is proposed, with focus on the Quadratic Assignment Problem as the hard-problem of choice - a choice that is reflected in the name of the method, BIMA-QAP. The algorithm employs a memetic structure and stores information on the single components along the search. This information is used to guide the search, through an operator inspired by the solution approaches to the Multi-Armed Bandit model.

Once the algorithm has been laid out and its set of parameters defined, its implementation has been extensively tested under a Naive-Bayesian assumption of independence among the parameters. The results show that BIMA-QAP consistently performs better than Multi-start Local Search, and the new operator perturb() alters the solutions better than a randomized approach.