Towards Landscape Analyses to Inform the Design of a Hybrid Local Search for the Multiobjective Quadratic Assignment Problem

摘要

The quadratic assignment problem (QAP) is a very difficult and practically relevant combinatorial optimization problem which has attracted much research effort. Local search (LS) moves can be quickly evaluated on the QAP, and hence favoured methods tend to be hybrids of global optimization schemes and LS. Here we introduce the multiobjective QAP (mQAP) where m ≥ 2 distinct QAPs must be minimized si-multaneuously over the same permutation space, and hence we require a set of solutions approximating the Pareto front (PF). We argue that the best way to organise a hybrid LS for the mQAP will depend on details of the multiobjective fitness landscape. By using various techniques and measures to probe the landscapes of mQAPs, we attempt to find evidence for the relative ease with which the following can be done by LS: approach the PF from a random initial solution, or search along or close to the PF itself. On the basis of such explorations, we hope to design an appropriate hybrid LS for this problem. The paper contributes a number of landscape measurement methods that we believe are generally appropriate for multiobjective combinatorial optimization.