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.

Burma

Floating point number isn't the difference. All the evolutionary strategies use floating point numbers. Algorithms of EC are no longer divided into types by their representation. – Perl

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.

Swim

Just to add to that, nothing about Genetic Algorithms precludes real-valued encodings. There are crossover operators like SBX (simulated binary crossover) as well as various ideas of "blending" the parents in different ways. Mutation of real-valued chromosomes has several obvious implementations, Gaussian bumps to the parameters, etc. – Gwennie

True, but the farther you get from the original notions, the more strained the metaphor becomes. I am not casting aspersions, I think they're all fascinating and useful, and can all reasonably be called genetic algorithms. It's just a judgement/aesthetic call. – Swim

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.

Clairvoyance

do you have a reference where GA is prone to getting stuck in local minima? – Pidgin

As I understand it, GA is particularly good at escaping local minima. If the space is very complicated, the mutation operator can be increased to force the GA to explore more aggressively and thus escape these local minima. This will, obviously, consume more processing time. – Analysis