An empirical comparison of memetic algorithm strategies on the multiobjective quadratic assignment problem

Abstract

Evolutionary algorithm based metaheuristics have gained prominence in recent years for solving multiobjective optimization problems. These algorithms have a number of attractive features, but the primary motivation for many in the community is rooted in the use of a population inherent to evolutionary algorithms, which allows a single optimization run to provide a diverse set of nondominated solutions. However, for many combinatorial problems, evolutionary algorithms on their own do not perform satisfactorily. For these problems, the addition of a local search heuristic can dramatically improve the performance of the algorithms. Often called memetic algorithms, these techniques introduce a number of additional parameters which can require careful tuning. In this work, we provide an empirical comparison of a number of strategies for the construction of multiobjective memetic algorithms for the multiobjective quadratic assignment problem (mQAP), and provide a more principled analysis of those results using insights gained from analysis of the fitness landscape properties of the different problem instances.