Functional operators for evolutionary algorithms

Photo by K. Mitch Hodge on Unsplash

Writing an evolutionary algorithm is one of the best ways to write an artificial intelligence hello world program. Of course, we want to keep it short, clean and easy to understand. Lately I started translating the usual operators to functional code and I was surprised by how good the code looks, so I decided to share the findings. I have a full project on Github for the interested.

We will use Javascript, but the same code structure may be achieved with any functional language, or any language that supports the usual map and reduce operators for arrays. So let’s take each evolutionary step and see how it looks using functional code!

Step one: a random population

Photo by mauro mora on Unsplash

The first step in finding an optimal solution to a problem is to generate a set of random solutions. We will apply our evolutionary operators on the set but first we need something to start with. So let’s see how these look like when relying on Javascript functional code:

export const pickRandomNumber = (max) => Math.round(Math.random() * max);

export const createRandomArray = (length) =>
  [...new Array(length)].map(() => Math.random());

export const createRandomMatrix = (length, width) =>
  [...new Array(length)].map(() => createRandomArray(width));

We need an integer random number generator to pick random parents from the population, we need random arrays to generate individuals and we need a random matrix, an array of individuals, to generate the initial random population. Note how we generate a random array of a given length. When calling new Array(5), the Javascript runtime will generate an empty array of size 5: we can iterate it and it will return undefined 5 times. As the array items are nothing, they will take no memory space.

Then we map each element from the array to Math.random(). This is a fast for loop which takes each element of the array and assigns it a random number between 0 and 1. We do the same for the matrix, the array of arrays, but this time for each undefined element we assign a full random array. This gives us the initial random population.

Step two: the evolutionary operators

Photo by Dan Cristian Pădureț on Unsplash

Once we have the population, we need to apply the usual operators: pick two parents, create child using crossover, mutate the child, select the best result and add it to the future generation:

export const crossover = (parent1, parent2, crossPoint) => [
  ...parent1.slice(0, crossPoint),
  ...parent2.slice(crossPoint, parent2.length),
];

export const mutate = (individual, probability) =>
  individual.map((e) =>
    Math.random() < probability ? e * Math.random() + Math.random() : e
  );

export const fitness = memoize((individual) => {
  const sum = individual.reduceRight((result, e, index) => result + e, 0);
  return Math.abs(sum - 50);
});

export const pickBest = (...args) =>
  args.reduceRight(
    (result, e) => (fitness(result) < fitness(e) ? result : e),
    args[0]
  );

The crossover operator receives two parents and a cut point and creates a child taking the first part of the first parent up to the cut point and the second part of the second parent. We are using Javascript slice to get the needed parts from the given arrays, and then we use destructuring to get them in the resulting array. The function is fully deterministic and has no dependencies, meaning it could become a const fn if we use the Rust programming language.

Mutation gets an individual and a mutation probability and we do the array mapping trick again: for each element in the array we replace it with a random variation if we match the mutation probability. Otherwise, we leave the element as it is in the array. When using e * Math.random() + Math.random() we simply show a sample alteration that works for the current problem. We are free to change this to a simple Math.random() or anything else that helps the algoritm converge on a solution faster.

The fitness calculator uses reduceRight to sum the elements of the array. For our problem, we try to get a set of numbers that add up to 50. We add the numbers from the given solution and see how far it strays from the needed result, so we use Math.abs(sum - 50). The fitness is also memoized so that if we get the same solution again, we already have the fitness for it and we will skip the calculation. We will look at the memoize function in a bit.

Finally we have the selector function pickBest. This takes a number of solutions and gives us the one with the best fitness. Since we want a single answer out of a set, we use reduceRight again. We start with the first solution, args[0], and for each element we see if its fitness is better than the current result. If it is, we replace the current result.

Side step: the tools

Photo by Elena Rouame on Unsplash

We also use a few tools in our algorithm. We saw the memoize function being used already, but we also want a few more:

export const memoize = (func) => {
  const cache = {};

  return (...args) => {
    const key = JSON.stringify(args);

    if (!cache[key]) cache[key] = func(...args);
    return cache[key];
  };
};

export const same = (a, b) => a.every((v, i) => v === b[i]);

export const roundAll = (array) => array.map((e) => e.toFixed(2));

Memoization cannot be done functionally as it requires a few checks and it doesn’t really act on vectors. But we can see that it creates a cache with key value pairs, where the key is the evolutionary solution, and the value is the fitness. We won’t spend much time on this: it’s a basic memoization solution.

Next we need a solution equality checker, to see if two vectors have the same elements. The simple a === b check won’t work on vectors because it will not perform element comparison, but array memory address comparison which is not useful in our algorithm. We use the Javascript every function for arrays which returns true if all elements of an array obey the given condition. So we check if the current element v is equal to the element at the same index i in the other array.

Finally we have a display tool used to show solutions in a nicer format. For this we again use the map function to round each element of the array to two decimals.

Step three: the evolutionary algorithm

Photo by Ross Sneddon on Unsplash

The last part of the algorithm unfortunately is not functional. It looks like an ordinary evolutionary iteration:

export const createChild = (parent1, parent2, mutationProbability) => {
  if (same(parent1, parent2)) return null;

  const crossPoint = pickRandomNumber(parent1.length);
  const child = crossover(parent1, parent2, crossPoint);
  const mutant = mutate(child, mutationProbability);

  return pickBest(parent1, parent2, child, mutant);
};

export const evolvePopulation = (population, mutationProbability) => {
  const result = [];

  const currentBest = pickBest(...population);
  const mutant = mutate(currentBest, mutationProbability);
  result.push(pickBest(currentBest, mutant));

  for (const element of population) {
    const other = population[pickRandomNumber(population.length - 1)];
    const child = createChild(element, other);

    if (child) result.push(child);
  }

  return result;
};

We have the create child which takes two parents and a probability and gives back the best result among the parents, the original child and the mutated child. If the parents are the same it returns null. This reduces our population from one iteration to the next, optimizing the calculation speed.

The main function, evolvePopulation takes one set of solutions and gives back the next one, ensuring that the next one is a better variant of the first. It also ensures that the best element from the previous population is kept in the new, so we won’t ever end up with an empty set.

The full program is available on Github as I said and I hope it will be useful. In the future I will try to change the main evolutionary algorithm to be functional as well, but for now I was very happy with the outcome for the evolutionary operators. Thank you for reading and see you next time!