DEV Community: Abdulrazaq Ahmad

Dots Simulation using Genetic Algorithm - Part 3

Abdulrazaq Ahmad — Sun, 09 Feb 2025 12:43:31 +0000

In this part, we'll code the following features:

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

Starting with the save and load system, we'll utilize the pickle package.

pickle allows saving entire Python objects, including lists, dictionaries, and custom objects (like Population class object), making it easier to pause and resume simulations.

An excerpt from the package documentation.

The pickle module implements binary protocols for serializing and de-serializing a Python object structure. “Pickling” is the process whereby a Python object hierarchy is converted into a byte stream, and “unpickling” is the inverse operation, whereby a byte stream (from a binary file or bytes-like object) is converted back into an object hierarchy.

Serialization/pickling is the process used to save the state of an object while de-serialization/unpickling is for loading the state of an object.

Now let's import the package inside the dots.py script. Add the following line.

import pickle

Next, let's add the following methods to the Population class to use the package.

def save(self, file):
    with open(file, 'w+b') as f:
        pickle.dump(self, f)

@staticmethod
def load(file):
    with open(file, 'r+b') as f:
        obj = pickle.load(f)
    return obj

The save method saves the current Population object to a file. It first opens the file in binary write mode ('w+b') and then uses pickle.dump to serialize the current object and store it in the specified file path.

The load method which is a static method (@staticmethod) loads a previously saved Population object from the specified file path. It first opens the file in binary read mode ('r+b') and then uses pickle.load to deserialize and reconstruct the Population object. And then finally returns the loaded object.

The load method is a static method while save is not because save saves a specific instance thereby needing the self argument. While load doesn't depend on an instance, it creates a new one.

I used @classmethod for the crossover method in Dot class but never used the cls argument. In that case too, it is better to use @staticmethod decorator which doesn't have the cls parameter.

You can now call population.save("path/to/file") or Population.load("path/to/file") to save or load respectively.

Let's add a simple system to save the Population periodically after some generations. Add the following code inside the main execution just below the obstacles variable.

run_dir = 'run1'
save_files = True

if save_files:
    os.makedirs(run_dir)
    pop_file_path = os.path.join(run_dir, 'population')

Code break down:

run_dir = 'run1': Defines the directory name where population data will be saved. If saving is enabled, a folder named 'run1' will be created to store files.
save_files = True: A flag that controls whether the program saves files or not. If False, saving is skipped.
if save_files:: This only runs if save_files is True.
os.makedirs(run_dir) creates a directory named 'run1' if it does not already exist. This ensures that files can be saved inside it. If it exists, a FileExistsError exception will be raised.
pop_file_path = os.path.join(run_dir, 'population') constructs a file path for saving the population.

To use os, you need to import the package using import os.

Add the following code at the end of the main execution block just below print('Generation', i, ...) to do the actual saving,

if save_files and i % 10 == 0:
    population.save(f'{pop_file_path}_{i}')

This piece saves the population every 10 generations (i is the generation number). This prevents saving on every generation, reducing file clutter. f'{pop_file_path}_{i}' constructs a filename like:

'run1/population_0' (for generation 0)
'run1/population_10' (for generation 10)
'run1/population_20' (for generation 20)

This allows tracking progress by keeping separate save files for different generations. You can modify the generations interval before each save by changing the 10 in i % 10 == 0 to your desired interval.

To load a saved population, you use population = Population.load('path/to/file') instead of population = Population(GOAL, POPULATION) which creates a new one.

You can now run the script. A new folder named run1 will be created in the scripts directory. And if you have let the first generation to finish, a file named population_0 will be created inside the new folder. That is the saved population file of generation one.

Sometimes, you might create obstacles that are very hard to deal with, taking thousands of generations before achieving something significant.

A very hard configuration of obstacles

In that case, if we can find a way to speed up the simulation, that will be of tremendous importance. To speed up the simulation, we can stop rendering the dots and the obstacles. And more importantly, stop limiting the frames. We'll only render the texts to get a sense of what's is happening. By doing all these, the speed of the program won't be intentionally limited, it will only be limited by the calculations it does.

