Neural Net with Genetic Algorithm
Link to Repository
Skip to Section
Overview
High Concept
Role: Programmer
Engine: Personal Engine in C++ with Opengl
The project controls a population of AI ships to avoid "asteroids" by using a neural net. The neural net is trained using a genetic algorithm and uses sensors as inputs.
Team Size: 1 individual project
Development Time: 8 weeks
Terminology
Genetic Algorithm
-
Genome – encoded data
-
Population – A collection of different genomes of a generation
-
Epoch – The process of moving from one generation to the next
-
Fitness – How fit a genome is to solve a problem
-
Selection – Process of selecting parents for next generation’s children
-
Crossover – The process of combining two genome’s DNA to create a child’s DNA.
-
Mutation – A low chance to randomize aspects of a child’s data
Neural Net
-
Neuron - A node in a neural net and neuron layer
-
Neuron Layer - A collumn of neurons that takes in inputs and weights from the previous layer or outside the net and generates output based on the weights and inputs.
-
Inputs and Outputs - Each node has associated inputs and outputs. Each line from one output to the next node has an associated weight that modifies the value before becoming an input for the next node.
Setup
-
The V's are ships
-
White ships haven't collided
-
Red ships collided with an asteroid
-
-
The brown circles are asteroids
-
Each ship has 7 sensors. Each sensor acts as the input for the input layer of the neural network.
-
Ideally, the sensors in the cardinal directions to the ship detect the nearby asteroids. The two sensors in front of the ship and the one centered on the ship act as multipliers.
Genetic Algorithm and Neural Network
The genetic algorithm acts as the learning mechanism to train the neural net. Each population consists of a 500 genomes, at least when the neural net was originally trained. Each genome is a vector of floats from -1 to 1 and acts as the weights used by the neural net. Each epoch lasts for 20 seconds at 60 fps (1200 frames). At the end of each epoch, each genome passes its genes on to the next generation based on each genome's fitness.
Fitness is determined by:
-
Distance travel forward
-
Number of turns alive
-
Number of asteroids visited
-
1.0 – (number of times died / number of times possible)
The traits used for fitness were chosen to motivate surviving, moving forward (not going in circles), and exploration.
Once genomes are selected for reproduction, they are combined with a crossover function causing each child to inherit from two parents. After a child is created, it is mutated a minute amount to seed in random behavior. To help prevent from the best genomes from being lost, the best few are added to the next generation without combining or mutating.
The input to the neural net is the current state of the sensors. The weights are the genome. The output is the what direction the ship should turn.
Demonstration of Results
Untrained Neural Net
Trained Neural Net