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

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.