The purpose of this article is to give the reader a quick insight into what genetic algorithms are, and how they work.
In short: What are genetic algorithms?
Genetic algorithms are a metaheuristic inspired by Charles Darwin's theory of natural selection. They replicate the operations: mutation, crossover and selection. These features make them suitable for use in optimization problems. Because of this, they find applications in a lot of disciplines like chemistry, climatology, robotics, gaming, etc. They are part of evolutionary computation.
The example problem
Before implementing the algorithm, let's take a look of the problem we are going to solve.
You might have heard about the infinite monkey theorem which states that, given an infinite amount of time, a monkey will almost certainly type logical, meaningful text while randomly pressing the keys on a keyboard. Of course, the lifetime of a monkey will probably not be long enough for this to happen. Still, the chances are greater than zero. Very close to zero, but not zero. Anyway, let's stick to the metaphor.
Another way we can imagine this: imagine we have a device that produces random strings. At some point in the future, regardless how long it takes, it will output our desired text.
The purpose of the genetic algorithm we are going to develop is to find an optimal way to achieve the result we are looking for rather than brute forcing it (which will inevitably take a ludicrous amount of time).
This problem is widely used as an example for GA, so for the sake of consistency and simplicity, we will stick to it.
Parts of GA
We already mentioned some of the operations involved in the process. Let's break down the different steps involved in the GA:
- Initializing the population - This is the first step. We will pick a set of members with different traits (or genes). The key here is to have a big enough variety in order to evolve to the target for which we are aiming.
- Selection - The process of selecting those members of our population who are fit enough to be reproduced. This happens by predetermined criteria.
- Reproduction - After we select the fittest members from our current generation, we will perform a crossover -- mixing their traits/genes. Optionally, we will mutate the newly produced members by some random factor. That way, we will further support the variety in our population.
- Repeat 2 and 3 - Simply said -- we will perform selection, crossover and mutation for every new generation until the population evolves to such an extent that we have the desired candidate.
Implementation
Okay, before we start with the algorithm, let's first introduce two utility functions that we are going to use throughout the example. The first one will be used for generating a random integer value in a provided interval, and the second -- generating a letter from a-z:
// Src: MDN
function random(min, max) {
min = Math.ceil(min);
max = Math.floor(max);
// The maximum is exclusive and the minimum is inclusive
return Math.floor(Math.random() * (max - min)) + min;
}
function generateLetter() {
const code = random(97, 123); // ASCII char codes
return String.fromCharCode(code);
}
Now that we have our utils ready, we'll start with the first step of the genetic algorithms, which is:
Initializing the population
Let's introduce our population member or the monkey that we referenced previously. It will be represented by an object called Member which contains an array with the pressed keys, and the target string. The constructor will generate a set of randomly pressed keys:
class Member {
constructor(target) {
this.target = target;
this.keys = [];
for (let i = 0; i < target.length; i += 1) {
this.keys[i] = generateLetter();
}
}
}
For example, new Member('qwerty') can result in a member who pressed a, b, c, d, e, f or y, a, w, r, t, w.
Next, after we have our member created, let's move to the population object, which will keep the set of members we want to evolve:
class Population {
constructor(size, target) {
size = size || 1;
this.members = [];
for (let i = 0; i < size; i += 1) {
this.members.push(new Member(target));
}
}
}
The Population should accept size and target (target string). In the constructor, we are going to generate size members all with randomly generated words, but with equal length.
This should be enough to create a diverse initial population!
Selection
It's time for us to add some methods to the classes we created. We will start with the Member. Do you remember that we had to develop some criteria based on how we determine the fitness of our members? This is exactly what we are going to do by introducing the fitness method.
Let me elaborate:
class Member {
// ...
fitness() {
let match = 0;
for (let i = 0; i < this.keys.length; i += 1) {
if (this.keys[i] === this.target[i]) {
match += 1;
}
}
return match / this.target.length;
}
}
As you can see, what we are attempting to do is to find how many of the randomly pressed keys (by a member) match the letters in our target string. The more, the better! Since we want to have a coefficient as an output, we will divide the matches by the length of the target.
Going back to our Population class, we will implement the actual selection operation. Logically, we would like to have the fitness calculated to every member of the population.
Based on that value, we want to increase the chances of the fittest members being selected, and respectively, decrease the chances of selection for the least fit candidates for the new generation. This can happen by adding an additional array called the mating pool. In it, we will add every member, multiplied by its-fitness-coefficient. To grasp this concept, let's take a look at this example:
Member1 (fitness = 4)
Member2 (fitness = 2)
Member3 (fitness = 1)
== Output ==
MatingPool = [
Member1, Member1, Member1, Member1,
Member2, Member2,
Member3
]
At this point, you should be able to guess the idea behind this approach -- to increase the chances of the fittest members being randomly selected. Note that there are different ways for building your mating pool distribution.
And the code:
class Population {
// ...
_selectMembersForMating() {
const matingPool = [];
this.members.forEach((m) => {
// The fitter it is, the more often it will be present in the mating pool
// i.e. increasing the chances of selection
// If fitness == 0, add just one member
const f = Math.floor(m.fitness() * 100) || 1;
for (let i = 0; i < f; i += 1) {
matingPool.push(m);
}
});
return matingPool;
}
}
Now that we have readied our selection process, it is time to reproduce!
Reproduction
In this section of the implementation, we will focus on the crossover, and mutation operations. This will require further extending of our Member class. I will start by creating the crossover method. Its role is to combine/mix the traits, genes, or in our case, keys, of two parents randomly selected from the mating pool. The output child might contain only keys from parent A or keys from parent B, but in most cases, it will contain keys from both the parents. This happens by selecting a random index from the array that contains them:
class Member {
// ...
crossover(partner) {
const { length } = this.target;
const child = new Member(this.target);
const midpoint = random(0, length);
for (let i = 0; i < length; i += 1) {
if (i > midpoint) {
child.keys[i] = this.keys[i];
} else {
child.keys[i] = partner.keys[i];
}
}
return child;
}
}
Since we are working with the Member, let's add our last method to it. This is the mutate method. Its purpose is to give some uniqueness, and randomness, to the newly created child. It's worth mentioning that the mutation is not something that every genetic algorithm incorporates. That's why we will use a rate which will make the process controlled:
class Member {
// ...
mutate(mutationRate) {
for (let i = 0; i < this.keys.length; i += 1) {
// If below predefined mutation rate,
// generate a new random letter on this position.
if (Math.random() < mutationRate) {
this.keys[i] = generateLetter();
}
}
}
}
// We will also have to update the Population constructor
class Population {
constructor(size, target, mutationRate) {
size = size || 1;
this.members = [];
this.mutationRate = mutationRate // <== New property
// ...
}
// ...
}
It's time to tie these two in our Population class. Previously, we added the _selectMembersForMating. Let's make use of it:
class Population {
// ...
_reproduce(matingPool) {
for (let i = 0; i < this.members.length; i += 1) {
// Pick 2 random members/parents from the mating pool
const parentA = matingPool[random(0, matingPool.length)];
const parentB = matingPool[random(0, matingPool.length)];
// Perform crossover
const child = parentA.crossover(parentB);
// Perform mutation
child.mutate(this.mutationRate);
this.members[i] = child;
}
}
}
Here, we only pick 2 random parents. Then, we perform the crossover. After that comes the mutation. And then finally, we replace the member with the new child. That's it!
We are almost done. For the purposes of this demo, we are going to add control over the number of generations (or iterations) that we want to have. That way, we can closely monitor how our population changes over time. In a real world scenario, we would like to create new generations until we reach our final goal or target. Anyway, let's add the final evolve method to the Population class for that goal:
class Population {
// ...
evolve(generations) {
for (let i = 0; i < generations; i += 1) {
const pool = this._selectMembersForMating();
this._reproduce(pool);
}
}
}
In the end, we will add a helper function that will make the running process a bit easier for us:
function generate(populationSize, target, mutationRate, generations) {
// Create a population and evolve for N generations
const population = new Population(populationSize, target, mutationRate);
population.evolve(generations);
// Get the typed words from all members, and find if someone was able to type the target
const membersKeys = population.members.map((m) => m.keys.join(''));
const perfectCandidatesNum = membersKeys.filter((w) => w === target);
// Print the results
console.log(membersKeys);
console.log(`${perfectCandidatesNum ? perfectCandidatesNum.length : 0} member(s) typed "${target}"`);
}
generate(20, 'hit', 0.05, 5);
Running this, we will create a population of 20 members whose target is to type "hit". We'll execute it for 5 generations with a mutation rate of 5%.
Note: Keep in mind that, for our demo, the target string must contain only lowercase a-z letters.
Results
Having this particular population evolve for 5 generations will probably end up with 0 members who typed "hit". However, making that number 20 might land us a good candidate:
5 Generations | 20 Generations
-----------------|------------------
... | ...
|
'gio' | 'fit'
'yix' | 'hrt'
'gio' | >> 'hit' <<
'kbo' | 'hiy'
You can find the full source code on GitHub
If you want to dig more into genetic algorithms ...
Since the article only lightly touches on what genetic algorithms are, I highly recommend you check out The Nature of Code by Daniel Shiffman (from which this text was based on). It is a great resource for those who want a deeper insight.
