遗传算法模式定理

文章编号:1000-1220(2000)04-0364-04 收稿日期:1999-05-05　基金项目:国家自然科学基金资助(69974002)、(69673004)　作者简介:唐飞,博士生,研究方向为智能CAD,演化算法,航天器布局优化设计.滕弘飞,教授,博士生导师,研究方向为智能CAD/CAM ,演化算法,布局优化,人机合作.十进制编码遗传算法的模式定理研究唐　飞1,2　滕弘飞1,2　孙治国1　王文忠11(大连理工大学机械工程系　大连116024)2(中国科学院现代制造CAD/CAM 技术开放实验室　沈阳110015)摘　要:根据遗传算法中采用的编码策略,可将遗传算法分为两大类:二进制编码遗传算法和十进制编码遗传算法.二进制编码遗传算法的数学基本定理是模式定理,但对于十进制编码遗传算法是否也存在其模式定理是待探讨的问题.本文在二进制数编码遗传算法的理论基础上,给出十进制编码遗传算法的相应概念并引入符号基因表和模式不变位的概念,根据十进制编码遗传算法的简单遗传算子对其模式的影响,推导出十进制编码遗传算法的模式定理.关键词:十进制编码;遗传算法;模式定理分类号:T P 18 文献标识码:A1　引　言遗传算法(Genetic A lg or ithm ,G A )源于自然界的生物进化过程,在Holland 和G oldber g 的文献中阐述了遗传算法的思想〔1-2〕.简言之,遗传算法是一种搜索技巧,它使用当前解和一些随机信息来产生新解.算法中的随机过程使得对解空间更广泛的搜索成为可能.遗传算法的编码策略包括至今仍在争论的两派,一派根据模式定理建议用尽量少的符号编码(如二进制编码),一派以数值优化计算的方便和精度为准采用一个基因一个参数的方法(如十进制编码),并把相应的基因操作改造成适合实数操作的方式〔3〕.文〔4〕解释了遗传算法中模式和模式定理的概念和含义,并检验了那些通常被用来描述遗传算法在实际问题求解中取得成功的一些根本假设.文〔5〕将具有选择、变异两种算子的二进制编码模式定理推广到等式的情况,并从理论上证明了经过选择算子作用后整个种群将得以改进,文〔6〕分析了基于序的遗传算法(Or der -based G A )的二进制编码模式定理及其M arko v 链建模,文〔7,8〕探讨了模式及模式定理是如何影响遗传算法的行为和性能,并揭示了积木块假设和模式增长之间的内在关系,这些文献都是在二进制编码遗传算法基础上对模式定理进行深入探讨和研究.标准遗传算法采用二进制编码方式,模式理论也是基于二进制的.单二进制编码易引起精度和效率的冲突.为得到高精度的最优解,个体的二进制编码串就要保持相当的长度,从而造成了计算量迅速增加;要保证计算效率,又不得不缩短编码长度,可能造成解的精度受限.而十进制编码遗传算法在很大程度上解决了这一冲突,因此在实践中采用十进制数编码来求解问题的情况越来越多.但由于十进制编码一直没有类似二进制编码遗传算法的模式定理,因而一直难于对其进化机制和性能进行精确分析.直接推导十进制编码遗传算法的模式定理有很大困难,至今尚未见有关文献出现.本文借鉴二进制编码遗传算法的理论基础,另辟蹊径给出了类似二进制编码表达的十进制编码方式,然后对二进制模式定理的一般证明过程进行推广,从而得出十进制编码遗传算法的基本定理,称之为十进制模式定理.必须说明的是,这种证明并不是十分严格的.2　二进制编码遗传算法理论基础及其模式定理2.1　遗传算法有关定义〔3-9〕为了讨论十进制模式定理,首先介绍遗传算法的有关概念定义.我们采用二进制编码的二元基因表V ={0,1}来给出遗传算法中基本术语定义.采用二元基因编码的染色体串可以用带下标的字母的形式来表示,其中下标代表其位置顺序,记为:A =a 1a 2a 3a 4a 5这里每个a i 表示一个二元基因,可取值1或者0.定义1:模式就是一个相同的构形.它描述的是一个染色体串的子集.这个集合中的染色体串之间在某些位上相同.考虑由三元基因表V +={*,0,1}表示的模式,其中添加的*代表不确定的基因,即在此特定位置上将与0或1相对应.定义2:模式的阶是指出现在模式中确定位置的数目,记为 (H ).在二进制编码的染色体串中一个模式的阶就是所有0或1的个数.例如,模式0*10*的阶 =3,而模式1****的阶为 =1.定义3:模式定义距是指模式中第一个确定基因位置与最后一个确定基因位置之间的距离,记为d (H ).如模式0*10*的定义距的第一个确定基因在第1位,最后一个确定基因在第4位,所以其定义距d =4-1=3,而模式1****的定义距为0.定义4:适应度值是指为群体中每个染色体串指定的一　第21卷第4期 2000年4月小型微型计算机系统M IN I-M I CR O SY ST EM Vo l .21No .4 A pr.2000 个数值,记为f,它经常是问题本身所具有的.适应度值必须有能力计算搜索空间中每个染色体串的性能值.控制遗传算法的主要参数有群体规模N、算法执行的最大进化代数M、复制概率p r、交叉概率p c和变异概率p m等参数.2.2　二进制编码遗传算法的基本定理--模式定理模式定理:具有短的定义距、低阶并且适应度值在群体平均适应度值以上的模式在遗传算法迭代过程中将按指数增长率被采样.也就是说,在使用遗传算法时,染色体群体中那些短的低阶模式是按照指数增加还是减少的数目进行采样,依赖于模式的平均适应度值.3　十进制编码遗传算法基本定理--模式定理经笔者在EI中检索,关于遗传算法模式定理的文献都是针对标准遗传算法即二进制编码遗传算法展开研究.目前,尚未见到公开发表的关于十进制编码遗传算法模式定理的文献,本文在上述定义基础上,借鉴标准遗传算法——二进制编码遗传算法模式定理的推导思路和过程,得出十进制编码遗传算法模式定理——称之为十进制模式定理.3.1　十进制编码遗传算法基本概念定义参考二进制编码遗传算法基本概念的定义,本文给出十进制编码遗传算法相应的基本概念的定义.对于十进制编码的遗传算法,我们提出采用2元符号基因表S={+,-}和11元数值基因表V={0,1,2,3,4,5,6,7,8, 9,・}对染色体串进行编码(其中“・”代表小数点),每个染色体串同样可以用带下标的字母来表示,其中下标代表位置顺序.举例说明如下:一个12位染色体串A=(+10・37-89・67)可以表示为:A=a1a2a3a4a5a6a7a8a9a10a11a12其中:a i表示基因,且a i∈S∪V.定义1:模式就是一个相同的构形.它描述的是一个染色体串的子集.这个集合中所有的染色体串之间在某些位上相同.考虑由3元符号基因表S+={#}∪{+,-}={+,-,#}和12元数值基因表V+={*}∪V={*,0,1,2,3,4,5,6,7,8,9,・}表示的模式,其中添加的#和*代表不确定的基因,即#与中某一基因相对应,而*则与V中某一基因相对应.例如染色体串长为12的模式A=(#10***#**・67),则前述的染色体串A=(+10・37-89・67)是模式H的一个具体表示形式.定义在染色体串长为l上的二进制染色体串的模式共有个3l.一般的,对于基数为k的基因表,共有(K+1)l个模式.因此定义在染色体串长为l的11元数值基因表V和2元符号基因表S={+,-}上的模式共有(2+1+11+1)l=15l个模式.在n个十进制整数编码的染色体串群体中至多有n・13l个模式包含在其中.由此可以得出,采用十进制整数编码表示染色体串时,群体中的模式的数目仅与群体大小和染色体长度有关.定义2:模式的阶是指出现在模式中的确定基因位置的数目,记为 (H).在十进制整数编码的染色体串中一个模式的阶就是所有符号基因表S和数值基因表V中元素在该模式中出现的个数.例如,模式(+1*4*-**・7*)的阶 =6.定义3:模式定义距是指模式中第一个确定基因位置与最后一个确定基因位置之间的距离,记为d(H).如模式(+1*4 *-**・7*)的第一个确定基因在第1位,最后一个确定基因在第10位,所以其定义距d=10-1=9.需要说明的是,如果一个模式中存在两个皆为小数点基因或符号基因的相邻位,那么该模式将无法通过解码获得有意义的解,这样的模式称为无效模式.如模式(+1*4--*・・7 *).为此,我们定义模式不变位和模式不变数的概念如下.定义4:模式的不变位是指模式中的小数点基因,而模式不变数就是指模式中不变位的个数,记为 (H).如模式(+1・4* -**・7*)的不变数 =2.我们可以采取一些措施,避免无效模式的出现.例如,设计合理的编码规则并使小数点基因不参加变异等方法.举例说明如下:对于优化问题:min f(x,y)=x2+y2s.t.　x∈(-70,80)　y∈(-500,600)假定计算精度为0.01,则在进行编码时要求表示x的基因段为6位(包括符号和小数点),表示y的基因段为7位(包括符号和小数点).下面给出两个染色体a,b,其中对于染色体a:x=-6. 60,y=288.88;对于染色体b:x=52.31,y=-256.65.染色体x ya-06・60+288・88b+52・31-256・65在编码中,对于不足的位应当补零,以保证染色体长度一致,同时禁止小数点基因位参加变异,即小数点基因位不能变异为数值基因,数值基因也不能变异为小数点.而符号基因参加变异,当然正号“+”只能变异成负号“-”,而“-”也只能变异成“+”.采用这种编码规则,染色体个体间无论是复制、交叉还是变异操作,都将避免无效模式的出现.3.2　十进制编码遗传算法模式定理及推导文献〔3-10〕中介绍并讨论了二进制编码遗传算法的模式定理及实数编码,本文在此基础上推导出十进制编码遗传算法的模式定理.控制遗传算法的主要参数有群体规模N、算法执行的最大进化代数M、复制概率p r、交叉概率p c和p m变异概率等参数.模式、模式阶和模式定义距对于严格讨论和区分染色体串的相似性是一个有力的工具.本文仅讨论在复制算子、一点交叉算子和变异算子对模式的影响来得出十进制编码遗传算法的模式定理.复制算子假定在给定的时间步t,一个特定的模式H有m个代表染色体串包含在群体P(t)中,记为m=m(H,t).在复制阶段,每个染色体串根据它的适应度值进行复制,或者更确切地说,一个染色体串的复制概率为:3654期 唐飞等:十进制编码遗传算法的模式定理研究 p r i =f i /∑nj =1fj(1)当采用非重叠的n 个染色体串的群体替代群体P (t )后,我们期望在时间步(t +1),模式H 在群体A (t +1)中有m (H ,t +1)个代表染色体串,这可以用下面的方程给出:m (H ,t +1)=m (H ,t ) n f (H )/∑nj =1fj(2)其中:f (H )为在时间步t 表示模式H 的染色体串的平均适应度值.由于整个群体的平均适应度值可记为f =∑nj =1fj/n因此模式的复制生长方程可以表示为:m (H ,t +1)=M (H ,t ) f (H )/f(3)令f (H )=f + f , 为一常数,则模式的复制生长方程变为:m (H ,t +1)=m (H ,t )・(1+ )(4)从t =0开始,假设 是一个固定值,则有:m (H ,t +1)=m (H ,0)・(1+)t (5)这表明,一个特定的模式按照其平均适应度值与群体平均适应度值之间的比率增长.平均适应度值以上(以下)的模式将会按照指数增长(衰减)的方式被复制.交叉算子由于复制过程不能检测搜索空间中新的区域,因此,需要采取杂交操作.杂交就是在两个染色体串之间进行信息交换.为叙述方便起见,我们仅采用简单的一点杂交算子.假定有一个染色体串长为12的特定的染色体串和包含在其中两个具有代表性的模式如下:A =(+10・37-89・67)H 1=(#1****#***67),d (H 1)=10H 2=(#1***37-****),d (H 2)=2假定染色体串A 被选择用来杂交,杂交位置在第4和第5位之间,则一点杂交算子对模式H 1和H 2的作用效果如下:A =(+10・ 37-89・67)H 1=(#1** **#***67)H 2=(#1** 37-*****)可以看出,除非染色体串A 的交配染色体串在模式H 1的确定位置上与A 相同,否则模式H 1将被破坏,而对于相同杂交位置的模式H 2将生存下来.即模式H 1比起模式H 2来更不易生存.这是由于模式H 1比模式H 2的定义距要长的缘故.一般地,对任意模式可计算出其杂交生存概率P cs 的下界.考虑在简单一点杂交算子作用下,对于长度为l 的模式的生存概率为p cs =1-d (H )/(l -1),当杂交位置落在定义距长度之外时,这个模式就可以生存.否则,当杂交位置一旦落在定义距之内时,则模式极易被破坏.若杂交本身也是按照随机选取方式进行,即以概率p c 进行杂交,则生存概率有下面的估计式:p cs ≥1-p c ・d (H )/(l -1)(6)现在考虑复制和杂交结合在一起时对模式的作用效果.这里假定复制和杂交是不相关的,则有下面估计:m (H ,t +1)≥m (H ,t )・f (H )f・[1-p c ・d (H )/(l -1)](7)比较(3)和(7)式,可以看到,交叉和复制一起对模式的作用效果是通过把仅有复制作用时的模式期望数与在交叉作用下的生存概率相乘得到的,模式H 增长或衰减依赖于一个乘积因子.在复制和杂交作用下,这个因子依赖于两个因素:模式适应度值和模式的定义距.显然,那些既在群体平均适应度值之上同时又具有短的定义距的模式将按照指数增长率被采样.变异算子假定一个模式H 的模式不变数为 (H ),变异算子以概率p m 随机地改变除模式不变位以外的所有基因位上的值,为了使得模式H 能够生存下来,所有特定位必须存活.因为单个基因存活的概率为(1-p m ),并且由于每次变异都是统计独立的,因此当模式H 中[ (H )- (H )]个确定位置都存活时,这个模式才存活,因而在变异算子的作用下,存活概率可以近似地表示为(1-p m ) (H )- (H ).对于很小的p m ,模式的存活概率可以近似地等于[1-( (H )- (H ))・p m ].因此,在复制、杂交和变异算子作用下,一个特定模式H 在下一代中期望出现的次数可以近似地表示为:m (H ,t +1)≥m (H ,t )・f (H )f[1-p c ・d (H )/(l -1)-( (H )- (H ))p m ](8)由上式可以看出,增加变异基本上不改变先前的结论,即那些既在群体平均适应度值之上同时又具有短的定义距的模式将按照指数增长率被采样.3.3　十进制模式定理根据复制、交叉、变异三种算子对模式的影响,我们可以得到十进制编码遗传算法的模式定理:采用十进制编码的遗传算法的群体中模式的数目仅与群体大小和染色体长度有关,其中具有短的定义距、低阶并且适应度值在群体平均适应度值以上的模式在遗传算法迭代过程中将按指数增长率被采样.本文是从十进制编码的一般形式(即实数编码)上推导出十进制编码遗传算法的模式定理,该结论对十进制编码的其他具体形式,如自然数编码、整数编码的情况完全成立.要注意的是在自然数编码和整数编码情况下,其数值基因表中应去掉小数点基因,即为10元数值基因表V ={0,1,2,3,4,5,6,7,8,9},具体推导过程与前文类似,这里不再赘述.4　结　论十进制编码较二进制编码的遗传算法的染色体所能表示的模式数目大,隐含并行性强.十进制编码的遗传算法在实践中得到广泛而成功地应用,但是其模式定理的相关研究尚欠缺,研究将二进制模式定理推广到十进制实数编码有助于对其进化机制和性能进行深入分析.由于在编码策略中引入符号基因表和模式不变位等概念,366 小　型　微　型　计　算　机　系　统 2000年从而使得十进制编码与二进制编码在本质上相统一,因此我们可以将二进制编码模式定理的推导推广到十进制编码的情况.本文在二进制数编码遗传算法的模式定理基础上,根据十进制编码遗传算法的简单遗传算子对其模式的影响,推导出十进制编码遗传算法的模式定理.十进制编码的遗传算法的模式定理在结论上与采用二进制编码的遗传算法模式定理相似.致谢:感谢中国科学院沈阳自动化研究所聂义勇研究员的帮助。

遗传算法原理及其应用遗传算法原理及其应用《遗传算法原理及其应用》Chap1 序论一. 遗传算法的生物学基础1.1 遗传与变异基本概念 Cell:细胞Chromosome:染色体 Gene:基因 Locus:基因座 Allele:等位基因 Genotype:基因型Phenotype:表现型 Genome:基因组 Reproduction:复制 Crossover:交叉 Mutation:变异1.2 进化基本术语Evolution:进化 Population:群体 Individual:个体 Fitness:适应度1.3 遗传与进化的系统观1) 生物的所有遗传信息都包含在其染色体中,染色体决定了生物的性状;2) 染色体是基因及其有规律的排列所构成,遗传和进化过程发生在染色体上; 3) 生物的繁殖过程是由其基因的复制过程完成的;4) 通过同源染色体之间的交叉或染色体的变异会产生新的物种,使生物呈现新的性状;5) 对环境适应性好的基因或者染色体会经常比适应性差的基因或染色体有更多的机会遗传到下一代。

