What Are Genetic Algorithms?

What is a genetic algorithm? It's a method of solving extremely hard problems by starting out with a bunch of random answers and gradually refining them until they start looking like the solution you want.

In other words, it solves problems heuristically, meaning it loops through iterations which gradually converge to the answer.

Terminology

This method of problem solving obviously gets it's name from the way biological organisms grow and evolve over time to better suit their environment by passing on genetic material (DNA), so much of the terminology used comes straight from the biology textbook.

• Generation - one iteration of the algorithm.
• Chromosomes - a chromosome represents a single answer/solution.
• Population - this is just the group of Chromosomes that we are currently dealing with.

The Method

• Starting Up:
  
  • Before you start the genetic algorithm, you need to decide a few things:
    How are you going to represent a chromosome? They could be simple numbers or strings or even arrays. In my Scheduler I used whole timetable grids as my chromosomes.
  • How big is your population going to be? There is a trade off between too little chromosomes which might never find the solution, and too many in which case it takes too long to run the program anyway. There is a point where adding more chromosomes does not increase the speed or efficiency of the GA. This point will depend on the problem and how you represent your chromosomes.
  
  
• 1. Initial Population:
  So, to start off your first generation, you need a good sized population of chromosomes with initial values. Now they can either be initalised to a random number or you can give them values which fit your criteria for the solution.
  
  
• 2. Fitness Testing:
  Just like in the wild, your answers must be tested to see how well they survive, ie. match the answer you're looking for. The fitness function is different for each problem, but it returns the same result: it assigns a value to each chromosome indicating how 'fit' they are compared to the answer. You have to design a function which will 'coax' your GA into giving you the right answer, usually consisting of rewarding good traits and punishing others (for example in the picture above, we want to find a yellow ball, so all balls with yellowish colours are rewarded with a high fitness value).
  
  
• 3. Selecting Best Parents:
  Now you need to select the best or fittest chromosomes to become parents and continue the species! There are many ways of statistically select pairs of parents but I just select pairs until I have enough (*enough* being about 1/2 to 1/4 of your original population) and let them breed. Other implementations also have a probability of crossover as opposed to just copying the chromosome across to the children population.
  
  
• 4. Breeding
  Also known as Crossover, what happens here is that each pair of parents creates two children chromosomes, these children have literally half of one parent and half of the other. You pick a random point from which to split the parent's chromosome. This means that child A gets: First half of parent A, second half of parent B, and child B gets: First half of parent B, second half of parent A.
  
  
  
  
  Splitting Numbers: If you are using just numbers as chromosomes, you'll have to convert them to their binary representations and split them that way. If you are using arrays, it's easy and you just select all the array entries before the split point and copy them into the one child and the other half into the other child, etc.
  
  Elitism: When breeding there is a very good chance that the fittest chromosome gets destroyed, so Elitism was introduced, this just copies the fittest chromosome(s) directly into the children population, ensuring that the best solution this far is preserved. This can also greatly decrease the time the GA takes to find an acceptable answer.
  
  Splitting Techniques: This is just one of many splitting techniques, others include splitting the chromosomes multiple times, completely random splitting etc.
  
  
• 5. Mutating:
  As your GA runs now, the solution will never get any better than the fittest parent's solution and your gene pool will now stagnate unless you introduce a few mutations to keep your options open. Mutations are not done on all the children, it's based on a probability which should be kept pretty low (5% - 20%). Performing a mutation is quite simple, you pick a random part of your chromosome and either flip it's binary bits (XOR) or reverse its numberical value, or even just replace it with a random number.
  
  
• And that's it!, your new children now become the active population ready to become parents for the next generation.
  

So genetic algorithms are incredibly powerfull tools. Most dyed-in-the-wool computer scientists dismiss them as a sloppy inaccurate solution, but given enough time and tweaking you can get it to produce an answer within even the finest tolerances.