遗传算法-1.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,遗传算法,Genetic Algorithm,GA,遗传算法是什么？,遗传算法,（,Genetic Algorithm,，,GA,）,是进化计算的一个分支，,是一种模拟自然界生物进化过程的随机搜索算法。,遗传算法的思想来源是怎样的？,它由谁提出的？,GA,思想源于,自然界“自然选择”和“优胜劣汰”的进化规律，,通过模拟生物进化中的自然选择和交配变异寻找问题的全局最优解。,它最早由美国密歇根大学教授,John H.Holland,提出，,现在已经广泛应用于各种工程领域的优化问题之中。,简介,遗传算法,借鉴生物界,自然选择原理,和,自然遗传机制,而形成的一种迭代式自适应概率性全局优化搜索算法。,它模拟自然界中生物进化的发展规律，在人工系统中实现待定目标的优化。,基本特点,简单易懂、通用、鲁棒性强、适合并行处理，可用于解决各种复杂优化问题,鼻祖,美国 密歇根,(Michigan)大学,John Holland教授,一 遗传算法的基本流程,二 模式定理和隐含并行性,四 遗传算法关键参数和操作设计,五 遗传算法的改进及其并行性,六 算法的实现及应用,三 收敛性分析,目录,引言,在人类历史上，学习和模拟的例子不胜枚举：,模拟飞禽，人类可以翱游太空；,模拟游鱼，人类可以横渡海洋；,模拟昆虫，人类可以纵观千里模拟大脑，人类创造影响世界发展的计算机；,第一节 GA的基本流程,遗传算法,就是一种更为宏观意义下的模拟，它模仿的机制是一切生命和智能的产生与进化过程,.,模拟,达尔文,“优胜劣汰、适者生存”的原理激励好的结构,模拟,孟德尔,遗传变异理论在迭代过程中保持已有结构，同时寻找更好的结构,70,年代初期由美国,Michigan,大学的,Holland,教授发展起来的。,1975,年,Holland,的专著,Adaptation in natural and Artificial systems,出版为标志。,遗传算法,达尔文进化论,现代遗传学,生物模拟技术,一、,算法提出依据,达尔文(Darwin),的,进化论,英国自然学家，进化论的奠基人。,青年时期在爱丁堡大学和剑桥大学学习，特别喜爱博物学。大学毕业时,22岁，以博物学者的身份登上英国海军舰艇贝格尔号(HMS Beagles)，进行了5年（1831年1836年）探险航行。,他观察了距厄瓜多尔西岸950km的加拉帕戈斯群岛上的海龟和地雀。,1859年，达尔文出版了,物种起源,这一划时代的著作。这一著作终结了神创论关于上帝创造人类的统治地位，使生物学开始成为科学，对人类的思想解放有巨大的意义。,达尔文(Darwin),的进化论,进化论是生物学最基本的理论之一。生物学上的所谓,进化,或者演化（,Evolution），旧称“天演”，,是指生物在变异、遗传与自然选择作用下的演变发展，物种淘汰和物种产生过程,。地球上原来无生命，大约在30多亿年前，在一定的条件下，形成了原始生命，其后，生物不断的进化，直至今天世界上存在着170多万个物种。,达尔文用,自然选择,来解释生物进化。自然选择就是,指生物由于环境中某些因素的影响而使得有利于一些个体的生存，而不利于另外一些个体生存的演化过程,。,简而言之,物竞天择，适者生存,达尔文的自然选择说,遗传（heredity）,：子代和父代具有相,同或相似的性状，保证物种的稳定性；,变异（variation）,：子代与父代，子代不同个体之间总有差异，是生命多样性的根源；,生存斗争和适者生存,：具有适应性变异的个体被保留，不具适应性变异的个体被淘汰。,自然选择过程是长期的、缓慢的、连续的过程。,1 遗传算法简介,1.1 生物进化理论和遗传学的基本知识,孟德尔(Mendel)的,遗传学,1822年7月22日孟德尔生于奥地利的海因岑多夫（今捷克的海恩塞斯）。他于1840年毕业于特罗保的预科学校，进入奥尔米茨哲学院学习。1843年因家贫而辍学，同年10月到奥古斯丁修道院做,修道士,。1847年被任命为,神父,。1849年受委派到茨纳伊姆中学任希腊文和数学,代课教师,。1851年1853年在维也纳大学学习物理、化学、数学、动物学和植物学。1853年，他从维也纳大学毕业回修道院。1854年被委派到布吕恩技术学校任物理学和植物学的,代理教师,。并在那里工作了14年。1884年1月6日卒于布吕恩(今捷克的布尔诺),。,科学遗传学的奠基人,代表作,1865植物杂交试验,孟德尔(Mendel),的遗传学,遗传学,是研究基因及它们在生物遗传中的作用的科学分支,。遗传学最早的应用在有历史记载之初就已经出现了，即驯养动物及植物的选择育种。遗传信息以化学方法被编码在,DNA（脱氧核糖核酸）中。,1865年，孟德尔首先记录了豌豆某些特性的遗传模式，表明它们遵守简单的统计学规律。由他的统计分析中，孟德尔定义了一个概念：,遗传的基本单位,等位基因,。他描述的等位基因类于现在的基因。直到孟德尔死后，20世纪初另外的科学家重新发现这个定律之后，孟德尔的工作的重要性才被大家了解。,改变一个生物的DNA从而达到某种目的被称为,基因工程,。,遗传学时间表,1859年 查尔斯达尔文发表了,物种起源,1865年 格雷戈尔孟德尔发表文章,植物杂交试验,1903年 发现染色体是,遗传单位,1905年 英国科学家威廉贝特森在给亚当塞奇威克的一封信中提出了“,遗传学,”这个名词。,1927年 基因的物理变化叫做,基因突变,1931年 交叉互换导致了,基因重组,1944年 奥斯瓦德西奥多艾弗里，科林麦克劳德和麦克林麦克卡提分离出,遗传物质DNA,（那时叫做遗传要素）,1953年 詹姆斯沃森和弗朗西斯克里克提出了,DNA的双螺旋结构,1958年 Meselson-Stahl试验证明,DNA是半保留复制,的,1961年 提出三联体,遗传密码,1977年,DNA测序,2001年,人类基因组序列草图,由人类基因组计划和赛雷拉基因公司同时完成,群体,竞争,淘汰的群 体,变异,子群,种群,婚配,生物遗传学基础,生物进化过程,遗传基因重组过程,1 遗传算法简介,遗传学基本概念与术语,染色体（chromosome）,：遗传物质的载体；,脱氧核糖核酸（DNA）,：大分子有机聚合物，双螺旋结构；,遗传因子（gene）,：DNA或RNA长链结构中占有一定位置的基本遗传单位；,1.1 生物进化理论和遗传学的基本知识,遗传算法中常用术语,基因（遗传因子）,：染色体的一个片段，通常为单个参数的编码值。,染色体（基因串）,：携带基因信息的数据结构，简称个体，二进制位串或整数数组。,1 遗传算法简介,1.1 生物进化理论和遗传学的基本知识,1 遗传算法简介,遗传学基本概念与术语,基因型（genotype）,：遗传因子组合的模型，染色体的内部表现；,表现型（phenotype）,：由染色体决定性状的外部表现，基因型形成的个体；,1.1 生物进化理论和遗传学的基本知识,1 1 1 1 1 1 1,1 1 1 0 1 1 1,遗传学基本概念与术语,基因座（locus）,：遗传基因在染色体中所占据的位置，同一基因座可能有的全部基因称为等位基因（allele）；,个体（individual）,：指染色体带有特征的实体；,种群（population）,：个体的集合，该集合内个体数称为种群的大小；,种群大小,：种群中个体的数量，也叫群体规模。,1 遗传算法简介,1.1 生物进化理论和遗传学的基本知识,遗传学基本概念与术语,进化（evolution）,：生物在其延续生存的过程中，逐渐适应其生存环境，使得其品质不断得到改良，这种生命现象称为进化；,适应度（fitness）,：个体性能的数量值，度量某个物种对于生存环境的适应程度。对生存环境适应程度较高的物种将获得更多的繁殖机会，而对生存环境适应程度较低的物种，其繁殖机会就会相对较少，甚至逐渐灭绝;,1 遗传算法简介,1.1 生物进化理论和遗传学的基本知识,遗传学基本概念与术语,选择（selection）,：指决定以一定的概率从种群中选择若干个体的操作；,复制（reproduction）,：细胞在分裂时，遗传物质DNA通过复制而转移到新产生的细胞中，新的细胞就继承了旧细胞的基因;,交叉（crossover）,：在两个染色体的某一相同位置处DNA被切断，其前后两串分别交叉组合形成两个新的染色体。又称基因重组，俗称“杂交”;,1 遗传算法简介,1.1 生物进化理论和遗传学的基本知识,遗传学基本概念与术语,变异（mutation）,：在细胞进行复制时可能以很小的概率产生某些复制差错从而使DNA发生某种变异，产生出新的染色体，这些新的染色体表现出新的性状;,编码（coding）,：表现型到基因型的映射；,解码（decoding）,：从基因型到表现型的映射。,1 遗传算法简介,1.1 生物进化理论和遗传学的基本知识,进化论与遗传学的融合,19301947年，达尔文进化论与遗传学走向融合，Th.Dobzhansky1937年发表的遗传学与物种起源是融合进化论与遗传学的代表作。,生物进化与智能学的关系,生物物种作为复杂系统，具有奇妙的自适应、自组织和自优化能力，这是一种生物在进化过程中体现的智能，也是人工系统梦寐以求的功能。,1 遗传算法简介,1.1 生物进化理论和遗传学的基本知识,如何借鉴？,对于一个优化问题，一定数量的候选解（生命个体）被表示为抽象的数字串（染色体），通过进化向更好的解发展。,选解一般为二进制数字串（即,0和1），但也可能有其他表示。一开始，生命个体完全随机产生，之后一代一代的进化，在进化过程中的每一代，每一个个体的适应程度被评价，通过自然选择和变异产生新的生命群体，该群体就是下一代的个体。,遗传算法与自然进化的比较,自然界,染色体,基因,等位基因,(allele),染色体位置,(locus),基因型,(genotype),表现型,(phenotype),遗传算法,字符串,字符，特征,特征值,字符串位置,结构,参数集，译码结构,进化过程的三种运算,选择,：根据适应度，按照一定的规则或方法，从第,t,代群体,p(,t,),中选择优良的个体遗传到下一代群体,p(,t,+1),中。,交叉,：将群体,p(,t,),内各个个体随机搭配成对，对每个个体中交换一部分染色体。,变异,：对群体,p(,t,),中的每个个体改变某个或一些值是其他个体的值。,选择运算,群体,p(,t,),交叉运算,变异运算,解 码,群体,p(,t,+1),解集合,个体评价,遗传空间,解 空 间,生物遗传概念,遗传算法中的作用,适者生存,个体,(individual),染色体,(chromosome),基因,(gene),适应性,(fitness),群体,(population),交叉,(crossover),变异,(mutation),种群,(reproduction),根据适应函数值选定的一组解,解,解的编码,(,字符串，向量等,),解中每一分量特征(编码单元),适应函数值,搜索空间中选定的一组有效解,算法停止，最优值被留住,交换部分基因,产生一组新解的过程,编码的某一分量发生变化,例,1,用遗传算法求解优化问题,其中 为整数。,产生群体,:,适应函数,交叉,变异,的第一个基因发生变异,二、算法发展回顾,遗传算法,最开始是产生于Holland教授和他的同事对cellular automata的研究过程中,。在二十世纪八十年代中期之前，对于遗传算法的研究还仅限于理论方面，直到在伊里诺斯大学召开了第一届世界遗传算法大会。随着计算机计算能力的发展和实际应用需求的增多，遗传算法逐渐进入实际应用阶段。,1989年，纽约时报作者约翰马克夫写了一篇文章描述第一个商业用途的遗传算法-进化者(Evolver）。,之后，越来越多种类的遗传算法出现并被用于许多领域中，财富杂志500强企业中大多数都用它进行时间表安排、数据分析、未来趋势预测、预算等很多其他优化问题。,1 遗传算法简介,产生,早在,50年代,，一些生物学家开始研究运用数字计算机模拟生物的自然遗传与自然进化过程；,1963年,，德国柏林技术大学的I.Rechenberg和H.P.Schwefel，做风洞实验时，产生了,进化策略,的初步思想；,60年代，L.J.Fogel在设计有限态自动机时提出,进化规划,思想。,1966年,Fogel等出版基于模拟进化的人工智能，系统阐述了进化规划的思想。,1.2 遗传算法的产生与发展,人工进化系统,早在20世纪50年代和60年代，就有计算机科学家进行了“,人工进化系统,”的研究。,这些研究大多都是以,用计算机来模拟生物系统,为主，从生物的角度进行进化模拟、遗传模拟等方面的研究工作。,形成了遗传算法的雏形,1 遗传算法简介,产生,60年代中期，美国Michigan大学的J.H.Holland教授提出借鉴生物自然遗传的基本原理用于自然,和人工系统的自适应行为研究和串编码技术；,1967年，他的学生J.D.Bagley在博士论文中首次提出“遗传算法(Genetic Algorithms)”一词；,1975年,，Holland出版了著名的“Adaptation in Natural and Artificial Systems”，标志,遗传算法的诞生,。,1.2 遗传算法的产生与发展,1 遗传算法简介,发展,70年代初，Holland提出了“模式定理”（Schema Theorem），一般认为是“遗传算法的基本定理”，从而奠定了遗传算法研究的理论基础；,1985年，在美国召开了第一届遗传算法国际会议，并且成立了国际遗传算法学会(ISGA，International Society of Genetic Algorithms)；,1.2 遗传算法的产生与发展,J.H.Holland 20世纪60年代,认识到了,生物的遗传和自然进化现象,与,人工自适应系统,的相似关系，,运用生物遗传和进化的思想来研究自然和人工自适应系统的生成以及它们与环境的关系，,提出在研究和设计人工自适应系统时，可以借鉴生物遗传机制，以群体的方法进行自适应搜索，,充分认识到了交叉、变异等,运算策略,在自适应系统中的重要性。,20世纪70年代，Holland提出了遗传算法的基本定理-,模式定理,(Schema Theorem)，奠定了遗传算法的理论基础。,20世纪80年代，Holland实现了第一个基于遗传算法的机器学习系统-,分类器系统,，开创了基于遗传算法学习的新概念，为分类器系统构造出了一个完整的框架。,1975年，Holland出版了第一本系统论述遗传算法和人工自适应系统的专著,自然系统和人工系统的自适应性（Adaptation in Natural and Artificial Systems）,。,J.D.Bagley,1967年，Holland的学生Bagley,在其博士论文中首次提出了“遗传算法”一词，并发表了遗传算法应用方面（在博弈中）的第一篇论文。,发展了复制、交叉、变异、显性、倒位等遗传算子，在个体编码上使用了双倍体编码方法。这些都与目前遗传算法中所使用的算子和方法类似。,意识到了在遗传算法执行的不同阶段可以使用不同的选择率，这将有利于防止遗传算法的早熟现象，从而创立了,自适应遗传算法,概念。,Holland,自然系统和人工系统的自适应性,第一次系统地论述了遗传算法的基本理论与方法，提出了遗传算法的基本定理模式定理（schema theorem），从而奠定了遗传算法的理论基础。,模式定理揭示了群体中优良个体（较好模式）的样本数将以指数规律增长，确认了结构重组遗传操作对于获得隐并行性的重要性，从理论上保证了遗传算法是一个可以寻求最优可行解的优化过程。,该书的出版标志着遗传算法得到正式承认，Holland也被视为遗传算法的创始人。,K.ADe Jong,1975年，De Jong在其博士论文中结合模式定理进行了大量的,纯数值函数优化的计算实验,，将选择、交叉、变异等遗传操作进一步完善和系统化，建立了遗传算法的,工作框架,，得到了一些重要且具有指导意义的结论。,他推荐了在大多数优化问题中都比较适用的遗传算法参数，还建立了著名的De Jong 五函数测试平台，定义了评价遗传算法性能的在线指标和离线指标。,发展,1989年，Holland的学生D.J.Goldherg出版了“Genetic Algorithms in Search,Optimization,and Machine Learning（,遗传算法搜索、优化及机器学习,对遗传算法及其应用作了全面而系统的论述。,该书系统总结了遗传算法的主要研究成果，全面完整地论述了遗传算法的基本原理及应用。,1 遗传算法简介,1.2 遗传算法的产生与发展,发展,1991年，L.Davis编辑出版了,Handbook of Genetic Algorithms（,遗传算法手册），,书中介绍了遗传算法在科学计算、工程技术和社会经济等领域中大量的应用实例，该书为推广和普及遗传算法的应用起到了重要的指导作用。,1 遗传算法简介,1.2 遗传算法的产生与发展,发展,1992年，J.R.KozaGenetic Programming将遗传算法应用于计算机程序的优化设计及自动生成，提出了遗传编程的概念。Koza成功地将提出的遗传编程方法应用于人工智能、机器学习、符号处理等方面。,1 遗传算法简介,1.2 遗传算法的产生与发展,几个名词概念,遗传算法,进化计算,计算智能,人工智能,1 遗传算法简介,1.2 遗传算法的产生与发展,几个名词概念,进化计算：,由于遗传算法、进化规划和进化策略是不同领域的研究人员分别独立提出的，在相当长的时期里相互之间没有正式沟通。直到90年代，才有所交流。,他们发现彼此的基本思想具有惊人的相似之处，于是提出将这类方法统称为“进化计算”(Evolutionary Computation)。,1 遗传算法简介,1.2 遗传算法的产生与发展,几个名词概念,计算智能：,计算智能主要包括神经计算、进化计算和模糊计算等。它们分别从不同的角度模拟人类的智能活动，以使计算机具有智能。,通常将基于符号处理的传统人工智能称为符号智能，以区别于正在兴起的计算智能。,符号智能的特点是以,知识,为基础，偏重于,逻辑推理,，而计算智能则是以,数据,为基础，偏重于,数值计算,。,1 遗传算法简介,1.2 遗传算法的产生与发展,三、算法机理,优化问题的,解,被视为,个体,，它表示为一个参数列表，叫做染色体或者基因串。染色体一般被表达为简单的,字符串或数字串,。,一开始，算法,随机生成一定数量的个体,，有时操作者也可以对这个随机产生过程进行,干预,，播下已经部分优化的种子。在每一代中，每一个个体都被,评价,，并通过适应度函数计算并返回一个,适应度数值,。,下一步是,产生下一代个体,并组成群落。这个过程是通过,选择,和繁殖完成的，其中繁殖包括,杂交,和,突变,。,选择,是根据新个体的,适应度数值,进行的，适应度越高，选择的机会越多，而适应度低的，被选择的机会就低。通过这样的过程，初始的数据可以达到一个优化的群体。,之后，被选择的个体进入,杂交,过程。一般的遗传算法都有一个,杂交率,的参数，范围一般是0.61，这个杂交率反映两个被选中的个体进行杂交的概率。,例如,，杂交率为0.8，则80%的“夫妻”会生育后代。每两个个体通过杂交产生两个新个体，代替原来的“老”个体，而不杂交的个体则保持不变。,杂交父母的染色体相互交错，从而产生两个新的染色体,，第一个个体前半段是父亲的染色体，后半段是母亲的，第二个个体则正好相反。不过这里的半段不是真正的一半，这个位置叫做,杂交点,，也是,随机产生,的，可以是染色体的任意位置。,再下一步是,变异,，通过变异产生新的“子”个体。一般遗传算法都有一个固定的变异常数，通常是0.01或者更小，这代表变异发生的概率。根据这个概率，新个体的染色体,随机的变异,，通常就是改变染色体的一个字节（0变到1，或者1变到0）。,经过这一系列的过程（选择、杂交和变异），产生的新一代个体不同于初始的一代，并,一代一代向增加整体适应度的方向发展因为最好的个体总是更多的被选择去产生下一代，而适应度低的个体逐渐被淘汰掉。这样的过程不断的重复：,每个个体被评价，计算出适应度，两个个体杂交，然后变异，产生第三代,。周而复始，直到,终止条件,满足为止。,终止条件有以下几种：,进化次数限制；,计算耗费的资源限制（例如计算时间、计算占用的内存等）；,一个个体已经满足最小值的条件，即最小值已经找到；,适应度已经达到饱和，继续进化不会造成适应度更好的个体；,人为干预；,以及以上两种或更多种的组合。,Step1,随机产生一组初始个体构成初始种群,并评价每一个个体的适配值,(fitness value);,Step2,判断算法收敛准则是否满足。若满足则输出搜索结果；否则执行以下步骤,;,Step3,根据适配值大小以一定方式进行复制操作,;,Step6,返回,Step2,.,四、标准遗传算法的主要步骤,Step4,按交叉概率 执行交叉操作,;,Step5,按变异概率 执行变异操作,;,算法基本流程,开始,随机产生初始种群并,计算各个体的适配值,算法收敛准则满足否？,输出搜索结果,Y,执行复制操作,交叉概率,满足否,?,执行交叉操作,变异概率,满足否？,执行变异操作,Y,Y,N,N,N,遗传算法流程图和伪代码,遗传算法基本要素,编码,：固定长度的二进制符号串,初始种群的产生,：若干初始解组成的初始群体,适值度函数的设定,：区分群中个体好坏的标准,遗传算子,：选择运算；交叉运算；变异运算,终止条件,：进化结束的条件。如最大进化代,数或最优解所需满足的精度。,运行参数,：群体规模、交叉概率、变异概率,五、SGA结构,标准遗传算法,(Simple Genetic Algorithms,简称SGA),是一种统一的最基本的遗传算法，它只使用,选择、交叉、变异,这三种基本遗传算子，其遗传进化操作过程简单，容易理解，是其他一些遗传算法的雏形和基础，它不仅给各种遗传算法提供了一个基本框架，同时也具有一定的应用价值。,又叫,基本遗传算法,或,简单遗传算法。,构成要素,染色体编码方法,。标准遗传算法使用固定长度的,二进制,符号串来表示群体中的个体，其等位基因是由二值符号集0，1所组成的。初始群体中各个个体的基因值可用均匀分布的随机数来生成。,个体适应度评价,。标准遗传算法,按与个体适应度成正比的概率,来决定当前群体中每个个体遗传到下一代群体中的机会多少。为正确计算这个概率，这里要求所有个体的,适应度必须为正数或零,。,遗传算子,。标准遗传算法使用下述三种遗传算子：,选择运算使用比例选择算子,，,交叉运算使用单点交叉算子,，,变异运算使用基本位变异算子或均匀变异算子,。,运行参数,。标准遗传算法有下述4个运行参数需要提前设定：,群体大小,M,，即群体中所含个体数目，一般取为20100；,遗传运算的终止进化代数,T,，一般取为100500；,交叉概率,P,c,，一般取为0.40.99；,变异概率,P,m,，一般取为0.00010.1。,形式化定义,算法可定义为一个8元组：,C,-,个体的编码方法；,E,-,个体适应度评价函数；,P,0,-,初始群体；,M,-,群体大小；,-,选择算子；,-,交叉算子；,-,变异算子,T,-,遗传运算终止条件。,例,1,用遗传算法求解优化问题,其中 为整数。,解:,(1)确定初始种群,参数编码,将整数,x,*,0,1,31作为参数，采用二进制进行编码：,X=0,00000，,x=31,11111,随机生成,例如:01001；11001；,01000；10011。,(2)选择,根据“适者生存”的自然选择原理,从初始种群中选择生命力强的个体(适者)产生新的种群,确定适应度函数,适应度函数取为非负函数,且适应度增大的方向对应于目标函数的优化方向,本例取适应度函数 fitness(X)=x,计算适应度和选择率,将初始种群的个体解码为X,并计算适应度f(X)及选择率f/,其中为适应度之和.,随机选择适者个体,采用,轮盘,法，对初始种群进行选择，使得最优秀的个体获得最多的生存繁殖机会。,(3),交叉,将选择出的个体存入交配池中，用随机方法配对交叉，以产生新一代的个体,随机选择配对；随机选择交叉点；,采用单点交叉，产生新的种群,(4)变异,在交叉过程中，可能丢失一些重要的遗传信息(特定位置的1与0)，因而产生变异。为了获得新的遗传信息，则需引入适度的变异。,1,是否有其他形式的候选解？,2,如何选取交叉概率、变异概率？,3,是否有适配值的其他替代形式？,4,交叉及变异点的如何选择？,5,如何利用更多的信息？,6,终止准则？,Problem,1,以优化变量的遗传编码为运算及搜索对象,;,2,非单个操作，使用群体搜索策略,;,3,使用概率搜索机制，无需其他信息,;,4,具有全局搜索能力，最善于搜索复杂问题和非线性问题。,六、遗传算法的特点,1 遗传算法简介,自组织、自适应和自学习性,在编码方案、适应度函数及遗传算子确定后，算法将利用进化过程中获得的信息自行组织搜索。,本质并行性,内在并行性与内含并行性,不需求导,只需目标函数和适应度函数,概率转换规则,强调概率转换规则，而不是确定的转换规则,1.6 遗传算法的特点,自组织、自适应和学习性（智能性）,传统的优化算法往往需要对具体问题进行实现全面了解，而遗传算法不需要事先描述问题的全部特性，可以用来解决复杂的非结构化问题，具有很强的鲁棒性。,以决策变量的编码作为运算对象,传统的优化算法往往直接利用决策变量的实际值本身进行优化计算，但遗传算法不是直接以决策变量的值，而是以决策变量的某种形式的编码为运算对象，从而可以很方便地引入和应用遗传操作算子。,遗传算法直接以目标函数值作为搜索信息,传统的优化算法往往不只需要目标函数值，还需要目标函数的导数等其它信息。这样对许多目标函数无法求导或很难求导的函数，遗传算法就比较方便。,同时进行解空间的多点搜索,传统的优化算法往往从解空间的一个初始点开始搜索，这样容易陷入局部极值点。遗传算法进行群体搜索，而且在搜索的过程中引入遗传运算，使群体又可以不断进化。这些是遗传算法所特有的一种,隐含并行性,。,使用随机搜索技术,遗传算法属于一种,自适应,随机搜索技术，其选择、交叉、变异等运算都是以一种概率的方式来进行的，从而增加了其搜索过程的灵活性。实践和理论都已证明了在一定条件下遗传算法总是以概率,1收敛于问题的最优解。,简单、通用、容易操作,遗传算法的基本思想简单，运行方式和实现步骤规范，便于具体使用。,1,、,编码不规范及编码存在表示的不准确性,;,2,、,单一的遗传编码不能全面地将优化问题的约束表示出来,;,3,、是否能保证收敛到最优解,.,七、遗传算法的不足,1,、,遗传算法适合数值求解那些有多参数、多变量、多目标、多区域的,NP-hard,问题,;,2,、,遗传算法在求解很多优化问题时，不需要有很强的技巧和对问题有非常深入的了解,;,3,、,遗传算法求解有较好的兼容性。,八、遗传算法的优越性,如何知道对某一特定问题使用遗传算法会得到优化解呢？,遗传算法的工作机理如何呢？,遗传算法如何改善其搜索能力呢？,Problem,