Genetic Algorithm for Solving a Maze using Python(with visualization)

14 min readApr 2, 2023

A genetic algorithm (GA) is a type of optimization algorithm that is inspired by the natural selection and genetics processes. It is used to find the best solution to a problem by simulating the process of biological evolution.

Starting with a population of possible solutions, the GA employs selection, crossover, and mutation operators to generate new candidate solutions. The selection operator selects the most fit individuals from the population to be the next generation’s parents. By combining the genetic material of two parents, the crossover operator generates new solutions. To explore new regions of the search space, the mutation operator randomly changes some of the genes in a solution.

The iterative process of selection, crossover, and mutation produces new generations of candidate solutions. Each solution’s fitness is assessed using a fitness function, which measures how well the solution meets the problem requirements.

Many optimisation problems, such as engineering design, scheduling, and financial modelling, make use of the GA. It is especially useful when the search space is large and complex, and traditional optimisation methods are ineffective.

We will develop the Genetic Algorithm in Python to solve the Maze Problem. This is one sample output of the code we will develop:

Studio Project - Kapwing

Gif made on Kapwing

www.kapwing.com

Our problem is to find a path from the starting point to the end point in a maze. We will represent the maze as a 2D array using pyamaze, where 1 represents a path, and 0 represents a wall.

Five phases are considered in a genetic algorithm:

Initial Population
Fitness Function
Selection
Crossover
Mutation

Let’s dive into the code for maze solving using GA.

The first step is to create the maze and agent. The maze is created using the pyamaze library. The agent is created using the same library, and it is used to navigate through the maze.

import random
from pyamaze import maze, agent

# Create the maze and agent
m = maze(rows, columns)
m.CreateMaze(loopPercent=100)
a = agent(m, filled=True, footprints=True, shape="arrow")
mazeMap = m.maze_map

Initial Population:

We will start by initializing a population of potential solutions. Each potential solution will be represented as an array of integers, where each integer represents a column in the maze. The first integer will always be 1, which represents the starting point, and the last integer will always be the number of columns, which represents the end point.

The function below generates an initial population of size populationSize:

def initialPopulation(populationSize , rows, columns):
    for i in range(populationSize):
        pop = []
        pop.append(1)
        for j in range(1, columns - 1):
            pop.append(random.randint(1, rows + 1))
        pop.append(columns)
        population.append(pop)

Fitness Function:

The fitness function determines how fit an individual is (the ability of an individual to compete with other individuals). It gives a fitness value to each individual. The probability that an individual will be selected for reproduction is based on its fitness value.

i) Number of Turns:

The first metric used to evaluate the fitness of an individual is the number of turns it takes to reach the end of the maze. The number of turns is defined as the number of times the individual changes direction while moving from the starting point to the end point of the maze.

To calculate the number of turns, the function loops through each individual in the population and for each individual, it loops through the columns of the maze and checks if the individual’s current position is different from its previous position. If the positions are different, it means that the individual has turned, and the turn count is incremented.

The turn count is then added to a list called “noOfTurns” which stores the number of turns for all individuals in the population. Finally, the turns variable is reset to 0 to prepare for the evaluation of the next individual in the population.

noOfTurns = []
def fitness():
    # Number of turns
    for i in population:
        turns = 0
        for j in range(columns-2):
            if i[j + 1] != i[j]:
                turns += 1
        noOfTurns.append(turns+1)
        turns = 0

ii) Finding Path:

The path list contains the path for each individual in the population. The path is represented as a list of (x, y) tuples that represent the coordinates of each point in the path. The first tuple is (1, 1) which is the starting point of the maze and the last tuple is (rows, columns) which is the endpoint of the maze.

To generate the path for each individual, the code loops through each chromosome in the individual and determines the direction of movement based on the difference between the adjacent chromosome values. If the difference is positive, then the movement is in the downward or rightward direction, and if the difference is negative, then the movement is in the upward or leftward direction.

For each chromosome, the code generates a sequence of (x, y) tuples based on the direction of movement. If the direction is downward or rightward, then the sequence is generated by iterating from the current chromosome value to the next chromosome value. If the direction is upward or leftward, then the sequence is generated by iterating from the current chromosome value to the next chromosome value in reverse.

The generated (x, y) tuples are then added to a temporary list p. Once all the chromosomes have been processed, the endpoint of the maze is appended to the p list to complete the path.

Finally, the p list is added to the path list, which contains the path for the current individual. The process is repeated for all individuals in the population.

path = []
def fitness():
for i in population:
        p = []
        for j in range(0, rows - 1):
            if (i[j + 1] - i[j]) >= 0: # down or right
                for k in range(i[j], i[j+1]+1):
                    if k <= rows or k <= columns: # check if value is within range
                        p.append((k, j+1))
            if (i[j + 1] - i[j]) < 0: # up or left
                for k in range(i[j], i[j+1]-1, -1):
                    if k <= rows or k <= columns: # check if value is within range
                        p.append((k, j+1))
        p.append((rows, columns))
        path.append(p)

iii) Finding Obstacles:

This code uses the path generated for each individual in the population to determine the number of obstacles encountered. It does this by iterating through each coordinate in the path and checking if there is an obstacle (represented by a 0 in the maze map(which contains the values of all 4 directions for all tuples)) between it and the next coordinate in the path. If an obstacle is encountered, the obs counter is incremented. Once all coordinates in the path have been checked, the obs counter is appended to the obstacles list, and then reset to 0 for the next individual.

Note that the code checks if the next coordinate in the path is in the same row or column as the current coordinate before checking for obstacles in the corresponding direction. This ensures that the code only checks for obstacles along horizontal or vertical paths, and doesn’t count diagonal obstacles.

obstacles = []
def fitness():
obs = 0
    for i in path:
        for j in range(len(i) - 1):
            if i[j+1][0]-i[j][0] >= 0 and i[j+1][1] == i[j][1]:
                if mazeMap[(i[j])]["S"] == 0:
                    obs += 1
            if i[j+1][0]-i[j][0] < 0 and i[j+1][1] == i[j][1]:
                if mazeMap[(i[j])]["N"] == 0:
                    obs += 1
            if i[j+1][1]-i[j][1] >= 0 and i[j+1][0] == i[j][0]:
                if mazeMap[(i[j])]["E"] == 0:
                    obs += 1
            if i[j+1][1]-i[j][1] < 0 and i[j+1][0] == i[j][0]:
                if mazeMap[(i[j])]["W"] == 0:
                    obs += 1
        obstacles.append(obs)
        obs = 0

iv) Number of Steps:

This code iterates through each element i in the list path and appends the length of that element (which is itself a list) to the noOfSteps list. Essentially, it's counting the number of steps taken to reach the goal for each path.

noOfSteps = []
def fitness():
for i in path:
        noOfSteps.append(len(i))

v) Fitness Value using Formulas:

This is the last part for fitness function. This code calculates the fitness value for each individual in the population. The fitness score is used to determine how well an individual performs the given task, which in this case is finding a path through a maze.

The fitness score is calculated based on three factors: the number of obstacles encountered, the number of turns made, and the number of steps taken. These factors are weighted differently, with the weight of obstacles being three times that of turns and two times that of steps.

To calculate the fitness value, first, the minimum and maximum values of each factor are determined from the population. Then, for each individual, the normalized values of each factor are calculated, ranging from 0 to 1. The normalized values are then multiplied by their respective weights and combined to obtain the final fitness score.

The final fitness score is calculated as follows:

