04-machine-evolution

1、,Machine Evolution,Outline,Introduction to Evolutionary ComputationBiological BackgroundEvolutionary ComputationGenetic AlgorithmGenetic Programming,Biological Basis,Biological systems adapt themselves to a new envir

2、onment by evolution.Generations of descendants are produced that perform better than do their ancestors.Biological evolutionProduction of descendants changed from their parentsSelective survival of some of these desc

3、endants to produce more descendants,Evolutionary Computation,What is the Evolutionary Computation? Stochastic search (or problem solving) techniques that mimic the metaphor of natural biological evolution.Metaphor（隱喻）,

4、EVOLUTIONIndividualFitnessEnvironment,PROBLEM SOLVINGCandidate SolutionQualityProblem,,,,Basic Concepts,個體 individual種群 population進化 evolution適應(yīng)度 fitness選擇 selection復(fù)制 reproduction交叉 cross

5、over變異 mutation,General Framework of EC,Generate Initial Population,Evaluate Fitness,Select Parents,Generate New Offspring,Termination Condition?,Yes,No,Fitness Function,,Crossover, Mutation,,Best Individual,Geometri

6、c Analogy - Mathematical Landscape,,,,Paradigms in EC,Evolutionary Programming (EP)[L. Fogel et al., 1966]FSMs, mutation only, tournament selectionEvolution Strategy (ES)[I. Rechenberg, 1973]Real values, mainly mut

7、ation, ranking selectionGenetic Algorithm (GA)[J. Holland, 1975]Bitstrings, mainly crossover, proportionate selectionGenetic Programming (GP)[J. Koza, 1992]Trees, mainly crossover, proportionate selection,(Simple)

8、Genetic Algorithm (1),Genetic RepresentationChromosomeA solution of the problem to be solved is normally represented as a chromosome which is also called an individual.This is represented as a bit string.This strin

9、g may encode integers, real numbers, sets, or whatever.PopulationGA uses a number of chromosomes at a time called a population.The population evolves over a number of generations towards a better solution.,Genetic Alg

10、orithm (2),Fitness FunctionThe GA search is guided by a fitness function which returns a single numeric value indicating the fitness of a chromosome.The fitness is maximized or minimized depending on the problems.Eg)

11、The number of 1's in the chromosome Numerical functions,Genetic Algorithm (3),SelectionSelecting individuals to be parentsChromosomes with a higher fitness value will have a higher probability of contributin

12、g one or more offspring in the next generation Variation of SelectionProportional (Roulette wheel) selectionTournament selectionRanking-based selection,Genetic Algorithm (4),Genetic OperatorsCrossover (1-point)A cr

13、ossover point is selected at random and parts of the two parent chromosomes are swapped to create two offspring with a probability which is called crossover rate.This mixing of genetic material provides a very ef

14、ficient and robust search method.Several different forms of crossover such as k-points, uniform,Genetic Algorithm (5),MutationMutation changes a bit from 0 to 1 or 1 to 0 with a probability which is called mutation rat

15、e.The mutation rate is usually very small (e.g., 0.001).It may result in a random search, rather than the guided search produced by crossover.ReproductionParent(s) is (are) copied into next generation without cros

16、sover and mutation.,Example of Genetic Algorithm,Machine Programmer,Question: is it possible for a machine to develop a computer program to solve a problem?,Genetic Programming,Genetic programming uses variable-size tre

17、e-representations rather than fixed-length strings of binary values.Program tree = S-expression = LISP parse treeTree = Functions (Nonterminals) + Terminals,GP Tree: An Example,Function set: internal nodesFun

18、ctions, predicates, or actions which take one or more argumentsTerminal set: leaf nodesProgram constants, actions, or functions which take no arguments,S-expression: (+ 3 (/ (? 5 4) 7))Terminals = {3, 4, 5, 7}Functi

19、ons = {+, ?, /},Setting Up for a GP Run,The set of terminalsThe set of functionsThe fitness measureThe algorithm parameterspopulation size, maximum number of generationscrossover rate and mutation ratemaximum depth

20、 of GP trees etc.The method for designating a result and the criterion for terminating a run.,Crossover: Subtree Exchange,+,b,+,?,a,+,?,a,b,?,?,?,a,b,+,b,+,?,a,b,?,,,,,,Mutation,?,a,b,+,b,/,?,a,+,?,b,+,b,/,?,a,-,b,a,,,,

21、Example: Wall-Following Robot,Program Representation in GPFunctionsAND (x, y) = 0 if x = 0; else yOR (x, y) = 1 if x = 1; else yNOT (x) = 0 if x = 1; else 1IF (x, y, z) = y if x = 1; else zTerminalsActions: move t

22、he robot one cell to each direction {north, east, south, west}Sensory input: its value is 0 whenever the coressponding cell is free for the robot to occupy; otherwise, 1. {n, ne, e, se, s, sw, w, nw},A Wall-Fol

23、lowing Program,Evolving a Wall-Following Robot,Experimental SetupPopulation size: 5,000Fitness measure: the number of cells next to the wall that are visited during 60 stepsPerfect score (320) One Run (32) ? 10 rando

24、mly chosen starting pointsTermination condition: found perfect solutionSelection: tournament selection,Creating Next Generation500 programs (10%) are copied directly into next generation.Tournament selection7 progra

25、ms are randomly selected from the population 5,000.The most fit of these 7 programs is chosen.4,500 programs (90%) are generated by crossover.A mother and a father are each chosen by tournament selection.A randomly c

26、hosen subtree from the father replaces a randomly selected subtree from the mother.In this example, mutation was not used.,Two Parents Programs and Their Children,Result (1),Generation 0 The most fit program (Fitness

27、= 92),Result (2),Generation 2The most fit program (fitness = 117)Smaller than the best one of generation 0, but it does get stuck in the lower-right corner.,Result (3),Generation 6The most fit program (fitness = 163)

28、Following the wall perfectly but still gets stuck in the bottom-right corner.,Result (4),Generation 10The most fit program (fitness = 320)Following the wall around clockwise and moves south to the wall if it doesn’t st

29、art next to it.,Result (5),Fitness CurveFitness as a function of generation numberThe progressive (but often small) improvement from generation to generation,Applications of EC,Numerical, Combinatorial OptimizationSys

30、tem Modeling and IdentificationPlanning and ControlEngineering DesignData Mining Machine LearningArtificial Life,Advantages of EC,No presumptions w.r.t. problem spaceWidely applicableLow development & applicat

31、ion costsEasy to incorporate other methodsSolutions are interpretable (unlike NN)Can be run interactively, accommodate user proposed solutionsProvide many alternative solutions,Disadvantages of EC,No guarantee for op

32、timal solution within finite timeWeak theoretical basisMay need parameter tuningOften computationally expensive, i.e. slow,Further Information on EC,ConferencesIEEE Congress on Evolutionary Computation (CEC)Genetic

33、and Evolutionary Computation Conference (GECCO)Parallel Problem Solving from Nature (PPSN)Int. Conf. on Artificial Neural Networks and Genetic Algorithms (ICANNGA)Int. Conf. on Simulated Evolution and Learning (SEAL)