Genetic algorithms have long been a favourite subject of mine as there’s something about computing that is inspired by biology that is quite fascinating, almost mystical. After researching the subject and understanding the procedures behind what makes the algorithm work I can see how the implementation is quite simple – however it still remains a fascinating approach to programming AI.
A genetic algorithm is an optimisation algorithm which means that even from the minute it’s switched one it will have an answer and the longer it runs the more accurate that answer will get, the more optimised. It’s a technique that takes inspiration from genetics and by applying a sort of natural selection upon the possible answers it can come up with the most optimal solution.
Common disadvantages that plague more complicated AI techniques crop up here as well as genetic algorithms tend to be too computationally costly to run in real time for a complex database. The final answer given might not be all that optimal due to the constraints of the program. It is also heavily resistant to tweaking as you cannot change much about the implementation without touching the initial database.
Genetic algorithms have been quite useful in many different situations as they can go over quitter large sets of data quite quickly and can provide multiple good solutions instead of one or none. If time is not an issue the algorithm can be let to run which will further optimise the answer given.
What follows is a rundown on how the algorithm works and a brief explanation of its steps
This can be done in a variety of ways. A common and low-cost solution is to have a completely random initialisation. A developer could use a heuristic of sorts that could point the algorithm towards a solution. This can speed up the process significantly however there is a risk that it will cause the algorithm to miss certain solutions and come up with a sub optimal solution. Finally, a developer could seed the algorithm with solutions with high fitness. They act as a guide and aid convergence however it avoids the pitfall of using heuristics as most of the solutions will be random and not influenced by the developer. If for example one the random solutions is a better fit than one the ready solutions we’ve provided that will be chosen instead. An easy to way to get these solutions is to include the result of a previous run of the algorithm.
This part is the core of the algorithm as it examines a particular solution and determines it’s fitness. The fitness function will be used multiple times so a good developer will have to ensure it’s not too computationally expensive while not sacrificing too much accuracy.
Crossover takes solutions and generates a new one using information from the last two mimicking sexual reproduction. There are a few different approaches to this all with their own advantages and disadvantages. It can split the parent solutions and combine the parts to create a new one This can be down as many times as the developer sees fit but one or two points seems to be most common. A more extreme option is to treat every individual gene as separate and selecting it from with parent.
Mutation changes elements in answers without needing parents or heeding fitness values. It is put in place to introduce more variety in a system. This is usually kept quite low as it can overwhelm an algorithm with random results. There are a variety of ways to perform the mutation but they all depend on making small and subtle changes to an existing solution. Depending on the implementation all mutations can be accepted or if they are of low fitness discarded.
This is simply when the algorithm stops. This is determined by the developer however some common implementations can be the number of cycles, the percentage of fitness between generations or the level of fitness itself.
Champanard, A. J. (2004). AI Game Development: Synthetic Creatures with Learning and Reactive Behaviors