New version page

Evolutionary Algorithms

This preview shows page 1-2-3-4-5-6 out of 18 pages.

View Full Document
Do you want full access? Go Premium and unlock all 18 pages.
Do you want full access? Go Premium and unlock all 18 pages.
Do you want full access? Go Premium and unlock all 18 pages.
Do you want full access? Go Premium and unlock all 18 pages.
Do you want full access? Go Premium and unlock all 18 pages.
Do you want full access? Go Premium and unlock all 18 pages.

Unformatted text preview:

Evolutionary Algorithms in a NutshellORHow I copied the comp.ai.genetic FAQ onto a bunch of slides at 5am this morningAniruddh Nath24 Sep 2006What are Evolutionary Algorithms?●“A subset of evolutionary computation, a generic population-based metaheuristic optimization algorithm.” - Wikipedia●Wuh?●A set of biologically inspired algorithms that work on the 'survival of the fittest' principle.Key Features●Population●Genetic operators (recombination, mutation)●Reproduction●Fitness function●ExplorationTypes of Evolutionary Algorithms●Genetic algorithms●Evolutionary programming●Evolution strategies●Genetic programming●Learning classifier systemsGenetic Algorithms●Search technique, often used for optimization problems.●Population: usually a set of binary strings (“chromosomes”).●Looking for a binary string that is exactly or approximately optimal, given a fitness function.Pseudocode (from c.a.genetic)t := 0;initpopulation P (t);evaluate P (t);while not done do t := t + 1; P' := selectparents P (t); recombine P' (t); mutate P' (t); evaluate P' (t); P := survive P,P' (t);odToy ExampleGive me a number as close to '42' as possible.Representation: unsigned binary strings.Fitness function: f(x) = 42 - |42 – x|Completion condition: f(x) > 40.Toy Example (cont'd)Init: P = {010010, 110011, 100001}Evaluate:f(010010) = 18f(110011) = 33f(100001) = 33Generation 1Select parents: 110011, 100001Recombination: we're using one point crossover. Other methods are possible.Mutation: 111001, 100010P = {110011, 100001, 111001, 100010}Condition not met.110 011100 001110001100011Generation 2Select parents: 110011, 100010Recombination: Mutation: 010010, 101011P = {110011, 100010, 010010, 101011}f(101011) = 41 > 40. Done.110 011100 010110010100011Evolutionary Programming●Similar idea, but not restricted to 'chromosome' structure.●Solutions can have any structure; various mutations are possible based on how you define your solutions.●Recombination tends not to play a role.Evolutionary Strategy●Uses vector of reals rather than bit string.●Mutation: add a random value to each element of the vector.●Recombination: take the mean of each element of the parent vector:[1.0, 2.0, 3.0], [2.0, 1.0, 4.0] [1.5, 1.5, 3.5]Genetic Programming●Solutions are actual programs, usually represented as parse trees.●Recombination consists of programs exchanging subtrees.●Mutation is generally not used.●This is awesome.Learning Classifier Systems●Population is a set of 'binary classifiers' (if-then rules about an environment).●Uses reinforcement learning: the environment gives the agent a reward for choosing a set of rules; agent aims to maximize award.Problems with EAs●Local maxima.●Highly dependent on problem formulation.●Not guaranteed to ever find a good solution (if you're really unlucky with your operators).Why bother?●Yields surprisingly good results on optimization problems.●Example: find a pretty good way to schedule jobs on a processor (minimize waiting time).●Scheduling problems tend to be NP-hard; cannot calculate exact solution.●EAs can also be used to find numbers close to 42.A Brief History of EAs●Nils Aall Barricelli used EAs in 1954 to play a card game.●The father of modern GAs is Prof. John Holland, at the University of Michigan.●Prof. David Goldberg in the GE department worked with Prof. Holland, and now runs the Illinois Genetic Algorithms Laboratory (IlliGAL).References/Further Reading●Goldberg, David. Genetic Algorithms in Search, Optimization, and Machine Learning.●comp.ai.genetic newsgroup.●Wikipedia.●Some website I found off