Kriss Jessop About Me Projects Personal Projects RPGs

An Introduction to Genetic Algorithms

Posted on November 14th, 2016

Anyways, genetic algorithms tend to be best in situations where other algorithms struggle to deal with the task. In fact if you were to use rules as the genes, you’ve got yourself some serious potential in game AI. There’s nothing like a bunch of bad guys that learn what kind of actions do and don’t work against you. Kinda reminds me of the giant robots in The Incredibles.

The general cycle of a genetic algorithm can be seen below. A population would be initialised, their effectiveness evaluated, then children would be produced that were different to the parents either through mutation, genetic crossover (sharing of genes), or other operators. The old population would die off, and the new population would be evaluated, and the cycle continues.

The Cycle of a Genetic Algorithm

A thing that I totally “borrowed” from Mohammad’s presentation.

The genes of the population can be anything from a string of bits, characters or numbers to collections of permutations, rules, program elements, etc. Pretty much any kind of data structure. When implementing genetic algorithms there should be some bias towards propagating fitter entities. That said, some randomness is still needed otherwise your little community of 1’s and 0’s is going to get stuck in a rut and potentially find a less efficient solution. Bias is good for exploiting a potential solution, but randomness is needed for better exploration.

Exercises

The given exercises this time are to build a genetic algorithm to find a solution to either the Travelling Salesman Problem, or a weird card/number game that I assume Mohammad pulled from a maths book or something. In this number game, one has to split the cards 1 through 10 into two groups of five. One has to add up to 36 (or as close to it as possible) while the other has to multiply out to 360 (or as close as possible).

tsp1

NB: Extra marks on the coursework for being among the first to solve the problem? Super uncool Mohammad!

For the post part, the tasks seem rather straight forward. For the Travelling Salesman Problem I made a function to spit out code for every possible a-to-b city combination from the list then began working agents/entities. You just initialise them all with a random gene sequence.

I used a list and took random elements from it to avoid duplication, as you only want each city once, then evaluated the effectiveness/fitness of each one. Next I wrote some mutation code (that swapped random parts of the gene sequence), before getting bored and finding something else to do… Yeah.