Genetic AlgorithmsDefinitionBiological AnalogyBiological TerminologyPseudo CodeTermination ConditionRandomizationParts of GAPopulationBinary ExampleFitness FunctionFitness Function ExamplesSelection FunctionFitness Proportional SelectionRank SelectionTournament SelectionGenetic OperatorsCrossoverMutationTSP RepresentationCode & Remove MethodCode & Remove (cont.)Partially Mapped Crossover (PMX)QuestionsReferencesGenetic AlgorithmsStephen Fulwider29 January 2008Definition•Genetic Algorithm – “a search technique … to find exact or approximate solutions to optimization and search problems.”-Wikipedia•Use of heuristics▫Smart Search▫Reduce Search Space2Biological Analogy•Gross Oversimplification•Leaves Many Details Out•Not a Perfect Analogy(Mitchell)3Biological Terminology•Chromosome•Gene•Allele•Locus•Recombination•Mutation(Mitchell)4Pseudo Code•Initialize Population•Do▫Evaluate Current Population▫Select Parents▫Apply Genetic Operators to Parents to Create Offspring▫Set Current Population Equal to be the New Offspring Population•While Termination Condition Not Satisfied (Wu)5Termination Condition•Ambiguous•Small Error•Fitness Plateau•Number of Generations6Randomization•Initial Population•Selection•Genetic Operators•Many Runs•Get Average Best Fitness / Generation•Get Average Avg. Fitness / Generation7Parts of GA•Population•Fitness Function•Selection Function•Genetic Operators•Goal of GA▫Explore Search Space▫Exploit Good Solutions8Population•Chromosomes – Candidate Solutions•Representation Techniques▫Binary▫Floating Point▫Objects9Binary Example•Standard Method•Created From Σ = {0,1}•Split Into Parameters▫3 Parameters: x, y, z▫x ≤ 7, y ≤ 3, z ≤ 63 => 3 bits, 2 bits, 6 bits_ _ _ _ _ _ _ _ _ _ _Each _ Can Be 0 or 1 – 2^11 Possibilities10Fitness Function•Returns Fitness of Individual•Problem Specific11Fitness Function Examples•OneMax Problem▫“11010111” => 6▫“1000010” => 2•TSP▫“ABCD” => 19▫“BDCA” => 1412Selection Function•Exploitation•Who Gets To Reproduce•Good Sample▫Take Good Individuals▫Don’t Prune Off All Low Fitness Individuals13Fitness Proportional Selection• •High Fitness => High Probability of Selection•Low Fitness => Low Probability of Selection•Generally Popular Method•Problems When Fitness Variance High/Low (Wu)14Rank Selection•Rank Each Individual Based on Fitness▫r(least fit individual) = 1▫r(most fit individual) = pop_size• •Eases Differences Early•Enhances Differences Later•Computationally Expensive (Wu)15Tournament Selection•Variables: t, k▫2 ≤ t ≤ pop_size, 0 ≤ k ≤ 1•Select t Individuals from Population▫With Probability k, Select Highest Fit Individual▫With Probability (1-k), Select Lowest Fit Individual•Proven to be similar to Rank Selection•But…▫Cheaper▫Parallelizable (Wu)16Genetic Operators•Exploration•Crossover•Mutation•Crossover Originally Thought Most Important▫Practice Proved Mutation Actually Key17Crossover•Standard: One-Point Crossover (1X)▫“100 01011” “10010100”▫“101 10100” “10101011”•Extendable to 2X, 3X, …, nX (n = pop_size)•Exhibits Positional Bias•Possible Isolation of Allele at Locus▫“..0……”▫“..0……”▫“..0……”▫“..0……”18Mutation•Ensures Diversity in Population•Gives Probability for Every Allele to Mutate▫“10110101” => “10010101”•Can Switch to Other Allele (Binary Case)•Can Randomly Choose Allele•Prevents Allele Isolation at Locus19TSP Representation•Imagine Encoding in Simplest Form▫“ABCDEF”•Problems Arise With Crossover▫“ABCDEF” “ABCFAE”▫“CDBFAE” “CDBDEF”•2 Options▫Modify Our Representation▫Modify Our Crossover Operator20Code & Remove Method•Standard Order Defined as “ABCDEF”•Sequences Coded Based on Removal of Letters From Standard Order▫“BDAFCE” is 231311B is 2 in ABCDEFD is 3 in ACDEFA is 1 in ACEFF is 3 in CEFC is 1 in CEE is 1 in E(Dewdney)21Code & Remove (cont.)•ith digit will never exceed (num_cities + 1 – i)▫Any Sequence Can Be Converted Into Cities•Now Crossover Works!▫“231311” “231321” = BDAFEC▫“512121” “512111” = EACBDF (Dewdney)22Partially Mapped Crossover (PMX)•Modify Crossover Operator•Pick 2 Crossover Points•Swap Bits From Middle Segment•Copy Rest, Replacing Bits Where Necessary•“984 567 132” “784 239 165”•“871 239 546” “891 567 243” (Wu)23Questions1. Compute the fitness for the tour “CBDA” from the TSP graph on page 12.2. Explain why normal crossover fails for the TSP problem on the following two individuals:“BEACD”“CDABE”3. Using the individuals from number two, use the Code & Remove method to convert both individuals to their respective codes, perform crossover on those two individuals, then convert those codes to the tours they represent in the TSP.24References•Dewdney, A.K. The (New) Turing Omnibus. New York: Henry Holt and Company, 1993.•Mitchell, Melanie. An Introduction to Genetic Algorithms. Cambridge: The MIT Press, 1998.•Wikipedia. Genetic algorithm. Last Updated: 16 January 2008. Online. Internet. Accessed: 27 January 2008. <http://en.wikipedia.org/wiki/Genetic_algorithm>.•Wu, Annie S. and Ayse S. Yilmaz. “Genetic Algorithms: Learning by Evolution.” Orlando: School of EECS, University of Central
View Full Document
Unlocking...