2022年遗传算法 .pdf
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《2022年遗传算法 .pdf》由会员分享,可在线阅读,更多相关《2022年遗传算法 .pdf(12页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、什么是遗传算法?遗传算法的原理生物的进化是一个奇妙的优化过程,它通过选择淘汰,突然变异,基因遗传等规律产生适应环境变化的优良物种。遗传算法是根据生物进化思想而启发得出的一种全局优化算法。遗传算法的概念最早是由Bagley J.D 在 1967 年提出的;而开始遗传算法的理论和方法的系统性研究的是1975 年,这一开创性工作是由Michigan 大学的 J.H.Holland所实行。当时,其主要目的是说明自然和人工系统的自适应过程。遗传算法简称GA(Genetic Algorithm),在本质上是一种 不依赖具体问题的直接搜索方法。遗传算法在模式识别、神经网络、图像处理、机器学习、工业优化控制、
2、自适应控制、生物科学、社会科学等方面都得到应用。在人工智能研究中,现在人们认为“遗传算法、自适应系统、细胞自动机、混沌理论与人工智能一样,都是对今后十年的计算技术有重大影响的关键技术”。1.1 遗传算法的基本概念遗传算法的基本思想是基于Darwin 进化论和 Mendel的遗传学说的。Darwin 进化论最重要的是适者生存原理。它认为每一物种在发展中越来越适应环境。物种每个个体的基本特征由后代所继承,但后代又会产生一些异于父代的新变化。在环境变化时,只有那些能适应环境的个体特征方能保留下来。Mendel 遗传学说最重要的是基因遗传原理。它认为遗传以密码方式名师资料总结-精品资料欢迎下载-名师精
3、心整理-第 1 页,共 12 页 -存在细胞中,并以基因形式包含在染色体内。每个基因有特殊的位置并控制某种特殊性质;所以,每个基因产生的个体对环境具有某种适应性。基因突变和基因杂交可产生更适应于环境的后代。经过存优去劣的自然淘汰,适应性高的基因结构得以保存下来。由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法;故而在这个算法中要用到各种进化和遗传学的概念。这些概念如下:一、串(String)它是个体(Individual)的形式,在算法中为二进制串,并且对应于遗传学中的染色体(Chromosome)。二、群体(Population)个体的集合称为群体,串是群体的元素三、群体大小(Po
4、pulation Size)在群体中个体的数量称为群体的大小。四、基因(Gene)基因是串中的元素,基因用于表示个体的特征。例如有一个串S1011,则其中的 1,0,1,1 这 4 个元素分别称为基因。它们的值称为等位基因(Alletes)。五、基因位置(Gene Position)一个基因在串中的位置称为基因位置,有时也简称基因位。基因位置由串的左向右计算,例如在串S1101 中,0 的基因位置是 3。基因名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页,共 12 页 -位置对应于遗传学中的地点(Locus)。六、基因特征值(Gene Feature)在用串表示整数时,基因的特征值与
5、二进制数的权一致;例如在串S=1011中,基因位置 3 中的 1,它的基因特征值为2;基因位置 1 中的 1,它的基因特征值为8。七、串结构空间SS 在串中,基因任意组合所构成的串的集合。基因操作是在结构空间中进行的。串结构空间对应于遗传学中的基因型(Genotype)的集合。八、参数空间SP 这是串空间在物理系统中的映射,它对应于遗传学中的表现型(Phenotype)的集合。九、非线性它对应遗传学中的异位显性(Epistasis)十、适应度(Fitness)表示某一个体对于环境的适应程度。遗传算法还有一些其它的概念,这些概念在介绍遗传算法的原理和执行过程时,再进行说明。1.2 遗传算法的原理
6、遗传算法 GA把问题的解表示成“染色体”,在算法中也即是以二进制编码的串。并且,在执行遗传算法之前,给出一群“染色体”,也即是假设解。然后,把这些假设解置于问题的“环境”中,并按适者生存的原则,从中选择出较适应环境的“染色体”进行复制,再通过名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页,共 12 页 -交叉,变异过程产生更适应环境的新一代“染色体”群。这样,一代一代地进化,最后就会收敛到最适应环境的一个“染色体”上,它就是问题的最优解。一、遗传算法的目的典型的遗传算法CGA(Canonical Genetic Algorithm)通常用于解决下面这一类的静态最优化问题:考虑对于一群
7、长度为L 的二进制编码 bi,i 1,2,,,n;有bi 0,1L(3-84)给定目标函数f,有 f(bi),并且0f(bi)同时f(bi)f(bi+1)求满足下式maxf(bi)|bi0,1L(3-85)的 bi。很明显,遗传算法是一种最优化方法,它通过进化和遗传机理,从给出的原始解群中,不断进化产生新的解,最后收敛到一个特定的串bi 处,即求出最优解。二、遗传算法的基本原理长度为 L 的 n 个二进制串 bi(i1,2,,,n)组成了遗传算法的初解群,也称为初始群体。在每个串中,每个二进制位就是个体染色体名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页,共 12 页 -的基因。根据
8、进化术语,对群体执行的操作有三种:1选择(Selection)这是从群体中选择出较适应环境的个体。这些选中的个体用于繁殖下一代。故有时也称这一操作为再生(Reproduction)。由于在选择用于繁殖下一代的个体时,是根据个体对环境的适应度而决定其繁殖量的,故而有时也称为非均匀再生(differential reproduction)。2交叉(Crossover)这是在选中用于繁殖下一代的个体中,对两个不同的个体的相同位置的基因进行交换,从而产生新的个体。3变异(Mutation)这是在选中的个体中,对个体中的某些基因执行异向转化。在串bi中,如果某位基因为1,产生变异时就是把它变成0;反亦反
9、之。遗传算法的原理可以简要给出如下:choose an intial population determine the fitness of each individual perform selection repeat perform crossover perform mutation determine the fitness of each individual perform selection until some stopping criterion applies 名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页,共 12 页 -这里所指的某种结束准则一般是指个体的适
10、应度达到给定的阀值;或者个体的适应度的变化率为零。三、遗传算法的步骤和意义1初始化选择一个群体,即选择一个串或个体的集合bi,i=1,2,.n。这个初始的群体也就是问题假设解的集合。一般取n30-160。通常以随机方法产生串或个体的集合bi,i1,2,.n。问题的最优解将通过这些初始假设解进化而求出。2选择根据适者生存原则选择下一代的个体。在选择时,以适应度为选择原则。适应度准则体现了适者生存,不适应者淘汰的自然法则。给出目标函数f,则 f(bi)称为个体 bi 的适应度。以(3-86)为选中 bi 为下一代个体的次数。显然从式(3 86)可知:(1)适应度较高的个体,繁殖下一代的数目较多。(
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 2022年遗传算法 2022 遗传 算法
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内