This is part of an ongoing series in which we experiment with different methods of AI. We’ll look at the state of the art and the out of fashion; the practical and the (seemingly) impractical; to find what works and what doesn’t. In this part, we will be writing the genetic algorithm that will evolve our UFOs behaviour. You can read the first part in the series for more information on what we are trying to accomplish. You can also see my earlier article for more general information on genetic algorithms, however, I’ll make sure to include the important parts here.
So what is a genetic algorithm?
A Genetic Algorithm (GA) is an attempt to mimic our evolutionary processes. GA’s are a specific type of evolutionary computing paradigm common to artificial life simulations. Solutions to problems are encoded in a structure called a chromosome (or genome). The solution can be represented as binary digits (bits) or in any other computer-readable format; we’ll be using the floating-point weights of our UFOs neural networks. Similarly, to biological evolution, new generations are created by mating two chromosomes and (possibly) applying mutation to produce a new offspring and consequently a new solution. So in terms of our game, the ‘mating’ will occur when we create a new neural network by combining two previously created neural networks.
While there was a lot of information hopefully as we write the genetic algorithm (which we will start now and finish in the next part) it will become more clear how this will help our UFOs.
For our GA to work, we need a method of deciding when to remove a UFO from the game and therefore creating ‘generations’. To accomplish this we’ll give each UFO an energy level. This energy value will decrease whenever they collide with another UFO or a screen edge, the two things we do not want our UFOs to do. When the energy reaches zero the UFO will be removed from the simulation and added to a ‘pool’. This pool represents a number of solutions to our problem, it is a collection of a UFOs predecessors. I’ll go into more detail as we go along but the general steps for genetic algorithm are:
The method is mostly unchanged however it now returns a reference to the created UFOs neural network. We’ll use this later to evolve the newly created UFOs. Don’t forget to remove SpawnUFO from the SceneGame class, we only want our GeneticAlgorithm class spawning UFOs from now on.
We need to instantiate our new GeneticAlgorithm class in SceneGame.
We add three new components in SpawnUFO:
The comparator function for the sort method uses the UFOs time alive.