Dots Simulation using Genetic Algorithm - Part 2

In this part of the series, we're going to add the following features to the simulation:

• Marking the elites with a different color.
• Adding more obstacles
• Adding 'Reached' text to the screen
• Using crossover instead of replication

To color the elites differently, we're going to pass a boolean value to the draw method of each dots whether is an elite or not. If a dot is an elite, it will be drawn with a different color.

First, let's start by adding the elites color to the Dot class.

ELITES_COLOR = 'blue'

This is a class attribute. We will be coloring the elites blue.

Next, update the draw method of the Dot class to use the color.

def draw(self, surface, is_elite=False):
    if is_elite:
        pg.draw.circle(surface, self.ELITES_COLOR, self.position, self.RADIUS)
    elif self.alive:
        pg.draw.circle(surface, self.LIVE_COLOR, self.position, self.RADIUS)
    else:
        pg.draw.circle(surface, self.DEAD_COLOR, self.position, self.RADIUS)

The draw method will now first check whether a dot is an elite. This way, even if an elite dot is dead, its color will still be blue not gray.

Next, let's update the draw method of the Population class to tell which dot is an elite.

def draw(self, surface):
    for dot in self.dots:
        if dot in self.elites:
            dot.draw(surface, True)
        else:
            dot.draw(surface)

The method will now pass True to dot.draw if a dot is in the elites list of the population class. Else, nothing will be passed and the default value (False) will be used for the is_elite argument of the dot.draw method.

In the first generation, the elites list will be empty and therefore no dot will be marked as an elite.

Run the program and wait the second generation to see your elites. If your value of ELITISM is still 15, then there are going to be 15 blue colored dots in the second generation. And remember, the elites are from the previous generation without any modification, no mutation, no nothing.

Simulation with elites highlighted

The next milestone is to add more obstacles. We're going move the Obstacle and Goal class to a different script and then import them. That way, the dot.py script will be kept clean. So now, create a new file and call it obstacles.py.

Then move the Obstacle and Goal classes to the new script. We'll also need to import the required packages in the script.

import pygame as pg

class Obstacle:
    COLOR = 'black'
    def __init__(self, x, y, width, height, pos='center'):
        if pos == 'center':
            x = x - width // 2
            y = y - height // 2
            self.rect = pg.Rect((x, y, width, height))
        elif pos == 'right':
            x = x - width
            self.rect = pg.Rect((x, y, width, height))
        elif pos == 'left':
            self.rect = pg.Rect((x, y, width, height))

    def draw(self, surface):
        pg.draw.rect(surface, self.COLOR, self.rect)

    def collides(self, dot):
        return self.rect.collidepoint(dot.position)


class Goal(Obstacle):
    COLOR = 'red'

Delete the goal instance inside the main execution loop. Then in the obstacles.py script, add the following variables at the bottom.