minimumObstacles = min(obstacles)
    maximumObstacles = max(obstacles)
    minimumTurns = min(noOfTurns)
    maximumTurns = max(noOfTurns)
    minimumSteps = min(noOfSteps)
    maximumSteps = max(noOfSteps)
    weightOfObstacle = 3
    weightOfPath = 2
    weightOfTurn = 2

    for i in range(populationSize):
        finalObstacles = (1 - ((obstacles[i] - minimumObstacles) / (maximumObstacles - minimumObstacles)))
        FinalObstacles.append(finalObstacles)
        finalTurns = (1 - ((noOfTurns[i] - minimumTurns) / (maximumTurns - minimumTurns)))
        FinalTurns.append(finalTurns)
        finalSteps = (1 - ((noOfSteps[i] - minimumSteps) / (maximumSteps - minimumSteps)))
        FinalSteps.append(finalSteps)
        finalFitness = ((100 * weightOfObstacle * FinalObstacles[i]) * ( ((weightOfPath * FinalSteps[i]) + (weightOfTurn * FinalTurns[i])) / (weightOfPath + weightOfTurn)))
        FinalFitness.append(finalFitness)

Selection:

The idea of selection phase is to select the fittest individuals and let them pass their genes to the next generation.

Two pairs of individuals (parents) are selected based on their fitness scores. Individuals with high fitness have more chance to be selected for reproduction.

Crossover:

Crossover is the most significant phase in a genetic algorithm. For each pair of parents to be mated, a crossover point is chosen at random from within the genes.

For example, consider the crossover point to be 3 as shown below.

Offspring are created by exchanging the genes of parents among themselves until the crossover point is reached.

The new offspring are added to the population.

This function implements a crossover operation for a genetic algorithm. The crossover operation is used to create new offspring from two parent solutions in the population. The function first loops through the population by pairs of individuals, selects a random crossover point between 0 and the number of columns in the maze, and then creates two children by combining the genetic code of the two parents. The genetic code in this case is the path of coordinates from the starting point to the goal point. The crossover point determines where the paths of the two parents are split and recombined to create the paths of the children. Finally, the function replaces the two parent solutions with the two children in the population.

def crossover():
    for i in range(0, populationSize - 1, 2):
        crossoverPoint = random.randint(0, columns - 1)
        parent1 = deepcopy(population[i])
        parent2 = deepcopy(population[i + 1])
        child1 = []
        child2 = []
        # Combine the genetic code of the parents to create the children
        for j in range(len(parent1)):
            if j < crossoverPoint:
                child1.append(parent1[j])
                child2.append(parent2[j])
            else:
                child1.append(parent2[j])
                child2.append(parent1[j])
        # Replace the parents with the children in the population
        population[i] = child1
        population[i + 1] = child2

Mutation:

In certain new offspring formed, some of their genes can be subjected to a mutation with a low random probability. This implies that some of the bits in the bit string can be flipped.

The Mutation function performs a random mutation on each individual in the population. Specifically, it randomly selects a position in the individual's genetic code (represented as a list of integers) between the second and second-to-last elements, and replaces the value at that position with a randomly generated integer between 1 and the number of rows in the maze. This introduces random variation in the population to help prevent premature convergence to suboptimal solutions.

Mutation occurs to maintain diversity within the population and prevent premature convergence.

def mutation():
    for i in population:
        i[random.randint(1, columns - 2)] = random.randint(1, rows)

Bubble Sorting Algorithm:

This function sorts the population based on the fitness of each individual in descending order, using a simple bubble sort algorithm. It first compares the fitness of each pair of individuals and swaps their positions if the individual with the higher fitness comes first, until the entire population is sorted. Then it prints the sorted population along with the corresponding fitness scores. This sorting step is important because it helps to select the fittest individuals for the next generation and discard the weaker ones.

# Bubble sorting in descending order
def sorting():
    for i in range(populationSize - 1):
        for j in range(i+1, populationSize):
            if FinalFitness[j] > FinalFitness[i]:
                FinalFitness[i], FinalFitness[j] = FinalFitness[j], FinalFitness[i]
                population[i], population[j] = population[j], population[i]
    for i in range(populationSize):
        print(f"{population[i]}          {FinalFitness[i]}")

Solution:

This function is responsible for finding the solution to the maze problem. It checks if there exists a solution in the current generation of the population. It does so by iterating over all the individuals in the population, and checking if their fitness score is greater than zero (indicating they have some valid path to the end point) and if they have zero obstacles in their path (as we are looking for the path with the least obstacles).

