Genetic AlgorithmsWhat is Evolutionary Computation?The ArgumentEvolutionary ComputingNatural SelectionWhen changes occur ...Genetic Change in IndividualsGenetic Change in IndividualsRecombination (Crossover)The Nature of Computational ProblemsWhy Evolution Proves to be a Good Model for Solving these Types of ProblemsThe MetaphorSlide 13Encoding the ProblemBasic Genetic AlgorithmFitness FunctionSample Search SpaceGenetic OperatorsProduction of New ChromosomesGenerationsThe Evolutionary CycleUltimate GoalDynamic EvolutionBasic Evolution StrategyEncodingFitness FunctionsForming the Next GenerationMutationDiscrete RecombinationIntermediate RecombinationExample: Find the max value of f(x1, …, x100).Evolution Processp,cSlide 34p+cTuning a GADomains of ApplicationLocal Beam SearchStochastic Beam SearchGA vs. Local Beam SearchGA vs. Stochastic Beam SearchGA suitable for Rugged TerrainDrawbacks of GAWhy use a GA?When NOT to use a GA?TaxonomyGenetic Algorithms22c: 145, Chapter 4.3What is Evolutionary Computation?An abstraction from the theory of biological evolution that is used to create optimization procedures or methodologies, usually implemented on computers, that are used to solve problems.The ArgumentEvolution has optimized biological processes;thereforeAdoption of the evolutionary paradigm to computation and other problems can help us find optimal solutions.Evolutionary ComputingGenetic Algorithmsinvented by John Holland (University of Michigan) in the 1960’sEvolution Strategiesinvented by Ingo Rechenberg (Technical University Berlin) in the 1960’sStarted out as individual developments, but converged in the later yearsNatural SelectionLimited number of resourcesCompetition results in struggle for existenceSuccess depends on fitness --fitness of an individual: how well-adapted an individual is to their environment. This is determined by their genes (blueprints for their physical and other characteristics).Successful individuals are able to reproduce and pass on their genesWhen changes occur ...Previously “fit” (well-adapted) individuals will no longer be best-suited for their environmentSome members of the population will have genes that confer different characteristics than “the norm”. Some of these characteristics can make them more “fit” in the changing environment.Genetic Change in IndividualsMutation in genesmay be due to various sources (e.g. UV rays, chemicals, etc.)Start:1001001001001001001001Location of MutationAfter Mutation:1001000001001001001001Genetic Change in Individuals Recombination (Crossover)occurs during reproduction -- sections of genetic material exchanged between two chromosomesRecombination (Crossover)Image from http://esg-www.mit.edu:8001/bio/mg/meiosis.htmlThe Nature of Computational ProblemsRequire search through many possibilities to find a solution(e.g. search through sets of rules for one set that best predicts the ups and downs of the financial markets)Search space too big -- search won’t return within our lifetimesRequire algorithm to be adaptive or to construct original solution(e.g. interfaces that must adapt to idiosyncrasies of different users)Why Evolution Proves to be a Good Model for Solving these Types of ProblemsEvolution is a method of searching for an (almost) optimal solutionPossibilities -- all individualsBest solution -- the most “fit” or well-adapted individualEvolution is a parallel processTesting and changing of numerous species and individuals occur at the same time (or, in parallel)Evolution can be seen as a method that designs new (original) solutions to a changing environmentThe MetaphorEVOLUTIONIndividualFitnessEnvironmentPROBLEM SOLVINGCandidate SolutionQualityProblemGenetic AlgorithmsClosely follows a biological approach to problem solvingA simulated population of randomly selected individuals is generated then allowed to evolveEncoding the ProblemExample: Looking for a new site which is closest to several nearby cities. Express the problem in terms of a bit stringz = (1001010101011100)where the first 8 bits of the string represent the X-coordinate and the second 8 bits represent the Y-coordinateBasic Genetic AlgorithmStep 1. Generate a random population of n chromosomesStep 2. Assign a fitness value to each individualStep 3. Repeat until n children have been producedChoose 2 parents based on fitness proportional selectionApply genetic operators to copies of the parentsProduce new chromosomesFitness FunctionFor each individual in the population, evaluate its relative fitnessFor a problem with m parameters, the fitness can be plotted in an m+1 dimensional spaceSample Search SpaceA randomly generated population of individuals will be randomly distributed throughout the search spaceImage from http://www2.informatik.uni-erlangen.de/~jacob/Evolvica/Java/MultiModalSearch/rats.017/Surface.gifGenetic OperatorsCross-overMutationProduction of New Chromosomes2 parents give rise to 2 childrenGenerationsAs each new generation of n individuals is generated, they replace their parent generationTo achieve the desired results, typically 500 to 5000 generations are requiredThe Evolutionary CycleRecombinationMutationPopulationOffspringParentsSelectionReplacementUltimate GoalEach subsequent generation will evolve toward the global maximumAfter sufficient generations a near optimal solution will be present in the population of chromosomesDynamic EvolutionGenetic algorithms can adapt to a dynamically changing search spaceSeek out the moving maximum via a parasitic fitness functionas the chromosomes adapt to the search space, so does the fitness functionBasic Evolution Strategy1. Generate some random individuals2. Select the p best individuals based on some selection algorithm (fitness function)3. Use these p individuals to generate c children4. Go to step 2, until the desired result is achieved (i.e. little difference between generations)EncodingIndividuals are encoded as vectors of real numbers (object parameters)op = (o1, o2, o3, … , om)The strategy parameters control the mutation of the object parameterssp = (s1, s2, s3, … , sm)These two parameters constitute the individual’s chromosomeFitness FunctionsNeed a method for determining if one solution is more optimal than anotherMathematical formulaMain difference from genetic algorithms is
View Full Document