遗传算法.pptx

遗传算法Page2遗传算法概述遗传算法生物学背景遗传算法基本运算流程遗传算法MATLAB应用实现1234目录生物的进化[Evolution]过程主要是通过染色体之间的交叉和变异来完成的。基于对自然界中生物遗传与进化机理的模仿,针对不同的问题,很多学者设计了许多不同的编码方法来表示问题的可行解,开发出了许多种不同的编码方式来模仿不同环境下的生物遗传特性,这样,由不同的编码[Coding]方法和不同的遗传算子就构成了各种不同的遗传算法。Page3遗传算法概述1类似于自然进化,遗传算法通过作用于染色体上的基因,寻找好的染色体来求解问题。与自然界相似,遗传算法对待求解问题本身一无所知,它所需要的仅是对算法所产生的每个染色体进行评价,并基于适应度值来改变染色体,使适应度好的染色体比适应度差的染色体有更多的繁殖机会。这个过程导致种群中个体的进化,得到的新个体比原个体更能适应环境,就像自然界改造一样。Page4遗传算法概述1遗传算法(icAlgorithms,简称GA)根据适者生存,优胜劣汰等自然进化规则来进行搜索计算和问题求解。对许多用传统数学难以解决或明显失效的复杂问题,特别是优化问题,GA提供了一个行之有效的新途径。遗传算法的发展历史1962年,Fraser提出了自然遗传算法。1965年,Holland首次提出了人工遗传操作的重要性。1967年,Bagley首次提出了遗传算法这一术语。1970年,hio把遗传算法应用于模式识别中。1971年,Hollstien在论文《计算机控制系统中人工遗传自适应方法》中阐述了遗传算法用于数字反馈控制的方法。1975年,《自然系统和人工系统的适配》;DeJong完成了重要论文《遗传自适应系统的行为分析》。20世纪80年代以后,遗传算法进入兴盛发展时期。遗传算法的应用生物进化的基本过程:适者生存:最适合自然环境的群体往往产生了更大的后代群体。染色体(chromosome):生物的遗传物质的主要载体。基因(gene):控制生物性状的遗传物质的功能单元和结构单位。复数个基因组成染色体。基因座(locus):染色体中基因的位置。等位基因(alleles):基因所取的值。基因和基因座决定了染色体的特征,也决定了生物个体的性质状态。遗传算法生物学背景2Page8染色体有两种相应的表示模式:基因型、表现型。表现型是生物个体所表现出来的性质状态;基因型是指与表现型密切相关的基因组成。表现型是基因型和环境条件相互作用的结果。在遗传算法中,染色体对应的是数据或数组,在标准的遗传算法中,通常由一维的串结构数据表现的,串上各个位置对应上述的基因座,而各个位置上所取的值对应上述的等位基因。遗传算法生物学背景2X1被编码为10位,x2被编码为15位(位数的多少能够反映精确度水平或个体决策变量的范围)Page9执行遗传算法时包含两个必要的数据转换操作:(一个是表现型到基因型的转换,它把搜索空间中的参数或解转换成遗传空间中的染色体或个体,此过程成为编码操作)遗传算法处理的是染色体或者叫基因型个体。一定数量的个体组成了群体,也叫集团。群体中个体的数目成为群体的大小,也叫群体规模。各个个体对环境的适应程度叫适应度。在决策变量域中的染色体表现型已被编码,可以估算种群的个体成员的特性或适应度。在再生(复制)期间,每个个体均被计算适应度值,由目标函数给出。这个值用来在选择中偏向更加适合的个体。相对整个种群,适应度高的个体具有高的选中参加交配的概率。遗传算法生物学背景2一旦个体计算了适应度值,个体能根据他们的相对适应度值从种群中被选中并重组,产生下一代。Page10自然遗传算法人工遗传算法个体(Individual)解适者生存目标值比较大的解被选择的可能性大适应性(Fitness)适应函数值群体(Population)根据适应函数值选定的一组解(解的个数为群体的规模)复制(Reproduction)根据适应函数值选取的一组解交配(Crossover)通过交配原则产生一组新解的过程变异(Mutation)编码的某一分量发生变化的过程遗传学和遗传算法中基本用语对照表