Differential Evolution - Algorithm

Algorithm

A basic variant of the DE algorithm works by having a population of candidate solutions (called agents). These agents are moved around in the search-space by using simple mathematical formulae to combine the positions of existing agents from the population. If the new position of an agent is an improvement it is accepted and forms part of the population, otherwise the new position is simply discarded. The process is repeated and by doing so it is hoped, but not guaranteed, that a satisfactory solution will eventually be discovered.

Formally, let be the cost function which must be minimized or fitness function which must be maximized. The function takes a candidate solution as argument in the form of a vector of real numbers and produces a real number as output which indicates the fitness of the given candidate solution. The gradient of is not known. The goal is to find a solution for which for all in the search-space, which would mean is the global minimum. Maximization can be performed by considering the function instead.

Let designate a candidate solution (agent) in the population. The basic DE algorithm can then be described as follows:

• Initialize all agents with random positions in the search-space.
• Until a termination criterion is met (e.g. number of iterations performed, or adequate fitness reached), repeat the following:
  • For each agent in the population do:
    • Pick three agents, and from the population at random, they must be distinct from each other as well as from agent
    • Pick a random index ( being the dimensionality of the problem to be optimized).
    • Compute the agent's potentially new position as follows:
      • For each, pick a uniformly distributed number
      • If or then set otherwise set
      • (In essence, the new position is outcome of binary crossover of agent with intermediate agent .)
    • If then replace the agent in the population with the improved candidate solution, that is, replace with in the population.
• Pick the agent from the population that has the highest fitness or lowest cost and return it as the best found candidate solution.

Note that is called the differential weight and is called the crossover probability, both these parameters are selectable by the practitioner along with the population size see below.