Transcript 오토메타형식언어
1. Genetic Algorithms: An Overview Objectives - Studying basic principle of GA Understanding applications in prisoner’s dilemma & sorting network Outline Brief history of EC Appeal of evolution Biological terminology Search space and fitness landscape Elements of GA Simple GA GA and traditional search methods Some applications of GAs Two brief examples How do GAs work? GA: An Overview EAs can be regarded as population-based, stochastic generate- and-test algorithms Two issues How to generate offspring? How to test (select) them? EAs represent a whole family of algorithms, with different representation, search operators, etc EC covers at least four major areas EC is closely related to AI, CS, Operations Research, Machine Learning, Engineering, etc Brief History Rechenberg (1965, 1973): evolution strategies Schwefel (1975, 1977) Fogel, Owens & Walsh (1966): evolutionary programming John Holland: GA chromosomes natural selection genes & allele (0 or 1) crossover/recombination with haploid schema Appeal of Evolution Searching through a huge number of possibilities for solutions computational protein engineering, financial market A computer program to be adaptive bottom-up paradigm: emergence of intelligence Designing innovative solutions to complex problems immune systems Rules of evolution is simple species evolve by means of random variation, followed by natural selection where the fittest tend to survive and reproduce Biological Terminology chromosomes (strings of DNA): blueprint for the organism a gene encodes a trait (eye color, …) alleles: possible settings for a trait (blue, brown, …) genome: multiple chromosomes in a cell genotype: particular set of genes phenotype: its physical & mental characteristics diploid vs haploid Search Spaces & Fitness Landscapes search space some collection of candidate solutions to a problem and some notion of distance between candidate solutions fitness landscape a representation of the space of all possible genotypes along with their fitnesses hill, peak, valley Elements of GAs Fitness function GA operators selection crossover mutation Simple GA: Generate-and-Test Loop Generate a candidate solution Test the candidate solution Until a satisfactory solution is found or no more candidate solutions can be found Generator Candidate Solutions … Tester GA and Traditional Search Methods Search for stored data Search for paths to goals Search for solutions Some Applications of GAs Optimization Automatic programming Machine learning Economics Immune systems Ecology Population genetics Evolution and learning Social systems Homework #1 Investigate on encoding, operators and results of EC methods to solve prisoner’s dilemma problem. Investigate on encoding, operators and results of EC methods to solve sorting network problem. Iterated Prisoner’s Dilemma (1) Non-zero sum, non-cooperative games The 2 player version Player B Player A C D 3 5 C 3 0 1 D 5 0 1 The purpose here is not to find the optimal solution for some simplified conditions, but to study how to find it Fitness evaluation Entirely determined by the total payoff obtained through playing against each other The initial population was generated at random Iterated Prisoner’s Dilemma (2) Representation of strategies Own History History Table Recent Action ∙∙∙ Opponent’s History Last Action Recent Action ∙∙∙ Last Action 2N History 0 1 0 ∙∙∙ 1 l = 2 : Example History 11 01 Iterated Prisoner’s Dilemma (3) Test strategies Strategy Characteristics Tit-For-Tat Initially cooperate, and then follow opponent Trigger Initially cooperate. Once opponent defects, continuously defect AllD Always defect CDCD Cooperate and defect over and over CCD Cooperate and cooperate and defect Random Random move Example Strategies 0 0 1 0 1 1 0 0 CDCD 0 1 0 1 0 1 0 1 Trigger 0 0 0 1 1 1 1 1 CCD 0 0 1 0 0 1 0 0 AllD 1 1 1 1 1 1 1 1 Random 1 1 0 1 0 0 1 1 Tit-for-Tat Sorting Networks (1) A sorting algorithm in essence, but can be represented graphically for the ease of understanding Used widely in switching circuits, routing algorithms, and other areas in interconnection networks Two issues Number of comparators Number of layers Best known networks with 16 inputs Year 1962 1964 1969 1969 Designers Bose, Nelson Batcher, Knuth Shapiro Green # comparators 65 63 62 60 still the best known today Sorting Networks (2) Comparators unsorted input sorted output small large Graphical representation of a sorting network input element unsorted input a layer sorted output How do GAs Work? (1) Traditional assumption GA works by discovering, emphasizing, and recombining good “building blocks” of solutions in a highly parallel fashion Schemas = building blocks A set of bit strings that can be described by a template made up of ones, zeros, and asterisks (don’t cares) Instance of H: strings fit the template H Order: defined bits (non-asterisks) in a H Defining length: distance between its outermost defined bits How does GA process schemas? A bit string of length l = an instance of 2^l different schemas No. of schema instances in a population of n strings 2^l ~ n*2^l How do GAs Work? (2) Schema Theorem P. 29: equation (1.2) lower bound in destructive effects of crossover and mutation Desription: Growth of a schema from one generation to the next Implication: Short, low-order schemas whose average fitness remains above the mean will receive exponentially increasing numbers of samples over time Reason: no. of samples of those schemas that are not disrupted and remain above average in fitness increases by a factor of U/F at each generation