About Genetic Algorithms ยท Updated 14 December 2005, by Jason
Genetic algorithms (or GA) were created to solve mathmatically definable problems. They are algorithms based on natural biological evolution. The architecture of systems that implement genetic algorithms are able to adapt to a wide range of problems, based on user definitions. A GA functions by generating a large set of possible solutions to a given problem. It then evaluates each of those solutions, and decides on a "fitness level" for each solution set. These solutions are then used to breed new solutions. The parent solutions that were more "fit" are more likely to reproduce, while those that were less "fit" are more unlikely to do so. In essence, solutions are evolved over time. This way one evolves his search space scope to a point where one can find the solution. Genetic algorithms can be incredibly efficient if programmed correctly.
General Algorithm for Genetic Algorithms
Genetic algorithms are not too hard to program or understand, since they are biological based. Thinking in terms of real-life evolution may help non-programmers understand. Here is the general algorithm for a GA:
1. Encode the Problem in a Binary String. One must first choose a programming language and define the solution by selecting which variables will be tested for. This also includes a definition of fitness, and a means to measure it.
2. Create a Random Initial State. An initial population is created from a random selection of solutions (which are analagous to chromosomes). This is unlike the situation for Symbolic AI systems, where the initial state in a problem is already given instead.
3. Evaluate Fitness. A value for fitness is assigned to each solution (chromosome) depending on how close it is to solving the problem. These "solutions" are not to be confused with "answers" to the problem -- as solutions generally evolve into more an more accurate "answers."
4. Reproduce (& Mutate Children) Those chromosomes with a higher fitness value are more likely to reproduce offspring (which can mutate after reproduction). The offspring is a product of the father and mother, whose composition consists of a combination of genes from them. This process is known as "crossing over," and the likelyhood of varied segments from each parent is a viriable called "crossover".
5. Next Generation If the new generation contains a solution that produces an output that is close enough or equal to the desired answer then the problem has been solved. If this is not the case, then the new generation will go through the same process as their parents did (Steps 3 through 5). This will continue until a solution is reached.
Applications of Computational Evolution
Genetic Algorithms can be applied to virtually any problem that has a large search space. Al Biles uses genetic algorithms to filter out 'good' and 'bad' riffs for jazz improvisation, the military uses GAs to evolve equations to differentiate between different radar returns, stock companies use GA-powered programs to predict the stock market. GAs have successfully even been used to evolve various aspects of other GAs - either the connection weights, the architecture, or the learning function. GAs are perfect for evolving the weights of a neural network - there are immense number of possibilities that standard learning techniques such as back-propagation would take thousands upon thousands of iterations to converge to. GAs could (given the appropriate direction) evolve working weights within a hundred or so iterations.
from http://www.generation5.org/content/2000/ga.asp by Sam Hsiung and James Matthews