2022年遗传算子构造理论-完全版 .pdf

《2022年遗传算子构造理论-完全版 .pdf》由会员分享，可在线阅读，更多相关《2022年遗传算子构造理论-完全版 .pdf（15页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、遗传算子及遗传操作理论摘要：遗传算法作为一种高效的搜索与寻求最优问题的方法，对解决现实问题有着很大的帮助。它面向结构对象进行操作，采取选取、交叉、变异等基本操作，进行问题的解决。 且选取操作下有概率方式选取、贪婪选取等方式， 重组分实值重组、离散重组等，变异有单点变异、离散变异等。除此外在特定的算法中还有响应的遗传操作， 看上去和基本算法有些不同， 但其本质未发生变化， 这对于解决问题有着很大的帮助，也为寻求一个问题的最优解提供他了重要的解决方法。关键词： 遗传原理、遗传算子、遗传操作、编码方式、改进算法名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - -

2、- - - - - - 名师精心整理 - - - - - - - 第 1 页，共 15 页 - - - - - - - - - 1 目录一、绪论 2 二、遗传算法的一些概念 3 1、何为遗传算法2、遗传算法的原理3、三、遗传操作 4 1、选择 -复制(selection-reproduction) 2、交叉重组 (Crossover Recombinantion) 3、变异 (Mutation)四、基于改进算法的遗传算子或遗传作 9 1、分层遗传算法2、CHC 算法3、并行遗传算法五、结语 16 参考文献名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - -

3、- - - - - - 名师精心整理 - - - - - - - 第 2 页，共 15 页 - - - - - - - - - 2 绪论遗传算法（ Genetic Algorithm）是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型， 是一种通过模拟自然进化过程搜索最优解的方法， 其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法， 能自动获取和指导优化的搜索空间， 自适应地调整搜索方向， 不需要确定的规则。 遗传算法的这些性质，已被人们广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命

4、等领域。它是现代有关智能计算中的关键技术。一、遗传算法的一些概念1、何为遗传算法名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 15 页 - - - - - - - - - 3 遗传算法简称 GA(Genetic Algorithm) ，在本质上是一种不依赖具体问题的直接搜索方法。 其主要特点是直接对结构对象进行操作，不存在求导和函数连续性的限定；具有内在的隐并行性和更好的全局寻优能力；采用概率化的寻优方法，能自动获取和指导优化的搜索空间， 自适应地调整搜索方向， 不需要

5、确定的规则。其基本思想是基于Darwin 进化论和 Mendel 的遗传学说的。Darwin 进化论最重要的是适者生存原理。它认为每一物种在发展中越来越适应环境。物种每个个体的基本特征由后代所继承，但后代又会产生一些异于父代的新变化。在环境变化时，只有那些熊适应环境的个体特征方能保留下来。而 Mendel 遗传学说最重要的是基因遗传原理。它认为遗传以密码方式存在细胞中，并以基因形式包含在染色体内。 每个基因有特殊的位置并控制某种特殊性质；所以，每个基因产生的个体对环境具有某种适应性。基因突变和基因杂交可产生更适应于环境的后代。 经过存优去劣的自然淘汰， 适应性高的基因结构得以保存下来。2、遗传

6、算法的原理遗传算法 GA 把问题的解表示成“染色体” ，在算法中也即是以二进制编码的串。并且，在执行遗传算法之前，给出一群“染色体”，也即是假设解。然后，把这些假设解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉，变异过程产生更适应环境的新一代 “染色体”群。这样，一代一代地进化， 最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解。在这里“染色体”（chromosome ）就是问题中个体的某种字符串形式的编码表示，字符串中的字符也就称为基因（gene ） 。例如：个体染色体9 - 1001 （2，5，6）- 010 101 110

7、3遗传操作亦称遗传算子 (genetic operator)，就是关于染色体的运算。遗传算法中有三种遗传操作 : 选择-复制(selection-reproduction) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 15 页 - - - - - - - - - 4 交叉重组 (crossover recombinantion，亦称交换、交配或杂交) 变异(mutation，亦称突变 ) 二、遗传操作1、选择 -复制(selection-reproduction) 选

