1、1Machine Evolution2Outline Introduction to Evolutionary Computation Biological Background Evolutionary Computation Genetic Algorithm Genetic Programming3Biological Basis Biological systems adapt themselves to a new environment by evolution. Generations of descendants are produced that perform better
2、 than do their ancestors. Biological evolution Production of descendants changed from their parents Selective survival of some of these descendants to produce more descendants4Evolutionary Computation What is the Evolutionary Computation? Stochastic search (or problem solving) techniques that mimic
3、the metaphor of natural biological evolution. Metaphor（隐喻）EVOLUTIONIndividualFitnessEnvironmentPROBLEM SOLVINGCandidate SolutionQualityProblem5Basic Concepts 个体 individual 种群 population 进化 evolution 适应度 fitness 选择 selection 复制 reproduction 交叉 crossover 变异 mutation6General Framework of ECGenerate Ini
4、tial PopulationEvaluate FitnessSelect ParentsGenerate New OffspringTermination Condition?YesNoFitness FunctionCrossover, MutationBest Individual7Geometric Analogy - Mathematical Landscape8Paradigms in EC Evolutionary Programming (EP) L. Fogel et al., 1966 FSMs, mutation only, tournament selection Ev
5、olution Strategy (ES) I. Rechenberg, 1973 Real values, mainly mutation, ranking selection Genetic Algorithm (GA) J. Holland, 1975 Bitstrings, mainly crossover, proportionate selection Genetic Programming (GP) J. Koza, 1992 Trees, mainly crossover, proportionate selection9(Simple) Genetic Algorithm (
6、1) Genetic Representation Chromosome A 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 string may encode integers, real numbers, sets, or whatever. Population GA uses a number of chromosomes at
7、 a time called a population. The population evolves over a number of generations towards a better solution.10Genetic Algorithm (2) Fitness Function The 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) The number of 1s in the chromosome Numerical functions
