How efficient are genetic algorithms to solve high epistasis deceptive problems?

Abstract

We present an overview of the properties that are involved in the complexity of global combinatorial optimization problems with a focus on epistasis and deceptiveness. As the complexity of a problem is linked to the exploration operators and algorithm used, we propose at first a bibliography of genetic algorithms. We discuss their efficiency to solve global combinatorial optimization problems following the canonical and the statistical approaches. We propose two strategies to handle such problems. In order to evaluate the capabilities and limitations of each of them, we undertake a comparison on a set of problems with varying levels of epistasis and deceptiveness.