To do this, we'll first create a variable that controls whether or not all objects will be rendered. Add the following code just below this line save_files = True.

render_objects = True

Setting this variable to render or not before running the program seems very static. Instead, it will be better if we can dynamically change the variable while the program is running. This will allow us to render everything or not when ever we want. We will use clicking on the screen to toggle the rendering. Clicking on the screen will turn off rendering everything and clicking it again will turn it on.

We will utilize the event for-loop to do this. But this is just one of the change we will make to the main execution block. We will also:

1- Use the variable inside the main execution block's while-loop to only render everything if the variable is set to True.
2- Use the variable to render only the texts if the variable is set to False.

Modify the block to match the following one in order to add the new features.

if __name__ == '__main__':
    window = pg.display.set_mode((WIDTH, HEIGHT))  # Creates the window
    pg.display.set_caption('Dots Simulation')  # Sets window's caption
    clock = pg.time.Clock()  # Clock for controlling fps
    font = pg.font.SysFont('comicsans', 20)  # font for creating texts

    obstacles = OBSTACLES3
    run_dir = 'run1'
    save_files = True
    render_objects = True

    if save_files:
        os.makedirs(run_dir)
        pop_file_path = os.path.join(run_dir, 'population')

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

    population = Population(GOAL, POPULATION)
    #population = Population.load('run1/population_100')
    reached_goal = 0

    for i in range(GENERATIONS):
        while population.alive():
            for e in pg.event.get():
                # Handling window close event
                if e.type == pg.QUIT:
                    pg.quit()
                    quit()
                elif e.type == pg.MOUSEBUTTONDOWN:  # Handling mouse/screen click
                    render_objects = not render_objects

            alive = population.update(obstacles)

            # If render_objects is set to true
            if render_objects:
                # Rendering all objects
                window.fill('white')

                for obstacle in obstacles:
                    obstacle.draw(window)

                population.draw(window)

                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)  # Limit frames to 60 per second

        best, best_moves, reached_goal = population.generate_next_generation()
        print('Generation', i, 'Best dot moves', best_moves, 'Reached Goal:', reached_goal)

        # If render_objects is set to false
        if not render_objects:
            # Rendering only texts
            window.fill('white')

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

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

            # Update the display. Frames not limited
            pg.display.flip()

        # Save population after every 10 generations
        if save_files and i % 10 == 0:
            population.save(f'{pop_file_path}_{i}')

First, this line elif e.type == pg.MOUSEBUTTONDOWN: checks if the user clicked the mouse (or tapped the screen on mobile). If it returns True, then render_objects = not render_objects will toggle the variable on or off depending on its current value. If it is True, it will set it to False, and if it is False, it will set it back to True.

Next, this line if render_objects: checks if render_objects is True. If True, the block proceeds with rendering everything onto the screen otherwise not. The block also limits the program to only 60 frames per second.

Lastly, this line if not render_objects: checks if render_objects is False and if so, the block proceeds with rendering only the 'Generation' and 'Reached' texts onto the screen. When render_objects is set to False, rendering is only done once - after the generation has finished - without limiting the frames to help speed up the program.

Run the program and try the new feature by clicking on the screen.

A window rendering only texts

You may have noticed a little delay before the objects disappear while turning off the display. This is because after clicking the screen to turn off rendering, the already rendered frame won't be updated unless the generation is finished. We can stop this by updating the display immediately after detecting a click event without waiting for the generation to finish. This is left to you, try removing it.

This will be the end of the Genetic Algorithm part of this simulation. In the coming parts (dateless), we will discard the weak chromosomes and give the dots brain and sensors (eyes) using NEAT to traverse the environment even more intelligently.

Next generation dots

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.

Download the full source code up to this point from GitHub.

If you've followed this far, it means you're passionate about AI! Take your learning further with my book, where I covered AI search techniques with hands-on projects. Get your copy on Amazon today!

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!

Dots Simulation using Genetic Algorithm - Part 2

Abdulrazaq Ahmad — Thu, 16 Jan 2025 08:48:21 +0000

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!

