遗传算法-1

遗传算法GeneticAlgorithmGA遗传算法是什么？遗传算法（GeneticAlgorithm，GA）是进化计算的一个分支，是一种模拟自然界生物进化过程的随机搜索算法。遗传算法的思想来源是怎样的？它由谁提出的？GA思想源于自然界“自然选择”和“优胜劣汰”的进化规律，通过模拟生物进化中的自然选择和交配变异寻找问题的全局最优解。它最早由美国密歇根大学教授JohnH.Holland提出，现在已经广泛应用于各种工程领域的优化问题之中。简介遗传算法借鉴生物界自然选择原理和自然遗传机制而形成的一种迭代式自适应概率性全局优化搜索算法。它模拟自然界中生物进化的发展规律，在人工系统中实现待定目标的优化。基本特点简单易懂、通用、鲁棒性强、适合并行处理，可用于解决各种复杂优化问题鼻祖美国密歇根(Michigan)大学JohnHolland教授一遗传算法的基本流程二模式定理和隐含并行性四遗传算法关键参数和操作设计五遗传算法的改进及其并行性六算法的实现及应用三收敛性分析目录引言在人类历史上，学习和模拟的例子不胜枚举：模拟飞禽，人类可以翱游太空；模拟游鱼，人类可以横渡海洋；模拟昆虫，人类可以纵观千里；模拟大脑，人类创造影响世界发展的计算机；……第一节GA的基本流程遗传算法就是一种更为宏观意义下的模拟，它模仿的机制是一切生命和智能的产生与进化过程.模拟达尔文“优胜劣汰、适者生存”的原理激励好的结构模拟孟德尔遗传变异理论在迭代过程中保持已有结构，同时寻找更好的结构70年代初期由美国Michigan大学的Holland教授发展起来的。1975年Holland的专著《AdaptationinnaturalandArtificialsystems》出版为标志。遗传算法达尔文进化论现代遗传学生物模拟技术一、算法提出依据达尔文(Darwin)的进化论英国自然学家，进化论的奠基人。青年时期在爱丁堡大学和剑桥大学学习，特别喜爱博物学。大学毕业时22岁，以博物学者的身份登上英国海军舰艇贝格尔号(HMSBeagles)，进行了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父代染色体2子代染色体1子代染色体2生物进化过程遗传基因重组过程1遗传算法简介遗传学基本概念与术语染色体（chromosome）：遗传物质的载体；脱氧核糖核酸（DNA）：大分子有机聚合物，双螺旋结构；遗传因子（gene）：DNA或RNA长链结构中占有一定位置的基本遗传单位；1.1生物进化理论和遗传学的基本知识遗传算法中常用术语基因（遗传因子）：染色体的一个片段，通常为单个参数的编码值。染色体（基因串）：携带基因信息的数据结构，简称个体，二进制位串或整数数组。1遗传算法简介1.1生物进化理论和遗传学的基本知识1遗传算法简介遗传学基本概念与术语基因型（genotype）：遗传因子组合的模型，染色体的内部表现；表现型（phenotype）：由染色体决定性状的外部表现，基因型形成的个体；1.1生物进化理论和遗传学的基本知识11111111110111遗传学基本概念与术语基因座（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生物进化理论和遗传学的基本知识进化论与遗传学的融合1930～1947年，达尔文进化论与遗传学走向融合，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用遗传算法求解优化问题310,)(max2xxxf其中为整数。x产生群体:)(000001x)(110012x)(011113x)(010004x适应函数2xxfxfitness)()(210)(xfitness2225)(xfitness2315)(xfitness248)(xfitnessjjiixfitnessxfitnessxp)()()(交叉)(110012x)(011113x)(010004x)(110012x)(111111y)(010012y)(110003y)(010014y变异的第一个基因发生变异)(110014y4y二、算法发展回顾遗传算法最开始是产生于Holland教授和他的同事对cellularautomata的研究过程中。在二十世纪八十年代中期之前，对于遗传算法的研究还仅限于理论方面，直到在伊里诺斯大学召开了第一届世界遗传算法大会。随着计算机计算能力的发展和实际应用需求的增多，遗传算法逐渐进入实际应用阶段。1989年，纽约时报作者约翰马克夫写了一篇文章描述第一个商业用途的遗传算法--进化者(Evolver）。之后，越来越多种类的遗传算法出现并被用于许多领域中，财富杂志500强企业中大多数都用它进行时间表安排、数据分析、未来趋势预测、预算等很多其他优化问题。1遗传算法简介产生早在50年代，一些生物学家开始研究运用数字计算机模拟生物的自然遗传与自然进化过程；1963年，德国柏