遗传算法综述.ppt

書式設定,書式設定,第 2,第 3,第 4,第 5,Soft Computing Lab.,XiDian,UNIVERSITY,*,Soft Computing Lab,.,XiDian,UNIVERSITY,書式設定,書式設定,第 2,第 3,第 4,第 5,I,nstitute,of Intelligent Information Processing,XiDian,University,Soft Computing Lab.,XiDian,UNIVERSITY,1,优化问题,对于一个求函数最大值的优化问题，一般可描述为下述数学规划模型：,Soft Computing Lab.,XiDian,UNIVERSITY,2,例：无约束单目标，多峰,Soft Computing Lab.,XiDian,UNIVERSITY,3,约束单目标,Soft Computing Lab.,XiDian,UNIVERSITY,6,TSP,A,D,E,C,B,The one below is length:33,A,B,C,D,E,A,5,7,4,15,B,5,3,4,10,C,7,3,2,7,D,4,4,2,9,E,15,10,7,9,Soft Computing Lab.,XiDian,UNIVERSITY,7,传统最优化面临新挑战,：实际问题,离散性问题主要指组合优化,不确定性问题随机性数学模型,半结构或非结构化的问题,大规模问题：超高维,动态优化问题,有噪的,现代优化方法：,追求满意近似解,实用性强解决实际问题,Soft Computing Lab.,XiDian,UNIVERSITY,8,优化问题的复杂性,Complexity:,Hard,problems and,Easy,problems,When,S,is small(e.g.10,100,or only 1,000,000 or so items),we can simply do so-called,exhaustive search,(,穷举搜索,),Exhaustive search,:Generate every possible solution,work out its fitness,and hence discover which is best(or which set share the best fitness),比如从,n,个数找到最大,This is also called,Enumeration(,列举法）,Soft Computing Lab.,XiDian,UNIVERSITY,9,问题的复杂度,This is all about characterising how hard it is to,solve,a given problem.Statements are made in terms of functions of,n,which is meant to be some indication of the size of the problem.E.g.:,（通过,n,的一个函数来描述问题的复杂度）,Correctly sort a set of,n,numbers,（排序）,Can be done in,around,n,log,n,steps,Find the closest pair out of,n,vectors,（从,n,个向量找出最接近两个,),Can be done in,O,(,n,2,),steps,Find,best,multiple alignment of,n,sequences.,Can be done in,O,(2,n,),steps,Soft Computing Lab.,XiDian,UNIVERSITY,10,Polynomial and Exponential Complexity,Given some problem,Q,with size,n,imagine that,A,is the fastest algorithm known for solving that problem exactly.The,complexity of problem,Q,is the,time it takes,A,to solve it,as a function of,n,.(,问题,Q,的维数为,n,，,A,是一个已知快速算法，复杂度就是通过,A,求解,Q,所用时间,),There are two key kinds of complexity:,Polynomial,:,the dominant term in the expression is polynomial in,n.,E.g.,n,34,n.,log.,n,sin(,n,2.2,),etc,Exponential,:,the dominant term is exponential in,n,.E.g.1.1,n,n,n+2,2,n,Soft Computing Lab.,XiDian,UNIVERSITY,11,Polynomial and Exponential Complexity,1.1,n,1.21,1.33,1.46,1.61,1.77,2.59,6.73,117,13,780,n,1.1,2.14,3.35,4.59,5.87,7.18,12.6,27.0,73.9,159,n,2,3,4,5,6,10,20,50,100,Problems with exponential complexity take too long to solve at large,n,Soft Computing Lab.,XiDian,UNIVERSITY,12,Polynomial,Complexity,:,these are called,tractable,and,easy,problems.Fast algorithms are known which provide the best solution.,Exponential Complexity,:these are called,intractable,and,hard,problems.The fastest known algorithm which,exactly,solves it is usually not significantly faster than exhaustive search.(,为所谓的,Hard,难问题,已有的快速算法与穷举算法相比较并没有明显的提高,),Soft Computing Lab.,XiDian,UNIVERSITY,13,polynomial,exponential,指数复杂度一般要比多项式复杂,要复杂,F(n),Increasing,n,Soft Computing Lab.,XiDian,UNIVERSITY,14,随机算法：爬山法,0.Initialise:Generate a random solution,c,;evaluate its fitness,f,(c).Call,c,the,current solution.,1.Mutate a copy of the current solution call the mutant,m,Evaluate fitness of,m,f(m).,2.If,f(m),is no worse,than,f,(c),then replace,c,with,m,otherwise do nothing(effectively discarding,m,).,3.If a termination condition has been reached,stop.Otherwise,go to 1.,Note.No population(well,population of 1).This is a very simple version of an EA,although it has been around for much longer.,Soft Computing Lab.,XiDian,UNIVERSITY,15,1,2,4,3,5,8,6,7,9,10,Soft Computing Lab.,XiDian,UNIVERSITY,16,易陷入局部最优,Soft Computing Lab.,XiDian,UNIVERSITY,17,1.Introduction of Genetic Algorithms,Foundations of Genetic Algorithms,1.1 Introduction of Genetic Algorithms,1.2 General Structure of Genetic Algorithms,1.3 Major Advantages,Example with Simple Genetic Algorithms,2.1 Representation,2.2 Initial Population,2.3 Evaluation,2.4 Genetic Operators,Encoding Issue,3.1 Coding Space and Solution Space,3.2 Selection,Soft Computing Lab.,XiDian,UNIVERSITY,18,1.Introduction of Genetic Algorithms,Genetic Operators,4.1 Conventional Operators,4.2 Arithmetical Operators,4.3 Direction-based Operators,4.4 Stochastic Operators,Adaptation of Genetic Algorithms,5.1 Structure Adaptation,5.2 Parameters Adaptation,Hybrid Genetic Algorithms,6.1 Adaptive Hybrid GA Approach,6.2 Parameter Control Approach of GA,6.3 Parameter Control Approach using Fuzzy Logic Controller,6.4 Design of aHGA using Conventional Heuristics and FLC,Soft Computing Lab.,XiDian,UNIVERSITY,19,1.Introduction of Genetic Algorithms,Foundations of Genetic Algorithms,1.1 Introduction of Genetic Algorithms,1.2 General Structure of Genetic Algorithms,1.3 Major Advantages,Example with Simple Genetic Algorithms,Encoding Issue,Genetic Operators,Adaptation of Genetic Algorithms,Hybrid Genetic Algorithms,Soft Computing Lab.,XiDian,UNIVERSITY,20,进化论,Simon,把复杂性定义为：当给定各部分的性质和他们的相互作用规律，却很难推演总体性质的情形，系统的复杂性不仅与相互作用各部分的数目有关，而且与其结构和功能上的差别有关,复杂系统具有进化性，而进化又使得系统变得更复杂，生物系统是复杂系统，进化的总趋势是产生越来越复杂的生物体。,Soft Computing Lab.,XiDian,UNIVERSITY,21,Lamarck,进化论,一切物种都是其他物种演变和进化而来的，而生物的演变和进化是一个,缓慢和连续的,过程。,环境的变化能够引起生物的变异，环境的变化迫使生物发生适应性的进化。,有神经系统的动物发生变异的原因，除了环境变化和杂交外，更重要是通过用进废退和获得性状遗传。,生物进化的方向从简单到复杂，从低到高。,最原始的生物起源于自然发生。生物并不起源于共同祖先。,拉马克曾以长颈鹿的进化为例，说明他的,用进废退,观点。长颈鹿的祖先预部并不长，由于干旱等原因。在低处已找不到食物，迫使它伸长脖颈去吃高处的树叶，久而久之，它的颈部就变长了。一代又一代，遗传下去，它的脖子越来越长，终于进化为现在我们所见的长颈鹿。,Soft Computing Lab.,XiDian,UNIVERSITY,22,Darwin,进化论,包括两部分：遗传,(,基因,),变异；自然选择,生物不是静止的，而是进化的。物种不断变异，旧物种消灭，新物种产生。,生物的进化是连续和逐渐，不会发生突变。,生物之间存在一定的亲缘关系，他们具有共同的祖先。,自然选择是变异的最重要的途径。生物过渡繁殖，但是它们的生存空间和食物有限，从而面临生存斗争，包括,:,种内、种间以及生物与环境的斗争。,自然选择是达尔文进化论的核心。,Soft Computing Lab.,XiDian,UNIVERSITY,23,孟德尔学说,1,、分离定律：基因作为独特的独立单位而代代相传。细胞中有成对的基本遗传单位，在杂种的生殖细胞中，一个来自雄性亲本，一个来自雌性亲本,.,2,、独立分配定律：在一对染色体上的基因对中的等位基因能够独立遗传,。,孟德尔的这两条遗传基本定律就是新遗传学的起点，孟德尔也因此被后人称为现代遗传学的奠基人。,Soft Computing Lab.,XiDian,UNIVERSITY,24,Soft Computing Lab.,XiDian,UNIVERSITY,25,比较,达尔文抛弃拉马克的获得性遗传法则，认为性状并不重要，只有,可遗传的变异,才具有明显的进化价值，变异在群体内遗传，产生进化效应。,不过达尔文过分强调物种形成的渐进方式。,如果进化是渐变的话，为什么在化石的范围里面，找不到证据；如果进化是突变的话，但是根据医学及科学的研究，突变产生的不是进化，而是退化,如突变产生癌，进化论证据缺乏。,Soft Computing Lab.,XiDian,UNIVERSITY,26,新达尔文主义,将达尔文进化论和魏斯曼选择和孟德尔,-,摩根基因相结合，成为现被广泛接受的新达尔文主义。,新达尔文注意认为，只用种群上和物种内的少量统计过程就可以充分地解释大多数生命历史，这些过程就是,繁殖、变异、竞争、选择,。繁殖是所有生命的共同特性；变异保证了任何生命系统能在正熵世界中连续繁殖自己；对于限制在有限区域中的不断膨胀的种群来说，竞争和选择是不可避免的结论。,Soft Computing Lab.,XiDian,UNIVERSITY,27,生物学中的遗传概念,在生物细胞中，控制并决定生物遗传特性的物质是脱氧核糖核酸，简称,DNA,。染色体是其载体。,DNA,是由四种碱基按一定规则排列组成的长链。四种碱基不同的排列决定了生物不同的表现性状。例如，改变,DNA,长链中的特定一段（称为基因），即可改变人体的身高。,细胞在分裂时，,DNA,通过复制而转移到新产生的细胞中，新的细胞就继承了上一代细胞的基因。,Soft Computing Lab.,XiDian,UNIVERSITY,28,生物学中的遗传概念,有性生殖生物在繁殖下一代时，两个同元染色体之间通过交叉而重组，亦即在两个染色体的某一相同位置处,DNA,被切断，其前后两串分别交叉形成两个新的染色体。,在细胞进行复制时可能以很小的概率产生某些复制差错，从而使,DNA,发生某种变异，产生新的染色体。,这些新的染色体将决定新的个体（后代）的新的性状。,Soft Computing Lab.,XiDian,UNIVERSITY,29,生物学中的遗传概念,在一个群体中，并不是所有的个体都能得到相同的繁殖机会，对生存环境适应度高的个体将获得更多的繁殖机会；对生存环境适应度较低的个体，其繁殖机会相对较少，即所谓自然选择。而生存下来的个体组成的群体，其品质不断得以改良，称为进化。,In particular,any new mutation that appears in a child,(e.g.longer neck(,脖,),longer legs,thicker skin,longer gestation(,孕,),period,bigger brain),and which,helps,it in its efforts to survive long enough to have children,will become more and more widespread in future generations.,Soft Computing Lab.,XiDian,UNIVERSITY,30,Evolution as Problem Solving,Heres a problem:,Design a material for the soles of boots that can help you walk up a smooth vertical brick wall,We havent solved this,but nature has:Geckos,（设计一种可以帮助人类爬上光滑的墙壁的鞋底材料）,生物的进化是经过无数次有利的进化积累而成的，不同的环境保留了不同的变异后代！,Soft Computing Lab.,XiDian,UNIVERSITY,31,Evolution as a Problem Solving Method,所有的生物经常面临一个共同的问题,How can I survive in this environment,？,自然界解决问题的方法就是：进化,Evolution,The basic,method,of it is trial and error,(,反复试验,).,1.Come up with a new solution by randomly changing an old one.,Does it work better than previous solutions?If yes,keep it and,throw away the old ones.Otherwise,discard it.,2.Go to 1.,Soft Computing Lab.,XiDian,UNIVERSITY,32,Lesson1:Keep a population/collection of different things on the go.,Lesson2:Select parents with a relatively,weak,bias,towards the fittest.,Its not really plain,survival of the fittest,what works is,the fitter you are,the more chance you have to reproduce,and it works best if even the least fit still have some chance.,（无偏见的选择父代，或适者生存,),Lesson3:It can sometimes help to use,recombination,of two or more,parents I.e.generate new,candidate solutions by combining,bits and pieces from different previous solutions.,通过重组将父代优良基因遗传给后代,This is genetic algorithm,什么是进化？,Soft Computing Lab.,XiDian,UNIVERSITY,33,More like selective breeding than natural evolution,Time,Soft Computing Lab.,XiDian,UNIVERSITY,34,Initial population,Soft Computing Lab.,XiDian,UNIVERSITY,35,Select,Soft Computing Lab.,XiDian,UNIVERSITY,36,Crossover,Soft Computing Lab.,XiDian,UNIVERSITY,37,Another Crossover,Soft Computing Lab.,XiDian,UNIVERSITY,38,A mutation,Soft Computing Lab.,XiDian,UNIVERSITY,39,Another Mutation,Soft Computing Lab.,XiDian,UNIVERSITY,40,Old population+children,Soft Computing Lab.,XiDian,UNIVERSITY,41,New Population:Generation 2,Soft Computing Lab.,XiDian,UNIVERSITY,42,Generation 3,Soft Computing Lab.,XiDian,UNIVERSITY,43,Generation 4,etc,Soft Computing Lab.,XiDian,UNIVERSITY,44,Soft Computing Lab.,XiDian,UNIVERSITY,45,遗传算法的基本思想,首先实现从性状到基因得映射，即编码工作，然后从代表问题可能潜在解集得一个种群开始进行进化求解。,初代种群（编码集合）产生后，按照优胜劣汰的原则，根据个体适应度大小挑选（选择）个体，进行复制、交叉、变异，产生出代表新的解集的群体，再对其进行挑选以及一系列遗传操作，如此往复，逐代演化产生出越来越好的近似解。,Soft Computing Lab.,XiDian,UNIVERSITY,46,选择：通过适应度的计算，淘汰不合理的个体。类似于,自然界的物竞天择,.,复制：编码的拷贝，类似于细胞分裂中染色体的复,制。,交叉：编码的交叉重组，类似于染色体的交叉重,组。,变异：编码按小概率扰动产生的变化，类似于基因,的突变。,这个过程将导致种群像自然进化一样，后代种群比前代更加适应环境，末代种群中得最优个体经过解码（从基因到性状的映射），可以作为问题近似最优解。,Soft Computing Lab.,XiDian,UNIVERSITY,47,遗传算法历史,遗传算法的发展历史：,1965年，,Holland,首次提出人工遗传操作的重要性，并把这些应用于自然系统和人工系统中。,1967年，,Bagley,在他的论文中首次提出了遗传算法这一术语，并讨论了遗传算法在自动博弈中的应用。,1970年，,Cavicchio,把遗传算法应用于模式识别中。第一个把遗传算法应用于函数优化的是,Hollstien。,Soft Computing Lab.,XiDian,UNIVERSITY,48,遗传算法历史,1975年是遗传算法研究的历史上十分重要的一年。这一年，,Holland,出版了他的著名专著自然系统和人工系统的适应性该书系统地阐述了遗传算法的基本理论和方法，并提出了对遗传算法的理论研究和发展极为重要的模式理论（,schemata theory），,该理论首次确认了结构重组遗传操作对于获得隐并行性的重要性。,同年，,DeJong,完成了他的重要论文遗传自适应系统的行为分析。他在该论文中所做的研究工作可看作是遗传算法发展过程中的一个里程碑，这是因为他把,Holland,的模式理论与他的计算使用结合起来。,Soft Computing Lab.,XiDian,UNIVERSITY,49,遗传算法历史,在一系列研究工作的基础上，上世纪80年代由,Goldberg,进行归纳总结，形成了遗传算法的基本框架。,Soft Computing Lab.,XiDian,UNIVERSITY,50,产生初,始种群,计算,适应度,是否满足,优化准则,最佳个体,选择,交叉,变异,编码,（性状到基因）,解码,（基因到性状）,Y,N,父 代,子,代,开始,结束,Soft Computing Lab.,XiDian,UNIVERSITY,51,1.3 Major Advantages,共轭梯度法、拟牛顿法、单纯形方法,特点：,渐进收敛,经典的优化搜索算法往往是基于梯度的,，,梯度方向提高个体性能,；,单点搜索,局部最优,Conventional Method,(point-to-point approach),initial single point,improvement,(problem-specific),termination,condition?,start,stop,Conventional Method,Yes,No,Soft Computing Lab.,XiDian,UNIVERSITY,52,遗传算法,improvement,(problem-independent),termination,condition?,start,stop,Genetic Algorithm,initial point,.,initial point,initial point,Initial population,Yes,No,遗传算法以决策变量的编码作为运算对象。传统的优化算法往往直接利用决策变量的实际值本身进行优化计算，但遗传算法不是直接以决策变量的值，而是以决策变量的某种形式的编码为运算对象，从而可以很方便地引入和应用遗传操作算子。,Soft Computing Lab.,XiDian,UNIVERSITY,53,遗传算法直接以目标函数值作为搜索信息。传统的优化算法往往不只需要目标函数值，还需要目标函数的导数等其它信息。这样对许多目标函数无法求导或很难求导的函数，遗传算法就比较方便。,遗传算法同时进行解空间的多点搜索。传统的优化算法往往从解空间的一个初始点开始搜索，这样容易陷入局部极值点。遗传算法进行群体搜索，而且在搜索的过程中引入遗传运算，使群体又可以不断进化。这些是遗传算法所特有的一种隐含并行性。,Soft Computing Lab.,XiDian,UNIVERSITY,54,遗传算法使用概率搜索技术。遗传算法属于一种自适应概率搜索技术，其选择、交叉、变异等运算都是以一种概率的方式来进行的，从而增加了其搜索过程的灵活性。实践和理论都已证明了在一定条件下遗传算法总是以概率1收敛于问题的最优解。,Random Search+Directed Search,Search space,Fitness,f,(,x,),local optimum,global optimum,local optimum,local optimum,0,x,x,1,x,2,x,4,x,5,x,3,Soft Computing Lab.,XiDian,UNIVERSITY,55,Soft Computing Lab.,XiDian,UNIVERSITY,56,1.1 Introduction of Genetic Algorithms,分支：,The best known algorithms in this class include:,Genetic Algorithms,(,GA,),developed by Dr.Holland.,Holland,J.,:,Adaptation in Natural and Artificial Systems,University of Michigan Press,Ann Arbor,MI,1975;MIT Press,Cambridge,MA,1992.,Goldberg,D.,:,Genetic Algorithms in Search,Optimization and Machine Learning,Addison-Wesley,Reading,MA,1989.,Evolution Strategies,(,ES,),developed by Dr.Rechenberg and Dr.Schwefel.,Rechenberg,I.,:,Evolution strategie:Optimierung technischer Systeme nach Prinzipien der biologischen Evolution,Frommann-Holzboog,1973.,Schwefel,H.:,Evolution and Optimum Seeking,John Wiley&Sons,1995.,Evolutionary Programming,(,EP,),developed by Dr.Fogel.,Fogel,L.A.Owens&M.Walsh,:,Artificial Intelligence through Simulated Evolution,John Wiley&Sons,1966.,Genetic Programming,(,GP,),developed by Dr.Koza.,Koza,J.R.,:,Genetic Programming,MIT Press,1992.,Koza,J.R.,:,Genetic Programming II,MIT Press,1994.,Soft Computing Lab.,XiDian,UNIVERSITY,57,1.2 General Structure of Genetic Algorithms,In general,a GA has,five basic components,as summarized by Michalewicz.,(,用遗传算法求解问题需要解决以下五个问题,),A,genetic representation,of potential solutions to the problem.,(,编码,),A way to create a population(an,initial set of potential solutions,).(,群体初始化,),An,evaluation function,rating solutions in terms of their fitness.,(,个体评价,),Genetic operators,that alter the genetic composition of offspring(,selection,crossover,mutation,etc.).,(,遗传算子,),Parameter values,that genetic algorithm uses(,population size,probabilities of applying genetic operators,etc.).,(,参数选择,).,Soft Computing Lab.,XiDian,UNIVERSITY,58,1.2 General Structure of Genetic Algorithms,Genetic Representation,and,Initialization,:,The genetic algorithm maintains a,population,P,(,t,),of,chromosomes,or,individuals,v,k,(,t,),k,=1,2,popSize,for,generation,t,.,(,保持一个规模不变群体,),Each,chromosome represents a potential,solution,to the problem at hand.,Evaluation,:,Each chromosome is,evaluated,to give some,measure of its,fitness,eval,(,v,k,),.,Genetic Operators,:,Some chromosomes undergo stochastic transformations by means of,genetic operators to form new chromosomes,i.e.,offspring,.,There are two kinds of transformation:,C,rossover,which creates new chromosomes by combining parts from two chromosomes.,M,utation,which creates,new chromosomes by making changes in a single,chromosome,.,New chromosomes,called,offspring,C,(,t,),are then evaluated.,Selection,:,A new population is formed by,selecting,the,more fit chromosomes,from the parent population and the offspring,population,.,Best solution,:,After several generations,the algorithm,converges to,the best chromosome,which hopefully represents,an optimal or suboptimal solution to the problem.,Soft Computing Lab.,XiDian,UNIVERSITY,59,1.2 General Structure of Genetic Algorithms,Initial,solutions,start,1100101010,1011101110,0011011001,1100110001,encoding,chromosome,1100101010,1011101110,110010,1110,101110,1010,00110,1,1001,00110,0,1001,crossover,mutation,1100101110,1011101010,0011001001,solutions candidates,decoding,fitness computation,evaluation,roulette wheel,selection,termination,condition?,Y,N,best solution,stop,new,population,The general structure of genetic algorithms,Gen,M.&R.Cheng:,Genetic Algorithms and Engineering Design,John Wiley,New York,1997.,offspring,offspring,t 0,P,(,t,),C,C,(,t,),C,M,(,t,),P,(,t,)+C(,t,),Soft Computing Lab.,XiDian,UNIVERSITY,60,1.2 General Structure of Genetic Algorithms,Procedure of Simple GA,procedure:,Simple GA,input:,GA paramet