An EvolutionaryAlgorithm is a type of heuristic search and optimization methods based on principles of biological evolution and breeding. The major camps and flavors are
although there are a plethora of other approaches.
In essence, they all come down to
- choose a quantitative problem to solve
- choose a "good" way to represent solutions - raw bitmaps, lists of floating-point numbers, tree structures, or something entirely different?
You want a representation such that, given some initial guess, small changes to that guess (in step 5) give rise to solutions that are slightly better or worse, rather than surrounding each reasonably-good initial guess with large moats of terrible solutions that have to be jumped over to reach better solutions.
- choose some initial guess solutions to the problem
- determine how good these are, objectively, at solving the problem
- allow the solutions that are better, objectively, to multiply more than the ones that aren't, with some minor variation
- get rid of some of the worse solutions you have hanging around, and keep the better ones
- repeat from (4)
Recombination of solutions features in a lot of these, but mutation (slight variation of certain "genes") is enough for some of the others. The literature on
EvolutionaryAlgorithms is full to the brim with slight fillips and specializations. --
BillTozier
Actually, mutation should be used sparingly. Some experts like Koza decry its use at all. The current framework for ExtremeGeneticProgramming is capable of evolving solutions using crossover only. -- JonGroff
Added "choose representation" step. I haven't done much with EvolutionaryAlgorithms (experts, please comment), but I suspect more ProgrammerTime? is spent diddling with various representations than any other step of this process. (Of course, most MachineTime? is spent iterating steps 2 through 5, but that can happen while the programmer is taking a CaffeineBreak?, overnight, or over a 3 day weekend. -- DavidCary
CategoryEvolution
Evolutionary Algorithms