二. 遗传算法简介遗传算法是模拟生物在自然环境中的遗传和进化过程而形成的一种自适应全局优化概率2.1 遗传算法概要对于一个求函数最大值的优化问题（求函数最小值也类同），一般可描述为下述数学规t划模型：s..f(X)X∈R R⊆U式中，X=[x1,x2,...,xn] 为决策变量，f（X）为目标函数，第2，3式为约束条件，U是基本空间，R是U的一个子集。

满足约束条件的解X称为可行解，集合R表示由所有满足约束条件的解所组成的一个集合，叫做可行解集合。

对上述最优化问题，目标函数和约束条件种类繁多，由的是线性的，有的是非线性的；有的是连续的，有的是离散的；有点是单峰的，有的是多峰的。

求最优解或近似最优解的方法主要有三种：枚举法，启发式算法和搜索算法：枚举法：枚举出可行解集合内的所有的可行解，以求出精确最优解。

对于连续1）函数，首先要求对其进行离散化处理。

遗传算法模式定理
遗传算法的一个主要前提假设是模式定理。

模式定理中主要概念有：模式（Schema）：指有相同特征的子集，比如二进制字符串11***\(*为通配符\)可以代表八个个体（2x2x2）。

阶（Order）：模式中确定位置的个数成为阶，比如1110*的阶为1。

