Note: This is part 2 of a multi-part series.
In Part 3 we created a Neural Network model for AI
In Part 1, we created a Neural Network model. That model is filled with random values and needs to be trained before it can behave correctly. In this part, we will implement the genetic algorithm to train it.
Introduction to Genetic algorithm
The genetic algorithm is a heuristic algorithm based on the theory of natural evolution. The concept of selection, crossover, and mutation is applied in this method. It consists of four phases.
In this phase, a population of creatures is created and introduced to the system. In the first generation, creatures are created with random values covering the entire range of possible values. These values make chromosomes based on which a creature's behaviour is determined.
Creatures performing best in the system are selected to produce offspring for the next generation. To measure the performance(score) of the creature, we will use the fitness function. We will be using time creature survived without colliding wall as the fitness function. Also, the creature scores a huge point when it reaches its goal.
The chromosomes from parents are taken and mixed to create new offspring. Gene of these creatures is taken and mixed to get chromosomes for offspring inheriting the parent's character. Various techniques are available for crossovers such as one-point crossover, two-point crossover, and uniform crossover. One-point crossover and two-point crossover slices chromosomes and swap them to create children. Uniform crossover picks random genes from either parent to create a gene for children. We will be using uniform crossover for path-finding AI.
A random gene of a chromosome is randomized to add unique characteristics in children. It allows offsprings to explore other possible solution that was not explored by the previous generation. The number of genes altered is determined by mutation chance. The lower mutation causes the finding of a solution long time. Higher mutation chance causes a drastic change in the behaviour of children compared to parents thus losing traits of parent. So, it is important to choose a good mutation chance.
After completing all of the above phases, a cycle of generation is completed. A new population of creatures is generated using chromosomes obtained and are introduced to the system. The cycle of selection, crossover, the mutation are repeated until the termination condition is met.
Creating general creature class
Let's first create a
Creatures class that acts as an interface for interacting creatures from the GA system. We will inherit from this class to create path finding creatures. The advantage of having a parent
Creatures class is that it provides an abstraction to the GA system so that, various types of creatures can be created, not just path finding AI.
A base creature requires a
NN model we will call it
brain . An
id will be assigned to each creature so that they can be recognized. To maintain a state of a creature,
isRunning will be used.
isInitialized will keep track of all required setups done and
isRunning will keep track of whether a creature is idle or being simulated.
To initialize a creature's
brain, number of
output are required. This can vary from type of creature but should be identical for all same type of creature.
Next, create getters and setters for manipulating chromosomes in a creature's brain. Also, create methods for sending and receiving signals from the brain. When the message is received from the brain,
GotResultFromBrain will be called. This method needs to be overridden to act according to the received output.
Now, let's create events so that other systems monitoring creatures can know what is happening. We will create
onFailed event to broadcast the success or failure of the creature. Two methods will be created so that child class can inform failure and success.
Implementing Genetic algorithm
To implement the genetic algorithm, let us first create
GeneticAlgorithm class. It consists of
GetOffsprings method that can be used to get chromosomes for the next generation. This method will take 5 parameters as follows:
parents- Chromosomes of all parents of the previous generation.
scores- Score received by each parent. The score must be in the same order as
parents, score at
thindex is a score of
selectionChance- Chance of best parent be used for crossover. It will be in the order of best parent at
thindex to least good parent at last index. Its length will determine the number of parents that will be chosen for crossover.
mutationChance- Chance of gene to be mutated. It must be chosen carefully as too high or too low value can cause a less efficient learning system. We can experiment with different mutation chances to find the right mutation value.
offspringCount- Number of offspring to generate.
Now, we can implement the process of selection, crossover and mutation.