What's differential evolution and how does it compare to a genetic algorithm?

Question

From what I've read so far they seem very similar. Differential evolution uses floating point numbers instead, and the solutions are called vectors? I'm not quite sure what that means. If someone could provide an overview with a little bit about the advantages and disadvantages of both.

Answer 1

Well, both genetic algorithms and differential evolution are examples of evolutionary computation.

Genetic algorithms keep pretty closely to the metaphor of genetic reproduction. Even the language is mostly the same-- both talk of chromosomes, both talk of genes, the genes are distinct alphabets, both talk of crossover, and the crossover is fairly close to a low-level understanding of genetic reproduction, etc.

Differential evolution is in the same style, but the correspondences are not as exact. The first big change is that DE is using actual real numbers (in the strict mathematical sense-- they're implemented as floats, or doubles, or whatever, but in theory they're ranging over the field of reals.) As a result, the ideas of mutation and crossover are substantially different. The mutation operator is modified so far that it's hard for me to even see why it's called mutation, as such, except that it serves the same purpose of breaking things out of local minima.

On the plus side, there are a handful of results showing DEs are often more effective and/or more efficient than genetic algorithms. And when working in numerical optimization, it's nice to be able to represent things as actual real numbers instead of having to work your way around to a chromosomal kind of representation, first. (Note: I've read about them, but I've not messed extensively with them so I can't really comment from first hand knowledge.)

On the negative side, I don't think there's been any proof of convergence for DEs, yet.

Answer 2

Differential evolution is actually a specific subset of the broader space of genetic algorithms, with the following restrictions:

• The genotype is some form of real-valued vector
• The mutation / crossover operations make use of the difference between two or more vectors in the population to create a new vector (typically by adding some random proportion of the difference to one of the existing vectors, plus a small amount of random noise)

DE performs well for certain situations because the vectors can be considered to form a "cloud" that explores the high value areas of the solution solution space quite effectively. It's pretty closely related to particle swarm optimization in some senses.

It still has the usual GA problem of getting stuck in local minima however.