遗传算法入门

《遗传算法入门》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、遗传算法入门遗传算法遗传算法（GeneticAlgorithm,GA）是近几年发展起来的一种崭新的全局优化算法。1962年霍兰德(Holland)教授首次提出了GA算法的思想，它借用了仿真生物遗传学和自然选择机理，通过自然选择、遗传、变异等作用机制，实现各个个体的适应性的提高。从某种程度上说遗传算法是对生物进化过程进行的数学方式仿真。这一点体现了自然界中"物竞天择、适者生存"进化过程。与自然界相似，遗传算法对求解问题的本身一无所知，它所需要的仅是对算法所产生的每个染色体进行评价,把问题的解表示成染色体，并

2、基于适应值来选择染色体，使适应性好的染色体有更多的繁殖机会。在算法中也即是以二进制编码的串。并且，在执行遗传算法之前，给出一群染色体，也即是假设解。然后，把这些假设解置于问题的“环境”中，也即一个适应度函数中来评价。并按适者生存的原则，从中选择出较适应环境的染色体进行复制,淘汰低适应度的个体，再通过交叉，变异过程产生更适应环境的新一代染色体群。对这个新种群进行下一轮进化，至到最适合环境的值。遗传算法已用于求解带有应用前景的一些问题，例如遗传程序设计、函数优化、排序问题、人工神经网络、分类系统、计算机图像处

3、理和机器人运动规划等。术语说明由于遗传算法是由进化论和遗传学机理而产生的搜索算法，所以在这个算法中会用到很多生物遗传学知识，下面是我们将会用来的一些术语说明：一、染色体(Chronmosome)染色体又可以叫做基因型个体(individuals),一定数量的个体组成了群体(population),群体中个体的数量叫做群体大小。二、基因(Gene)基因是串中的元素，基因用于表示个体的特征。例如有一个串S＝1011，则其中的1，0，1，1这4个元素分别称为基因。它们的值称为等位基因(Alletes)。三、基因

4、地点(Locus)基因地点在算法中表示一个基因在串中的位置称为基因位置(GenePosition)，有时也简称基因位。基因位置由串的左向右计算，例如在串S＝1101中，0的基因位置是3。四、基因特征值(GeneFeature)在用串表示整数时，基因的特征值与二进制数的权一致；例如在串S=1011中，基因位置3中的1，它的基因特征值为2；基因位置1中的1，它的基因特征值为8。五、适应度(Fitness)各个个体对环境的适应程度叫做适应度(fitness)。为了体现染色体的适应能力，引入了对问题中的每一个染色

5、体都能进行度量的函数，叫适应度函数.这个函数是计算个体在群体中被使用的概率。操作算法霍兰德(Holland)教授最初提出的算法也叫简单遗传算法，简单遗传算法的遗传操作主要有三种：选择(selection)、交叉(crossover)、变异(mutation)这也是遗传算法中最常用的三种算法：1．选择(selection)选择操作也叫复制操作，从群体中按个体的适应度函数值选择出较适应环境的个体。一般地说，选择将使适应度高的个体繁殖下一代的数目较多，而适应度较小的个体，繁殖下一代的数目较少,甚至被淘汰。最通常

6、的实现方法是轮盘赌(roulettewheel)模型。令Σfi表示群体的适应度值之总和，fi表示种群中第i个染色体的适应度值，它被选择的概率正好为其适应度值所占份额fi／Σfi。如下图表中的数据适应值总和Σfi=6650,适应度为2200变选择的可能为fi／Σfi=2200/6650=0.394.图1.轮盘赌模型 Fitness值：220018001200950400100选择概率：33310.2710.180.1430.060.015　2．交叉(Crossover)交叉算子将被选中的两个个体的基因链按一

7、定概率pc进行交叉，从而生成两个新的个体，交叉位置pc是随机的。其中Pc是一个系统参数。根据问题的不同，交叉又为了单点交叉算子（SinglePointCrossover）、双点交叉算子（TwoPointCrossover）、均匀交叉算子(UniformCrossover)，在此我们只讨论单点交叉的情况。单点交叉操作的简单方式是将被选择出的两个个体S1和S2作为父母个体，将两者的部分基因码值进行交换。假设如下两个8位的个体：S110001111S211101100产生一个在1到7之间的随机数c，假如现在产生

8、的是2，将S1和S2的低二位交换：S1的高六位与S2的低六位组成数串10001100，这就是S1和S2的一个后代P1个体；S2的高六位与S1的低二位组成数串11101111，这就是S1和S2的一个后代P2个体。其交换过程如下图所示：Crossover11110000Crossover11110000S110001111S211101100P110001100P2111011113．变异(Mutation)这是在选中的个体中，将