Keith Madden
Creative Computing / Year 4

alt_text
Keith Madden

Keith Madden

Creative Computing

Year 4

  • Project Title Using a genetic algorithm to solve a user defined maze
  • Course BSc [Hons] Creative Computing
  • Year 4
  • Contact Info keith-madden@hotmail.com

Using a genetic algorithm to solve a user defined maze

The aim of this project is to understand genetic algorithms and learn about the behaviour of the smart rockets application. Studying a genetic algorithm that has been made previous, this project will be adding key functions to a genetic algorithm to try and alter the behaviour of each rocket. Giving them a greater understanding of the maze along with a custom-built fitness function.

Project Description

Have you ever thought about how machines learn without being explicitly programmed? What about how a machine learns about the environment that it is placed in. We are able to give a problem to a machine and actually watch the progress on how the machine thinks and learns while trying to find a solution. I used a Genetic Algorithm to show how a machine can follow an object, find the optimal route or even dodge obstacles. Built using nothing else but Processing, you can see just how easy it is to create a Genetic Algorithm. Genetic Algorithms are based off biology. Given the same characteristics as evolution we can see the progress of the algorithm evolving generation by generation. Using a custom-built fitness function, the machine is able to get the distance from the current target and use it to gather the information needed to try and find an optimal path and speed to try and reach it. The main aim of Smart Rockets is to gather an understanding of how genetic algorithms worked and also learn a small bit in machine learning. This project was also setting out the understanding of how a machine was able to learn the environment around it and also try and find a way around a maze that has been built for it. The book studied was Daniel Shiffman’s Nature of Code. Shiffman gave me the initial idea to learn and study the genetic algorithm and start to try and build my own genetic algorithm. Managing to implement some other features such as the grid, graph, boundaries of the rockets touching the walls and the BFS algorithm. The approach to designing a project such as this involved a large amount of preliminary research to get accustomed to the field of machine learning. Finding that this project was more about the study and development of my machine learning knowledge rather than the full implementation of the code that was going to be used. Very happy with the progress that I have made over the course of this project and the learning curve that I managed to overcome. I started off this project with no prior knowledge about genetic algorithms or even machine learning. The time spent on the research phase allowed me to gather a full understanding of how a genetic algorithm works and what each part of the code manages to do.

Project Findings

The project findings and results were quite interesting. The machine was able to figure out a way around the maze quite fast with the original fitness function. The goal later was turned into a long path to try and implement a breadth-first-search algorithm that allowed the rockets to be judged on not only the straight-line distance from the rocket end PVector to the end target but how the rocket was able to move around the maze and get a new fitness function based on the path it had used.

Keith Madden
Creative Computing / Year 4