Deception Considered Harmful* *With apologies to Edsger Dijkstra (Dijkstra, 1968).

It is argued that the characterization of hard problems must take into account the basic features of genetic algorithms, especially their dynamic, biased sampling strategy, such as the static average fitness of competing schemas.

Abstract

A central problem in the theory of genetic algorithms is the characterization of problems that are difficult for GAs to optimize. Many attempts to characterize such problems focus on the notion of Deception, defined in terms of the static average fitness of competing schemas. This article examines the Static Building Block Hypothesis (SBBH), the underlying assumption used to define Deception. Exploiting contradictions between the SBBH and the Schema Theorem, we show that Deception is neither necessary nor sufficient for problems to be difficult for GAs. This article argues that the characterization of hard problems must take into account the basic features of genetic algorithms, especially their dynamic, biased sampling strategy.