Maze Solution in python using Genetic Algorithm

I am a student of Bsc Mechatronics Engineering at the University of Engineering and Technology, Lahore. The purpose of writing this blog to entertain people with the project of maze in python by using a genetic algorithm. As there are functions in python and by using pyamaze a maze in python can be generated straight forward. By using the genetic algorithm method a maze is generated step by step. So what is a genetic algorithm?what is the purpose of using this method?

Genetic Algorithm : A genetic algorithm is a type of search heuristic used in computer science and operations research, which is inspired by the process of natural evolution described by Charles Darwin .It is a natural process In this method first a random population is generated and In a genetic algorithm, fitness refers to a measure of how well an individual solution performs in solving a given problem. The fitness value of each individual is used to determine their likelihood of being selected for reproduction and passing on their genetic information to the next generation. After this the most fittest among the individual selected for cross over .After that mutation occures in which random gene is changed to create a new population of solutions that are likely to be better

Visualization of maze solution using Genetic Algorithm:

maze solution of 15 by 15 grid

Random Population:

In python First, a random population is generated using the random function in python by importing random library. A number of rows of the maze and number of columns is given also population size is given here so a random population is generated.

There are two main categories of maze:

1. Square maze (Number of rows equal to number of columns)
2. Rectangular maze (Number of rows less or greater than number of columns)
3. The criteria for maze where number of rows equal to number of columns are same as where number of rows less than number of columns
4. The criteria for maze where number of rows greater than number of columns is different from the rest
5. The random population is generated is in such a way that for maze where number of columns equal to number of number of rows and where number of rows less than number of columns, The first and last gene of chromosme remains always same and it is equal to number of rows and between these genes the values of genes are (column-2)
6. The random population where number of rows greater than number of columns The first and last gene of chromosme in population always remains same and it is from number columns and between these genes ,the genes are calculated as (rows-2) and between these genes are placed

from random import *
No_of_Rows=15
No_of_Columns=15
Population_size=400
population=[]
#Function to generate random population
def random_population():
    pop=[]
#For square maze and rectangular maze where number of rows less or equal to no of columns
    if (No_of_Rows<=No_of_Columns):
        for i in range(Population_size):
            pop.append(1)
            for j in range(No_of_Columns-2):
                pop.append(randint(1,No_of_Rows))
            pop.append(No_of_Rows)
            population.append(pop) 
            pop=[]
#For rectangular maze where number of rows greater than number of columns
    elif(No_of_Rows>No_of_Columns):
        for i in range(Population_size):
            pop.append(1)
            for j in range(No_of_Rows-2):
                pop.append(randint(1,No_of_Columns))
            pop.append(No_of_Columns)
            population.append(pop)
            pop=[]

Fitness Function :

After a random population is generated the fittest one is calculated based on path length, number of turns, and obstacles.

There are some criteria regarding fitness function which are required to calculate fitness:

1. The first one is to calculate path , the population and population size are given by calculating the path between them as in the maze the starting point is in form of x and y (1,1) and hence the whole maze is formed , the task is to find path by observing gene difference ,row and column .

m=maze(No_of_Rows,No_of_Columns)
my_map=m.maze_map
print(my_map)

def Fitness():
    Calculate_path()
    hurdles()
    count_step()
    no_of_turns()
    w_hurdles=3
    w_turns=2
    w_steps=2
    for i in range(Population_size):
        obs_fit=1-((OBs[i]-min(OBs))/(max(OBs)-min(OBs)))
        Obs_Fitness.append(obs_fit)
        turn_fit=1-((Turns[i]-min(Turns))/(max(Turns)-min(Turns)))
        Turn_Fitness.append(turn_fit)
        step_fit=1-((Steps_count[i]-min(Steps_count))/(max(Steps_count)-min(Steps_count)))
        steps_Fitness.append(step_fit)
        fitness=100*(w_hurdles*obs_fit)*(((w_turns*turn_fit)+(w_steps*step_fit))/(w_steps*w_turns))
        Total_fitness.append(fitness)

By using fitness formulas: at the end, total fitness is calculated

fit=1-(T-T(min))/T(max))

fitness= 100*(w_hurdles*obs_fit)*(((w_turns*turn_fit)+(w_steps*step_fit))/(w_steps*w_turns))

The path function calculates path using population generated in the form of x and y