定义距（Defining Length）：模式中第一个确定位置和最后一个确定位置之间的距离成为定义距。

模式定理：具有低阶、短定义距以及平均适应度高于种群平均适应度的模式在子代中呈指数增长。

它保证了较优的模式（遗传算法的较优解）的数目呈指数增长，为解释遗传算法机理提供了数学基础。

遗传算法算法原理（原创实用版）目录1.遗传算法的概述2.遗传算法的原理3.遗传算法的应用正文一、遗传算法的概述遗传算法（Genetic Algorithm，简称 GA）是一种模拟自然界生物进化过程的优化算法。

其核心思想是基于自然选择、遗传和突变等生物学原理，通过群体中的个体在不断迭代中进行优胜劣汰，达到解决问题和优化目标的效果。

遗传算法在解决复杂问题、非线性问题和全局最优解问题等方面具有较强的优势，广泛应用于各个领域。

二、遗传算法的原理1.遗传操作遗传算法的基本操作包括选择、交叉和变异。

选择操作是根据适应度函数对当前群体中的个体进行评估，选择优秀个体进行繁殖。

交叉操作是将选中的优秀个体进行染色体互换，产生新的后代。

变异操作是在后代中随机选择某个位点进行变异，以一定的概率产生新的特性。

2.适应度函数适应度函数是遗传算法中的重要概念，用于评估每个个体的优劣程度。

