Introduction
Machine learning is a growing aspect of computing that's capable of letting systems learn from data provided to it, those systems could be divided into
- Supervised: Supervised learning simply involves learning from labeled data, an example of that would be regression and classification.
- Unsupervised: unsupervised learning involves a system or algorithm that learns from unlabeled data, it is able to classify data based on similarities it finds in data passed into it, an example would be K means cluster algorithm
- Reinforcement learning: This is a newer approach to solving machine learning problems, where an agent is given an environment and asked to interact with its environment, each interaction is scored and rewarded or penalized based on certain defined rules.
There are numerous approaches to solving machine learning problems, some of them can be classified as both supervised and unsupervised learning, so it's not always a yes and no classification.
What is a Genetic Algorithm
A genetic algorithm is a Metaheuristic problem-solving process inspired by the process of natural selection in nature. It is used for finding solutions to high-optimization problems in a problem space, and it does this by following steps inspired by natural processes whereby the strongest or the fittest individuals are the ones that are allowed to survive and pass on their genetic material to the next generation. Doing this enables the next generations to be more optimized to survive the environment they exist in or solve the problem set better.
The Process of natural selection
In nature, the concept of natural selection champions the idea of survival of the fittest whereby organisms that are more adept for the environment survive and are most likely to pass on their traits/genes to the next generation. It also involves the concept of mutation, which implies that organisms are able to mutate their genes to be able to survive or will adapt to their current environment. These mutations are random and play a big variable role in the process of natural selection. This happens over multiple generations or cycles, and is seen in human beings too: in the case of individuals whose ancestors developed immunities to ailments and survived were able to pass that immunity down to their offsprings.¹
A similar process can be applied to computing and problem solving where we try to simulate all the steps of this process to be able to recreate it in real life.
Let's view the components and steps individually.
- Population
- Genes
- Fitness
- Gene Pool
- Selection
- Crossover
- Mutation
Population
These are individuals we generate for our sample problem. They are individual solutions to our given problem, and are all wrong at the start. They are optimized over time to be able to solve problems in their problem space. Each are characterized by components called genes and chromosomes. Let's look at a problem where we want to solve for finding a simple text, lets say that text is a 24 letter string "I am the bone of my sword", initializing a population to solve this would simply be an N population of strings composed of randomized sets of 24 characters.
Gene and chromosomes
The smallest unit of a characteristic of an individual in a population in a genetic algorithm problem are genes. Chromosomes are made up of genes; they define the approach of solving the problems. They can be defined by any means that match your use case, but, in our simple example mentioned above where we want to optimize members of our population to equal the phrase "I am the bone of my sword", our genes for our population are simply the letters in every individual of our population, while the chromosomes can be the full text.
Fitness (Fitness Function)
This is a function that calculates the ability of an individual to solve the problem set given to it. It gives every individual in the population a fitness score. This is used to later assess if the genes are to be passed on to the next generation. Every population apart from the first population is made up of previous individuals, and the average fitness score of the previous generation is always larger than the previous generation.
Gene pool
The gene pool is regarded as a list of every available set of genes(chromosomes) available to be passed on to the next generation. It is distributed to support more parents with more favorable genes, and an individual that has more favorable genes is added to the pool multiple times to increase its probability of being selected to create offspring or pass on its trait to the next generation. An individual with fewer traits won't be added as often, but would still be added, mainly because it may have a desirable trait that we still want to have.
Selection
In nature it is very common that individuals who have desirable characteristics or individuals who are more adept to the environment are able to reproduce and pass on their genetic traits to the next generation. The same is applicable in a genetic algorithm. In this case, we prioritize selecting individuals that have higher fitness scores than the ones that have less, this is done by making sure that the gene pool has more suitable individuals to select from.
A pair of individuals are selected to come together and make one or possibly more offspring (depending on your design). Individuals with high fitness stand a better chance of being selected.
Crossover
This is the process of combining 2 parents individuals to create one or more offspring. This involves crossing both chromosomes of the parents. For this to be possible, we have to select a cross over point or it could be random, or a fixed point in the middle depending on how you design it. The new individuals created are added to the next population.
Mutation
Unfortunately, this won't be the kind of mutation we see in sci-fi movies, Mutation simply implies genes in chromosomes changing their value. The likelihood of. mutation occurring is low and random, but can be adjusted as needed for the purpose of the algorithm. This is necessary since there is a possibility that no member of the initial population has a specific trait to help it reach global ultima.
Last step
We terminate our algorithm after we notice that current generations are not solving the problem more efficiently than the previous generation, so we are left with multiple individuals which are all solutions to our problem set.
Bring this project to life
The codeBase for sample Genetic algorithm problem
You can run this GNN class within your local environment. For faster runs or work on more complicated tasks, consider powering up your workflow by remote accessing a virtual desktop with a high end GPU through Paperspace Core.
class GNN {
constructor(number, goal) {
this.population = []
this.goal = goal || '';
this.genePool = []
this.numnber = number
this.mostFit = {fitness:0}
this.initializePopulation()
}
initializePopulation() {
const length = this.goal.length;
for (let i = 0; i <= this.numnber; i++) this.population.push({ chromosomes: this.makeIndividual(length), fitness: 0 })
}
solve() {
for (var i = 0; i < 10000; i++) {
this.calcFitnessAll()
this.crossParents()
this.mutate()
}
console.log( this.mostFit )
}
mutate() {
this.population.forEach((object) => {
const shouldIMutateChromosome = Math.random() < 0.1
if (shouldIMutateChromosome) {
for (var i = 0; i < object.chromosomes.length; i++) {
const shoulIMutateGene = Math.random() < 0.05
if (shoulIMutateGene) {
const splitVersion = object.chromosomes.split('')
splitVersion[i] = this.makeIndividual(1)
object.chromosomes = splitVersion.join('')
}
}
}
})
}
calcFitnessAll() {
let mostFit = {fitness:0}
this.population.forEach((object) => {
let str1 = this.goal
let str2 = object.chromosomes
let counter = 0;
for (var i = 0; i < str1.length; i++) {
if (str1.charAt(i) === str2.charAt(i)) {
counter++;
}
}
object.fitness = counter > 0 ? counter : 1
for (var i = 0; i < object.fitness; i++) {
this.genePool.push(object.chromosomes)
}
object.fitness > mostFit.fitness ? mostFit = object : mostFit = mostFit
})
if (mostFit.fitness>this.mostFit.fitness) {
this.mostFit = mostFit
}
console.log('Max fitnees so far is ' + this.mostFit.fitness)
}
crossParents() {
const newPopulation = [];
const pool = this.genePool
this.population.forEach(() => {
const parent1 = pool[Math.floor(Math.random() * pool.length)];
const parent2 = pool[Math.floor(Math.random() * pool.length)];
////select crossSection
const crossSection = Math.floor(Math.random() * this.goal.length - 1)
let newKid = `${parent1.slice(0, crossSection)}${parent2.slice(crossSection, this.goal.length)}`;
newPopulation.push({ chromosomes: newKid, fitness: 0 })
})
this.population = newPopulation
this.genePool = []
}
makeIndividual(length) {
var result = '';
var characters = 'ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz .,';
var charactersLength = characters.length;
for (var i = 0; i < length; i++) {
result += characters.charAt(Math.floor(Math.random() *
charactersLength));
}
return result;
}
}
const goal = `I am the bone of my sword. Steel is my body, and fire is my blood.`
const gnn = new GNN(1000, goal)
gnn.solve()
Breaking down the code base
We use a class-based model approach to be able to manage our state for our genetic algorithm.
We first create our population in the initializePopulation function.
initializePopulation() {
const length = this.goal.length;
for (let i = 0; i <= this.number; i++) this.population.push({ chromosomes: this.makeIndividual(length), fitness: 0 })
}This function creates an individual with the makeIndividual function and adds that to the array of populations.
The next step would be to solve the problem with a genetic algorithm.
solve() {
for (var i = 0; i < 10000; i++) {
this.calcFitnessAll()
this.crossParents()
this.mutate()
}
console.log( this.mostFit )
}
The solve function iterates 10000 times and performs the optimization steps over and over again, with every step creating a batch of individuals that are more optimal to our problem.
this.calcFitnessAll()
this.crossParents()
this.mutate()These are steps we follow which include checking the fitness, crossing parents, and then mutating it.
Bonus Facts
Vanilla Genetic algorithm is a nice tool but there exist other variants of this which are also worth noting.
Elitism
This implies a situation where we pass on a certain number of the best performing individuals to the next population unaltered or unchanged. This would make sure that the solution quality would not reduce over time.
Parallel Genetic algorithm
This involves when multiple genetic algorithms are used to solve a particular problem. These networks are all ran in parallel to each other, then after they are completed, the best of them is selected.
Final thoughts
Genetic algorithm is an interesting concept used in machine learning to find optimal solutions to problem sets. It is not always the most ideal tool to solve some problems, but it works well for global optimization problems. Processes like mutation and crossover help move the solutions from a local to a global maximum.
Next steps
This is the first part of our series. I felt it was important to explain the theoretical aspect of the project and provide a foundational codebase, we would be working next on building our environment and agent to interact with the environment