GOAL = Goal(WIDTH // 2, 50, GOAL_SIZE, GOAL_SIZE)

OBSTACLES0 = [GOAL]

OBSTACLES1 = [
    GOAL,
    Obstacle(WIDTH // 2, HEIGHT // 2, 400, 20),
]

GOAL is same as the deleted goal variable. OBSTACLES0 is a list containing only the goal, so it will place only the goal in the screen and no any obstacle. OBSTACLES1 is the previous obstacle we used - a goal and one obstacle at the center. This way, we can keep creating more custom obstacles list.

But to use GOAL_SIZE, WIDTH, and HEIGHT, we also need them in the new script. Copying them will lead us to having two copies of the same variables in different scripts, and we don't want that. We can also just put all the global variables inside the obstacles.py script and then import it inside dots.py script to use them, but that violates the name of the script because the name suggests that we only have things related to obstacles inside the script. As a result, we're going to move the global variables to a new script called constants.py, and then import it in the obstacles.py script.

Create it and move the variables to it.

GENERATIONS = 1000
WIDTH = 600
HEIGHT = 600
POPULATION = 500
MATING_POOL_SIZE = POPULATION // 10
MUTATION_PROB = 0.05
ELITISM = 15
GOAL_SIZE = 10
GOAL_RADIUS = GOAL_SIZE // 2
GOAL_REWARD = 100
DOTS_XVEL = 5
DOTS_RADIUS = 3
POSITION = (WIDTH // 2, HEIGHT * 0.95)

Then import the constants script inside the obstacles.py script.

from constants import *

This will import everything inside the constants script. Make sure all the scripts are in the same folder.

Next, import the obstacles script inside dots.py script.

from obstacles import *

This will import everything inside the obstacles script including the imported constants.

Lastly, inside the main execution block, set obstacles to any of the created obstacles list.

if __name__ == '__main__':
    # Window, clock, and font code here

    obstacles = OBSTACLES0
    population = Population(GOAL, POPULATION)

    # for-loop and remaining code here

Note that Population(GOAL, POPULATION) is using GOAL not the previous goal.

The block now uses the specified obstacles list created in obstacles.py as the list of obstacles to challenge the dots with. This way, we can easily change between obstacles lists without much modification to our script.

Run the program and if everything works fine you should see the simulation window with no obstacle inside, only the dots and the goal will be present.

Simulation running OBSTACLES0 obstacles

To challenge the dots even more, add this obstacles lists to the obstacles script.

OBSTACLES2 = [
    GOAL,
    Obstacle(WIDTH // 2, HEIGHT * 0.3, 400, 20),
    Obstacle(WIDTH // 2, HEIGHT * 0.7, 400, 20),
]

OBSTACLES3 = [
    GOAL,
    Obstacle(WIDTH * 0.75, HEIGHT * 0.25, 100, 20),
    Obstacle(WIDTH * 0.75, HEIGHT * 0.75, 100, 20),
    Obstacle(WIDTH * 0.25, HEIGHT * 0.25, 100, 20),
    Obstacle(WIDTH * 0.25, HEIGHT * 0.75, 100, 20),
    Obstacle(WIDTH // 2, HEIGHT // 2, 400, 20),
]

OBSTACLES4 = [
    Obstacle(x, HEIGHT * y / 10, 50, 20, 'left')
    for x in range(0, 600, 60) for y in range(2, 9, 1)
]

OBSTACLES5 = [
    GOAL,
    Obstacle(0, HEIGHT * 0.7, 400, 20, 'left'),
    Obstacle(WIDTH // 2, HEIGHT // 2, 400, 20),
    Obstacle(WIDTH, HEIGHT * 0.3, 400, 20, 'right'),
]

If you run the program with OBSTACLES4, you won't see the goal because OBSTACLES4 is using a list comprehension to create its obstacles so we can't directly add GOAL to the list. We can use OBSTACLES4.append(GOAL) directly below OBSTACLES4, but to make it even more easier so that each time we use comprehension we don't have to add an append line, we can check for the presence of GOAL inside the obstalces list and add it if it is not there. Update the main execution block to do that.

if __name__ == '__main__':
    # Window, clock, and font code here

    obstacles = OBSTACLES4
    if GOAL not in obstacles:
        obstacles.append(GOAL)

    population = Population(GOAL, POPULATION)

    # for-loop and remaining code here

Now, rerun the program and everything should be fine.

It will be best if the program can show the number of dots that reached the target. This way, we can track whether the population is evolving or has stagnated. To do this, we'll add the Reached text to the screen. The text will show the number of dots that reached the target in the previous generation. We'll start by modifying the generate_next_generation method so that it also returns the number of dots that reach the target. Any dot that has its fitness score greater than or equals GOAL_REWARD means that it has reached the goal.

def generate_next_generation(self):
    new_population = []
    best_dots = self.select_best_dots(MATING_POOL_SIZE)
    best_dot = best_dots[0]
    best_dot_moves = best_dot.move_idx
    reached_goal_dots = 0

    for _ in range(0, self.size - ELITISM):
        # Previous code

    for dot in self.dots:
        if dot.get_fitness(self.goal) >= GOAL_REWARD:
            reached_goal_dots += 1

    for dot in best_dots[:ELITISM]:        
        dot.reset()

    # Previous code

    return best_dot, best_dot_moves, reached_goal_dots

The method now counts and returns the number of dots that reached the goal.

Then update the main execution block to render the text.

if __name__ == '__main__':
    # Previous window, clock, font, obstacles code here

    population = Population(GOAL, POPULATION)
    reached_goal = 0

    for i in range(GENERATIONS):
        while population.alive():
            # Previous code here

            gen_text = font.render('Generation: ' + str(i), 1, 'black')
            window.blit(gen_text, (10, 10))

            alive_text = font.render('Alive: ' + str(alive), 1, 'black')
            window.blit(alive_text, (10, gen_text.get_height() + 10))

            reached_goal_text = font.render('Reached: ' + str(reached_goal), 1, 'black')
            window.blit(reached_goal_text, (10, alive_text.get_height() * 2 + 10))

            # Update the display
            pg.display.flip()
            clock.tick(60)
        best, best_moves, reached_goal = population.generate_next_generation()
        print('Generation', i, 'Best dot moves', best_moves, 'Reached Goal:', reached_goal)

Now, the block receives and renders the number of dots that have reached the target.

Run the program and you should see the new text.

Lastly, for part 2 of the series, we're going add the crossover operator to the Dot class. We're going to look at a type of crossover operator called Single-point crossover. In single-point crossover, the two parents' chromosomes (i.e. list of direction vectors) is going to be splitted at a random position. And then the last parts will be swapped to produce two offsping.

Single-point crossover

The offspring will first follow the path of one parent and then later switch to the path of the other parent. And this is the essence of crossover - to combine the chromosomes of two parents aiming to create a better offspring.

Now let's add the crossover method to the Dot class.

@classmethod
def crossover(cls, parent1, parent2):
    point = random.randrange(min(parent1.move_idx, parent2.move_idx))
    offspring1_directions = []
    offspring2_directions = []

    offspring1_directions.extend(parent1.directions[:point])
    offspring1_directions.extend(parent2.directions[point:parent2.move_idx])

    offspring2_directions.extend(parent2.directions[:point])
    offspring2_directions.extend(parent1.directions[point:parent1.move_idx])

    offspring1 = Dot(offspring1_directions)
    offspring2 = Dot(offspring2_directions)

    return offspring1, offspring2

This method is a class method (@classmethod) meaning it can be used directly using the class without an instance. The method starts by generating a random number between 0 and the smaller move_idx of the parents. We're using the smaller value to avoid IndexError.

The method then copies directions (genes) in the range 0-point from parent1 into offspring1_directions. It then copies directions (genes) in the range point-parent2.move_idx (point:parent2.move_idx) from parent2 into offspring1_directions. We're stopping at parent2.move_idx to make sure the parent is only passing directions it followed to the offspring. This can be a little bit complicated, but imagine that parent2's parent reached goal at its 100th move, and it passed these 100 moves to parent2. But due to mutation, parent2 reached the goal at its 80th move. And since reaching the goal will kill it, this means that it has 20 unfollowed directions in its directions list. Now, during crossover between parent1 and parent2, if parent1 first passes its part to offspring1, parent2 only needs to pass up to its 80th move (i.e. move_idx). The remaining 20 are not required in the offspring because those are not followed by it. Not doing this will not break the program, but the dots will end up with directions not required in their chromosomes. This means storing what is not required in the computer's memory. Why all this? Just optimizing the optimization algorithm.

After creating the offspring's directions lists, the offspring are then created by initializing the Dot class with the lists. The method finally returns two offspring.

Next, let's update the first for-loop of the generate_next_generation method. And remember that replication produces only one child while crossover produces two.

for _ in range(0, self.size - ELITISM, 2):
    parents = random.choices(best_dots, k = 2)
    child1, child2 = Dot.crossover(*parents)

    child1.mutate()
    child2.mutate()

    new_population.append(child1)
    new_population.append(child2)

The loop now picks two parents at random from the mating pool, perform crossover, mutate the offspring, and then add them to the new_population list. The loop now also runs for half the amount of offspring needed, due to the step argument passed to the loop, this is because each iteration produces two offspring. Note how we call crossover directly using the DOt class because it is a class method.

You can now run the program even though there won't be any visible change.

Feel free to experiment with the code by adding new obstacles, changing parameters, or even modifying the fitness function. Share your results or insights from your experiments in the comments.

The full code up to this point with even more obstacles can be downloaded on GitHub.

In the next part of the blog, we'll:

• Add a save and load system
• Add a way to speed up the evolution

Love diving into the world of AI and creativity? Join our AICraftsLab Discord community and connect with fellow enthusiasts—let’s craft something amazing together!