8、择操作也叫复制操作，是建立在对个体的适应度进行评价的基础之上的，目的是为了避免基因缺失、 提高全局收敛性和计算效率。 意思是从群体中按个体的适应度函数值选择出较适应环境的个体。一般地说，选择将使适应度高的个体繁殖下一代的数目较多，而适应度较小的个体，繁殖下一代的数目较少, 甚至被淘汰。最通常的实现方法是轮盘赌(roulette wheel) 模型，既比例选择算子个体的适应度越高，被选中的概率越大。 令 f(xi)表示群体的适应度值之总和， f(xi)表示种群中第 i 个染色体的适应度值， 它被选择的概率正好为其适应度值所占份额值为如下图表中的数据适应值总和fi=6650, 适应度为 2200

9、变选择的可能为f(xi)f(xi)=2200/6650=0.394. 图 1. 轮盘赌模型Fitness 值：2200 1800 1200 950 400 100 NjjiixfxfxP1)()()(名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 15 页 - - - - - - - - - 5 选择概率：3331 0.271 0.18 0.143 0.06 0.015 除此之外还有其他的选择方法， 例如贪婪选择法、 级差选择法、竞争选择法、排序选择法、随机联赛选择法等等

10、。必须指出的是在基于适应度比例的选择下，高适应度的个体很容易大量繁殖， 这使得参加交叉运算的两个个体相同的可能性很大，从而很难生成新的个体，而变异算子生成的个体即使适应度高，但由于数量小， 所以被淘汰的概率仍然很大，从而导致过早收敛至局部最优解。 同时，如果群体中的个体适应度相差不大，则它们后代的个体数量也会基本相同，好的个体得不到更多繁殖的机会，从而延缓了算法的速度。总之，复制算子具有“优胜”的性质。那么就要找到一种较好的方法来保存适应度较好的个体，下面来介绍一种方式。最优保存策略最优保存策略进化模型可进行优胜劣汰操作，既当前群体中适应度最高的个体不参与交叉运算和变异运算， 而是用它来替换掉

11、本带群体中经过交叉、变异等操作后产生的适应度较低的个体。其操作过程如下：1、找出当前群体中适应度最小的个体和适应度最高的个体。2、若当前群体中最佳个体的适应度比总的迄今为止的最好个体的适应度还要高，则以当前群体中的最佳个体作为新的迄今为止的最好个体。3、用迄今位置最好个体替换掉当前群体中的最差个体。最优保存策略可视为选择操作的一部分，它是算法收敛性的一个重要保证条件，对产生较优的搜索结果起着至关作用。2、交叉重组 (Crossover R ecombinantion ) 重组是结合来自父代基因信息而生成的，而交叉是将被选中的两个个体的基因链按一定概率 pc 进行交叉， 从而生成两个新的个体，

12、交叉位置 pc（Pc 是一个系统参数）是随机的。根据问题的不同，实值重组分为离散重组（discrete recombinantion）、中间重组（ intermediate recombinantion）等，交叉可分为单点交叉算子（Single Point Crossover ） 、 双点交叉算子（Two Point Crossover ） 、名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 15 页 - - - - - - - - - 6 均匀交叉算子 (Uniform

13、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 位的个体：

14、名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 15 页 - - - - - - - - - 7 S1 1000 1111 S2 1110 1100 产生一个在 1 到 7 之间的随机数 c，假如现在产生的是2，将 S1和 S2的低二位交换：S1的高六位与 S2的低六位组成数串10001100， 这就是 S1和 S2 的一个后代 P1个体；S2的高六位与 S1的低二位组成数串11101111，这就是 S1和 S2的一个后代 P2个体。其交换过程如下图所示：Crossove

15、r 11110000 Crossover 11110000 S1 1000 1111 S2 1110 1100 P1 1000 1100 P2 1110 1111 3、变异 (Mutation) 变异算子的基本内容是对群体中的个体串的某些基因座上的基因值作变动。依据个体编码表示方法的不同，可以有以下的算法：a)实值变异b)二进制变异一般来说，变异算子操作的基本步骤如下：a)对群中所有个体以事先设定的编译概率判断是否进行变异b)对进行变异的个体随机选择变异位进行变异。对于二进制的变异其实就是在选中的个体中，将新个体的基因链的各位按概率 pm进行异向转化，最简单方式是改变串上某个位置数值，将0 与

