搜索
10遗传算法GeneticAlgorithm（GA）达尔文(Darwin)的进化论进化论是生物学最基本的理论之一。是指生物在变异、遗传与自然选择作用下的演变发展，物种淘汰和物种产生过程。达尔文用自然选择来解释生物进化。自然选择就是指生物由于环境中某些因素的影响而使得有利于一些个体的生存，而不利于另外一些个体生存的演化过程。简而言之——物竞天择，适者生存遗传算法就是对进化论一种宏观意义下的模拟.模拟达尔文“优胜劣汰、适者生存”的原理激励好的结构模拟孟德尔遗传变异理论在迭代过程中保持已有结构，同时寻找更好的结构遗传算法（GA）是进化计算的一个分支，是一种模拟自然界生物进化过程的随机搜索算法。借鉴生物界自然选择原理和自然遗传机制而形成的一种迭代式自适应概率性全局优化搜索算法。它最早由美国密歇根大学教授JohnH.Holland提出，现在已经广泛应用于各种工程领域的优化问题之中。达尔文的自然选择学说遗传（heredity）：子代和父代具有相同或相似的性状，保证物种的稳定性；变异（variation）：子代与父代，子代不同个体之间总有差异，是生命多样性的根源；生存斗争和适者生存：具有适应性变异的个体被保留，不具适应性变异的个体被淘汰。自然选择过程是长期的、缓慢的、连续的过程。1遗传算法简介1.1生物进化理论和遗传学的基本知识孟德尔(Mendel)的遗传学遗传学是研究基因及它们在生物遗传中的作用的科学分支。由他的统计分析中，孟德尔定义了一个概念：遗传的基本单位——等位基因。他描述的等位基因类似于现在的基因。父代染色体1父代染色体2子代染色体1子代染色体2遗传基因重组过程1遗传算法简介遗传学基本概念与术语染色体（chromosome）：携带基因信息的数据结构，简称个体，二进制位串或整数数组。基因（gene）：染色体中的字符。基因座（locus）：遗传基因在染色体中所占据的位置；等位基因（allele）：同一基因座可能有的全部基因；个体（individual）：指染色体带有特征的实体；种群（population）：个体的集合；种群规模（populationsize）:种群内个体的个数。1遗传算法简介基因型（genotype）：遗传因子组合的模型；表现型（phenotype）：由染色体决定性状的外部表现；适应度（fitness）：度量某个物种对于生存环境的适应程度。对生存环境适应程度较高的物种将获得更多的繁殖机会，而对生存环境适应程度较低的物种，其繁殖机会就会相对较少，甚至逐渐灭绝;选择（selection）：以一定的概率从种群中选择若干个体的操作；复制（reproduction）：细胞在分裂时，遗传物质DNA通过复制而转移到新产生的细胞中，新的细胞就继承了旧细胞的基因;交叉（crossover）：在两个染色体的某一相同位置处基因分别交叉组合形成两个新的染色体；变异（mutation）：在细胞进行复制时可能以很小的概率产生某些复制差错，从而使DNA发生某种变异，产生出新的染色体，这些新的染色体表现出新的性状;1遗传算法简介编码（coding）：表现型到基因型的映射；解码（decoding）：从基因型到表现型的映射。1遗传算法简介基因型：1000101110110101000111表现型：0.637197个体（染色体）基因解码编码遗传算法与自然进化的比较自然界染色体基因等位基因(allele)染色体位置(locus)基因型(genotype)表现型(phenotype)遗传算法字符串字符，特征特征值字符串位置结构参数集，译码结构1遗传算法简介进化过程的三种运算选择：根据适应度，按照一定的规则或方法，从第t代群体p(t)中选择优良的个体遗传到下一代群体p(t+1)中。交叉：将群体p(t)内各个个体随机搭配成对，对每个个体中交换一部分染色体。变异：对群体p(t)中的每个个体改变某个或一些值为其他个体的值。1遗传算法简介选择运算群体p(t)交叉运算变异运算解码群体p(t+1)解集合个体评价遗传空间解空间生物遗传概念遗传算法中的作用适者生存个体(individual)染色体(chromosome)基因(gene)适应性(fitness)群体(population)交叉(crossover)变异(mutation)种群(reproduction)根据适应函数值选定的一组解解解的编码(字符串，向量等)解中每一分量特征(编码单元)适应函数值搜索空间中选定的一组有效解算法停止，最优值被留住交换部分基因产生一组新解的过程编码的某一分量发生变化1遗传算法简介产生早在50年代，一些生物学家开始研究运用数字计算机模拟生物的自然遗传与自然进化过程；1963年，德国柏林技术大学的I.Rechenberg和H.P.Schwefel，做风洞实验时，产生了进化策略的初步思想；60年代，L.J.Fogel在设计有限态自动机时提出进化规划思想。1966年Fogel等出版《基于模拟进化的人工智能》，系统阐述了进化规划的思想。1.2遗传算法的产生与发展1遗传算法简介产生60年代中期，美国Michigan大学的J.H.Holland教授提出借鉴生物自然遗传的基本原理用于自然和人工系统的自适应行为研究和串编码技术；1967年，他的学生J.D.Bagley在博士论文中首次提出“遗传算法(GeneticAlgorithms)”一词；1975年，Holland出版了著名的“AdaptationinNaturalandArtificialSystems”，标志遗传算法的诞生。1遗传算法简介发展70年代初，Holland提出了“模式定理”（SchemaTheorem），一般认为是“遗传算法的基本定理”，从而奠定了遗传算法研究的理论基础；1985年，在美国召开了第一届遗传算法国际会议，并且成立了国际遗传算法学会(ISGA，InternationalSocietyofGeneticAlgorithms)；发展1989年，Holland的学生D.J.Goldherg出版了“GeneticAlgorithmsinSearch,Optimization,andMachineLearning（遗传算法——搜索、优化及机器学习）”，对遗传算法及其应用作了全面而系统的论述。—该书系统总结了遗传算法的主要研究成果，全面完整地论述了遗传算法的基本原理及应用。1遗传算法简介1.2遗传算法的产生与发展发展1991年，L.Davis编辑出版了《HandbookofGeneticAlgorithms（遗传算法手册）》，书中介绍了遗传算法在科学计算、工程技术和社会经济等领域中大量的应用实例，该书为推广和普及遗传算法的应用起到了重要的指导作用。1遗传算法简介1.2遗传算法的产生与发展发展1992年，J.R.Koza《GeneticProgramming》将遗传算法应用于计算机程序的优化设计及自动生成，提出了遗传编程的概念。Koza成功地将提出的遗传编程方法应用于人工智能、机器学习、符号处理等方面。1遗传算法简介1.2遗传算法的产生与发展优化问题的解被视为个体，它表示为一个参数列表，叫做染色体或者基因串。染色体一般被表达为简单的字符串或数字串。一开始，算法随机生成一定数量的个体，有时操作者也可以对这个随机产生过程进行干预，播下已经部分优化的种子。在每一代中，每一个个体都被评价，并通过适应度函数计算并返回一个适应度数值。1.3遗传算法的算法机理1遗传算法简介下一步是产生下一代个体并组成群落。这个过程是通过选择和繁殖完成的，其中繁殖包括交叉和变异。选择是根据新个体的适应度数值进行的，适应度越高，选择的机会越多，而适应度低的，被选择的机会就低。通过这样的过程，初始的数据可以达到一个优化的群体。1遗传算法简介之后，被选择的个体进入杂交过程。一般的遗传算法都有一个杂交率的参数，范围一般是0.6~1，这个杂交率反映两个被选中的个体进行杂交的概率。例如，杂交率为0.8，则80%的“夫妻”会生育后代。每两个个体通过杂交产生两个新个体，代替原来的“老”个体，而不杂交的个体则保持不变。杂交父母的染色体相互交错，从而产生两个新的染色体，第一个个体前半段是父亲的染色体，后半段是母亲的，第二个个体则正好相反。不过这里的半段不是真正的一半，这个位置叫做杂交点，也是随机产生的，可以是染色体的任意位置。1遗传算法简介再下一步是变异，通过变异产生新的“子”个体。一般遗传算法都有一个固定的变异常数，通常是0.01或者更小，这代表变异发生的概率。根据这个概率，新个体的染色体随机的变异，通常就是改变染色体的一个字节（0变到1，或者1变到0）。1遗传算法简介经过这一系列的过程（选择、杂交和变异），产生的新一代个体不同于初始的一代，并一代一代向增加整体适应度的方向发展，因为最好的个体总是更多的被选择去产生下一代，而适应度低的个体逐渐被淘汰掉。这样的过程不断的重复：每个个体被评价，计算出适应度，两个个体杂交，然后变异，产生第三代。周而复始，直到终止条件满足为止。1遗传算法简介终止条件有以下几种：进化次数限制；计算耗费的资源限制（例如计算时间、计算占用的内存等）；一个个体已经满足最小值的条件，即最小值已经找到；适应度已经达到饱和，继续进化不会造成适应度更好的个体；人为干预；以及以上两种或更多种的组合。1遗传算法简介Step1随机产生一组初始个体构成初始种群,并评价每一个个体的适配值(fitnessvalue);Step2判断算法收敛准则是否满足。若满足则输出搜索结果；否则执行以下步骤;Step3根据适配值大小以一定方式进行选择操作;Step6返回Step2.Step4按交叉概率执行交叉操作;cpStep5按变异概率执行变异操作;mp1.4遗传算法的主要步骤1遗传算法简介遗传算法流程图和伪代码初始化群体选择交配变异适应值评价，保存最优染色体重新评价适应值，更新最优染色体满足终止条件/*P(t)表示某一代的群体，t为当前进化代数Best表示目前已找到的最优解*/ProcedureGAbegint←0;initialize(P(t));//初始化群体evaluate(P(t));//适应值评价keep_best(P(t));//保存最优染色体while(不满足终止条件)dobeginP(t)←selection(P(t));//选择算子P(t)←crossover(P(t));//交配算子P(t)←mutation(P(t));//变异算子t←t+1;P(t)←P(t-1);evaluate(P(t));if(P(t)的最优适应值大于Best的适应值)//以P(t)的最优染色体替代Bestreplace(Best);endifendend是否开始结束1遗传算法简介编码：固定长度的二进制符号串初始种群的产生：若干初始解组成的初始群体适值度函数的设定：区分群中个体好坏的标准遗传算子：选择运算；交叉运算；变异运算终止条件：进化结束的条件。如最大进化代数或最优解所需满足的精度。运行参数：群体规模、交叉概率、变异概率1.5遗传算法的基本要素1遗传算法简介标准遗传算法(SimpleGeneticAlgorithms,简称SGA)是一种统一的最基本的遗传算法，它只使用选择、交叉、变异这三种基本遗传算子，其遗传进化操作过程简单，容易理解，是其他一些遗传算法的雏形和基础，它不仅给各种遗传算法提供了一个基本框架，同时也具有一定的应用价值。又叫基本遗传算法或简单遗传算法。1.6标准遗传算法（SGA）1遗传算法简介构成要素①染色体编码方法。标准遗传算法使用固定长度的二进制符号串来表示群体中的个体，其等位基因是由二值符号集{0，1}所组成的。初始群体中各个个体的基因值可用均匀分布的随机数来生成。1遗传算法简介②个体适应度评价。标准遗传算法按与个体适应度成正比的概率来决定当前群体中每个个体遗传到下一代群体中的机会多少。为正确计算这个概率，这里要求所有个体的适应