Genetic Algorithm in action!

What is the Genetic Algorithm?, to a human!

The Genetic Algorithm is a clever idea used in many fields to solve problems that otherwise take too much computing power or time. It mimics the process of evolution in nature, in a very bare-bones manner. The usage of various processes to evaluate genes, fitness scores, the target really makes it useful in implementing it for various different needs.

What is the Genetic Algorithm?, to a computer!

Now, the computer doesn't understand English or any other communication language for that matter. So how do you implement it in code. I'll be using Python and a library called Pygame, to visualize the Genetic Algorithm.

Setting up the environment

Tools required:

1. python=3.8 or above
2. pygame=2.0.2 or above
3. A good text editor(I'll be using Microsoft Visual Studio Code)
4. A cup of coffee(or more!)

Building the Pygame display

The pygame display is easy to build. All you have to do is initialize a screen with,

display = pygame.display.set_mode((width, height))

where width and height are the dimensions of your display. Then in a function, initialize a while loop and update the pygame display. The code for the above mentioned is,

import pygame

width = 720
height = 480
display = pygame.display.set_mode((width, height))
pygame.display.set_caption("Genetic Algorithm")

def main():
    run = True
    while run:
        for event in pygame.event.get():
            if event.type == pygame.QUIT:
                run = False


        pygame.display.flip()

if __name__ == "__main__":
    main()

The structure of the algorithm

The genetic algorithm uses a clever way to mimic the process of evolution in nature. Generally, the are n number of individuals I call genomes. Each genome has a set of "genes" and their behavior is dictated by their genes.

These genes are randomly initialized and are then evaluated on a specific task. For our example, we will be using vertical motion of each individual. Then the best performing genes are selected and a "breeding" process is done in hopes or increasing the pattern of the best performing genes. There is also a process of "mutation" where a small change is done to the genes of the genome to introduce variance and hopefully some helpful genes to boost up the evolution process.

Creating the Genome class:

What I'll be referring to as "Genomes" are the individuals who are going to evolve using the magic of natural selection and mutation to become the best at a specific task(or at least, good enough)

We will create a class called Genome() since we will be using multiple instances of it later on.

class Genome:
    def __init__(self, target):
        self.gene_length = GENE_LENGTH
        self.gene = []
        self.x = width // 2
        self.y = 10
        self.step = 0
        self.target = target
        self.fitness = -1
        self.dead = False
        self.generation = -1

    def draw(self):
        pygame.draw.circle(display, (0, 170, 200), (self.x, self.y), 4)

    def create_genes(self):
        pass

    def move(self):
        pass

    def calc_distance(self):
        pass

    def calc_fitness(self):
        pass

    def crossover(self, partner):
        pass

    def mutate(self):
        pass

Each genome has a target and the performance of the genome is evaluated based on the target. In our case, the target is just a box and the objective of the genome is to reach the box/target.

The performance of a genome is also called the "fitness" of that genome. They are ranked based on their fitness. The step variable is used to step through the gene of the genome and make the moves based on that position of the gene.

The methods the genes are

• create_genes: Create the initial genes randomly, consisting of (x, y) ordered pairs each with a random value between -1 and 1.
• move: The move function steps through the gene using the step variable and updates the x position and the y position of the genome based on the (x, y) pair in the gene.
• calc_distance: This method is used to calculate the distance between the genome and the target. The distance used here is the euclidean distance.
• calc_fitness: The fitness is calculated based on the euclidean distance between the genome and the target. Then the distance is normalized between 0 and 1.
• crossover: This is one of the important methods in the algorithm. We create new genomes from the genes of old ones. The crossover process in done by intertwining the genes of two parents. For example, let the following genomes be the parents.

Then to breed them, their gene are intertwined to make a new gene of the same length.

By this process, we can multiply the genes that result in a better fitness than poorly performing genes.

• mutate: Mutation is also an important step in the genetic algorithm. Generally mutation is done based on a mutation rate, which is a constant. But we can also introduce varying mutation rates if we need to. However, we are going to use a constant mutation rate. Initialize a MUTATION_RATE variable which holds how much percentage of the genes should be mutated. In my code, I've given a 2% chance for mutation. Therefore, my MUTATION_RATE is going to be,

MUTATION_RATE = 0.02

While we are at it, we can also initialize some other important constants like the population size, the gene length etc...

POPULATION_SIZE = 100
MUTATION_RATE = 0.02
GENE_LENGTH = 10000

Now we can populate the genome class with actual code...

class Genome(object):
    def __init__(self, target):
        self.gene_length = GENE_LENGTH
        self.gene = []
        self.x = width // 2
        self.y = 10
        self.step = 0
        self.target = target
        self.fitness = -1
        self.dead = False
        self.generation = -1

    def create_genes(self):
        for _ in range(self.gene_length):
            x_direction = random.uniform(-1, 1)
            y_direction = random.uniform(-1, 1)
            self.gene.append([x_direction, y_direction])

    def draw(self):
        pygame.draw.circle(display, (0, 170, 200),
                           (self.x, self.y), 4)

    def move(self):
        self.x += self.gene[self.step][0]
        self.y += self.gene[self.step][1]
        self.step += 1

        if self.step >= self.gene_length:
            self.fitness = self.calc_fitness()
            self.dead = True

    def calc_distance(self):
        # using pythagoras' theorem to fing the shortest distance between the
        # genome and the give target
        perpendicular = abs(self.target.x - self.x)
        base = abs(self.target.y - self.y)
        dist = math.sqrt(perpendicular**2 + base**2)
        return dist

    def calc_fitness(self):
        # using a fitness function to find the fitness of
        # the specific genome, and use it as the metric to
        # improve it's probability of becoming a parent
        dist = self.calc_distance()
        normalized_dist = dist / height
        fitness = 1 - normalized_dist
        return fitness

    def crossover(self, partner):
        child = Genome(self.target)
        for i in range(self.gene_length):
            if i % 2 == 0:
                child.gene.append(self.gene[i])
            else:
                child.gene.append(partner.gene[i])

        return child

    def mutate(self):
        for i in range(GENE_LENGTH):
            mutation_probability = round(random.uniform(0, 1), 2)
            if mutation_probability < MUTATION_RATE:
                mutated_gene_x = random.uniform(-1, 1)
                mutated_gene_y = random.uniform(-1, 1)
                self.gene[i] = [mutated_gene_x, mutated_gene_y]

Creating the Population class:

A population is just a group of n number of genomes. In our case, a population consists of 100 genomes(POPULATION_SIZE). But, since we need to process the fitness of each genome, breed them, and also keep track of the generation, we'll encapsulate the information in a Population class.

class Population(object):
    def __init__(self, target):
        self.target = target
        self.population = []
        self.generation = 0

    def populate(self):
        pass

    def natural_selection(self):
        pass

    def breed(self):
        pass

The population class is going to hold a target, which will be passed on to the genomes of the population. It also keeps track of the generation and an array of all the genomes in the population.

As usual, we'll go through the methods in the class.

• populate: As the name suggests, this method is used to populate the genomes in the population class. In the first generation, the genomes are made with random genes. At the later stages, the genomes are the children of their previous generation.
• natural_selection: The natural selection method creates a mating pool, which is essentially just an array of genomes. But the mating pool has genomes whose frequency in the mating pool is directly proportional to the fitness of the genome. So the "fitter" a genome the higher the number of it in the mating pool. Since the fitter genomes are higher in frequency, the chances of them being selected for the mating process is also higher. Hence, the fitter genomes survive longer.

Survival of the fittest.

• breed: Finally, the breeding part. Here we are just going to select random individuals from the mating pool generated by the natural_selection method and breed their genes by intertwining their genes as mentioned above.

Hence the code for the methods are,

class Population(object):
    def __init__(self, target):
        self.target = target
        self.population = []
        self.generation = 0

    def populate(self):
        self.population = [Genome(self.target) for _ in range(POPULATION_SIZE)]
        for genome in self.population:
            genome.create_genes()
            genome.generation = self.generation

    def natural_selection(self):
        mating_pool = []
        for genome in self.population:
            fitness_ratio = math.floor(max(genome.fitness, 0) * 100)
            for _ in range(fitness_ratio):
                mating_pool.append(genome)

        return mating_pool

    def breed(self):
        generation_dead = all([genome.dead for genome in self.population])
        if generation_dead:
            self.population = self.natural_selection()
            children = Population(self.target)

            for _ in range(POPULATION_SIZE):
                father_genome = random.choice(self.population)
                mother_genome = random.choice(self.population)
                child_genome = father_genome.crossover(mother_genome)
                child_genome.mutate()
                child_genome.generation = self.generation
                children.population.append(child_genome)

            self.population = children.population
            self.generation += 1

Creating the Target class:

The Target is the object that is going to be the destination for the genomes. We are going to evaluate the fitness of the genomes by calculating the distance between the target and the genome. The smaller the distance, the fitter the genome is. Therefore, the target object is only ever going to need to have two variables, x and y. And a draw method to draw the target to the screen.

class Target(object):
    def __init__(self):
        self.x = width // 2
        self.y = height - 10
        self.width = 20

    def draw(self):
        pygame.draw.rect(display, (0, 200, 170), (
            self.x - self.width // 2, self.y - self.width // 2, self.width, self.width))

Genetic Algorithm!

Finally it is time to see the algorithm work. But before that we have to create the necessary objects and add them to the main function. To do that,

def main():
    run = True
    food = Target()
    population = Population(food)
    population.populate()

    while run:
        display.fill((0, 0, 0))
        for event in pygame.event.get():
            if event.type == pygame.QUIT:
                run = False

        for genome in population.population:
            genome.draw()
            genome.move()

        food.draw()
        population.breed()
        pygame.display.flip()


if __name__ == "__main__":
    main()

Now if you run the code, you should see a screen like this,

Over time, you'll see those dots(genomes) get closer and closer to the target. Eventually, by the magic of the genetic algorithm, they'll be able to reach the target consistently. This is just a taste of the genetic algorithm's potential. There is a lot more to explore.

Thank you for reading. Feel free to comment your thoughts and opinions about this article.

My GitHub repo for genetic algorithm
I've added some extra flare to the code as well. :)