遗传算子构造理论-完全版

遗传算子及遗传操作理论摘要：遗传算法作为一种高效的搜索与寻求最优问题的方法，对解决现实问题有着很大的帮助。它面向结构对象进行操作，采取选取、交叉、变异等基本操作，进行问题的解决。且选取操作下有概率方式选取、贪婪选取等方式，重组分实值重组、离散重组等，变异有单点变异、离散变异等。除此外在特定的算法中还有响应的遗传操作，看上去和基本算法有些不同，但其本质未发生变化，这对于解决问题有着很大的帮助，也为寻求一个问题的最优解提供他了重要的解决方法。关键词：遗传原理、遗传算子、遗传操作、 编码方式、改进算法目录一、绪论2二、遗传算法的一些概念31、何为遗传算法2、 遗传算法的原理3、 一般遗传算法的遗传操作三、遗传操作4 1、选择-复制(selection-reproduction)2、交叉重组(CrossoverRecombinantion) 3、变异(Mutation)四、基于改进算法的遗传算子或遗传作91、分层遗传算法 2、CHC算法 3、并行遗传算法五、结语16参考文献绪论遗传算法（Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法，其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域。它是现代有关智能计算中的关键技术。 一、遗传算法的一些概念1、何为遗传算法遗传算法简称GA(Genetic Algorithm)，在本质上是一种不依赖具体问题的直接搜索方法。其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间，自适应地调整搜索方向，不需要确定的规则。其基本思想是基于Darwin进化论和Mendel的遗传学说的。Darwin进化论最重要的是适者生存原理。它认为每一物种在发展中越来越适应环境。物种每个个体的基本特征由后代所继承，但后代又会产生一些异于父代的新变化。在环境变化时，只有那些熊适应环境的个体特征方能保留下来。而Mendel遗传学说最重要的是基因遗传原理。它认为遗传以密码方式存在细胞中，并以基因形式包含在染色体内。每个基因有特殊的位置并控制某种特殊性质；所以，每个基因产生的个体对环境具有某种适应性。基因突变和基因杂交可产生更适应于环境的后代。经过存优去劣的自然淘汰，适应性高的基因结构得以保存下来。2、遗传算法的原理遗传算法GA把问题的解表示成“染色体”，在算法中也即是以二进制编码的串。并且，在执行遗传算法之前，给出一群“染色体”，也即是假设解。然后，把这些假设解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代“染色体”群。这样，一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解。在这里“染色体”（chromosome）就是问题中个体的某种字符串形式的编码表示，字符串中的字符也就称为基因（gene）。 例如： 个体 染色体 9 - 1001 （2，5，6）- 010 101 1103、一般遗传算法的遗传操作遗传操作亦称遗传算子(genetic operator)，就是关于染色体的运算。遗传算法中有三种遗传操作: 选择-复制(selection-reproduction) 交叉重组(crossoverrecombinantion，亦称交换、交配或杂交) 变异(mutation，亦称突变)二、遗传操作1、选择-复制(selection-reproduction)选择操作也叫复制操作，是建立在对个体的适应度进行评价的基础之上的，目的是为了避免基因缺失、提高全局收敛性和计算效率。意思是从群体中按个体的适应度函数值选择出较适应环境的个体。一般地说，选择将使适应度高的个体繁殖下一代的数目较多，而适应度较小的个体，繁殖下一代的数目较少,甚至被淘汰。最通常的实现方法是轮盘赌(roulette wheel)模型，既比例选择算子个体的适应度越高，被选中的概率越大。令f(xi)表示群体的适应度值之总和，f(xi)表示种群中第i个染色体的适应度值，它被选择的概率正好为其适应度值所占份额值为如下图表中的数据适应值总和fi=6650,适应度为2200变选择的可能为f(xi)f(xi)=2200/6650=0.394.图1. 轮盘赌模型Fitness 值：220018001200950400100选择概率：33310.2710.180.1430.060.015除此之外还有其他的选择方法，例如贪婪选择法、级差选择法、竞争选择法、排序选择法、随机联赛选择法等等。必须指出的是在基于适应度比例的选择下，高适应度的个体很容易大量繁殖，这使得参加交叉运算的两个个体相同的可能性很大，从而很难生成新的个体，而变异算子生成的个体即使适应度高，但由于数量小，所以被淘汰的概率仍然很大，从而导致过早收敛至局部最优解。同时，如果群体中的个体适应度相差不大，则它们后代的个体数量也会基本相同，好的个体得不到更多繁殖的机会，从而延缓了算法的速度。总之，复制算子具有“优胜”的性质。那么就要找到一种较好的方法来保存适应度较好的个体，下面来介绍一种方式。最优保存策略最优保存策略进化模型可进行优胜劣汰操作，既当前群体中适应度最高的个体不参与交叉运算和变异运算，而是用它来替换掉本带群体中经过交叉、变异等操作后产生的适应度较低的个体。其操作过程如下：1、 找出当前群体中适应度最小的个体和适应度最高的个体。2、 若当前群体中最佳个体的适应度比总的迄今为止的最好个体的适应度还要高，则以当前群体中的最佳个体作为新的迄今为止的最好个体。3、 用迄今位置最好个体替换掉当前群体中的最差个体。最优保存策略可视为选择操作的一部分，它是算法收敛性的一个重要保证条件，对产生较优的搜索结果起着至关作用。2、交叉重组(CrossoverRecombinantion)重组是结合来自父代基因信息而生成的，而交叉是将被选中的两个个体的基因链按一定概率pc进行交叉，从而生成两个新的个体，交叉位置pc（Pc是一个系统参数）是随机的。根据问题的不同，实值重组分为离散重组（discrete recombinantion）、中间重组（intermediate recombinantion）等，交叉可分为单点交叉算子（Single Point Crossover）、双点交叉算子（Two Point Crossover）、均匀交叉算子 (Uniform Crossover)、洗牌交叉（Shuffle Crossover）等在此我们只讨论中间重组和单点交叉的情况。 中间重组只适合于实变量，而非二进制变量，见下图2示 父个体1 12 25 5父个体2 123 4 34的样本为 ：样本1 0.5 1.1 -0.1样本2 0.1 0.8 0.5计算出的新个体为：子个体1 67.5 1.9 2.1子个体2 23.1 8.2 19.5下图3为中间重组后子个体的可能位置变量1 可能的子个体 父个体 变量2 单点交叉操作的简单方式是将被选择出的两个个体S1和S2作为父母个体，将两者的部分基因码值进行交换。假设如下两个8位的个体： S1 1000 1111 S2 1110 1100 产生一个在1到7之间的随机数c，假如现在产生的是2，将S1和S2的低二位交换：S1的高六位与S2的低六位组成数串，这就是S1和S2 的一个后代P1个体；S2的高六位与S1的低二位组成数串，这就是S1和S2的一个后代P2个体。其交换过程如下图所示：CrossoverCrossoverS11000 1111S21110 1100P11000 1100P21110 11113、变异(Mutation)变异算子的基本内容是对群体中的个体串的某些基因座上的基因值作变动。依据个体编码表示方法的不同，可以有以下的算法： a)实值变异 b)二进制变异 一般来说，变异算子操作的基本步骤如下： a)对群中所有个体以事先设定的编译概率判断是否进行变异 b)对进行变异的个体随机选择变异位进行变异。 对于二进制的变异其实就是在选中的个体中，将新个体的基因链的各位按概率pm进行异向转化，最简单方式是改变串上某个位置数值，将0与1互换：0变异为1，1变异为0。如下8位二进制编码：1 1 1 0 1 1 0 0随机产生一个1至8之间的数i，假如现在k=6，对从右往左的第6位进行变异操作，将原来的1变为0，得到如下串：1 1 0 0 1 1 0 0整个交叉变异过程如下图： 除了上述基本变异方法外，还有其他的变异方法，如换位、复制、插入、删除等等。三、基于改进算法的遗传算子或遗传操作 自从1975年J.H.Holland系统的提出遗传算法的完整结构和理论以来，各学者致力于遗传算法的性能改进，对编码方式、控制参数的确定、选择方式和交叉机理的进行了深入的研究，提出了不同操作的遗传算法。其基本途径概括而来有以下几个方面： 改变遗传算法的组成部分或使用技术，如选用优化控制参数、适合问题特性的编码技术等； 采用混合遗传算法； 采用动态适应技术，在进化过程中调整算法控制参数和编码粒度； 采用非标准的遗传操作算子； 采用并行遗传算法; 基于以上几种思想所产生的算法有分层遗传算法、CHC算法、messy GA算法、自适应遗传算法、混合遗传算法、并行遗传算法等等。在这里我们只简单地介绍几种算法。1、分层遗传算法对于一个问题，分层算法也像普通算法一样，首先随机生成Nn个样本，只是将样本分成N个种群各自进行自己的遗传操作，进行到一定的代数后再将N个遗传结果记录到二维数组R1,N,1,n中，则Ri,j(i=1,N;j=1n)表示GAi的结果种群的第j个个体。同时，用A1N记录N个结果种群的平均适应度，Ai表示第i个种群的平均适应度。高层遗传算法也可分为选择、交叉、变异操作。选择：基于数组A1N，即N个遗传算法的平均适应度值，对数组R代表的结果种群进行选择操作，一些结果种群会因为适应度值高而被复制至少一次；另一些则会因为适应度值低而被淘汰。交叉：如果数组A1,N和Rj,1,n被随机的匹配到一起，而且从位置x进行交叉(1i,jN;1xn-1),则Ri,x+1,n和Rj,x+1,n相互交换相应的部分。即交换GAi和GAj中结果种群的nx个个体。变异：以很小的概率将少量的随机生成的新个体替换R1,N,1,n中随机抽取的个体。至此，高层遗传算法的第一轮运行结束。从而N个遗传算法GAi可以从相应于新的R1,N,1,n中继续各自的操作，并在此基础上再运行一次后更新数组R1,N,1,n和A1N，进入第二轮高层操作。如此反复的进行，直至得到满意的结果。流程图如下：2、CHC算法 CHC算法是，同样进行选择、交叉、变异操作。只是和普通算法进行机制略有不同。选择：将上世代的种群与通过交叉发放产生的个体种群混合，从中按一定的概率选择较优的个体。这一策略称为跨世代精英选择。 交叉：CHC使用的重组操作是对均匀交叉的一种改进。改进之处为当两个父个体位值相异的位数为m时，从中选取m/2个位置，实行父个体位值的互换。显然这样的从中模式具有很强的破坏性，因此，要限定个体间的海明距离在一确定阀值内才能交叉，并该值随种群收敛而减小。变异：CHC算法在进化前期不采取变异操作，当中群进化到一定收敛时期，从优秀个体中选择一部分个体进行初始化。其方法为选择一定比例的基因座，随机决定它们的位值。这个比例值称为扩散率，一般取0.35。3、并行遗传算法一般来说，遗传算法中适应度的计算最为费时间，再加之随进化规模会扩大，所以提高运算速率很重要。由于遗传算法的并行机制，其并行处理理所当然。并行遗传算法的实现方案可分为：全局型主从模式(masterslave model)、独立型粗粒度模型(coarsegrained model)、分散型细粒度模式(finegrained model)。在这种算法中，引入了一个新的遗传算子迁移，它是指在进化过程中子群体间交换个体的过程一般迁移方法是将子群体中最好的个体发给其它的子群体，通过迁移可以加快较好个体在种群间的传播，提高收敛速度和解的精度。其特点为：更适合全局搜索，计算量较小。以基于粗粒度模型的并行算法为例，其迁移策略可分为以下两种：一传多 每个处理器对应有若干个相邻处理器，每个处理器产生新一代个体后，都将自己最好的一个个体传送给其所有相邻的处理器，并且接受来自相邻处理器的最好个体，将这些个体与自己的个体同时考虑，淘汰适应度差的个体，其程序流程图如下所示终止条件满足否？结束YN计算适应度选择进行交叉，变异将最好的个体传送给相邻的处理器接受来自相邻处理器的最好个体淘汰适应度差的个体Generation=Generation+1初始化种群Generation=0开始 一传多流程图 一传一 考虑到染色体的多样性，每个处理器都将自己最好的个体仅传给与之相邻的一个处理器同时增加两个参数：一是send_rate决定处理器之间通讯的频率，如send_rate=3时表示当遗传代数是3的倍数时，各处理器之间相互传送个体；二是send_best决定每次传送最好个体的数目，如send_best=5时表示每个处理器把最好的前五个个体传送给各自相邻的处理器。其流程图如下所示选择进行交叉、变异计算适应度Generation%Send_rate=0?终止条件满足否？结束Generation=0初始化种群开始YNNYGeneration=Generation+1接受来自相邻处理器的最好个体淘汰适应度差的个体将最好个体send_best传送给相临处理器将最好个体send_best传送给相临处理器 一般的，个体迁移的方法可以有：均匀随机挑选个体作为迁移对象、按适应度挑选个体作为迁移对象 对于种群间的个体迁移结构也有多种可能性，例如：迁移发生在所有的种群，即发生在完全的网络拓扑、迁移发生在环状拓扑、迁移发生在临集拓扑。而最一般化的是完全网络拓扑。 并行算法提高了效率，究其效果如何，人们在评价其性能过程中提出了许多不同的评价方法，其中最重要的一个评价标准是加速比。设T为某算法在串行时对的运行时间，Tp是该算法在p个处理机构成的并行机上所用时间，则加速比Sp为：Sp=T/Tp。但对于并行遗传算法，由于搜索的随机性，仅加速比不足以衡量其优劣程度。比较现实的方法是，设计一些好的几何特性的测试函数