16、 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 整个交叉变异过程如下图：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 15 页 - - - - - - - - - 8 除了上述基本变异方法外，还有其他的变异方法，如换位、复制、插入、删除等等。三、基于改进算法的

17、遗传算子或遗传操作自从 1975年 J.H.Holland 系统的提出遗传算法的完整结构和理论以来，各学者致力于遗传算法的性能改进，对编码方式、 控制参数的确定、 选择方式和交叉机理的进行了深入的研究， 提出了不同操作的遗传算法。 其基本途径概括而来有以下几个方面：改变遗传算法的组成部分或使用技术，如选用优化控制参数、 适合问题特性的编码技术等；采用混合遗传算法；采用动态适应技术，在进化过程中调整算法控制参数和编码粒度；采用非标准的遗传操作算子；采用并行遗传算法 ; 基于以上几种思想所产生的算法有分层遗传算法、CHC 算法、 messy GA算法、自适应遗传算法、混合遗传算法、并行遗传算法等等

18、。在这里我们只简单地介绍几种算法。1、分层遗传算法名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 15 页 - - - - - - - - - 9 对于一个问题，分层算法也像普通算法一样，首先随机生成Nn 个样本，只是将样本分成 N 个种群各自进行自己的遗传操作， 进行到一定的代数后再将N个遗传结果记录到二维数组R1,N,1,n中，则 Ri,j(i=1, N;j=1n)表示 GAi的结果种群的第 j 个个体。同时，用 A1N记录 N 个结果种群的平均适应度， Ai 表示第

19、 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 个遗传

20、算法 GAi可以从相应于新的 R1,N,1,n中继续各自的操作，并在此基础上再运行一次后更新数组 R1,N,1,n和 A1N，进入第二轮高层操作。 如此反复的进行，直至得到满意的结果。流程图如下：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 15 页 - - - - - - - - - 10 2、CHC 算法CHC 算法是，同样进行选择、交叉、变异操作。只是和普通算法进行机制略有不同。选择：将上世代的种群与通过交叉发放产生的个体种群混合，从中按一定的概率选择较优的个体

21、。这一策略称为跨世代精英选择。交叉： CHC 使用的重组操作是对均匀交叉的一种改进。改进之处为当两个父个体位值相异的位数为m 时，从中选取 m/2 个位置，实行父个体位值的互换。显然这样的从中模式具有很强的破坏性，因此，要限定个体间的海明距离在一确定阀值内才能交叉，并该值随种群收敛而减小。变异：CHC 算法在进化前期不采取变异操作，当中群进化到一定收敛时期，从优秀个体中选择一部分个体进行初始化。其方法为选择一定比例的基因座，随机决定它们的位值。这个比例值称为扩散率，一般取0.35。3、并行遗传算法一般来说，遗传算法中适应度的计算最为费时间， 再加之随进化规模会扩大，所以提高运算速率很重要。由于

22、遗传算法的并行机制，其并行处理理所当然。并行遗传算法的实现方案可分为：全局型主从模式(masterslave model)、独立型粗粒度模型 (coarse grained model)、分散型细粒度模式(finegrained model)。在这种算法中， 引入了一个新的遗传算子迁移，它是指在进化过程中子群体间交换个体的过程一般迁移方法是将子群体中最好的个体发给其它的子群体，通过迁移可以加快较好个体在种群间的传播，提高收敛速度和解的精度。 其特点为：更适合全局搜索，计算量较小。以基于粗粒度模型的并行算法为例，其迁移策略可分为以下两种：一传多每个处理器对应有若干个相邻处理器，每个处理器产生新一

