文章目录

前言

遗传算法(Genetic Algorithm,GA)是模拟生物在自然环境中的遗传和进化的过程而形成的自适应全局优化搜索算法。它借用了生物遗传学的观点,通过自然选择、遗传和变异等作用机制,实现各个个体适应性的提高。遗传算法起源于20世纪60年代对自然和人工自适应系统的研究;70年代,基于遗传算法的思想,在计算机上进行了大量纯数值函数优化计算实验;80年代,遗传算法在一系列研究工作的基础上归纳总结而成。

20世纪90年代后,遗传算法作为一种高效、实用、鲁棒性强的优化技术,发展极为迅速,在机器学习、模式识别、神经网络、控制系统优化及社会科学等不同领域得到广泛应用,引起了广泛关注。进入21世纪,以不确定性、非线性、时间不可逆为内涵的复杂性科学成为一个研究热点。遗传算法因能有效求解NP(Non-deterministic Polynomial)问题以及非线性、多峰函数优化和多目标优化问题,得到了众多研究者的高度重视。

遗传算法借鉴了达尔文的进化论和孟德尔的遗传学说,本质上是一种并行、高效、全局搜索的方法,它能在搜索过程中自动获取和积累有关搜索空间的知识,并自适应地控制搜索过程以求得最优解。遗传算法操作使用“适者生存”的原则,在潜在的解决方案种群中逐次产生一个近似最优的方案。在每一代中,根据个体在问题域中的适应度值和从自然遗传学中借鉴来的再造方法进行个体选择,产生一个新的近似解。这个过程导致种群中个体的进化,得到的新个体比原个体更能适应环境。

同传统的优化算法相比,遗传算法具有对参数的编码进行操作、不需要推导和附加信息、寻优规则非确定性、自组织、自适应和自学习性等特点。当染色体结合时,双亲的遗传基因的结合使得子女保持父母的特征;当染色体结合后,随机的变异会造成子代同父代的不同。

遗传算法的生物学基础

自然选择学说认为适者生存,生物要存活下去,就必须进行生存斗争。生存斗争包括种内斗争、种间斗争以及生物跟环境之间的斗争三个方面。在生存斗争中,具有有利变异的个体更容易存活下来,并且有更多的机会将有利变异传给后代;具有不利变异的个体就容易被淘汰,产生后代的机会也将少得多。因此,凡是在生存斗争中获胜的个体都是对环境适应性比较强的个体。达尔文把这种在生存斗争中适者生存、不适者淘汰的过程叫做自然选择。

达尔文的自然选择学说表明,遗传和变异是决定生物进化的内在因素。遗传是指父代与子代之间,在性状上存在的相似现象;变异是指父代与子代之间,以及自带个体之间,在性状上存在的差异现象。在生物体内,遗传和变异的关系十分密切。一个生物体的遗传性状往往会发生变异,而变异的形状有的可以遗传。遗传能使生物的性状不断地传送给后代,因此保持了物种的特性;变异能够使生物的性状发生改变,从而适应新的环境而不断地向前发展。

生物的各项生物活动都有它的物质基础,生物的遗传与变异也是这样。根据现代细胞学和遗传学的研究得知,遗传物质的主要载体是染色体,基因是有遗传效应的片段,它储存着遗传信息,可以准确地复制,也能够发生突变。生物体自身通过对基因的复制和交叉,使其性状的遗传得到选择和控制。同时,通过基因重组、基因变异和染色体在结构和数目上的变异产生丰富多彩的变异现象。生物的遗传特性,是生物界的物种能够保持相对的稳定;生物的变异特性,使生物个体产生新的性状,以致形成新的物种,推动生物的进化和发展。

由于生物在繁衍中可能发生基因交叉和变异,引起生物性状的连续微弱改变,为外界环境的定向选择提供了物质条件和基础,是生物的进化成为可能。人们正是通过对环境的选择、基因的交叉和变异这一生物演化的迭代过程的模仿,才提出了能够用于求解最优化问题的强鲁棒性和自适应性的遗传算法。生物遗传和进化的规律有:

(1) 生物的所有遗传信息都包含在其染色体中,染色体决定了生物的性状。染色体是由基因及其有规律的排列所构成的。

(2) 生物的繁殖过程是有其基因的复制过程来完成的。同源染色体的交叉或变异会产生新的物种,使生物呈现新的性状。

(3) 对环境适应能力强的基因或染色体,比适应能力差的基因或染色体有更多的机会遗传给下一代。

遗传算法理论基础

模式定理

模式定义:模式是描述种群在位串的某些确定位置上具有相似性的位串子集的相似性模板。

不失一般性,考虑二值字符集{0, 1},由此可以产生通常的0、1字符串。增加一个符号“*”,称作“通配符”,即“*”即可以当作“0”,也可以当作“1”。这样,二值字符集{0, 1}就扩展为三值字符集{0, 1, *},由此可以产生诸如0110,0*11**,**01*0之类的字符串。

基于三值字符集{0, 1, *}所产生的能描述具有某些结构相似性的0、1字符串集的字符串,称作模型。这里需要强调的是。“*”只是一个描述符,而并非遗传算法中实际的运算符号,它仅仅是为了描述上的方便引入的符号而已。

模式的概念可以简明地描述具有相似结构特点的个体编码字符串。在引用了模式概念之后,遗传算法的本质是对模式所进行的一系列运算,即通过选择操作数将当前群体中优良模式遗传到下一代群体中,通过交叉操作数进行模式的重组,通过变异操作数进行模式的突变。通过这些遗传算法,一些较差的模式逐步被淘汰,而一些较好的模式逐步被遗传和进化,最终就可以得到问题的最优解。

多个串中隐含着多个不同的模式。确切地说,长度为L的串,隐含着$$2^L$$个不同的模式,而不同的模式所匹配的串的个数是不同的。为了反应这种确定性的差异,引用模式阶概念。

模式阶定义:模式H中确定位置的个数称作该模式的模式阶,记作$$O(H)$$。

比如,模式011*1*的阶数为4,而0******的阶数为1,显然,一个模式的阶数越高,其样本数就越少,因而不确定性越高。但是,模式阶并不能反映模式的所有性质;即使具有同阶的模式,在遗传操作下,也会有不同的性质。为此,引入定义距概念。

定义距定义:在模式H中第一个确定位置和最后一个确定位置之间的距离称作该模式的定义距,记作$$D(H)$$。

模式定理:在遗传算法选择、交叉和变异算子的作用下,具有低阶、短定义距,并且其平均适应度高于群体平均适应度的模式在子代中将呈指数级增长。

模式定理又称为遗传算法的基本定理。模式定理阐述了遗传算法的理论基础,说明了模式的增加规律,同时也给遗传算法的应用提供了指导作用。根据模式定理,随着遗传算法的一代一代地进行,那些定义距短的、位数更少的、高适应度的模式将越来越多,因此可期望最后得到的位串的性能越来越得到改善,并最终趋向全局的最优点。

模式的思路提供了一种简单而有效的方法,实的能够在有限字母表的基础上讨论有限长位串的严谨定义的相似性;而模式定理从理论上保证了遗传算法是一个可以用来寻求最优可行解的优化过程。

积木块假设

模式定理说明了具有某种结构特征的模式在遗传进化过程中其样本数木将呈指数级增长。这种模式定义为积木块。它在遗传算法中非常重要。

积木块定义:具有低阶、短定义距以及高平均适应度的模式称作积木块。