Genetic algorithms: applied evolution

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

Original Source Here

Genetic algorithms: applied evolution

Photo by Sangharsh Lohakare on Unsplash

Last time we started our artificial intelligence journey by looking at biological evolution and how a program would go about implementing it. As we were only interested in the theory, our algorithms could stray and divert wildly into any form given by our imagination. But that’s ok: after all evolution is just an optimization strategy. It doesn’t really matter how we implement it and for what purpose. If we are looking for an optimal solution and we know how to judge a result, we can iterate over thousands of generations to find what we need with minimal CPU cost.

But let’s focus now on a particular kind of evolution: the genetic kind, which brings us as close to biology as a software developer will ever get. Last time we considered the solution as to be a random object, a dog for example that has a few dog attributes like age, breed, speed and so on. We computed a dog’s fitness by performing an imaginary addition of these attributes: we didn’t care exactly how it’s done, it was just theory. Well genetic algorithms are stricter. The solution in a genetic algorithm population is called an individual and it’s an array of numbers called genes. It’s like representing a human and its DNA.

Assigning meaning to genes

Photo by Rodrigo Abreu on Unsplash

So if we are restricted to arrays of numbers, we may call them fancy names but how can we solve anything useful? Let’s consider a distribution problem: we have a truck and it needs to go through several locations to deliver goods. We need to create a route that goes through all locations optimally: once per location and having minimal distances between locations. How would our solution look like?

let individual = [0, 1, 2, 3, 4, 5];

Above we define an individual as an array of genes. The genes represent the location where the truck will go next. In the above example, the truck would go in all six locations in order. The genes are the locations and the individual is a full schedule, a solution. In this case, having a population of such solutions would look like this:

let population = [ 
[0, 1, 2, 3, 4, 5],
[1, 3, 5, 0, 2, 4],
[2, 5, 0, 3, 1, 4]];

The above population has three individuals, each of them a solution to our problem. We want to find the quickest route, the one spending fewer miles, so we need to define the distances between every location:

let distances = [
[0, 15, 7, 25, 33, 11], // location 0
[9, 0, 24, 30, 15, 10], // location 1
[11, 25, 0, 18, 10, 10], // location 2
[33, 66, 13, 0, 95, 50], // location 3
[14, 15, 11, 9, 0, 10], // location 4
[10, 10, 22, 25, 30, 0]] // location 5

The distance matrix puts a distance value for each location. If we want to go from location 0 to location 2, the distance is 7. If we want to go from location 2 to location 4, the distance is 10. The distance from location 0 to location 0 is of course 0. We can also create no go routes by setting the distance to infinity. For example if there is no route between location 1 and 4, we put Infinity instead of 15.

Computing fitness

Photo by Graphic Node on Unsplash

With this configuration, computing the fitness of a solution is easy:

function fitness(solution, distances) {
let result =
distances[solution[0]][solution[1]] +
distances[solution[1]][solution[2]] +
distances[solution[2]][solution[3]] +
distances[solution[3]][solution[4]] +
distances[solution[4]][solution[5]];
return result;
}

The route goes from location to location as defined by the solution vector. So what we need to do is simply add the distances between these locations in the order they appear in the solution. So first we go from the location defined in solution[0] to solution[1]. To get the distance, we look in the distances matrix and take the first row corresponding to solution[0] and the column corresponding to solution[1]. Once we understand the algorithm we can make it generic:

function fitness(solution, distances) {
let result = 0;
for (let i = 0; i < solution.length() - 1; i++)
for (let j = 1; j < solution.length(); j++)
result += distances[solution[i]][solution[j]];
return result;
}

The above function will give us a raw number of the total distance our truck will make for a given route, or solution. But if we are looking for the shortest path, there is a loophole a genetic algorithm will quickly find: with the above fitness function, the solution [1, 1, 1, 1, 1, 1] has perfect fitness, zero. So what do we do to press the system to evolve routes that always go somewhere instead of standing still? The only thing we can: penalize wrong routes in the fitness function:

