Recombinative evolution will outperform local search on fitness functions that have a property called deep contingency. In this blog post I will:

1. Present a fitness function possessing the property in question and empirically show that a genetic algorithm handily outperforms simulated annealing.
2. Argue that the presented problem is a difficult one, and the non-trivial computation performed by the genetic algorithm is just what’s needed.
3. Explain why simulated annealing, and indeed, local search of any kind, is the wrong way to approach the problem presented.

This is going to be a lengthy post, and you are welcome to jump to the punch. First, I want to explain why it has taken till now to procure a whitebox optimization problem on which a genetic algorithm outperforms simulated annealing. The short story is that we did not, till recently, have good theories about the computational power of recombinative evolution.

Here’s the long story:

Logical Positivism vs the Scientific Method in Genetic Algorithmics

The genetic algorithm owes its form to biomimicry, not derivation from first principles. So, unlike the workings of conventional optimization algorithms, which are typically apparent from the underlying mathematical derivations, the workings of the genetic algorithm require elucidation. Attempts to explain how genetic algorithms work can be divided in two: those based to a lesser or greater extent on the scientific method, and those that reject the scientific method in favor of logical positivism. Continue reading “When Will Evolution Outperform Local Search?” →