Unformatted text preview:

1Genetic Algorithms22c: 145, Chapter 4.3What is Evolutionary Computation?An abstraction from the theory of biological evolution that is used to create optimization procedures orcreate optimization procedures or methodologies, usually implemented on computers, that are used to solve problems.The ArgumentEvolution has optimized biological processes;thereforethereforeAdoption of the evolutionary paradigm to computation and other problems can help us find optimal solutions.2Evolutionary Computing Genetic Algorithms invented by John Holland (University of Michigan) in the 1960’sg) Evolution Strategies invented by Ingo Rechenberg (Technical University Berlin) in the 1960’s Started out as individual developments, but converged in the later yearsNatural Selection Limited number of resources Competition results in struggle for existenceSuccess depends on fitnessSuccess 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 environment Some 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.3Genetic Change in Individuals Mutation in genes may be due to various sources (e.g. UV rays, chemicals, etc.)y, , )Start:1001001001001001001001Location of MutationAfter Mutation:1001000001001001001001Genetic Change in Individuals  Recombination (Crossover) occurs during reproduction -- sections of genetic material exchanged between two ggchromosomesRecombination (Crossover)Image from http://esg-www.mit.edu:8001/bio/mg/meiosis.html4The Nature of Computational Problems Require 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)predicts the ups and downs of the financial markets) Search space too big -- search won’t return within our lifetimes Require 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 Problems Evolution is a method of searching for an (almost) optimal solution Possibilities -- all individuals Best solution -- the most “fit” or well-adapted individual Evolution is a parallel process Testing 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 MetaphorEVOLUTIONIndividualPROBLEM SOLVINGCandidate SolutionIndividualFitnessEnvironmentCandidate SolutionQualityProblem5Genetic Algorithms Closely follows a biological approach to problem solving A simulated population of randomly selected individuals is generated then allowed to evolveEncoding the Problem Example: Looking for a new site which is closest to several nearby cities. Express the problem in terms of a bit stringgz = (1001010101011100)where the first 8 bits of the string represent the X-coordinate and the second 8 bits represent the Y-coordinateBasic Genetic Algorithm Step 1. Generate a random population of nchromosomes Step 2. Assign a fitness value to each individualg Step 3. Repeat until nchildren have been produced Choose 2 parents based on fitness proportional selection Apply genetic operators to copies of the parents Produce new chromosomes6Fitness Function For each individual in the population, evaluate its relative fitness For a problem with mparameters, the fitness can be plotted in an m+1 dimensional spaceSample Search Space A randomly generated population of individuals will be randomly distributed throughout the search spacethroughout the search spaceImage from http://www2.informatik.uni-erlangen.de/~jacob/Evolvica/Java/MultiModalSearch/rats.017/Surface.gifGenetic Operators Cross-over Mutation7Production of New Chromosomes 2 parents give rise to 2 childrenGenerations As each new generation of nindividuals is generated, they replace their parent generation To achieve the desired results, typically 500 to 5000 generations are requiredThe Evolutionary CycleRecombinationParentsSelectionRecombinationMutationPopulationOffspringReplacement8Ultimate Goal Each subsequent generation will evolve toward the global maximum After sufficient generations a near optimal solution will be present in the population of chromosomesDynamic Evolution Genetic algorithms can adapt to a dynamically changing search space Seek out the moving maximum via a parasitic fitness function as the chromosomes adapt to the search space, so does the fitness functionBasic Evolution Strategy1. Generate some random individuals2. Select thepbest individuals based on some2. Select the pbest individuals based on some selection algorithm (fitness function)3. Use these pindividuals to generate cchildren4. Go to step 2, until the desired result is achieved (i.e. little difference between generations)9Encoding Individuals are encoded as vectors of real numbers (object parameters)op=(o1,o2,o3,,o)op (o1, o2, o3, … , om) The strategy parameters control the mutation of the object parameterssp= (s1, s2, s3, … , sm) These two parameters constitute the individual’s chromosomeFitness Functions Need a method for determining if one solution is more optimal than anotherhlfl Mathematical formula Main difference from genetic algorithms is that only the most fit individuals are allowed to reproduce (elitist selection)Forming the Next Generation Number of individuals selected to be parents (p) too many: lots of persistent bad traits too few: stagnant gene pool Total number of children produced (c) limited by computer resources more children ⇒ faster evolution10Mutation Needed to add new genes to the pool optimal solution cannot be reached if a necessary gene is not presentnecessary gene is not present bad genes filtered out by evolution Random changes to the chromosome object parameter mutation strategy parameter


View Full Document
Download Genetic Algorithms
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Genetic Algorithms and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Genetic Algorithms 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?