Differential Evolution

Radu Angelescu
emulator

This weekend I was looking into d3js. I saw a lot of cool visualizations on the web that used d3js and was actively searching for something good for rendering data in javascript.

I started learning the basics and while doing this I said to myself I should actually do something to express an algorithm, not just random art.

Because I am currently interested in machine learning and I actually plan to use differential evolution tuning for my neural network in Carvatar I decided implement it in javascript and plot the steps using d3js. This allowed me to brush up on my understanding of the algorithm, javascript skills, learn some d3js and if it all goes well maybe give back to the awesome programming community.

What is Differential Evolution?

Well it’s an optimization method that iteratively tries to improve a candidate solution with a regard to a given measure of quality. We use the word “tries” because it does not guarantee an optimal solution is ever found (it’s a metaheuristic).

When is it used?

We can use it whenever, but I guess the main reason for using something that does not guarantee a solution is that we have a very weak understanding of the problem we want to optimize. By weak understanding I mean that we don’t know the function we want to optimize (and the function is not differentiable, or we cannot easily find the gradient). If we had more knowledge about the function, then there are almost always better algorithms (gradient based algorithms for example). We will use this in a simple problem (a problem that could be solved easier with other techniques, just so that we can watch what actually happens on screen)

Formulation

Let $f:\mathbb{R}^n \mapsto \mathbb{R}$ be the cost function (it’s the heuristic that we pick, that actually approximates how close we are to a solution, also called fitness function)

Goal: Find $m$ that satisfies $f(m) \leq f(p)$ for all $p$ in the search-space.

Basically find the global minimum of $f$.

Parameters

  • $x \in \mathbb{R}^n$ - candidate solution
  • $F \in [{0,2}]$ - differential weight
  • $CR \in [{0,1}]$- crossover probability
  • $NP \geq 4$ - population size

Algorithm

  • Initialize x randomly

  • Do:

    • For each agent x in the population do:
      • Random Pick $a \neq b \neq c$
      • Random Pick index $r \in { 1 \dots n }$
      • Compute $y = [{y_1 \dots y_n }]$
        • For each $i$, pick $r_i = U(0,1)$
        • If $r_i < CR$ or $i= R$:
          • set $y_i = a_i + F (b_i - c_i)$
        • Else $y_i = x_i$
      • If $f(y) < f(x)$ : replace x with y
    • While (not finished)
    • Pick the best candidate to be the agent from the population that has the highest fitness

    If you want more on Differential Evolution the wikipedia entry is really good.

    Picking our problem

    I picked an easy problem so bear with me.

    • Formulation
      • Given a real polynomial $P(x)$ of degree 4 (quatric), what are it’s coefficients $a_i \in \mathbb{R}$ where $i \in {0 \dots 4}$ so that it approximates the generator function?

    • Reformulation

      • Basically we have this black box that spits values and we want to simulate the black box (generator function) with a 4’th degree polynomial.

    • Thoughts

      • We can intuitively understand that if the black box is really complicated, our system will not end up with a good approximation.

      We can actually state that if the generator function has more than 3 critical points, it is safe to say our approximation will (at best) work for a small interval. I think that by watching the algorithm work on this problem you can intuitively understand better what’s actually going on with differential evolution.

  • Implementation

So the main Differential Evolution algorithm step looks like this:

function differentialEvolutionStep(dataset)
{
  //For each agent in the population
    for(var candidateIdx = 0 ; candidateIdx < POPULATION_SIZE; candidateIdx++)
    {
      //Pick three agents a,b,c from the population at random (a!=b!=c)
        invalididxlist = [];
        //pick a
        invalididxlist.push(candidateIdx);
        aIdx = pickRandomIdx(invalididxlist);
        //pick b
        invalididxlist.push(aIdx);
        bIdx = pickRandomIdx(invalididxlist);
        //pick c
        invalididxlist.push(bIdx);
        cIdx = pickRandomIdx(invalididxlist);

        //hold the candidates
        var xCandidate = population[candidateIdx];
        var aCandidate = population[aIdx];
        var bCandidate = population[bIdx];
        var cCandidate = population[cIdx];

        //Pick a random index r {1 ... NUMBER_OF_GENES}
        // we name it crossPoint
        var crossPoint = Math.round(Math.random() * (NUMBER_OF_GENES-1));

        //calculate the child of a, b and c
        var newCandidate = generateNewCandidate(aCandidate,bCandidate,cCandidate,xCandidate, crossPoint);

        //evaluate the fitness values
        var fitnessNewCandidate = calculateFitnessofCandidate(newCandidate,dataset);
        var fitnessOldCandidate = calculateFitnessofCandidate(xCandidate,dataset);

        // update the best candidate and also swap old candidate with new candidate if new candidate is fitter
        if(fitnessNewCandidate < fitnessOldCandidate)
        {
          population[candidateIdx] = newCandidate;
          if(bestFitness > fitnessNewCandidate)
          {
            bestFitness = fitnessNewCandidate;
            bestCandidate = population[candidateIdx];
          }
        }

        if(bestFitness > fitnessOldCandidate)
        {
          bestFitness = fitnessOldCandidate;
          bestCandidate = population[candidateIdx];
        }

    }
}

So this is the function that generates the new candidates

//The new candidate is outcome of binary crossover of agent x with intermediate agent z =a +F (b -c)
function generateNewCandidate(a,b,c,x, crossPoint)
{
    var newCandidate = [];

    for( var i =0 ; i< NUMBER_OF_GENES ; i++)
    {
      var randomPick = Math.random();
      if(randomPick < crossPoint || i == crossPoint )
      {
        var ai = a[i];
        var bi = b[i];
        var ci = c[i];
        newCandidate.push(ai + F *(bi-ci))
      }
      else
      {
        newCandidate.push(x[i])
      }
    }
    return newCandidate;
}

Our evaluation function evalCandidate is basically a normal polynomial evaluator. You can read more about this here

We use MSE for a cost function (inverse of the fitness function)

function calculateFitnessofCandidate(candidate,dataset)
{
  // We will use the MSE
  error = 0;
  for(var i = 0 ; i< dataset.length; i++)
  {
    var value = evalCandidate(candidate,dataset[i].x);
    var diff = dataset[i].y - value;
    error = error + diff * diff;
  }
  return error;
}

This is the visualization

You can find the full source code on my github