Dots Simulation using Genetic Algorithm - Part 1

Abdulrazaq Ahmad — Tue, 07 Jan 2025 22:12:38 +0000

Genetic algorithms (GAs) are a fascinating branch of artificial intelligence inspired by the process of natural selection, where individuals in a population compete for survival, and the fittest traits are passed on to the next generation. They excel in solving optimization problems by iteratively improving a population of candidate solutions. This blog post will guide you through a captivating project where we use a genetic algorithm to teach a population of "dots" to navigate toward a target while avoiding obstacles.

Steps of implementing a Genetic Algorithm

Generally, the basic steps of a genetic algorithm include:

Initialization: Create an initial population of candidate solutions, often generated randomly.
Evaluation: Assess the fitness of each individual in the population based on a predefined fitness function. A fitness function scores each individual based on how well it performed.
Selection: Select the fittest individuals to serve as parents for the next generation.
Crossover: Combine the genetic information of two parents to produce offspring, introducing variation.
Mutation: Apply small random changes to the offspring’s genetic material to maintain diversity and explore new solutions.
Replacement: Form a new population by replacing the previous generation with the offspring.
Elitism: Preserve a set number of the best-performing individuals of the previous generation by adding them unchanged into the next generation to ensure that the highest fitness individuals are retained.
Iteration: Repeat the process for a set number of generations.

The Project Overview

The goal of this project is to simulate a population of dots that evolves over generations to reach a specified target. Each dot has a set of movement directions that act as its "genes." This collection of genes is called "chromosome." Through selection, mutation, and replication, the population adapts over time, improving its ability to reach the target.

Key Components of the Simulation

Dots:
Each dot starts at a predefined position and moves according to its set of directions (chromosome). Dots are characterized by their ability to move, collide with obstacles, and determine their fitness based on proximity to the target.
Fitness Function:
Fitness is calculated based on the distance between a dot and the target. Dots closer to the target receive higher scores.
Population:
A collection of dots forms a population. Each generation, the best-performing dots are selected to create the next generation through crossover and mutation.
Genetic Algorithm:
The GA ensures that the population evolves by selecting the fittest dots, mutating their movement directions, and introducing diversity to avoid getting stuck in a local optimum.
Obstacles:
Obstacles challenge the dots, requiring them to adapt their paths to successfully navigate around them.
Goal:
The goal is represented as a small red square. Dots aim to reach this target to maximize their fitness.

Coding the Project

We'll be using Pygame to create the project. First, start by creating a new file and name it dots.py. Then import the following packages:

import pygame as pg
import random
import math

pg.font.init()

The last line initializes the font module of Pygame which we will use for rendering texts on the screen.

Then add the following global variables.

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 // 2)

GENERATIONS: Total number of generations for the simulation.
WIDTH and HEIGHT: Dimensions of the simulation window.
POPULATION: Number of dots in each generation.
MATING_POOL_SIZE: Size of the mating pool (10% of the population). The mating pool is a group of dots selected for reproducing the next generation.
MUTATION_PROB: Probability of mutation for a dot's movement direction (5%).
ELITISM: Number of elite dots carried over to the next generation unchanged.
GOAL_SIZE and GOAL_RADIUS: Size and radius of the goal.
GOAL_REWARD: Reward for a dot reaching the goal.
DOTS_XVEL: Horizontal velocity of the dots.
DOTS_RADIUS: Radius of each dot.
POSITION: Starting position of the dots (center of the screen).

These global variables control key aspects of the simulation and how the GA operates. They allow for easy customization of the simulation's parameters.

Next, let's create a class to represent a dot.

class Dot:
    VEL = pg.Vector2((DOTS_XVEL, 0))
    RADIUS = DOTS_RADIUS
    LIVE_COLOR = 'green'
    DEAD_COLOR = 'gray'

    def __init__(self, moves=None):
        self.position = pg.Vector2(POSITION)
        self.directions = [] if moves is None else moves
        self.move_idx = 0
        self.alive = True

