Monday, September 22, 2014

Genetic Algorithms

After a week of reading I see that we need to start with Genetic Algorithms.
So here is a brief description of what ill be making over the course of next week.

In a general algorithm for computing we see that alll the steps are defined by the programmer beforehand.

In GA we try to encode the solution set to be represented in a genome. This genome is simply a collection of instructions which when followed will lead to a solution.

This solution may not be optimum, it might even be barely solving the problem. However it is a solution.

eg. A good example is a collection of directions. 'lrlrllrrlrlllr'
This might not get the vehicle to the objective. However it is a possible solution.

First we create a population of these genomes. Thus the task of solving the problem is reduced to simply correctly representing the problem's solution  in a genome.

After this, we simply let the population evolve using two techniques. Crossover and Mutation rate. The evolution creates very optimized solutions for the problem due to natural selection.

In GAs the natural selection is carried out by the 'fitness' function. The method by which the fitness,crossover and mutation functions do their tasks may be varied to have different results.

Thus genetic algorithms are very good for searching things where the solution space is very large.
eg. If you need to search for a specific mathematical equation which correctly predicts a given data set, the search space is essentially all the possible mathematical equations. Here exhaustive searching will take a long time. Thus GAs will prove to be useful here.