function fitness(solution, distances) {
let result = 0;
for (let i = 0; i < solution.length() - 1; i++)
for (let j = 1; j < solution.length(); j++)
result += distances[solution[i]][solution[j]];
for (let i = 0; i < solution.length(); i++)
if (!result.includes(i))
result += 1000;
return result;
}

In the updated fitness function above, we take all available locations and we check to see if they are somewhere in the solution vector. If any is missing, the result will be penalized with 1000 points. This means that while striving to minimize the fitness in the population, the algorithm will favor solutions that have all locations in them. Else the solution will be penalized so bad that the distance between locations won’t matter much anymore. Those solutions will quickly be discarded.

Crossover and mutation

Photo by FLY:D on Unsplash

A genetic algorithm also has the classical evolutionary operations: the mix of parents here is called crossover, as we take two individuals and cross their genes to create the child and then we have mutation. Because we always talk about the same representation, a vector of numbers called genes, these two operations can be fully generalized to work with any problem, for any genetic algorithm. We are fully decoupling and abstracting away the evolutionary operations from the problem:

function crossover(parent1, parent2) {
let index = Math.random() * parent1.length();
let part = parent2.slice(index);
let child = parent1;
child.splice(index, child.length() - index, ...part);
return child;
}
function mutation(child, randomGeneProvider) {
let result = child;
for (let i = 0; i < result.length(); i++)
if (Math.random < 0.3) result[i] = randomGeneProvider();
return result;
}

In the crossover function we are selecting a random split point called index, we copy the first parent fully in the child and then we splice the second parent from the index to the end. Basically if we have two parents [0, 1, 2, 3, 4, 5] and [3, 5, 1, 4, 0, 2], if the split index is 4, the child will be [0, 1, 2, 3, 0, 2]. Note that the crossover and mutation functions don’t care much about the resulting child. In this case, the child provides a solution that makes the truck go twice in location 0 and 2. But again, this is not the responsibility of crossover or mutation, it’s fully with the fitness function.

In the mutation function receives a callback randomGeneProvider. It’s just a function that gives me a number that makes sense for my problem: in this case a random number between 0 and 5. Here I am giving the gene provider as a parameter so that the mutation function remains generic for any problem.

Considering different problems

Photo by Clay Banks on Unsplash

I am skimming the explanations a bit because all of this is exactly what we talked last time about evolutionary algorithms. The only thing we changed is the solution format which for genetic algorithms is a vector of numbers. If you can represent the solution to your problem as a vector of numbers, you are able to solve it with a genetic algorithm.

So before we end this article, let’s think about a few other problems and how they would be represented in a format suitable for a genetic algorithm. For example, polynomial regression. We want to find a polynomial, an equation of the form 1+x+x²+x³+…=0 that passes through a given set of points. We know the points, we want the equation. For this problem, a solution can be neatly fitted in a vector: [1, 6, 7, 8, 3] means 1+6*x+7*x²+8*x³+3*x⁴=0. The fitness of this solution means we run all the points we have in our database on this function and add up the differences. The points will be values for every power of x and the difference will be our result minus the correct result. Add all differences together and you get the total fitness of the solution.

Another example: filling a backpack with objects of different weights. The solution can be a full backpack, a vector containing numbers representing the object we add in the backpack. The fitness function is the result of adding all the weights that we have in the backpack solution and subtracting the maximum weight that the backpack can hold. We also need to penalize the solutions that have the same object twice or the solutions that don’t include certain preferred objects for example.

Different one: school class schedule. The solution is a matrix this time, having the whole schedule for a class, Monday to Friday, for each hour from 8 AM to 3 PM for example. The fitness would check that all courses are present in the schedule, that no two courses overlap and that each course has the correct number of hours per week.

AI/ML

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

%d bloggers like this: