Evolutionary algorithms: theoretical aspects of evolution

https://miro.medium.com/max/1200/0*Xth0KDQFPG6UlX9C

Original Source Here

Evolutionary algorithms: theoretical aspects of evolution

Photo by Anne Nygård on Unsplash

We are kicking off our incursions into artificial intelligence by visiting my all time favorite: evolutionary algorithms. We talked a bit last time about what means to implement artificial intelligence. We saw that it’s not about what the game character does to avoid your target, nor what it does to solve a maze. Both things can be done perfectly fine using deterministic algorithms. Defined by computer science, artificial intelligence is about borrowing biologic traits and behaviors into programs to solve a given task.

Evolutionary algorithms try to find a solution by straight up implementing the evolutionary process of biological organisms. That is, begin with a random solution and improve it using evolutionary behaviors until the solution is able to solve our problem. Of course to make this work, scientists had to split and tag evolution and transform it into an algorithm, keeping it true to our current suppositions on how the world functions. The result? Four steps.

Step one: choose the parents

Photo by Victoriano Izquierdo on Unsplash

We all believe in true spontaneous love but in biology that’s just a byproduct of natural selection: the tendency to favor better parents on the long run. What does better mean? It depends on the problem that needs solving: maybe it’s an ice age, pollution, over population, each situation requires certain well adapted parents that are able to create even better adapted children. This of course won’t happen over night but across several generations, leaving room for the random artifact we call love.

If we want to implement this in code, we need to take two solutions from a set by measuring all available solutions and find the best two. They don’t have to be two either. It’s our algorithm so we may select as many parents as we want, but we still have to implement some tendency to pick the better ones. This is easy. I will use a sort of random javascript syntax here to explain:

let population = [a, b, c, d, e];
let parent1 = pickParent(population);
let parent2 = pickParent(population);

So we have our population of solutions for a given problem (we will see in a moment how those look like) and we need to pick two parents. We could pick them randomly:

function pickParent(population) {
let populationSize = population.length();
let index = Math.random() * populationSize;
return population[index];
}

The above will simply pick a random solution from the population, by using Math.random() which gives us a random number between zero and one and setting that result to expand to our population size. But this is not pressing for the best parents, it’s not adding any biological intelligence. It’s just a random selector. To do that, we must check the solution we want to return and only give it back if it’s one of the better:

