31-07-2012, 03:15 PM
Genetic Algorithms
Genetic Algorithms.ppt (Size: 197 KB / Downloads: 169)
Genetic Algorithms (GA) OVERVIEW
A class of probabilistic optimization algorithms
Inspired by the biological evolution process
Uses concepts of “Natural Selection” and “Genetic Inheritance” (Darwin 1859)
Originally developed by John Holland (1975)
The Metaphor (cont)
The computer model introduces simplifications (relative to the real biological mechanisms),
BUT
surprisingly complex and interesting structures have emerged out of evolutionary algorithms
Representation
When choosing an encoding method rely on the following key ideas
Use a data structure as close as possible to the natural representation
Write appropriate genetic operators as needed
If possible, ensure that all genotypes correspond to feasible solutions
If possible, ensure that genetic operators preserve feasibility
Local Tournament Selection
Extracts k individuals from the population with uniform probability (without re-insertion) and makes them play a “tournament”, where the probability for an individual to win is generally proportional to its fitness
Selection pressure is directly proportional to the number k of participants