The Dot class represents the individual agents in the simulation. If a dot didn't inherit directions (moves being None), it initializes it to an empty list. This is particularly useful for the first generation's dots that have no parents.

Attributes:

VEL: A constant velocity vector that determines the dot's movement speed.
RADIUS: The radius of the dot.
LIVE_COLOR and DEAD_COLOR: Colors to represent live and dead dots.
position: The current position of the dot (a Vector2 object).
directions: A list of movement directions (vectors).
move_idx: The index of the current direction in the directions list.
alive: A boolean indicating whether the dot is alive.

def move(self):
    if self.move_idx < len(self.directions):
        direction = self.directions[self.move_idx]
    else:
        direction = self.VEL.rotate(random.randrange(360))
        self.directions.append(direction)

    self.position += direction
    self.move_idx += 1

This method moves the dot according to its current direction. It does so by adding the current direction vector (vector at index move_idx) to the dot's position vector.

If the dot has no more directions or an empty directions list, a random direction is added. This way, if a dot inherits a list of directions, it will have to finish following it before it starts generating it own directions. This ensures that the dot follows its parent's path.

The first generation's dots that don't have parents generate a random movement direction at each frame.

A direction is generated by rotating a copy of the VEL vector to a random angle. VEL vector is facing straight right, so it will only move the dot right. But rotating it to a random angle makes it face a random direction thereby making the dot move in a random direction.

def draw(self, surface):
    if 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)

This method draws the dot on the screen using the appropriate color (green for alive, gray for dead).

Now, let's create the main execution block to run the simulation. We will start by simulating a single dot.

if __name__ == '__main__':
    window = pg.display.set_mode((WIDTH, HEIGHT))  # Creates the window
    pg.display.set_caption('Dots Simulation')  # Sets window's caption
    clock = pg.time.Clock()  # Clock for controlling fps
    font = pg.font.SysFont('comicsans', 20)  # font for creating texts

    for i in range(GENERATIONS):
        dot = Dot()
        while dot.alive:
            # Handling window close event
            for e in pg.event.get():
                if e.type == pg.QUIT:
                    pg.quit()
                    quit()

            dot.move()

            # Kill dot on going out of window's boundary
            if dot.position.x < 0 or dot.position.x > WIDTH or \
               dot.position.y < 0 or dot.position.y > HEIGHT:
                dot.alive = False

            # Rendering objects
            window.fill('white')
            dot.draw(window)

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

            # Updating the display
            pg.display.flip()
            clock.tick(60)
        print('Generation', i, dot.move_idx, dot.directions[:3])

Now, run the script and watch the lone dot.

If the dot's I-will-not-die maneuvers intimidate you, increase DOTS_XVEL to speed it up.

Running simulation with one dot (at bottom left corner)

Simulation generations' details

The printed message shows a generation, the total movements done by the dot before dying, and the first three direction vectors of the dot.

Now that we have a single dot on the screen, the next thing is to create a population of dots. We'll start by creating a class to represent the dots population.

class Population:
    def __init__(self, goal, size):
        self.goal = goal
        self.size = size
        self.dots = []
        self.elites = []
        self.__alive = size

        self.__populate()

    def __populate(self):
        for _ in range(self.size):
            dot = Dot()
            self.dots.append(dot)

The Population class manages a group of Dot instances, representing the entire population of dots.

Attributes:

goal: The goal object the dots are trying to reach.
dots: A list of all the dots in the population.
size: The total number of dots in the population.
elites: A list of elite dots that will be preserved for the next generation.
__alive: A private variable tracking how many dots are still alive.

The __init__ method initialises the population with a given goal, and size. It also calls __populate to create the initial population of dots.

The __populate method populates the population with Dot instances at the initial position. These dots have no parents so they will be initialized with an empty list of direction vectors.

def update(self):
    alive = 0
    for dot in self.dots:
        if dot.alive:
            alive += 1
            dot.move()

            # Kill dots on going out of window's boundary
            if dot.position.x < 0 or dot.position.x > WIDTH or \
               dot.position.y < 0 or dot.position.y > HEIGHT:
                dot.alive = False

    self.__alive = alive
    return alive