function pickParent(population) {
let populationSize = population.length();
let index = Math.random() * populationSize;
if (fitness(population[index]) < 0.3) {
return population[index];
else {
return pickParent(population);
}
}

Above we are using a secret function we will talk about in a moment, called fitness. This function will return a number between zero and one, saying how close to perfect is our solution. Zero means the solution is perfect, one means it’s the worst. The above pickParent function then will only return solutions that are close to perfect (fitness < 0.3). But is this fair? Not at all and it does not implement the random flukes of love. Any two individuals should have at least a chance to “fall in love”. So let’s change it a little:

function pickParent(population) {
let populationSize = population.length();
let index = Math.random() * populationSize;
if (fitness(population[index]) < 0.3 || Math.random() < 0.5) {
return population[index];
else {
return pickParent(population);
}
}

There. If the fitness won’t be good, we will make an additional coin toss with fifty-fifty chance. This way, even though the fitness won’t be good, the chosen individual will still have a random chance. Of course we may set the chance however we want: Math.random() < 0.3 will provide a 30% chance, meaning a stronger preference towards better solutions.

Step two: mix the parents to produce the child

Photo by Bilal O. on Unsplash

We have our two parents selected by better fitness or chance, not that it would matter too much in the end. We are still talking about a process that runs over hundreds of thousands of generations. But how do we turn procreation into an algorithm? Again, scientists like to simplify everything to its very core and so here comes the blatantly irritating algorithm: take a part of one parent and the other part of the other parent.

So, we don’t care at this point how a parent looks like in our program. We just have this instruction: take one part from parent1, one part from parent2 to form child. This is how it will look like again, in approximate javascript:

let population = [a, b, c, d, e];
let parent1 = pickParent(population);
let parent2 = pickParent(population);
let child = mix(parent1, parent2);

Again, we can consider how many parents we want but in our case we will stick to two. So let’s define the mix function then:

function mix(parent1, parent2) {
let part1 = selectRandomPart(parent1);
let part2 = selectRandomPart(parent2);

return combine(part1, part2);
}

As you see, we are doing exactly what the recipe says: pick one part from one parent, one from the other and combine the parts to create the child. We will see in the next article how this looks in an actual problem. As a sneak peek it can mean anything really but there are some forms and representations that make it work easier. For now we stick to the theory.

Step three: arrange for random mutations

Photo by Sangharsh Lohakare on Unsplash

Continuing with the evolutionary process, from time to time mutations occur so we need to accommodate our algorithm for that. Mutations may happen in many places of one’s life. For example you get exposed to radiation during your lifetime or something happens before birth, during the combination of the parent’s genes. But the result is always the same: something changes and it’s not related to anything, it’s just random. If combining the parents takes given and proven parts that we know work, mutation is something much more vague. It may work better or it may completely destroy a perfect combination of genes. So let’s add it to our algorithm:

let population = [a, b, c, d, e];
let parent1 = pickParent(population);
let parent2 = pickParent(population);
let child = mix(parent1, parent2);
let mutant = mutate(child);

How does mutate look then:

function mutate(child) {
let doesMutationOccur = Math.random();
if (doesMutationOccur < 0.5) return child;
let childProperties = Object.keys(child);
let randomIndex = Math.random() * childProperties.length();
let randomProperty = childProperties[randomIndex];
child[randomValue] = getRandomValue(randomProperty);
return child;
}

Again, the above algorithm does not strive to be correct, it’s just a prototype so we understand what mutation means. Basically if the child is an object like dog with some properties like dog.breed and dog.age, a mutation means we pick a property at random for example age and we give it a new random value. Note that the random value has to make sense for the given property, that’s why we resort to a getRandomValue function that receives the property as a parameter.

Basically if the random property is age, the result of getRandomValue(age) would be something like 3. If the property is breed, the result would be husky. Of course in real life mutation doesn’t randomly change a dog’s breed but this is just a prototype algorithm so we understand how mutation works. We will see next time when we talk about genetic algorithms that breeding a new child and mutating it matches a lot better with the biological organisms.

Step four: the fitness function

Photo by Victor Freitas on Unsplash

We created a few functions here that help us interpret evolution in a way that makes sense for a computer program, but we conveniently left out the most important part, the fitness of each solution. Fitness in this case means how good is it, how well it matches and solves our problem. You see, our algorithm is based on the fitness function. Without it, it cannot work, it will forever create children and mutate them, but there won’t be any force to push for better results. Let’s finish our algorithm:

let population = [a, b, c, d, e];
let parent1 = pickParent(population);
let parent2 = pickParent(population);
let child = mix(parent1, parent2);
let mutant = mutate(child);
if (fitness(mutant) < fitness(child)) {
nextGeneration.push(mutant);
} else {
nextGeneration.push(child);
}

The algorithm is supposed to receive a population, apply some evolutionary functions on it and create the next generation. What will the next generation contain? The parents will certainly die although we can include them for a while (again, it’s our algorithm and we do as we see fit). But in the above example we do a single thing: pick between the child and the mutant. We check their fitness and pick the best. That’s the next generation. We can do this for every individual in the group and so we have a new generation of identical size:

function createNextGeneration(population) {
let result = [];
for (let i = 0; i < population.length(); i++) {
let parent1 = pickParent(population);
let parent2 = pickParent(population);
let child = mix(parent1, parent2);
let mutant = mutate(child);
if (fitness(mutant) < fitness(child)) {
result.push(mutant);
} else {
result.push(child);
}
}
return result;
}

The above function will take a random population and give us the next generation of identical size. If ten individuals go in, ten individuals will come out. This allows us to repeat the process forever. But still, what is the fitness function?

That’s the trick: it depends on the problem we want to solve. There is no generic fitness function. We are pressing forward with better and better results but there cannot be a generic fitness for all problems. If our program is to breed better dogs, the fitness function may be something like this:

function fitness(dog) {
let result = dog.age + dog.pastIllnesses.length() + dog.temper + dog.visionMeasurement + dog.speed;
return sigma(result);
}

The above function will add up all characteristics of a dog and return them as a fitness number. Remember that fitness should be a number between zero and one, the lower the better, so I am passing the result through a sigma transformation function that takes whatever integer it receives and returns a weighted value of it, between zero and one. There is no such function in javascript so again we need to write it ourselves. But again, this is closely related to the values of the properties in the dog object so it cannot be generic. Here is an example:

function sigma(raw) {
return 1 / (1 + Math.exp(-1 * raw));
}

The above function will map any integer to a number between zero and one. It’s up to us to make sure we add the numbers correctly so a lower fitness is better.

Adding everything up

Photo by Wyron A on Unsplash

Our program is ready. We have all the building blocks we need to create an evolutionary algorithm that adds pressure with each generation to find a better result. What is the better result? As we saw, it all depends on the fitness function: that’s the one that decides between individuals. To look for the perfect dog is one thing, but we may be looking for something that actually solves a business problem, like the best route for a delivery truck. We will see in the next article practical applications for evolutionary algorithms, but for now let’s wrap our program up:

var population = getRandomPopulation();for (let i = 0; i < 100; i++) {
population = createNextGeneration(population);
}
population = sortByFitness(population)
console.log(population[0]);

Again we are missing a few functions but I won’t spend time writing them here. The next article will be more practical as we will try to create a useful application that solves an actual problem. For the theory, the above will suffice. We create a random population: it doesn’t really matter with what we start since we will pressure the system to improve. Then for 100 times we create a next generation based on the previous. After 100 generations we stop, sort the final population by fitness and display the first one, the individual with the fitness closest to zero: the best one.

We can easily see that this algorithm can basically run forever. If we are not satisfied with the result, we can run the algorithm for another 100 generations and so on. We can also note that the algorithm is heuristic, meaning for a given input we won’t get the same output. The output is always different, based on many random aspects we applied for each function. But one thing remains constant: each new generation will be better than the last and we have certain triggers to control how fast everything converges to the best solution, like the mutation probability and the random parts selected from the parents to compose the child.

If you think all of the above may never work, there is a full statistical theory behind evolutionary algorithms that goes very deep in all the aspects that make it work. If you think about it, it’s basically a search through a vast space of solutions. But even though it starts at a random point each time, the way it pushes itself to find better solutions is not random. Yes, it will take many generations to find the perfect answer but that’s how biologic intelligence works. The catch? What evolution does in millions of years, a computer can run and simulate in a few seconds.

AI/ML

Trending AI/ML Article Identified & Digested via Granola by Ramsey Elbasheer; a Machine-Driven RSS Bot

%d bloggers like this: