# Functional operators for evolutionary algorithms

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

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

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  );`

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`, 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

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

`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.