6.遗传算法-1.ppt

遗传算法;遗传算法是什么？;简介;基本特点 简单易懂、通用、鲁棒性强、适合并行处理，可用于解决各种复杂优化问题 鼻祖 美国 密歇根(Michigan)大学 John Holland教授;一 遗传算法的基本流程;引言; 遗传算法就是一种更为宏观意义下的模拟，它模仿的机制是一切生命和智能的产生与进化过程.;遗传算法 ;一、算法提出依据;达尔文 (Darwin) 的进化论 进化论是生物学最基本的理论之一。生物学上的所谓进化或者演化（Evolution），旧称“天演”，是指生物在变异、遗传与自然选择作用下的演变发展，物种淘汰和物种产生过程。地球上原来无生命，大约在30多亿年前，在一定的条件下，形成了原始生命，其后，生物不断的进化，直至今天世界上存在着170多万个物种。 达尔文用自然选择来解释生物进化。自然选择就是指生物由于环境中某些因素的影响而使得有利于一些个体的生存，而不利于另外一些个体生存的演化过程。 简而言之——物竞天择，适者生存;达尔文的自然选择说 遗传（heredity）：子代和父代具有相 同或相似的性状，保证物种的稳定性； 变异（variation）：子代与父代，子代不同个体之间总有差异，是生命多样性的根源； 生存斗争和适者生存：具有适应性变异的个体被保留，不具适应性变异的个体被淘汰。 自然选择过程是长期的、缓慢的、连续的过程。;孟德尔(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 遗传算法简介 ;遗传算法中常用术语 基因（遗传因子）：染色体的一个片段，通常为单个参数的编码值。 染色体（基因串）：携带基因信息的数据结构，简称个体，二进制位串或整数数组。; 1 遗传算法简介 ;遗传学基本概念与术语 基因座（locus）：遗传基因在染色体中所占据的位置，同一基因座可能有的全部基因称为等位基因（allele）； 个体（individual）：指染色体带有特征的实体； 种群（population）：个体的集合，该集合内个体数称为种群的大小； 种群大小：种群中个体的数量，也叫群体规模。;遗传学基本概念与术语 进化（evolution）：生物在其延续生存的过程中，逐渐适应其生存环境，使得其品质不断得到改良，这种生命现象称为进化； 适应度（fitness）：个体性能的数量值，度量某个物种对于生存环境的适应程度。对生存环境适应程度较高的物种将获得更多的繁殖机会，而对生存环境适应程度较低的物种，其繁殖机会就会相对较少，甚至逐渐灭绝;;遗传学基本概念与术语 选择（selection）：指决定