适应度函数的取值范围为 [0, 1]，其中 1 表示最优解，0 表示最劣解。

在遗传算法中，适应度函数的取值会直接影响到个体的选择和淘汰。

3.遗传算法的基本流程遗传算法的基本流程如下：（1）初始化种群：创建一个初始种群，包括多个随机生成的个体，每个个体表示一个解。

（2）评估适应度：计算种群中每个个体的适应度值。

（3）选择操作：根据适应度值对种群进行选择，选择一定数量的优秀个体进行繁殖。

（4）交叉操作：对选中的优秀个体进行染色体互换，生成新的后代。

（5）变异操作：在后代中随机选择某个位点进行变异，以一定的概率产生新的特性。

（6）更新种群：将新产生的后代替换掉原种群中一些适应度较低的个体，形成新的种群。

（7）重复步骤 2-6，直至满足停止条件。

三、遗传算法的应用遗传算法在许多领域都取得了显著的应用成果，如机器学习、控制系统、信号处理、图像处理、运筹学等。

遗传算法总结By xudong 内容提要遗传算法的实现过程遗传算法基本理论遗传算法的三个算例TSP问题装箱问题网络结构优化遗传算法的实现过程产生初始种群在适应度函数的基础上选择parents从parents中产生children有三种途径：将parents中最优秀的个体直接保留到children杂交变异遗传算法实现流程下面以一个函数优化的过程为例说明遗传算法的工作过程，材料来自matlab中遗传算法的算法说明。

