资源描述
Negnevitsky,Pearson Education,20051Lecture 7Evolutionary Computation Negnevitsky,Pearson Education,20052Contents:nIntroduction,or can evolution be intelligent?nSimulation of natural evolutionnGenetic algorithmsnCase study:maintenance scheduling with genetic algorithms Negnevitsky,Pearson Education,20053遗传算法的生物学基础遗传算法的生物学基础遗传算法的生物学基础遗传算法的生物学基础生物在自然界中的生存繁衍，显示出了其对自然环境的自适应能力。受其启生物在自然界中的生存繁衍，显示出了其对自然环境的自适应能力。受其启发，发，人们致力于对生物各种生存特性的机理研究和行为模拟，为人工自适应人们致力于对生物各种生存特性的机理研究和行为模拟，为人工自适应系统的设计和开发提供了广阔的前景。系统的设计和开发提供了广阔的前景。遗传算法遗传算法(Genetic Algorithms，简称，简称GAs)就是这种生物行为的计算机模拟中就是这种生物行为的计算机模拟中令人瞩目的重要成果。基于对生物遗传和进化过程的计算机模拟，遗传算法令人瞩目的重要成果。基于对生物遗传和进化过程的计算机模拟，遗传算法使得各种人工系统具有优良的自适应能力和优化能力。使得各种人工系统具有优良的自适应能力和优化能力。遗传算法所借鉴的生物学基础就是生物的遗传和进化。遗传算法所借鉴的生物学基础就是生物的遗传和进化。遗传遗传遗传遗传(Heredity)(Heredity)世间的生物从其父代继承特性或性状，这种生命现象就称为遗传世间的生物从其父代继承特性或性状，这种生命现象就称为遗传染色体染色体(Chromosome)细胞中含有的一种微小的丝状化合物，生物的所有细胞中含有的一种微小的丝状化合物，生物的所有遗遗传传传传信信息息都包含在这个复杂而又微小的染色体中。都包含在这个复杂而又微小的染色体中。基因基因(gene)(gene)遗传的基本单位。细胞通过分裂具有自我复制的能力，在细胞分裂的遗传的基本单位。细胞通过分裂具有自我复制的能力，在细胞分裂的过程中，其过程中，其遗传基因遗传基因也同时被复制到下一代，从而其性状也被下一代所继承。也同时被复制到下一代，从而其性状也被下一代所继承。Negnevitsky,Pearson Education,20054生物的遗传方式：生物的遗传方式：生物的遗传方式：生物的遗传方式：1.1.复制复制复制复制 生物的主耍遗传方式是复制。遗传过程中，父代的遗传物质生物的主耍遗传方式是复制。遗传过程中，父代的遗传物质生物的主耍遗传方式是复制。遗传过程中，父代的遗传物质生物的主耍遗传方式是复制。遗传过程中，父代的遗传物质DNADNA被复制到子被复制到子被复制到子被复制到子 代。即细胞在分裂时，遗传物质代。即细胞在分裂时，遗传物质代。即细胞在分裂时，遗传物质代。即细胞在分裂时，遗传物质DNADNA通过复制通过复制通过复制通过复制(Reproduction)(Reproduction)而转移到新生的细而转移到新生的细而转移到新生的细而转移到新生的细 胞中，新细胞就继承了旧细胞的基因。胞中，新细胞就继承了旧细胞的基因。胞中，新细胞就继承了旧细胞的基因。胞中，新细胞就继承了旧细胞的基因。2.2.交叉交叉交叉交叉 有性生殖生物在繁殖下一代时，两个同源染色体之间通过交叉有性生殖生物在繁殖下一代时，两个同源染色体之间通过交叉有性生殖生物在繁殖下一代时，两个同源染色体之间通过交叉有性生殖生物在繁殖下一代时，两个同源染色体之间通过交叉(Crossover)(Crossover)而重而重而重而重 组，亦即在两个染色体的某一相同位置处组，亦即在两个染色体的某一相同位置处组，亦即在两个染色体的某一相同位置处组，亦即在两个染色体的某一相同位置处DNADNA被切断，其前后两串分别交叉组合被切断，其前后两串分别交叉组合被切断，其前后两串分别交叉组合被切断，其前后两串分别交叉组合 而形成两个新的染色体。而形成两个新的染色体。而形成两个新的染色体。而形成两个新的染色体。3.3.变异变异变异变异 在进行细胞复制时，虽然概率很小，仅仅有可能产生某些复制差错，从而使在进行细胞复制时，虽然概率很小，仅仅有可能产生某些复制差错，从而使在进行细胞复制时，虽然概率很小，仅仅有可能产生某些复制差错，从而使在进行细胞复制时，虽然概率很小，仅仅有可能产生某些复制差错，从而使 DNADNA发生某种变异发生某种变异发生某种变异发生某种变异(Mutation)(Mutation)，产生出新的染色体。这些新的染色体表现出新的，产生出新的染色体。这些新的染色体表现出新的，产生出新的染色体。这些新的染色体表现出新的，产生出新的染色体。这些新的染色体表现出新的 性状。性状。性状。性状。如此这般，遗传基因或染色体在遗传的过程中由于各种各样的原因而发生变化。如此这般，遗传基因或染色体在遗传的过程中由于各种各样的原因而发生变化。如此这般，遗传基因或染色体在遗传的过程中由于各种各样的原因而发生变化。如此这般，遗传基因或染色体在遗传的过程中由于各种各样的原因而发生变化。Negnevitsky,Pearson Education,20055进化进化进化进化 地球上的生物，都是经过长期进化而形成的。根据达尔文的自然选择学说，地地球上的生物，都是经过长期进化而形成的。根据达尔文的自然选择学说，地 球上的生物具有很强的繁殖能力。在繁殖过程中，大多数生物通过遗传，使物种球上的生物具有很强的繁殖能力。在繁殖过程中，大多数生物通过遗传，使物种 保持相似的后代；部分生物由于变异，后代具有明显差别，甚至形成新物种。正保持相似的后代；部分生物由于变异，后代具有明显差别，甚至形成新物种。正 是由于生物的不断繁殖后代，生物数目大量增加，而自然界中生物赖以生存的资是由于生物的不断繁殖后代，生物数目大量增加，而自然界中生物赖以生存的资 源却是有限的。因此，为了生存，生物就需要竞争。生物在生存竞争中，根据对源却是有限的。因此，为了生存，生物就需要竞争。生物在生存竞争中，根据对 环境的适应能力，适者生存，不适者消亡。环境的适应能力，适者生存，不适者消亡。自然界中的生物，就是根据这种优胜自然界中的生物，就是根据这种优胜 劣汰的原则，不断地进行进化。劣汰的原则，不断地进行进化。生物的进化是以集团的形式共同进行的，这样的一个团体称为生物的进化是以集团的形式共同进行的，这样的一个团体称为群体群体(Population)，或称为种群。或称为种群。组成群体的单个生物称为组成群体的单个生物称为个体个体(Individual)，每一个个体对其生存环境都有不同的每一个个体对其生存环境都有不同的适应能力适应能力，这种适应能力称为个体的，这种适应能力称为个体的适应度适应度(Fitness)。Negnevitsky,Pearson Education,20056遗传与进化的系统观遗传与进化的系统观遗传与进化的系统观遗传与进化的系统观 虽然人们还未完全揭开遗传与进化的奥秘，即没有完全掌握其机制、也不完全虽然人们还未完全揭开遗传与进化的奥秘，即没有完全掌握其机制、也不完全 清楚染色体编码和译码过程的细节，更不完全了解其控制方式，但遗传与进化的清楚染色体编码和译码过程的细节，更不完全了解其控制方式，但遗传与进化的 以下几个特点却为人们所共识：以下几个特点却为人们所共识：(1)生物的所有遗传信息都包含在其染色体中，染色体决定了生物的性状；生物的所有遗传信息都包含在其染色体中，染色体决定了生物的性状；(2)染色体是由基因及其有规律的排列所构成的，遗传和进化过程发生在染色体上；染色体是由基因及其有规律的排列所构成的，遗传和进化过程发生在染色体上；(3)生物的繁殖过程是由其基因的复制过程来完成的；生物的繁殖过程是由其基因的复制过程来完成的；(4)通过同源染色体之间的交叉或染色体的变异会产生新的物种，使生物呈现新的通过同源染色体之间的交叉或染色体的变异会产生新的物种，使生物呈现新的 性状。性状。(5)对环境适应性好的基因或染色体经常比适应性差的基因或染色体有更多的机会对环境适应性好的基因或染色体经常比适应性差的基因或染色体有更多的机会 遗传到下一代。遗传到下一代。Negnevitsky,Pearson Education,20057生物进化理论生物进化理论.flv生物进化理论生物进化理论 Negnevitsky,Pearson Education,200587.1 Can evolution be intelligent?n nIntelligence-the capability of a system to adapt its Intelligence-the capability of a system to adapt its behaviour to ever-changing environment.behaviour to ever-changing environment.n nEvolutionary computationEvolutionary computation simulates evolution on a computer.simulates evolution on a computer.The result of such a simulation is a series of optimisation The result of such a simulation is a series of optimisation algorithms,usually based on a simple set of rules.algorithms,usually based on a simple set of rules.OptimisationOptimisation iteratively improves the quality of solutions until an optimal,or iteratively improves the quality of solutions until an optimal,or at least feasible,solution is found.at least feasible,solution is found.最优化最优化 Negnevitsky,Pearson Education,20059nEvolution is a tortuously slow process from the human Evolution is a tortuously slow process from the human perspective,but the simulation of evolution on a perspective,but the simulation of evolution on a computer does not take billions of years!computer does not take billions of years!nThe evolutionary approach to machine learning is The evolutionary approach to machine learning is based on computational models of natural selection based on computational models of natural selection and genetics.We call them and genetics.We call them evolutionary evolutionary computationcomputation genetic algorithmsgenetic algorithms evolution strategies evolution strategies genetic programminggenetic programmingCan evolution be intelligent?(con.)Negnevitsky,Pearson Education,2005107.2 Simulation of natural evolutionn nOn 1 July 1858,On 1 July 1858,Charles Darwin Charles Darwin presented his theory of presented his theory of evolution before the Linnean Society of London.This day evolution before the Linnean Society of London.This day marks the beginning of a revolution in biology.marks the beginning of a revolution in biology.n nNeo-Darwinism Neo-Darwinism Reproduction Reproduction mutationmutation competition competition selectionselection Negnevitsky,Pearson Education,200511nEvolution can be seen as a process leading to the maintenance of a populations ability to survive and reproduce in a specific environment.This ability is called evolutionary fitness.nEvolutionary fitness can also be viewed as a measure of the organisms ability to anticipate changes in its environment.nThe fitness,or the quantitative measure of the ability to predict environmental changes and respond adequately,can be considered as the quality that is optimised in natural life.Negnevitsky,Pearson Education,200512nTo illustrate fitness,we can use the concept of adaptive topology.适应性拓扑适应性拓扑是一个连续函数。是一个连续函数。它模拟的环境或自然拓扑不是静态的。它模拟的环境或自然拓扑不是静态的。随着时间推移，拓扑性状发生改变，随着时间推移，拓扑性状发生改变，所有的物种要不断地经历选择。所有的物种要不断地经历选择。进化的目标就是进化的目标就是产生适应性增加的后代产生适应性增加的后代。Negnevitsky,Pearson Education,200513How is a population with increasing fitness generated?例：兔子种群例：兔子种群例：兔子种群例：兔子种群 Negnevitsky,Pearson Education,200514Genetic Algorithms(GA)nIn the early 1970s,John Holland introduced the concept of genetic algorithms.美国密歇根大学心理系和计算机与电子工程系的教授美国密歇根大学心理系和计算机与电子工程系的教授复杂理论和非线性科学的先驱复杂理论和非线性科学的先驱遗传算法之父遗传算法之父获得美国获得美国“麦克阿瑟天才奖麦克阿瑟天才奖”John Henry Holland1929.2.2“机器可以像动物一样被训练去适应周机器可以像动物一样被训练去适应周围的环境。进化就像学习适应环境的一围的环境。进化就像学习适应环境的一种方式。进化是次代叠加的，而不是只种方式。进化是次代叠加的，而不是只发生在某一生命周期里。发生在某一生命周期里。”Negnevitsky,Pearson Education,200515n nHe viewed these algorithms as an abstract form of natural He viewed these algorithms as an abstract form of natural evolution.Hollands population of artificial chromosomes evolution.Hollands population of artificial chromosomes to a new population.It uses natural selection and genetics-to a new population.It uses natural selection and genetics-inspired techniques known as crossover and mutation.inspired techniques known as crossover and mutation.Genetic Algorithms(con.)将人造染色体的一个种群进化到另一个种群的过程。使用将人造染色体的一个种群进化到另一个种群的过程。使用“自然自然”选择机制和遗传学的交叉和突变机制。选择机制和遗传学的交叉和突变机制。nEach artificial“chromosomes”consists of a number of“genes”,and each gene is represented by 0 or 1.Fig7.1 A 16-bit binary string of an artificial chromosomeFig7.1 A 16-bit binary string of an artificial chromosome Negnevitsky,Pearson Education,200516n nNature has an ability to adapt and learn without being told Nature has an ability to adapt and learn without being told what to do.In other words,nature finds good chromosomes what to do.In other words,nature finds good chromosomes blindly.GAs do the same.Two mechanisms link a GA to the blindly.GAs do the same.Two mechanisms link a GA to the problem it is solving:problem it is solving:encoding encoding and and evaluationevaluation.n nThe GA uses a measure of fitness of individual chromosomes The GA uses a measure of fitness of individual chromosomes to carry out reproduction.As reproduction takes place,the to carry out reproduction.As reproduction takes place,the crossover operatorcrossover operator exchanges parts of two single chromosomes,exchanges parts of two single chromosomes,and the and the mutation operator mutation operator changes the gene value in changes the gene value in some randomly chosen location of the chromosome.some randomly chosen location of the chromosome.Genetic Algorithms(con.)评估函数是为要解决问题度量染色体评估函数是为要解决问题度量染色体的性能或适应性。的性能或适应性。Negnevitsky,Pearson Education,2005177.3 Basic genetic algorithmsnGenetic algorithms are a class of stochastic search algorithms based on biological evolution.Given a clearly defined problem to be solved and a binary string representation for candidate solutions.A GA applies the following major steps:Negnevitsky,Pearson Education,200518双亲染色体被选择的概率双亲染色体被选择的概率crossovermutationGA represents an iterative process.GA represents an iterative process.Each iteration is called a Each iteration is called a generationgeneration.A.A typical number of generations for a typical number of generations for a simple GA can range from 50 to over simple GA can range from 50 to over 500.The entire set500.The entire set of generations is of generations is called a called a runrun.Negnevitsky,Pearson Education,200519Are any conventional termination criteria used in genetic algorithms?nA common practice is to terminate a GA after a specified number of generations and then examine the best chromosomes in the population.If no satisfactory solution is found,the GA is restarted.nBecause GAs use a stochastic search method,the fitness of a population may remain stable for a number of generations before a superior chromosome appears.终止条件终止条件 Negnevitsky,Pearson Education,200520Suppose that the size of the chromosome population Suppose that the size of the chromosome population N N is 6,the is 6,the crossover probability crossover probability p pc c equals 0.7equals 0.7,and the,and the mutation probability mutation probability p pm m equals 0.001equals 0.001.The fitness function in our example is defined.The fitness function in our example is defined bybyf(x)=15 x x2Tab7.1 The encoding methodTab7.1 The encoding methodGenetic algorithms:case study 1Let us find the maximum value of the function(15Let us find the maximum value of the function(15x x-x x2 2)where parameter where parameter x x varies between 0 and 15.varies between 0 and 15.Negnevitsky,Pearson Education,200521Genetic algorithms:case study 1(con.)n nThe GA creates an initial population of chromosomes by filling The GA creates an initial population of chromosomes by filling six 4-bit strings with randomly generated ones and zerossix 4-bit strings with randomly generated ones and zeros.n nIn natural selection,only the fittest species can survive,breed,and In natural selection,only the fittest species can survive,breed,and thereby pass their genes on to the next generation.GAs use a similar thereby pass their genes on to the next generation.GAs use a similar approach,but unlike nature,the size of the chromosome population approach,but unlike nature,the size of the chromosome population remains unchanged from one generation to the next.remains unchanged from one generation to the next.Tab7.2 Tab7.2 Tab7.2 Tab7.2 染色体随机产生的初始种群染色体随机产生的初始种群染色体随机产生的初始种群染色体随机产生的初始种群f f(x x)=)=15 15 x x x x2 2 编号编号 染色体串染色体串 解码后整数解码后整数 适应性适应性 适应性比率适应性比率 Negnevitsky,Pearson Education,200522Roulette wheel selectionn nEach chromosome is given a slice of a circular roulette wheel.Each chromosome is given a slice of a circular roulette wheel.The area of the slice within the wheel is equal to the chromosome The area of the slice within the wheel is equal to the chromosome fitness ratio.fitness ratio.轮盘选择轮盘选择轮盘选择轮盘选择Fig9.4 Roulette wheel selectionFig9.4 Roulette wheel selection Negnevitsky,Pearson Education,200523Roulette wheel selectionnTo select a chromosome for mating,a random number is generated in the interval 0,100,and the chromosome whose segment spans the random number is selected.It is like spinning a roulette wheel where each chromosome has a segment on the wheel proportional to its fitness.nThe roulette wheel is spun,and when the arrow comes to rest on one of the segments,the corresponding chromosome is selected.Negnevitsky,Pearson Education,200524How does the crossover operator work?nIn our example,we have an initial population of 6 chromosomes.Thus,to establish the same population in the next generation,the roulette wheel would be spun six times.nOnce a pair of parent chromosomes is selected,the crossover operator is applied.Negnevitsky,Pearson Education,200525n nFirst,the crossover operator randomly chooses a crossover point First,the crossover operator randomly chooses a crossover point where two parent chromosomes “break”,and then exchanges the where two parent chromosomes “break”,and then exchanges the chromosome parts after that point.As a result,two new offspring chromosome parts after that point.As a result,two new offspring are created.are created.n nIf a pair of chromosomes does not cross over,then the If a pair of chromosomes does not cross over,then the chromosome cloning takes place,and the offspring are created chromosome cloning takes place,and the offspring are created as exact copies of each parentas exact copies of each parent.How does the crossover work(con.)Fig 7.5a CrossoverFig 7.5a Crossover随机选择交叉点，并交换染色随机选择交叉点，并交换染色随机选择交叉点，并交换染色随机选择交叉点，并交换染色体交叉点后的部分，产生两个体交叉点后的部分，产生两个体交叉点后的部分，产生两个体交叉点后的部分，产生两个新的子代染色体。新的子代染色体。新的子代染色体。新的子代染色体。平均适应性从平均适应性从平均适应性从平均适应性从3636增加到增加到增加到增加到42.42.Negnevitsky,Pearson Education,200526nMutation is a background operator.Its role is to provide a guarantee that the search algorithm is not trapped on a local optimum.The sequence of selection and crossover operations may stagnate at any homogeneous set of solutions.nMutation is equivalent to a random search,and aids us in avoiding loss of genetic diversity.What does mutation represent?Negnevitsky,Pearson Education,200527n nThe mutation operator flips a randomly selected gene in a The mutation operator flips a randomly selected gene in a chromosome.chromosome.Mutation can occur at any gene in a chromosome Mutation can occur at any gene in a chromosome with some probability.with some probability.n nThe mutation probability is quite small in nature,and is kept The mutation probability is quite small in nature,and is kept low for GAs,typically in the range between 0.001 and 0.01.low for GAs,typically in the range between 0.001 and 0.01.What does mutation operator work?随机选择染色体中的某个基因并反转其值。随机选择染色体中的某个基因并反转其值。随机选择染色体中的某个基因并反转其值。随机选择染色体中的某个基因并反转其值。Fig7.5b MutationFig7.5b Mutation Negnevitsky,Pearson Education,200528Fig7.5c The genetic algorithm cycleFig7.5c The genetic algorithm cycleGAGA循环循环循环循环第第第第i i代代代代第第第第i+1i+1代代代代 Negnevitsky,Pearson Education,200529n nGenetic algorithms assure the continuous improvement of the average Genetic algorithms assure the continuous improvement of the average fitness of the population,and after a number of generations the population fitness of the population,and after a number of generations the population evolves to a near-optimal solution.In this example,the final population evolves to a near-optimal solution.In this example,the final population would consist of only chromosomes and .would consist of only chromosomes and .What does mutation work?(con.)0 01 11 11 11 1 0 0 0 0 0 0Tab7.3 Tab7.3 Tab7.3 Tab7.3 适应性函数和染色体位置适应性函数和染色体位置适应性函数和染色体位置适应性函数和染色体位置 Negnevitsky,Pearson Education,200530Genetic algorithms:case study 2 Represent the problem variables as a chromosome Represent the problem variables as a chromosome-parameters parameters x x and and y y as a concatenated binary string:as a concatenated binary string:Choose the size of the chromosome population,for instance 6,Choose the size of the chromosome population,for instance 6,and randomly generate an initial population.and randomly generate an initial population.Calculate the fitness of each chromosome.Calculate the fitness of each chromosome.Negnevitsky,Pearson Education,200531n nThen these strings are converted from binary(base 2)to decimal Then these strings are converted from binary(base 2)to decimal(base 10):(base 10):n nFirst,a chromosome,that is a string of 16 bits,is partitioned First,a chromosome,that is a string of 16 bits,is partitioned into two 8-bit strings:into two 8-bit strings:Genetic algorithms:case study 2(con.)Negnevitsky,Pearson Education,200532n nNow the range of integers that can be handled by 8-bits,that is Now the range of integers that can be handled by 8-bits,that is the range from 0 to(2the range from 0 to(28 8 -1),is mapped to the actual range of 1),is mapped to the actual range of parameters parameters x x and and y y,that is the range from,that is the range from-3 to 3:3 to 3:n nTo obtain the actual values of To obtain the actual values of x x and and y y,we multiply their decimal,we multiply their decimal values by 0.0235294 and subtract 3 from the results:values by 0.0235294 and subtract 3 from the results:Genetic algorithms:case study 2(con.)Negnevitsky,Pearson Education,200533n nUsing decoded values of Using decoded values of x x and and y y as inputs in the mathematical as inputs in the mathematical function,the GA calculates the fitness of each chromosome.function,the GA calculates the fitness of each chromosome.Probability(crossover)equal to 0.7Probability(crossover)equal to 0.7 Probability(mutation)equal to 0.001Probability(mutation)equal to 0.001 The desired number of generations is 100.The desired number of generations is 100.Genetic algorithms:case study 2(con.)Negnevitsky,Pearson Education,200534Fig7.6a Chromosome locations on the surface of the“peak”functionFig7.6a Chromosome locations on the surface of the“peak”function初始群体初始群体第第1代代全局最优结果全局最优结果局部最优结果局部最优结果 Negnevitsky,Pearson Education,200535n nSince genetic algorithms are stochastic,their performance Since genetic algorithms are stochastic,their performance usually varies from generation to generation.usually varies from generation to generation.n nAs a result,a curve showing the As a result,a curve showing the l laverage performance of the entire population of average performance of the entire population of chromosomeschromosomes l lthe performance of the best individual in the populationthe performance of the best individual in the population What s a performance graph?is a useful way of examining the behaviour of a GA over the is a useful way of examining the behaviour of a GA over the chosen number of generations.chosen number of generations.整个染色体种群的平均性能整个染色体种群的平均性能整个染色体种群的平均性能整个染色体种群的平均性能种群中最优染色体的性能种群中最优染色体的性能种群中最优染色体的性能种群中最优染色体的性能 Negnevitsky,Pearson Education,200536F i t n e s sFig7.7b Performance graphs for 100 generations of 6 chromosomes:Fig7.7b Performance graphs for 100 generations of 6 chromosomes:global maximumglobal maximumWhat s a performance graph?(con.)F i t n e s s全局最优结果全局最优结果局部最优结果局部最优结果 Negnevitsky,Pearson Education,200537n nThe erratic behaviour of the average performance curves is due to mutation.The erratic behaviour of the average performance curves is due to mutation.Mutation may lead to significant improvement in the population fitness,but Mutation may lead to significant improvement in the population fitness,but more often decreases it.To ensure diversity and to reduce the harmful effects more often decreases it.To ensure diversity and to reduce the harmful effects of mutation,we can increase the size of the chromosome population.of mutation,we can increase the
展开阅读全文