23、代个体后，都将自己最好的一个个体传送给其所有相邻的处理器，并且接受来自相邻处理器的最好个体， 将这些个体与自己的个体同时考虑， 淘汰适应度差的个体，其程序流程图如下所示名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 15 页 - - - - - - - - - 11 一传多流程图一传一考虑到染色体的多样性， 每个处理器都将自己最好的个体仅传给与之相邻的一个处理器同时增加两个参数：一是send_rate决定处理器之间通讯的终止条件满足否？结束Y N 计算适应度选择进行交叉

24、，变异将最好的个体传送给相邻的处理器接受来自相邻处理器的最好个体淘汰适应度差的个体Generation=Generation+1 初始化种群Generation=0 开始名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 15 页 - - - - - - - - - 12 频率，如 send_rate=3时表示当遗传代数是3 的倍数时，各处理器之间相互传送个体；二是 send_best决定每次传送最好个体的数目，如 send_best=5时表示每个处理器把最好的前五个个体传

25、送给各自相邻的处理器。其流程图如下所示选择进行交叉、变异计算适应度Generation%Send_rate=0? 终止条件满足否？结束Generation=0 初始化种群开始Y N N Y 接受来自相邻处理器的最好个体将最好个体send_best传送给相临处理器名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 15 页 - - - - - - - - - 13 一般的，个体迁移的方法可以有：均匀随机挑选个体作为迁移对象、按适应度挑选个体作为迁移对象对于种群间的个体迁移结构

26、也有多种可能性，例如：迁移发生在所有的种群，即发生在完全的网络拓扑、 迁移发生在环状拓扑、 迁移发生在临集拓扑。而最一般化的是完全网络拓扑。并行算法提高了效率，究其效果如何，人们在评价其性能过程中提出了许多不同的评价方法，其中最重要的一个评价标准是加速比。设T 为某算法在串行时对的运行时间， Tp 是该算法在 p 个处理机构成的并行机上所用时间，则加速比 Sp 为：Sp=T/Tp。但对于并行遗传算法，由于搜索的随机性，仅加速比不足以衡量其优劣程度。 比较现实的方法是， 设计一些好的几何特性的测试函数和时间计算函数， 来测试达到最优化的平均时间和平均进化代数，以衡量其优劣性能。并行算法的性能主要

27、体现在收敛速度和精度两个方面，它们除了与迁移策略有关，还与一些参数选取的合理性密切相关，如遗传代数、 群体数目、群体规模、迁移率和迁移间隔。 因此，遗传代数和群体规模、 迁移率和迁移间隔的设定也理当成为一个影响算法性能的因素， 同时也可作为我们的参考系数来衡量算法的优劣性能。五、结语从以上论述看来，遗传算法是从代表问题可能潜在的解集的一个种群（population）开始的，而一个种群则由经过基因（gene ）编码的一定数目的个名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，

28、共 15 页 - - - - - - - - - 14 体(individual)组成。在对遗传算子操作中，待初代种群产生之后，按照适者生存和优胜劣汰的原理，逐代（generation）演化产生出越来越好的近似解，在每一代，根据问题域中个体的适应度（fitness）大小选择（ selection）个体，并借助于自然遗传学的遗传算子（genetic operators ）进行组合交叉（ crossover ）和变异（mutation） ，产生出代表新的解集的种群。 这个过程将导致种群像自然进化一样的后生代种群比前代更加适应于环境，末代种群中的最优个体经过解 码（decoding） ，可以作为问题近似最优解。进一步的我们也可以在改进的遗传算法中找到这种本质性的操作， 而这些改进的操作在另一方面对问题的解决产生的很大的作用，也说明遗传算法的发展将有很大的空间。参考文献：1、 遗传算法理论、应用与软件实现王小平、曹立明西安交通大学出版社2、 遗传算法原理及应用 p46、47 周明、孙树栋国防工业出版社名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 15 页 - - - - - - - - -