This is a short article that explains what are genetic algorithms in general
Introduction
One of the fields in programming world is Artificial Intelligence we as humans make very weird solutions to some weirder problems that we have in our modern society which add a little bit knowledge to our understanding, in this article we are gonna talk about a field or a branch in AI which is called genetic algorithms what are they? how do they work? in what kind of problems we use them?
in simplest terms genetic algorithms are to solve those kind of problems which have multiple solutions or have a very large search space that is just unfeasible to try solving it with traditional programming.
The Idea
Best way to deliver our idea is to make an example or make a story and we try to understand through it basically genetic algorithms are using the idea of evolution and the concept of natural selection if we take a population of animals in nature we may find strong individuals, weak ones, old ones...
what is important here what are the individuals who reproduce and make a new generation
Problem Example
Let's say you have a a hypothetical echo system where animals have a DNA consisted only of binary numbers and the length of DNA for every animal is 8bit(1 byte) long rather miserable animals 🤔 but assume that what our goal is to find an animal that have a DNA which is exactly like 11111111
in another way the problem is like this
in a binary string of length 8 find a string that have all bits set to 1
to start solving those kind of problems which we know the solution but we miss the path to reaching that solution or at least approximation of the solution is acceptable we use genetic algorithms
in our example what is the best way to find an animal which have a DNA of 1's ?
the answer is simple Guessing is our best choice we generate random DNA samples and evaluate each sample and we pick only ones that are more like our ideal animal, our animals have genomes consist of chromosomes which consist of DNA's so animals in our echo system have 1 chromosome which contains 1 DNA stripe with size of 1 byte.
we talked about picking animals that are similar to our ideal animal evaluation is based on something called a fitness value and fitness function
fitness value : is related to each individual(animal in our case)
fitness function: is the function that assigns and evaluates fitness value for each individual saying this animal is more like our ideal animal ex: because it's DNA contains 5 ones so we pick that over another animal.
The Steps
Steps for approaching the solution we use our ideal animal example
Generate initial population
We start by making a population(an array) of 22 animals(DNA strings) randomly(math.random 😁) we call this Generation1 or g1
Run fitness function on g1
We run fitness function on g1 and assign fitness value to each animal or DNA string
Pick best animals to reproduce
What our randomly generated animals would do reproduce of course but it's not up to them to pick we do that by picking ones that have highest fitness value or there are multiple ways to do that it's called
Selection phase in academic books
a. Roulette Wheel Selection(we talk about this)
b. Rank Selection
c. Steady State Selection
d. Tournament Selection
e. Elitism Selection
let's say we went with Roulette Wheel Selection what this does it will assign a portion of the wheel to each individual based on their calculated fitness value the higher the value the larger are they occupy on the wheel
then we spin the wheel and pick a spot randomly what we see is that animals with higher fitness value are most likely to get picked
mating season 🎉
our animals do their thing and produce offspring's this action is called Crossover in academic books before we produce Generation2 or g2 we have another action that is happening while our animals do Crossover its called Mutation just like natural beings our baby animals are subjected mutation in our case maybe in each 1,000 baby we will change DNA of 3 of them at random by 1 bit also randomly this may increase the chance of getting closer to our ideal animal after that we say that we generated second generation g2
Repeat
What we did to generate g2 from g1 we repeat that process many times till we get closer and closer to our solution but when to stop is also our decision we may say that if you find an animal that is 85% like our ideal animal we stop and pick this as a solution.
Key points
1- Very good at approximating solutions that are hard to program or expensive to calculate
2- For very complex problems they may require many generations to produce a good approximation
3- Genetic algorithms weak point is that when you have time bounded variables in your logic which means our data may change according to time
Actual example
This is a demo what if we wanted to approximate a cat picture
Final words
This was a humble explanation for a very interesting topic if you find any inconsistency or mistake please correct me thanks.
Top comments (0)