【生成初始种群】这是函数的等值线图，图中的蓝点表示初始种群中的个体。

【生成下一代种群】图中的符号表示下一代个体，具体不同符号表示不同的产生途径。

【迭代过程】可以看出，随着迭代的增加，整个种群逐渐收敛到最优解。

遗传算法基本理论这里只叙述定理的内容和评价，定理中所涉及的概念和定理的推导过程大家感兴趣的话可以翻翻书。

【模式定理】内容：遗传算法中，在选择、交叉、变异算子的作用下，具有低阶、短的定义长度，并且平均适应度高于群体平均适应度的模式将按指数级增长。

评价：看到这个定理首先想到的就是《自私的基因中》的核心观点，基因是进化的基本单位。

短小，并且适应度高的基因在进化过程中被保留下来，并且在群体中不断增加。

【积木块假定】内容：基因能够互相拼接在一起，形成适应度更高的编码串。

评价：模式定理是说遗传算法能够产生高质量的建筑砖头（基因），积木块假定是说可以用这些高质量的建筑砖头建造高质量的大楼（编码串）。

需要注意的是，我们把上述内容称为假定，而并非定理，这是因为有时候积木块假定并不成立，也就是说高质量的转头不一定能够建成高质量的大楼。

出现这种情况的原因是1+1<2的现象，各个基因之间高度相关，适应度很高的两个基因之间存在很强的负交互作用，结果导致整体的适应度下降。

【遗传算法收敛性】内容1.不保留优秀个体，收敛于最优解的概率小于12.保留优秀个体，遗传算法收敛于最优解的概率等于1评价：这两个定理说明了我们为什么在遗传算法中保留优秀个体的一个原因，保留优秀个体的另外一个原因是保证遗传算法每一代的解总是单调减少的（假设目标是极小化目标函数）。