21-11-2012, 01:00 PM
Genetic Algorithms
Genetic-Algorithms.ppt (Size: 496.5 KB / Downloads: 569)
Introduction
After scientists became disillusioned with classical and neo-classical attempts at modeling intelligence, they looked in other directions.
Two prominent fields arose, connectionism (neural networking, parallel processing) and evolutionary computing.
It is the latter that this essay deals with - genetic algorithms and genetic programming.
What is GA
A genetic algorithm (or GA) is a search technique used in computing to find true or approximate solutions to optimization and search problems.
Genetic algorithms are categorized as global search heuristics.
Genetic algorithms are a particular class of evolutionary algorithms that use techniques inspired by evolutionary biology such as inheritance, mutation, selection, and crossover (also called recombination).
Genetic algorithms are implemented as a computer simulation in which a population of abstract representations (called chromosomes or the genotype or the genome) of candidate solutions (called individuals, creatures, or phenotypes) to an optimization problem evolves toward better solutions.
Traditionally, solutions are represented in binary as strings of 0s and 1s, but other encodings are also possible.
GA Requirements
A typical genetic algorithm requires two things to be defined:
a genetic representation of the solution domain, and
a fitness function to evaluate the solution domain.
A standard representation of the solution is as an array of bits. Arrays of other types and structures can be used in essentially the same way.
The main property that makes these genetic representations convenient is that their parts are easily aligned due to their fixed size, that facilitates simple crossover operation.
Variable length representations may also be used, but crossover implementation is more complex in this case.
Tree-like representations are explored in Genetic programming.
General Algorithm for GA
Initialization
Initially many individual solutions are randomly generated to form an initial population. The population size depends on the nature of the problem, but typically contains several hundreds or thousands of possible solutions.
Traditionally, the population is generated randomly, covering the entire range of possible solutions (the search space).
Occasionally, the solutions may be "seeded" in areas where optimal solutions are likely to be found.
Reproduction
The next step is to generate a second generation population of solutions from those selected through genetic operators:
crossover (also called recombination), and/or mutation.
For each new solution to be produced, a pair of "parent" solutions is selected for breeding from the pool selected previously.
By producing a "child" solution using the above methods of crossover and mutation, a new solution is created which typically shares many of the characteristics of its "parents". New parents are selected for each child, and the process continues until a new population of solutions of appropriate size is generated.
Mutation
After selection and crossover, you now have a new population full of individuals.
Some are directly copied, and others are produced by crossover.
In order to ensure that the individuals are not all exactly the same, you allow for a small chance of mutation.
You loop through all the alleles of all the individuals, and if that allele is selected for mutation, you can either change it by a small amount or replace it with a new value. The probability of mutation is usually between 1 and 2 tenths of a percent.
Mutation is fairly simple. You just change the selected alleles based on what you feel is necessary and move on. Mutation is, however, vital to ensuring genetic diversity within the population.