Transcript math
Genetic Algorithms Vida Movahedi November 2006 Contents • • • • • What are Genetic Algorithms? From Biology … Evolution … To Genetic Algorithms Demo What are Genetic Algorithms? • A method of solving Optimization Problems – Exponentially large set of solutions – Easy to compute cost or value • Search algorithm (looking for the optimum) • Very similar to random search?! • Population- based – We start with a set of possible solutions (initial population) and evolve it to get to the optimum – Also called Evolutionary Algorithms • Based on evolution in biology From Biology … • Charles Darwin (1859) • Natural selection , “survival of the fittest” • Improvement of species Can we use the same idea to get an optimal solution? Evolution To implement optimization as evolution, We need • Mapping features to genes, showing each individual with a chromosome • An initial population • Have a function to measure fitness same as what we want to optimize • Implement and apply Reproduction • Replace offspring in old generation • Have an exit condition for looping over generations Initial Population • Representation of possible solutions as chromosomes – Binary – Real – etc. • Random initial population • If not random stuck in local optima Recombination (crossover) • Random crossover points • Inheriting genes from one parent Mutation • Random Mutation Point • Changing gene value to a random value … to Genetic Algorithms BEGIN /* genetic algorithm*/ Generate initial population ; Compute fitness of each individual ; LOOP Select individuals from old generations for mating ; Create offspring by applying recombination and/or mutation to the selected individuals ; Compute fitness of the new individuals ; Kill old individuals ,insert offspring in new generation ; IF Population has converged THEN exit loop; END LOOP END Simple Example Example • http://www.rennard.org/alife/english/gavgb. html References • [1] Hue, Xavier (1997), “Genetic Algorithms for Optimisation: Background and Applications”, http://www.epcc.ed.ac.uk/overview/publicat ions/training_material/tech_watch/97_tw/te chwatch-ga/ • [2] Whitely, Darell (1995), “A Genetic Algorithm Tutorial”, http://samizdat.mines.edu/ga_tutorial/ Questions?