This method updates the state of the population by moving the dots, checking if they are still alive, and returns the number of dots alive.

def alive(self):
    return self.__alive > 0

This method returns whether the population is alive. The population is alive if at least one dot is still alive in the population.

def draw(self, surface):
    for dot in self.dots:
        dot.draw(surface)

The draw method draws all the dots on the surface (screen).

Now, update the main execution point's for-loop and run the program again.

for i in range(GENERATIONS):
    population = Population(None, POPULATION)
    while population.alive():
        # Handling window close event
        for e in pg.event.get():
            if e.type == pg.QUIT:
                pg.quit()
                quit()

        alive = population.update()

        # Rendering objects
        window.fill('white')
        population.draw(window)

        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))

        # Update the display
        pg.display.flip()
        clock.tick(60)
    print('Generation', i)

Now, instead of a single dot, the program shows the whole population. After each population is dead, a new one is created without any inheritance so the dots will never improve at this stage.

A population of dots

Next, let's add the goal and obstacles.

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)

The Obstacle class represents obstacles in the environment that the dots need to avoid.

Attributes:

COLOR: The color of the obstacle.
rect: A pg.Rect object representing the obstacle's position and size.

The __init__ method initializes the obstacle at a specified position. The pos argument determines the positioning of x and y, whether (x, y) is the center, left, or right of the obstacle.

The draw method draws the obstacle on the screen.

The collides method checks if the obstacle collides with a given dot by checking if the dot's position intersects with the obstacle's rect.

class Goal(Obstacle):
    COLOR = 'red'

The Goal class inherits from Obstacle and represents the target the dots are trying to reach. The goal is also an obstacle but its COLOR is overridden to 'red'.

Now, we need to create a way to detect collisions between the dots and the obstacles. To do that, start by adding the following method to the Dot class.

def collides(self, obstacles):
    for obstacle in obstacles:
        if obstacle.collides(self):
            return True

    return False

This method checks if the dot collides with any obstacle using the collides method of the Obstacle class.

And then update the update method in Population class.

def update(self, obstacles):
    alive = 0
    for dot in self.dots:
        if dot.alive:
            alive += 1
            dot.move()

            # Kill dots on going out of window's boundary or colliding with an obstacle
            if dot.position.x < 0 or dot.position.x > WIDTH or \
               dot.position.y < 0 or dot.position.y > HEIGHT or \
               dot.collides(obstacles):
                dot.alive = False

    self.__alive = alive
    return alive

Now the method takes in a list of obstacles that will be used by the dots to check for collision.

Currently, the dots are spawning in the middle of the screen and the obstacle we're going to add will be in the middle too. So, update the POSITION global variable so that the population starts at the bottom center.

POSITION = (WIDTH // 2, HEIGHT * 0.95)

Finally, update the main execution block to include the obstacles.

if __name__ == '__main__':
    window = pg.display.set_mode((WIDTH, HEIGHT))  # Creates the window
    pg.display.set_caption('Dots Simulation')  # Sets window's caption
    clock = pg.time.Clock()  # Clock for controlling fps
    font = pg.font.SysFont('comicsans', 20)  # font for creating texts

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

    obstacles = [
        goal,
        Obstacle(WIDTH // 2, HEIGHT // 2, 400, 20),
    ]

    for i in range(GENERATIONS):
        population = Population(goal, POPULATION)
        while population.alive():
            # Handling window close event
            for e in pg.event.get():
                if e.type == pg.QUIT:
                    pg.quit()
                    quit()

            alive = population.update(obstacles)

            # Rendering objects
            window.fill('white')

            for obstacle in obstacles:
                obstacle.draw(window)

            population.draw(window)

            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))

            # Update the display
            pg.display.flip()
            clock.tick(60)
        print('Generation', i)

The method now creates an obstacles list which contains goal and an Obstacle object. It then passes a reference to goal to the Population class which will later be used for calculating fitness. Inside the while-loop, obstacles is passed to the population.update method to check for collisions.

