📂Optimization

What is Differential Evolution in Genetic Algorithm?

Terminology ¹

In genetic algorithms, differential evolution denotes a strategy that imparts a specific direction when producing mutations.

Description

As the name suggests, differential evolution starts from an idea similar to gradient descent. If the objective function is differentiable, one can generate mutations in the direction of the derivative; if differentiation is too costly or impossible, various strategies can be attempted depending on the problem².

If differentiation is not possible but function evaluation is not prohibitively expensive, and the solution set is a vector space, the mutation direction can be determined using differences between randomly selected solutions as follows:

1. Randomly select $\mathbf{a}, \mathbf{b}, \mathbf{c}$ from the population.
2. For the hyperparameter $w \in \mathbb{R}$, compute a temporary vector $\mathbf{z} = \mathbf{a} + w(\mathbf{b}-\mathbf{c})$.
3. Compare $\mathbf{z}$ and $\mathbf{a}$; if $\mathbf{z}$ has higher fitness, replace $\mathbf{a}$ with $\mathbf{z}$.

Here $\mathbf{b}-\mathbf{c}$ should be understood not so much as a strict derivative but rather as a “sensible direction” when attacking an objective function whose manifold structure is completely unknown. For example, it is not a vector that increases every coordinate by 1; what matters is that it can actually be discovered within the evolutionary cycles of the genetic algorithm.