Analysis of recombinative algorithms on a non-separable building-block problem

Richard A. Watson richardw@cs.brandeis.edu    Dynamical & Evolutionary Machine Organization, Volen Center for Complex Systems, Brandeis University, Waltham, MA, USA

Abstract

Our analysis seeks to exemplify the utility of crossover by studying a nonseparable building-block problem that is as easy as possible under recombination but very hard for any kind of mutation-based algorithm. The interdependent fitness contributions of blocks in this problem produce a search space that has an exponential number of local optima for a mutation-only algorithm. In contrast, the problem has no local optima for a recombinative algorithm - that is, there is always a path of monotonically ...

Get Foundations of Genetic Algorithms 2001 (FOGA 6) now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.