This page is incomplete. You can check out hill_climbing, which implements the same thing in a simpler way
Hello everyone. In this article I will be trying to make a super simple introduction to genetic algorithms that will hopefully be suitable for beginners. First of all, let’s begin by defining the term “genetic algorithm”. The Wikipedia definition tells us that a genetic algorithm is a search heuristic that mimics the process of natural selection.
Now don’t let the big words like heuristic and natural selection scare you. Genetic Algorithms are actually really easy to understand. To put it simply; we start with a list of random and incorrect solutions, we make random modifications to those solutions, we breed them together and then we eliminate the ones that perform badly. Do this enough times and we’ll be left with a solution that is good enough. Sounds cruel? Well, so is natural selection.
With all the defining out of the way, let’s begin to code a simple example. This example is a classic one if you’ve read another Genetic Algorithm tutorial. We’ll try to evolve the string Hello world.
Generating the Initial Population
In order to begin the whole mutate-breed-evaluate-repeat loop, we will first need an initial list of random solutions. Since we are trying to evolve a string, our solutions will need to be random strings of ASCII characters. Python has a helpful module called string for this. We will create a chromosome class which we will use throughout this article.
import string
import random
def random_string(length):
return "".join([random.choice(string.ascii_letters) for _ in range(length)])
class Chromosome:
def __init__(self, length):
self.code = random_string(length)
self.fitness = None
population = []
for _ in range(20):
# Generate 20 random solutions for the population
population.append(Chromosome(11)) # 11 is the length of our target string
This will leave us with 20 random chromosomes. Now we can begin the main loop that will eventually evolve Hello world.
Mutating the solutions
In our main loop, we will have a small chance of mutations. The mutated solutions will be added to the population while keeping the old ones so only a better solution will replace the random one.
def mutate(self):
target_len = len(self.code)
index = random.randrange(target_len)
new_solution = list(self.code)
new_solution[index] = random.choice(string.ascii_letters)
self.code = new_solution
Breeding / Crossing-over the solutions
When searching for an optimal solution, some chromosomes might have solved part of the problem while other chromosomes have solved other parts. Breeding those chromosomes together increases the likelihood of finding a solution that performs well. Now we will add a method to our chromosome class that will cross-over with another instance. Again, these will only replace the current solutions if they are better.
def crossover(self, other)