If a valid solution is found, it stores the path in a list sol, and then iterates over the path to update a dictionary named dictionary. This dictionary represents the mapping of each cell to the next cell in the path, i.e., the keys of the dictionary represent the coordinates of the cells in the path and the values of the dictionary represent the coordinates of the next cell in the path.

Finally, it returns 1 if a solution is found, else it returns 0 indicating that no solution exists in the current generation of the population.

def solution():
    sol = []
    for i in range(populationSize):
        if FinalFitness[i] > 0 and obstacles[i] == 0:
            sol = path[i]
            for j in range(len(sol) - 1):
                dictionary.update({sol[j+1]:sol[j]}) # This loop updates a dictionary named dictionary where the keys represent the coordinates of the cells that form the path, and the values represent the coordinates of the cells that should be visited next in order to follow the path.
            return 1
    return 0

Main Function:

This code is the main driver code for the genetic algorithm to solve the maze. First, it generates the initial population of populationSize individuals using the initialPopulation() function. Then, it enters into a loop which runs until a solution is found. In each iteration of the loop, it calculates the fitness of each individual using the fitness() function.

Then, it checks if a solution has been found using the solution() function. If a solution has been found, it prints a message to indicate the iteration number and uses the tracePath() function from the maze module to visualize the solution path on the maze. Finally, it terminates the program using the break statement.

If a solution has not been found yet, it proceeds with the genetic operations to create the next generation of individuals. It first sorts the population based on fitness using the sorting() function. It then performs crossover on the population using the crossover() function. Finally, it performs mutation on the population using the mutation() function.

The loop then continues with the next iteration, and the process repeats until a solution is found.


initialPopulation(populationSize,rows,columns)
i = 0
while True:
    i+=1
    fitness()
    if solution():
        print(f"Solution found in iteration number = {i}")
        m.tracePath({a:dictionary},delay=500)
        m.run()
        break
    sorting()
    crossover()
    mutation()

Pseudocode:

START
Generate the initial population
Compute fitness
REPEAT
    Selection
    Crossover
    Mutation
    Compute fitness
UNTIL population has converged
STOP

Complete Code in Python:

To implement this algorithm in Python we will use the pyamaze module.

# Registratioin Number : 2021-MC-77
# Name : Muhammad Faisal
# Section : B
# Home Work : CEP - 1
# Date : 5th March 2023
# Submitted To : Sir Doctor Muhammad Ahsan Naeem

import random
from copy import deepcopy
from pyamaze import maze, agent

rows = 7
columns = 7
population = []
populationSize = 400
FinalObstacles = []
FinalTurns = []
FinalSteps = []
FinalFitness = []
dictionary = {}

# Create the maze and agent
m = maze(rows, columns)
m.CreateMaze(loopPercent=100)
a = agent(m, filled=True, footprints=True, shape="arrow")
mazeMap = m.maze_map

def initialPopulation(populationSize , rows, columns):
    for i in range(populationSize):
        pop = []
        pop.append(1)
        for j in range(1, columns - 1):
            pop.append(random.randint(1, rows + 1))
        pop.append(columns)
        population.append(pop)
       
