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. -
WIDTHandHEIGHT: 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_SIZEandGOAL_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_COLORandDEAD_COLOR: Colors to represent live and dead dots. -
position: The current position of the dot (aVector2object). -
directions: A list of movement directions (vectors). -
move_idx: The index of the current direction in thedirectionslist. -
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.
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.
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: Apg.Rectobject 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.
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.
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!
Top comments (4)
Masha Allah
Best of luck 👍 ✨️
Great project
Best of luck 👍
Great! I wish you the best.
Masha Allah