Understanding the elementary landscape decomposition of the QAP and its effects on local search based algorithms

Abstract

Elementary landscapes are a special type of combinatorial landscapes that have some properties that make them particularly suitable for working with meta-heuristic algorithms, specially local search based methods. In most of the cases a landscape is not elementary, however, if the neighborhood function meets some conditions, it can be decomposed into a set of elementary landscapes through a process that is called Elementary Landscape Decomposition (ELD). This is the case of the Quadratic Assignment Problem (QAP) under the swap neighborhood, which can be additively decomposed into three elementary landscapes.

This work has two main goals. First, we use the ELD approach to analyze the behaviour of two local search based meta-heuristics that optimize the QAP. In this sense, we intend to check whether incorporating the ELD during the optimization process improves the performance of meta-heuristic algorithms. Second, we propose an additional decomposition of the elementary landscapes that form the QAP. This decomposition defines a framework that helps us to characterize what is measured by each elementary landscape, hence giving us a deeper insight into the ELD of the problem.