Evolutionary multiobjective optimization with a segment-based external memory support for the multiobjective quadratic assignment problem

Abstract

Multiobjective evolutionary optimization has been demonstrated to be an efficient method for some difficult multiobjective optimization problems; particularly the quadratic assignment problem which is a provably difficult NP-complete problem with a multitude of real-world applications. This paper introduces the use of a segment-based external memory in evolutionary multiobjective optimization. In principle, variable-size solution segments taken from a number of previously promising solutions are stored in an external memory whose elements are used in the construction of new solutions. In the construction of a solution, a solution segment is retrieved from the external memory and used in the construction of complete solutions through evolutionary recombination operators. The aim is to provide further intensification around promising solutions without weakening the exploration capabilities. Different instances of the multiobjective quadratic assignment problem are used for performance evaluations and, almost in all trials, the proposed external memory strategy provided significantly better results than the multiobjective genetic algorithm (MOGA).