The obstacle is created at the center of the screen (WIDTH // 2, HEIGHT // 2) and has a dimension of 400x20 pixels. The goal is centered horizontally (WIDTH // 2) and 50 pixels from the top of the screen vertically. It is a square of size GOAL_SIZE. Both the goal and the obstacle are centered at their positions properly because pos parameter of the Obstacle class is set to center (the default). Try playing around with the values. Try Obstacle(WIDTH // 2, HEIGHT // 2, 400, 20, 'left').

The method also loops over obstacles list to render all the obstacles (including goal) to the screen.

Now, run the program. You should see both the obstacle and the goal.

Simulation window with both goal and obstacle

Finally, it is time to add the evolution process. Start by adding the following methods to the Dot class.

def get_fitness(self, goal):
    distance_to_goal = math.dist(self.position, goal.rect.center)
    distance_score = GOAL_REWARD if distance_to_goal <= GOAL_RADIUS + DOTS_RADIUS else -distance_to_goal
    fitness = distance_score + (1 / self.move_idx)
    return fitness

def replicate(self):
    return Dot(self.directions.copy())

def mutate(self):
    for i in range(len(self.directions)):
        if random.random() < MUTATION_PROB:
            direction = Dot.VEL.rotate(random.randrange(360))
            self.directions[i] = direction

def reset(self):
    self.move_idx = 0
    self.position = pg.Vector2(POSITION)
    self.alive = True

The get_fitness method calculates the fitness of a dot based on its distance to the goal. If the dot is within the goal's radius, it receives a high reward (GOAL_REWARD). The fitness is also influenced by the number of moves made, rewarding shorter paths (inverse of move_idx).

The replicate method creates a new dot at the starting position with the same movement directions as the parent. At this step, we're supposed to do crossover (by combining two parent to get offspring) but to make things easier, we're replicating the dot to produce an exact copy of itself. We will later use the crossover operator.

The mutate method mutates the dot's movement directions with a given probability by rotating the direction vectors randomly.

The reset method resets the dot's position and move_idx to the initial configuration and makes it alive again. This is particularly useful for resetting the state of the elites that will be passed to the next generation unchanged.

Next, add the following methods to the Population class.

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

    for _ in range(0, self.size - ELITISM):
        parent = random.choice(best_dots)
        child = parent.replicate()
        child.mutate()
        new_population.append(child)

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

    new_population.extend(best_dots[:ELITISM])

    self.__alive = len(new_population)
    self.elites = best_dots[:ELITISM]
    self.dots = new_population

    return best_dot, best_dot_moves

This method creates the next generation of dots using the genetic algorithm steps. It first selects the best dots, then creates offspring by replicating and mutating them, and adds the top best dots to the new population via elitism. The best dots are restored to the starting configuration using the reset method. The method finally returns the best dot and its number of moves.

def select_best_dots(self, n):
    key = lambda x: x.get_fitness(self.goal)
    dots = sorted(self.dots, key=key, reverse=True)
    dots = dots[:n]

    return dots

This method performs the selection step of the GA. It sorts the dots by fitness and selects the top n best-performing dots.

And then update the main execution block.

# Previous code here
population = Population(goal, POPULATION)

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

    best, best_moves = population.generate_next_generation()
    print('Generation', i, 'Best dot moves', best_moves)

The method now creates only one instance of Population class throughout all the generations. At the end of each generation, the generate_next_generation method of the Population instance is called to perform all the evolution processes on the population. The method then returns the best performing dot and the number of moves it made.

After the first dot to reach the target, best_moves should start to decline as the goal is no longer to reach the target but to find the shortest path.

Simulation with many of the dots reaching the target

The full code up to this point can be downloaded on GitHub.

There is some variance in this simulation especially with the default values. Sometimes finding even a single dot to cross the obstacle is very hard. While sometimes most of the population will converge to a solution easily. But after all, even after a decade (if you're that patient), they will reach the target.

Feel free to experiment with the code by adding new obstacles or changing the global variables. Share your results or insights from your experiments in the comments.

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

Mark the elites with a different color
Add more obstacles
Use crossover instead of replication
Add 'Reached' text to the screen

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!