Genetic Algorithm: A very simple primer

Here I am going to post a very short intuitive description of Genetic algorithm while I am reviewing and refreshing my knowledge which I gathered in my bachelors fourth year.

Genetic algorithm actually mimics the nature by first selecting the best persons in the population, then reproducing (in AI term, its called crossover) children from the best parents, and then mutating the new generation (as per Darwin).

Population: So what is actually a population. A population is a set of possible solutions to the problem. Normally, we randomly pick some solutions, and call those a population (initial population) and then process each of them through the engine to get their fitness (are they good solutions?) and depending upon that we assign each of the population a fitness value.

Crossover: After we get all the fitnees values, we can choose the best persons from the population and then we do cross over just like DNA crossover in human. It can be of several types. The simplest is in the case of binary input. Say, there are two best persons A and B and they are represented

A: 01010101

B: 11110000

And the crossover rule is to cross after 4th position. So the reproduction would be:

x: 01010000

y: 11110101

Now, to be more precise, crossover is not always done between the best persons in the population. The best persons marely have the best chance to be participating in a crossover funciton. Normally we use a function called a Roulette Wheel. It works like following:

The total population is charted like a pie chart with the people having a slice of the pie proportional to his fitness score. And then randomly choose a position in the pie and take that person.

Crossover rate: This rate defines the probability that two members of the population will have crossover. This probability is set to around 0.7

Mutation: Mutation refers to randomly change some bits of the children for evolution. This rate of mutation can be very small (like 0.001) or quite large (say 0.07) depending upon the scenario. We randomly flip the bits in case of binary population.

Actual Working: So, how the genetic algorithm actually work? With the primer above, you should be able to understand the following:

Generate enough possible random solutions to the problem, create a population of all the solutions. Check the solutions for accuracy. Create rule for fitness. The rule is upto you and depends on the problem in hand. It can be as simple as proportional or inverse proportional to the actual solution and the random solution. Give a fitness value to each member of the population. Apply roullette wheel algorithm to choose person to apply cross over. Then, apply crossover to the picked members and generate a new generation of children by mutating the crossovered members. So, now we got a whole new set of evolved population. Iterate the whole procedure again until the fitness value comes to a certain threshold where we stop and accept that the current population is the best.

A very good primer can be found at: http://www.ai-junkie.com/ga/intro/gat1.html