noOfTurns = []
path = []
obstacles = []
noOfSteps = []
def fitness():
    # Number of turns
    for i in population:
        turns = 0
        for j in range(columns-2):
            if i[j + 1] != i[j]:
                turns += 1
        noOfTurns.append(turns+1)
        turns = 0

    # Finding Path
    for i in population:
        p = []
        for j in range(0, rows - 1):
            if (i[j + 1] - i[j]) >= 0: # down or right
                for k in range(i[j], i[j+1]+1):
                    if k <= rows or k <= columns: # check if value is within range
                        p.append((k, j+1))
            if (i[j + 1] - i[j]) < 0: # up or left
                for k in range(i[j], i[j+1]-1, -1):
                    if k <= rows or k <= columns: # check if value is within range
                        p.append((k, j+1))
        p.append((rows, columns))
        path.append(p)

   # Obstacles
    obs = 0
    for i in path:
        for j in range(len(i) - 1):
            if i[j+1][0]-i[j][0] >= 0 and i[j+1][1] == i[j][1]:
                if mazeMap[(i[j])]["S"] == 0:
                    obs += 1
            if i[j+1][0]-i[j][0] < 0 and i[j+1][1] == i[j][1]:
                if mazeMap[(i[j])]["N"] == 0:
                    obs += 1
            if i[j+1][1]-i[j][1] >= 0 and i[j+1][0] == i[j][0]:
                if mazeMap[(i[j])]["E"] == 0:
                    obs += 1
            if i[j+1][1]-i[j][1] < 0 and i[j+1][0] == i[j][0]:
                if mazeMap[(i[j])]["W"] == 0:
                    obs += 1
        obstacles.append(obs)
        obs = 0

    # Number of steps
    for i in path:
        noOfSteps.append(len(i))

    # Fitness Value
    minimumObstacles = min(obstacles)
    maximumObstacles = max(obstacles)
    minimumTurns = min(noOfTurns)
    maximumTurns = max(noOfTurns)
    minimumSteps = min(noOfSteps)
    maximumSteps = max(noOfSteps)
    weightOfObstacle = 3
    weightOfPath = 2
    weightOfTurn = 2

    for i in range(populationSize):
        finalObstacles = (1 - ((obstacles[i] - minimumObstacles) / (maximumObstacles - minimumObstacles)))
        FinalObstacles.append(finalObstacles)
        finalTurns = (1 - ((noOfTurns[i] - minimumTurns) / (maximumTurns - minimumTurns)))
        FinalTurns.append(finalTurns)
        finalSteps = (1 - ((noOfSteps[i] - minimumSteps) / (maximumSteps - minimumSteps)))
        FinalSteps.append(finalSteps)
        finalFitness = ((100 * weightOfObstacle * FinalObstacles[i]) * ( ((weightOfPath * FinalSteps[i]) + (weightOfTurn * FinalTurns[i])) / (weightOfPath + weightOfTurn)))
        FinalFitness.append(finalFitness)

def crossover():
    for i in range(0, populationSize - 1, 2):
        crossoverPoint = random.randint(0, columns - 1)
        parent1 = deepcopy(population[i])
        parent2 = deepcopy(population[i + 1])
        child1 = []
        child2 = []
        # Combine the genetic code of the parents to create the children
        for j in range(len(parent1)):
            if j < crossoverPoint:
                child1.append(parent1[j])
                child2.append(parent2[j])
            else:
                child1.append(parent2[j])
                child2.append(parent1[j])
        # Replace the parents with the children in the population
        population[i] = child1
        population[i + 1] = child2

def mutation():
    for i in population:
        i[random.randint(1, columns - 2)] = random.randint(1, rows)

# Bubble sorting in descending order
def sorting():
    for i in range(populationSize - 1):
        for j in range(i+1, populationSize):
            if FinalFitness[j] > FinalFitness[i]:
                FinalFitness[i], FinalFitness[j] = FinalFitness[j], FinalFitness[i]
                population[i], population[j] = population[j], population[i]
    for i in range(populationSize):
        print(f"{population[i]}          {FinalFitness[i]}")

def solution():
    sol = []
    for i in range(populationSize):
        if FinalFitness[i] > 0 and obstacles[i] == 0:
            sol = path[i]
            for j in range(len(sol) - 1):
                dictionary.update({sol[j+1]:sol[j]}) # This loop updates a dictionary named dictionary where the keys represent the coordinates of the cells that form the path, and the values represent the coordinates of the cells that should be visited next in order to follow the path.
            return 1
    return 0

# Main Function
initialPopulation(populationSize,rows,columns)
i = 0
while True:
    i+=1
    fitness()
    if solution():
        print(f"Solution found in iteration number = {i}")
        m.tracePath({a:dictionary},delay=500)
        m.run()
        break
    sorting()
    crossover()
    mutation()