def Calculate_path():
    path=[]
    for i in population:
        if No_of_Rows<=No_of_Columns:
            for j in range(No_of_Columns-1):
                if (i[j+1]-i[j])>=0:
                    for k in range (i[j],i[j+1]+1):
                        path.append((k,j+1))
                if i[j+1]-i[j]<0:
                    for k in range(i[j],i[j+1]-1,-1):
                        path.append((k,j+1))
            path.append((No_of_Rows,No_of_Columns))
        elif No_of_Rows>No_of_Columns:
            for j in range(No_of_Rows-1):
                if (i[j+1]-i[j])>=0:
                    for k in range (i[j],i[j+1]+1):
                        path.append((j+1,k))
                if i[j+1]-i[j]<0:
                    for k in range(i[j],i[j+1]-1,-1):
                        path.append((j+1,k))
            path.append((No_of_Rows,No_of_Columns))
        Path.append(path)
        path=[]

The function which calculates hurdles is such that the x and y coordinates from maze map is checked and based on the conditions that is :If number of rows are increasing then its direction is “South” , If number of rows are decreasing its direction is “North”, If number of colums are increasing it is “East”, if number of columns are Decreasing ,its direction is “West”.

def hurdles():
    Obstacles = 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 my_map[i[j]]["S"]==0:
                    Obstacles+=1
            if i[j+1][0]-i[j][0]<0 and i[j+1][1]==i[j][1]:
                if my_map[i[j]]['N']==0:
                    Obstacles+=1
            if i[j+1][1]-i[j][1]>0 and i[j+1][0]==i[j][0]:
                if my_map[i[j]]["E"]==0:
                    Obstacles+=1
            if i[j+1][1]-i[j][1]<0 and i[j+1][0]==i[j][0]:
                if my_map[i[j]]["W"]==0:
                    Obstacles+=1
        OBs.append(Obstacles)
        Obstacles=0

The next step in fitness function is count steps which takes to complete path

def count_step():
    for i in Path:
        Steps_count.append(len(i))

The next step is to count number of turns ,If column is changed then turns will be added:

def no_of_turns():
    turns=0
    for i in population:
        for j in range(len(i)-1):
            if (i[j+1]!=i[j]):
                turns+=1
        Turns.append(turns)
        turns=0

Crossover Function: Now the fittest one is selected for crossover. Crossover is done by dividing the population. Two chromosomes are selected the chromosome are randomly cut into half and the genes of chromosome interchange and new chromosomes are formed .The fittest chromosomes are selected for cross over :

cross over

def Cross_Over():
    for i in range(0,Population_size//2,2):
        Parent_1=deepcopy(population[i])
        Parent_2=deepcopy(population[i+1])
        if(No_of_Rows<=No_of_Columns):
            cut_point=randint(1,No_of_Columns-2)
            for j in range(cut_point,No_of_Columns):
                Parent_1[j],Parent_2[j]=Parent_2[j],Parent_1[j]
        else:
            cut_point=randint(1,No_of_Rows-2)
            for j in range(cut_point,No_of_Rows):
                Parent_1[j],Parent_2[j]=Parent_2[j],Parent_1[j]
        population[(Population_size//2)+i]=Parent_1
        population[(Population_size//2)+(i+1)]=Parent_2

Mutation Function: In mutation the randomly gene is changed .After cross over and mutation the new chromosomes are formed which are fittest and show shortest path. The randomly gene in the chromosome is changed. This is done to convert the population from converging too quickly to a local optimum and to improve a diversity of solutions in the population

def Mutation():
#For square and rectangular maze where number of rows less than or equal to number of columns
    if(No_of_Rows<=No_of_Columns):
        for i in population:
            i[randint(1,No_of_Columns-2)]=randint(1,No_of_Rows)
    elif(No_of_Rows>No_of_Columns):
        for i in population:
            i[randint(1,No_of_Rows-2)]=randint(1,No_of_Columns)

Sorting:

The next step is sorting or in genetic algorithm is parenting, The final fitness is swapped with the population.This sorting process is used to maintain diversity in the population and to ensure that a range of trade-offs between the multiple objectives is explored.

def sorting():
    for i in range(Population_size-1):
        for j in range(i+1,Population_size):
            if(Total_fitness[j]>Total_fitness[i]):
                Total_fitness[i], Total_fitness[j]=Total_fitness[j], Total_fitness[i]
                population[i],population[j]=population[j],population[i]

Solution :

At last solution is obtained :

def is_solution():
    sol=[]
    for i in range(Population_size):
        if(Total_fitness[i]>=0 and OBs[i]==0):
            sol=Path[i]
            for j in range(len(sol)-1):
                Final.update({sol[j+1]:sol[j]})
            return 1
    return 0

Github gits code:

Graphs to visualize :

Graph between number of steps and population :

Graph between number of turns and population :

Graph between Obstacles and population: