Introduction to Differential Evolution Algorithm

February 23, 2019

Differential Evolution was introduced by Rainer Storn and Kenneth Price in 1995. It is an evolutionary algorithm that optimizes a problem by iteratively improving a candidate solution concerning a given measure of quality or fitness. DE is simple to implement and has few parameters to tune, and it is used in engineering, machine learning, and artificial intelligence.

Background

Evolutionary computation dates back to the 1950s. Early evolutionary algorithms typically followed a population-based iterative computational process, which later evolved into three main research directions:

Evolutionary Programming (EP)
Evolution Strategies (ES)
Genetic Algorithms (GA)

In the 1990s, these three independent research streams merged into a new field known as evolutionary computation. The DE algorithm, introduced by R. Storn and K. V. Price in 1995, emerged during this period.

Optimization Problem

An optimization problem involves finding the optimal solution for a given objective function. For example, we seek three values between 0 and 1 that minimize the function $f$ :

\min \ f(x_1, x_2, x_3) = x_1 + x_2 + x_3 \quad \text{s.t.} \quad 0 \leq x_i < 1

Here, we define these three values as a vector, and the function becomes our objective function. Our goal is to find the vector that minimizes $f$ among a series of vectors.

DE Algorithm

The DE algorithm is specifically designed to solve optimization problems, particularly global optimization problems. The relationship between the two can be summarized as follows:

Objective Function: The objective function of an optimization problem is central to the DE algorithm, as it is used to evaluate the fitness of candidate solutions.
Solution Space: The DE algorithm searches for the optimal solution within the solution space of the optimization problem. Initialization, mutation, crossover, and selection operations all occur within this space.
Global Search: The DE algorithm, through population diversity and global search strategies, can escape local optima and find the global optimum.
Adaptability: The DE algorithm is suitable for various complex, multimodal, and nonlinear optimization problems.

Algorithm

Initialization

In the initialization step, the DE algorithm randomly generates NP D-dimensional real-parameter vectors. In simple terms, NP D-dimensional points. Here, NP represents the population size. In the following sections about DE variants, N represents the number of steps, and P represents the number of chains, with their product being the total number of generated samples. A D-dimensional vector is represented by Equation 2, and in the initial stage, we generate multiple vectors similar to Equation 2.

\vec{X} = \begin{bmatrix} x_1, x_2, \ldots, x_D \end{bmatrix}^T

In each iteration, we obtain new vectors, thus defining the i-th vector in generation G by:

\vec{X}_{i,G} = [x]

Generally, the initialization of the DE algorithm can be completed by sampling from a D-dimensional Gaussian or uniform distribution.

Mutation

First, several concepts need to be introduced:

The vector selected for updating in the current sample is called the target vector.
The vector obtained after the differential mutation operation is called the donor vector.
The vector recombined from the target and donor vectors is called the trial vector.

To update all vectors in the current sample, we first select a target vector in order, which is the vector to be updated. Three other vectors are then randomly selected. The difference between the first two vectors, scaled by a factor F, is added to the third vector to generate the donor vector.

The process of generating the donor vector for the i-th vector can be represented by Equation 4. The subscripts on the right-hand side of the equation represent three different vector indices. Note that the three randomly selected numbers cannot be the same as the target vector’s index (i).

\vec{V}i = \vec{X}{r_1^i} + F \cdot \left( \vec{X}{r_2^i} - \vec{X}{r_3^i} \right)

Crossover

Elements of the donor vector and the target vector are exchanged to form the trial vector. Here, two common crossover strategies are introduced.

Exponential crossover or two-point modulo crossover. From 1 to D, select two integers, n (crossover start point) and L (crossover length). We use u to represent elements in the trial vector and v to represent elements in the donor vector. The crossover strategy is described by Equation 5.

u_{j,i,G} = v_{j,i,G} \quad \text{for} \quad j = \langle n \rangle_D, \langle n + 1 \rangle_D, \ldots, \langle n + L - 1 \rangle_D

Starting from the n-th element, replace the next L-1 elements. If replacing to the end of V, continue from the beginning until L elements have been replaced in total. The length L can be generated by the following Python code.

$Cr$ is the crossover rate, controlling the crossover process. The crossover length is closely related to $Cr$ . Let $v$ be an integer between 1 and D. The probability of $L = v$ is:

P(L=v)=(Cr)^{v-1}

Binomial crossover is the most commonly introduced crossover method. For all elements from 1 to D in the target and donor vectors, if the condition $rand(0, 1) \leq Cr$ is met, we replace the elements; otherwise, we do not.

In a two-dimensional parameter space, there are three possible trial vectors:

Neither element is exchanged, so the trial vector is the same as the donor vector.
The first element is replaced, but the second element is not.
The first element is not replaced, but the second element is.

These three scenarios can be illustrated by the following diagram.

Selection

To maintain a constant population size after multiple iterations, the selection algorithm determines whether to retain the target or trial vector for the next generation. By calculating their objective functions, the vector that minimizes the objective function is retained. Thus, if the trial vector keeps the objective function unchanged or smaller, it will replace the corresponding target vector; otherwise, the target vector is retained.

de.py

import numpy as np

def differential_evolution(func, bounds, pop_size=20, F=0.5, CR=0.7, max_iter=1000):
    """
    Differential Evolution (DE) algorithm.

    :param func: Objective function to be minimized.
    :param bounds: Bounds for variables as a list of tuples [(min, max), ...].
    :param pop_size: Population size.
    :param F: Differential weight.
    :param CR: Crossover probability.
    :param max_iter: Maximum number of iterations.
    :return: Best solution found and its objective value.
    """
    dim = len(bounds)
    # Initialize population
    pop = np.random.rand(pop_size, dim)
    for i in range(dim):
        pop[:, i] = bounds[i][0] + pop[:, i] * (bounds[i][1] - bounds[i][0])
    
    # Evaluate initial population
    fitness = np.asarray([func(ind) for ind in pop])
    
    best_idx = np.argmin(fitness)
    best = pop[best_idx]
    best_fitness = fitness[best_idx]
    
    for _ in range(max_iter):
        for j in range(pop_size):
            # Mutation
            indices = list(range(pop_size))
            indices.remove(j)
            a, b, c = pop[np.random.choice(indices, 3, replace=False)]
            mutant = np.clip(a + F * (b - c), [b[0] for b in bounds], [b[1] for b in bounds])
            
            # Crossover
            cross_points = np.random.rand(dim) < CR
            if not np.any(cross_points):
                cross_points[np.random.randint(0, dim)] = True
            trial = np.where(cross_points, mutant, pop[j])
            
            # Selection
            f_trial = func(trial)
            if f_trial < fitness[j]:
                pop[j] = trial
                fitness[j] = f_trial
                
                # Update the best solution found
                if f_trial < best_fitness:
                    best_fitness = f_trial
                    best = trial
    
    return best, best_fitness

if __name__ == "__main__":
    # Define an objective function
    def objective_function(x):
        return np.sum(x**2)
    
    # Bounds for variables
    bounds = [(-5, 5)] * 2  # Example for a 2-dimensional problem
    
    # Run DE
    best_solution, best_value = differential_evolution(objective_function, bounds)
    
    print("Best Solution:", best_solution)
    print("Best Value:", best_value)

Conclusion

DE searches the solution space through random sampling and differential mutation, without assuming a particular form for the target distribution. It has three parameters to tune: population size, scaling factor, and crossover rate.

Through initialization, mutation, crossover, and selection, DE iteratively refines its population of candidate solutions. Later work builds variants on this base: adaptive DE, multi-objective DE, and others.

Note: Portions of this article were generated by AI and have been edited to ensure accuracy and clarity.

Testing Large Language Models: An Overview