遗传算法及其改进_段玉倩

第10卷第1期电力系统及其自动化学报　Vol.10No.1　　　　　　　　　　　　　　1998年3月ProceedingsoftheEPSAMarch　1998

遗传算法及其改进

段玉倩　　贺家李

(天津大学自动化学院电力系,天津,300072)

摘要

本文首先对遗传算法的来源、基本原理、数学机理、特点及其应用进行了论述;为了提高遗

传算法的收敛性能,同时考虑到交叉率和变异率的选取问题,本文简要介绍了一种基于个体适

应度值的自适应调整交叉率和变异率的自适应遗传算法。分析其不足后,提出了本文的改进方

法——改进的自适应遗传算法。在文章的最后,针对几种优化问题对本文所提出的方法和其它

两种方法进行了性能比较,证明本文提出的改进方法达到最优解的收敛速度有了明显的提高。

关键词　遗传算法　自适应遗传算法

1　遗传算法简介

早在1967年J.D.Bagley就首次提出了遗传算法(GeneticAlgorithm,简称GA)的概念。但是具有开创意义的遗传算法的理论和方法则是1975年左右由美国密执安(Michi-gan)大学的心理学教授、电工及计算机科学教授JohnH.Holland和他的同事、学生共同研究出的。近年来遗传算法已经吸引了大量的研究者和探索者,其中以D.E.Goldberg的贡献最为卓越。他不但建立和完善了整个GA的体系,而且成功地将其应用到搜索、优化及机器学习等多个领域,为GA的应用开辟了广阔的天地。经过数年的努力,GA已经成为一种成熟的具有极高鲁棒性和广泛适用性的全局优化算法。

遗传算法是建立在达尔文(Darwin)的生物进化论和孟德尔(Mendel)的遗传学说基础上的算法。生物体可以通过遗传和变异来适应于外界环境。在进化论中,每一物种在不断的发展过程中都是越来越适应环境,物种的每个个体的基本特征被后代所继承,但后代又不完全同于父代,这些新的变化,若适应环境,则被保留下来,否则,就将被淘汰。亦即适者生存,不适者被淘汰。在遗传学中认为,遗传是作为一种指令遗传码封装在每个细胞中,并以基因的形式包含在染色体中,每个基因有特殊的位置并控制某个特殊的性质。每个基因产生的个体对环境有一定的适应性。基因杂交和基因突变可能产生对环境适应性强的后代,通过优胜劣汰的自然选择,适应值高的基因结构就保存下来[2]。

遗传算法就是模仿了生物的遗传、进化原理,并引用了随机统计理论而形成的。在求解过程中,遗传算法从一个初始变量群体开始,一代一代地寻找问题的最优解,直至满足收敛判据或预先设定的迭代次数为止。它是一种迭代式算法。[1]

2　遗传算法的基本原理

本文系国家教委博士学科点基金资助项目6

·40·电力系统及其自动化学报　　　　　　　　　1998年第1期　　遗传算法是一种基于自然选择和群体遗传机理的搜索算法,它模拟了自然选择和自然遗传过程中发生的繁殖、杂交和突变现象。在利用遗传算法求解问题时,问题的每个可能的解都被编码成一个“染色体”,即个体,若干个个体构成了群体(所有可能解)。在遗传算法开始时,总是随机地产生一些个体(即初始解),根据预定的目标函数对每个个体进行评价,给出了一个适应度值。基于此适应度值,选择个体用来复制下一代。选择操作体现了“适者生存”原理,“好”的个体被选择用来复制,而“坏”的个体则被淘汰。然后选择出来的个体经过交叉和变异算子进行再组合生成新的一代。这一群新个体由于继承了上一代的一些优良性状,因而在性能上要优于上一代,这样逐步朝着更优解的方向进化。因此,遗传算法可以看作是一个由可行解组成的群体逐代进化的过程。

图1示出了简单遗传算法的基本过程

。

图1　简单遗传算法基本流程图

遗传算法的操作过程详述如下。

2.1　编码(encoding)

利用遗传算法进行问题求解时,首先确定问题的目标函数和变量,然后对变量进行编码。这样做主要是因为在遗传算法中,问题的解是用数字串来表示的,而且遗传操作算子也是直接对串进行操作的。编码方式可分为二进制编码和所谓的实数编码,即十进制编码。　　遗传算法的创始人Holland认为,将一个十进制数利用二进制编码后,其占的位数增多,描述的比较细致,相当于加大了搜索范围,从而能以较大的概率搜索到全局最优解。同时通过一些简单的变换规则就可以逐步地改进这些二进制编码表示的结构,使之往好的方向“进化”,因此,在他的专著中基本上采用这种传统的编码方式。总的说来,采用二进制编码方式有如下优点:它与计算机码制相一致,适于计算机应用;对于码串的每一位,只有1和0两个码值,在交叉和变异等操作中原理清晰,操作简单;表示的变量范围大,如长为L的码串最多可表示2个不同的变量;适合于表示离散变量,而对于连续变量,只要群体总数取足够

[3]多,就可以达到足够的精度。

但是,利用二进制编码方式也存在着缺点。对于一些大规模的多变量的优化问题,如果,L

1998年第1期　　　　　　　　　　　　　遗传算法及其改进·41·长,这就使得遗传操作算子的计算量较大,计算时间增多,同时占用了较大的计算机内存空间;此外,用二进制来表示问题的解,在优化过程中就需要对参数进行编码和译码,以进行二进制和十进制之间的数据转换,这就存在数据之间的转换误差(引入了量化误差),如果目标函数值在最优点附近变化较快的话就可能会错过最优点。因此,采用实数编码的方式被提出。

利用实数进行编码,表示问题的解的数字串将会比用二进制表示的数字串短得多,相应的遗传操作算子的计算量也会减少,所需的计算时间也降低。利用实数编码来表示解,在优化过程中不需对参数进行编码和译码,相应地就不存在解的精度问题。

综上所述,采用实数编码要比二进制编码计算量小,不会存在编码、译码造成的解的误差。但是,具体使用哪种编码方式,要根据实际的优化问题来确定。

2.2　遗传操作

遗传操作是模拟生物基因的操作,它的任务就是根据个体的适应度对其施加一定的操作,从而实现优胜劣汰的进化过程。从优化搜索的角度而言,遗传操作可使问题的解逐代地优化,逼近最优解。

遗传操作包括以下三个基本遗传算子(geneticoperator):选择、交叉、变异。选择和交叉基本上完成了遗传算法的大部分搜索功能,变异增加了遗传算法找到接近最优解的能力。

2.2.1　选择(selection)

选择是指从群体中选择优良的个体并淘汰劣质个体的操作。它建立在适应度评估的基础上。适应度越大的个体,被选择的可能性就越大,它的“子孙”在下一代的个数就越多。选择出来的个体放入配对库(matingpool)中。

目前常用的选择方法有以下几种:

轮盘赌方法(roulettewheelmodel):又称为适应度比例法,是目前遗传算法中最基本也是最常用的选择方法。设群体的大小为N,个体的适应度为fi,则个体i被选择的概率Psi为

Psi=fi/∑Nj=1fj(1)从式(1)可以看出,概率Psi反映了个体i的适应度值在整个群体适应度总和中所占的比例,如前所述,个体的适应度值越大,它被选中的概率就越高,体现了“适者生存,不适者被淘汰”这一自然选择原理。被选中的个体被放入配对库中,随机地进行配对,以进行下面的交叉操作。

最佳个体保存法(elitistmodel):把群体中适应度最高的个体不进行配对交叉而直接复制到下一代。这样做的好处是保证了进化过程中某一代的最优解不被交叉和变异操作所破坏。但这也带来了弊端:局部最优的遗传基因会急速增加而使进化停滞于局部最优解,也就是说,这种方法影响了遗传算法的全局搜索能力。因此,最佳个体保存法通常不单独使用。期望值法(expectedvaluemodel):是对轮盘赌方法的改进。当群体规模不大时,使用轮盘赌方法进行选择操作,在选择过程中存在的随机性可能会产生较大的随机误差,使适应度高的个体被淘汰。为避免这种情况的出现,引入了期望值法:

1计算个体应被选中进行交叉操作的期望值:M=fi/-f=fi/∑fj=1Nj/N

2按期望值M的整数部分安排个体被选中的次数;,

·42·

选满为止。电力系统及其自动化学报　　　　　　　　　1998年第1期

排序选择法(rank-basedmodel):首先根据各个体的适应度大小进行排序,然后基于所排序号进行选择。

竞争法(tournamentselection):个体的选择公式为:fm=max{fi,fj},即随机地选取两个个体,对其适应值进行比较,大的被选中,小的被自然淘汰;如果两个个体的适应值相同,则任意选取其中的一个。被选中的个体放入配对库中。重复此过程,直至配对库中包含N个个体为止。这种方法既保证了配对库中的个体在解空间中有较好的分散性,同时又保证了加入配对库中的个体具有较大的适应值[4]。

窗口方法(windowingmethod):首先求出目前解群中适应值最小的个体,令其适应值为Q。让解群中的每个个体的适应值都减去Q后作为其适应值,再用轮盘赌法形成配对库。采用这种方法时,个体入选配对库的概率虽不与其适应值直接成比例,但关系比较大,与解群中最大的个体与最小的个体的适应值之差以及个体的分散程度有关。

线性标准化方法(linearnormalizationmethod):首先,把目前解群中的个体按适应值大小降序排列,令最大的适应值为U。解群中的其它个体的适应值以V线性递减。再用轮盘赌法产生配对库。V值越大,对解群中优良个体的选择压力越大。

以上讲述的几种选择方式均以适应度为基础进行选择,这就可能在进化过程中导致以下问题:

1在群体中出现个别或极少数适应度值相当高的个体时,采用这类选择机制就有可能导致这些个体在群体中迅速繁殖,经过少数几次迭代后就占满了群体的位置,这样GA的求解过程就结束了,也即收敛了。但这样很有可能是收敛到局部最优解,即遗传算法的不成熟收敛,即“早熟”现象的出现,这是因为搜索的范围很有限。因而一般不希望有个别个体在GA运算的最初几次迭代时就在群体中占据主导地位。

2当群体中个体适应度彼此非常接近时,这些个体进入配对库的机会相当,而且交叉后得到的新个体也不会有多大变化,这样搜索过程就不能有效地进行,这类选择机制有可能趋向于纯粹的随机选择,从而使进化过程陷于停顿的状态,难以找到全局最优解。

针对上述问题,可以采用适应度函数的定标方案来解决。适应度函数的定标方案在2.3中给予论述。另外,还可以采取以下几种提高GA性能的选择方法:

稳态繁殖(steadystatereproduction):就是在迭代过程中用部分优质新个体(子代)来更新目前群体中部分旧个体(父代)后,来作为下一代群体。这样一些优质父代个体在下一代群体中就得以保留。计算表明,这种方法也有助于改善GA的行为,但需合理地确定每次用多少子代个体来取代父代个体。

没有重串的稳态繁殖(steadystatereproductionwithoutduplicates):在形成新一代群体时,使其中的个体均不重复。作法是:在将某个个体加入到新一代群体之前,先检查该个体与群体中现有的个体是否重复,如果重复就舍弃。这种作法会明显改善GA的行为,因为其增大了个体在群体中的分布区域,但增加了计算时间。

2.2.2交叉(crossover)

交叉是指把两个父代个体的部分结构加以替换重组而生成新个体的操作。交叉的目的是为了能够在下一代产生新的个体,就象人类社会的婚姻过程。通过交叉操作,遗传算法的搜索能力得以飞跃性的提高。交叉是GA获取新优良个体的最重要手段。,

1998年第1期　　　　　　　　　　　　　遗传算法及其改进·43·个体进行的。交叉的位置也是随机确定的。交叉率Pc的值一般取的很大,在0.6到0.9之间。交叉算子分为以下几种:

一点交叉(one-pointcrossover):又简称为简单交叉。具体操作是:在个体串中随机地选定一个交叉点,两个个体在该点前或后进行部分互换,以产生新的个体。举例如下

:

图2　一点交叉示意图

两点交叉(two-pointcrossover):与一点交叉类似,只是随机地产生两个交叉点。

多点交叉(multi-pointcrossover):是两点交叉的推广,一般较少使用。

一致交叉(又称均匀交叉)(uniformcrossover):是通过设置屏蔽字(mask)来决定新个体的基因如何继承父代个体中相应的基因。举例如下

:

图3　一致交叉示意图

当屏蔽字位为1时,父代的两个个体相应位互换生成两个新个体的相应位;如果屏蔽字位为0,则父代的两个个体的相应位直接复制给新个体的相应位。

根据不同的问题,可以采用多种不同的交叉方式,如部分匹配交叉、顺序交叉和周期交叉等。对于复杂的多变量问题,一般说来,采用均匀交叉和两点交叉比一点交叉的效果要好。

2.2.3变异(mutation)

变异就是以很小的概率Pm(变异概率,即变异率)随机地改变群体中个体(染色体)的某些基因的值。变异操作的基本过程是:对于交叉操作中产生的后代个体的每一基因值,产生一个[0,1]之间的伪随机数rand,如果rand<Pm,就进行变异操作。在二进制编码方式中,变异算子随机地将某个基因值取反,即“0”变成“1”,或“1”变为“0”。

变异本身是一种局部随机搜索,与选择、交叉算子结合在一起,就能避免由于选择和交叉算子而引起的某些信息的永久性丢失,保证了遗传算法的有效性,使GA具有局部的随机搜索能力;同时使得遗传算法保持群体的多样性,以防止出现未成熟收敛。变异操作是一种防止算法早熟的措施。

在变异操作中,变异率不能取的太大,如果Pm>0.5,遗传算法就退化为随机搜索,而遗传算法的一些重要的数学特性和搜索能力也就不复存在了。

2.3　适应函数定标

遗传算法在进化搜索中基本上不利用外部信息,仅以适应函数为依据,利用群体中每个个体的适应度值来进行搜索。因此适应函数的选取至关重要,直接影响遗传算法的收敛速度以及能否找到最优解[2]。适应函数是由目标函数变换而成的。对目标函数值域的某种映射变换称为适应函数定标。

前文已述,在选择操作时可能会出现以下问题:

1在遗传进化的初期,通常会出现一些超常的个体,若按照比例选择法,这些异常个体因竞

·44·电力系统及其自动化学报　　　　　　　　　1998年第1期小个体的适应度差异以降低选择强度;

2在遗传进化的后期,即算法接近收敛时,由于群体的个体间适应度值差异较小,继续优化的潜能较低,因此此时应放大个体间的适应度值的差异,以提高选择强度,使遗传算法收敛到一更优解。

由于上述问题的存在,使得有必要进行适应函数定标。适应函数定标应满足以下基本要求:

1遗传算法搜索最大值的要求。遗传算法搜索的目标是全局最大值,因此对于求解极小值的最优问题应进行转换,将最小化问题转换为最大化问题,形成目标函数,以便进行适应函数定标。

2适应度非负的要求。这是以适应度评估为基础的选择操作的基本要求。因为概率值不可能出现负值。

常用的定标方式有以下几种:

线性定标[1]:假设原适应度函数为f,定标后的适应度函数为f',则线性定标可用下式表示:　　　　　　　　　　　f'=af+U

式中的系数a和U的设定方式有多种,但是要满足下面两个条件:

1原适应度的平均值favg要等于定标后的适应度的平均值f'avg,以保证适应度等于平均值favg的个体在下一代中的期望复制数为1,即f'avg=favg;

*2定标后的适应度最大值f'max要等于原适应度平均值favg的指定倍数cmult,即fmax=cmult'*

favg,以控制适应度最大的个体在下一代中的复制数量。试验表明,cmult可在1.2～2.0范围内取值。根据以上条件可确定a和U

multavgmaxmultavgavg　　T=　　　　　U=fmax-favgfmax-favg

如图4a)所示,线性变换调整了原始适应度之间的差距,保持了群体内个体的多样性,并且计算简便,易于实现。按上述系数a和U进行线性变换时,如果群体内某些个体的适应度远远低于平均适应度时,有可能会出现定标后的适应度值为负的情况,如图4b)所示。为此,考虑到保证最小适应度值fmin为非负的条件,进行如下调整,见图4c)所示:

　　T=avgminavg　　　　　U=favg-fminfavg-f

min

图4线性定标

幂函数定标:其定标公式为:　　f'=fK

式中的幂指数K与所求的最优化问题有关,其取值需在理性分析的基础上,结合一些试验进行一定程度的精细调整才能获得较好的结果。该定标方式由Gillies提出,他在机器

1998年第1期　　　　　　　　　　　　　遗传算法及其改进·45·指数定标:其定标公式为:　　　f'=exp(-β*f)

这种调整方法的基本思想来源于模拟退火过程(simulatedannealing,SA)。其中系数b决定了复制的强制性,其值越小,复制的强制就越趋向于那些具有最大适应度的个体。3　遗传算法的数学机理

从上述内容可以看出,遗传算法的执行过程中包含了大量的随机性操作,因此有必要对其数学机理进行分析。为此首先引入“模式”(schema)这一概念。

3.1　模式定理

我们将群体中的个体即基因串中的相似样板称为“模式”,模式表示基因串中某些特征位相同的结构。在二进制编码的串(即个体)中,模式是基于三字符集{0,1,}的字符串,符号*表示任意字符,或“0”或“1”。一个长度为L的串包含着2L个模式。遗传算法中串的运算实际上就是模式的运算。

模式中包含两个重要的参数:模式阶(schemaorder)和定义距(defininglength)。定义1　模式H中确定位置的个数成为模式H的模式阶,记做O(H)。

模式阶用来反映不同模式间确定性的差异。模式的模式阶数越高,模式的确定性就越高,所匹配的样本的个数就越少。

定义2　模式H中第一个确定位置和最后一个确定位置之间的距离称为该模式的定义距,

记做δ(H)。

在遗传操作中,即使阶数相同的模式,也会有着不同的性质,而模式的定义距就反映了这种性质的差异。

对于某种模式,在下一代群体中将会有多少个体与这种模式匹配呢?模式定理【8】给出了答案。

模式定理:在遗传算子选择、交叉、变异的作用下,具有低阶、短定义距以及平均适应度高于群体平均适应度的模式在子代中将呈指数增长。用公式可表示为:-c·m　　　　m(H,t+1)≥m(H,t)··(1-Pfl-1-O(H)·P)

式中,m(H,t)——表示在t代群体中存在模式H的个体的数目;

　-f(H)——表示在t代群体中包含模式H的个体的平均适应度;

　　-f——表示t代群体中所有个体的平均适应度;

　　l——表示个体的长度。

在统计确定理论表明,要获得最优的可行解,必须保证较优解的样本数呈指数增长。模式定理是遗传算法的基本理论,保证了较优的模式(遗传算法的较优解)的数目呈指数增长,为解释遗传算法机理提供了一种数学工具。

3.2　积木块假设[18]

在模式定理中所指的具有低阶、短定义距以及平均适应度高于群体平均适应度的模式被定义为积木块(buildingblock),它们在遗传算法中非常重要,在子代中将呈指数增长,在遗传操作下相互结合,产生适应度更高的个体,从而找到更优的可行解。

积木块假设(buildingblockhypothesis):低阶、短距、低平均适应度的模式(积木块)在遗传,*

·46·电力系统及其自动化学报　　　　　　　　　1998年第1期　　目前大量的实践证据支持积木块假设,它在很多领域中都取得了成功,例如平滑多峰问题、带干扰多峰问题以及组合优化问题等。

综上所述,模式定理保证了较优模式(遗传算法的较优解)的样本数呈指数增长,从而满足寻找最优解的必要条件,即遗传算法存在着寻找到全局最优解的可能性;而积木块假设指出,遗传算法具备寻找到全局最优解的能力,即积木块在遗传算子的作用下,能生成高阶、长距、高平均适应度的模式,最终生成全局最优解。上述结论是基于模式定理对遗传算法的全局收敛性问题进行的定性的分析。但是最近基于马尔科夫链的定量的数学证明认为,简单遗传算法不是全局收敛的,而带最优个体保留的遗传算法是全局收敛的[5]。但后者的结论建立在搜索时间趋向无穷且把变异操作作为主要搜索的基础上。实质上的遗传算法的主要搜索工具是交叉操作。在文献[6]中应用齐次有限马尔科夫链严密证明了简单遗传算法不是全局收敛的,带有最优个体保留的遗传算法是全局收敛的。

4　遗传算法的特点及其应用

由上可以看出,遗传算法利用了生物进化和遗传的思想,所以它有许多与传统优化算法不同的特点:

a遗传算法利用目标函数变量的编码(个体)进行进化,而不像传统方法用变量本身。遗传算法是在求解问题的决定因素可控制参数的编码串上进行操作,从中找出高适应度值的个体,而不是对函数和它们的控制参数直接操作,它不受函数约束条件(如连续性、导数存在、单极值等)的限制。

b遗传算法在解空间中从多点寻找问题解,而不像某些传统方法从某一点寻找解。在最优化问题中,传统的方法是从一个点开始搜索,如登山法,若一个细微变动能改善质量,则沿该方向前进;否则取相反方向。然而复杂问题会使“地形”中出现若干“山峰”,传统的方法很容易走入假“山顶”;而遗传算法同时从群体的每个个体开始搜索,象一张网罩在“地形”上,数量极大的个体同时在很多区域中进行采样,大大地减小了陷入局部解的可能性。

c遗传算法直接应用目标函数的函数值信息(即适应度值),而非函数的导数或其它辅助信息。传统搜索算法需要一些辅助信息,如梯度法需要导数,当这些信息不存在时,这些算法就失败了;而遗传算法只需目标函数和编码串,因此遗传算法几乎可以处理任何问题。

d遗传算法引用了概率转换规则,而不采用确定性的转换规则指导搜索,因此能搜索离散的有噪声的多峰值复杂空间。

e遗传算法使用随机操作,但并不意味着遗传算法是简单的随机搜索,它具有一定的方向性,它使用随机工具来指导搜索向着一个最优解前进,它的方向性使得它的效率远远高于一般的随机算法。

f遗传算法在解空间内进行充分的搜索,但不是盲目的穷举或试探,因为选择操作以适应度为依据。因此它的搜索时耗和效率往往优于其它优化算法。

g遗传算法具有隐含的并行性(implicitparallelism)。隐含的并行性与并行性不是同一概念。遗传算法的隐含的并行性是指:遗传算法在搜索空间里使用相对少的个体,就可以检()

1998年第1期　　　　　　　　　　　　　遗传算法及其改进·47·是指虽然每一代只对N个个体操作,但实际上处理了大约O(N3)个模式。基于模式定理,可得出每次遗传有效保留的模式为O(N3)的估计[9],从而证明了遗传算法的隐含并行性。隐含并行性是遗传算法优于其它求解过程的关键所在。另外,遗传算法的隐含并行性还有助于处理非线性问题。

h遗传算法最适合于搜索复杂地区,从中找出期望值高的区域,但在解决简单问题时效率并不是很高。正如遗传算法的创始人Holland所指出的“如果只对几个变量作微小的改动就能进一步改进解,则最好能另外使用一些更普遍的方法,来为遗传算法助一臂之力”。[2]　　遗传算法随着计算机技术的高速发展已经引起人们越来越多的注意,并已经应用于求解许多领域中的难题,并取得了卓越的成就。在许多情况下,遗传算法表现得优于传统的优化设计。其主要应用领域有:问题及函数的优化求解、机器学习、模式识别、图象处理、工业优化控制、自适应控制;与其它算法的结合,如模拟退火和神经网络等等多方面。近年来,遗传算法在电力系统中也得到了广泛的应用,如利用遗传算法进行PID参数的优化设计、将遗传算法用于电力系统规划设计[8、9,10、14]、无功优化的实现[11、12、13]、以及电力系统中的故障信息诊断[4]等。[7][1]

5　自适应遗传算法及其改进

前文已述,Pc和Pm的选择是影响遗传算法行为和性能的关键所在,直接影响算法的收敛性,这一点已早为人所承认。另外,遗传算法用来求解多峰函数最优化问题时应具备两方面的能力:一是局部搜索能力,即在确定包含最优解的区域后能够收敛于最优解(局部或全局);二是全局搜索能力,即在全局最优解的搜索过程中能够探索新的解空间区域。这两方面的均衡是由Pc和Pm来保证的。

我们已经知道,交叉概率Pc控制着个体进行交叉的速率。Pc越大,新个体产生的速度就越快。然而当Pc过大时,个体被破坏的可能性就会增加,使得具有高适应度值的个体结构很快被破坏;但是如果Pc过小,会使搜索过程缓慢,以致停滞不前。对于变异概率Pm,如果Pm过小,就不易产生新的个体结构;如果Pm取值过大,那么遗传算法就变成了纯粹的随机搜索算法。针对不同的优化问题,需要反复实验来确定Pc和Pm,这是一件很繁琐的工作,而且很难找到适应于每个解的最佳值。因此,如何选取Pc和Pm成为很重要的问题。　　在简单遗传算法中,由于Pc和Pm取为恒定值,因此用于复杂的多变量优化问题时,效率不高,并且存在“早熟”的可能性。基于上述原因,文献[15]提出了一种“自适应遗传算法(AdaptiveGeneticAlgorithm,简写为AGA)”。在自适应遗传算法中,Pc和Pm基于个体的适应度值来自适应地进行改变。当群体有陷入局部最优解的趋势时,就相应地提高Pc和Pm,当群体在解空间发散时,就降低Pc和Pm。同时,对于适应值高于群体平均适应值的个体,对应于较低的Pc和Pm,使该解得以保护进入下一代;而低于平均适应值的个体,相对应于较高的Pc和Pm,使该解被淘汰掉。因此,自适应的Pc和Pm能够提供相对某个解的最佳Pc和Pm。自适应遗传算法在保持群体多样性的同时,保证遗传算法的收敛能力,有效地提高了遗传算法的优化能力。,

·48·

k1(fmax-f′)　　　电力系统及其自动化学报　　　　　　　　　1998年第1期　　　　Pc=/

/　　　　≥favg(fmax-favg)　　　f′(2)2f<favg

k3(fmax-f)　　　　　　　f≥favg　　　(fmax-favg)　　　　Pm=(3)

k4f<favg

式中:　　　fmax——代表群体中最大的适应度值;

　　　　favg——代表每代群体的平均适应度值;

　　　　f'——代表要交叉的两个个体中较大的适应度值;

　　　　f——要变异个体的适应度值。

这里,只要设定取k1,

k3,k2,k4(在[0,1]取值)的值,Pc和Pm就可以自适应地进行调整了。　　对公式(1)和(2)进行分析表明:适应度与交叉率和变异率呈简单的线性映射关系,如图5所示。在图5中,k1=k2=k,k3=k

4=k',

图5　自适应遗传算法

当适应度低于平均适应度时,说明该个体是性能不好的个体,对它就采用较大的交叉率和变异率;如果适应度高于平均适应度,说明该个体性能优良,对它就根据其适应度值取相应的交叉率和变异率。可以看出,当适应度值越接近最大适应度值,交叉率和变异率的值就越小;当等于最大适应度值时,交叉率和变异率的值为零。这种调整交叉率和变异率的方法对于群体处于进化后期时比较合适,这是因为在进化后期,群体中每个个体基本上表现出较优的性能,这时不宜对个体进行较大的变化以免破坏了个体的优良性能结构;但是这种调整方式对于群体处于进化初期阶段就使得进化过程略显缓慢,因为在进化初期阶段群体中的较优良的个体几乎处于一种不发生变化的状态,而此时的优良个体不见得是优化问题的全局最优解,这容易使进化走向局部最优解的可能性增加。

为此,在本文中,对文献[15]提出的自适应遗传算法加以改进,具体如下:

图6　改进的自适应遗传算法

1998年第1期　　　　　　　　　　　　　遗传算法及其改进·49·　　在改进的自适应遗传算法中,对应于群体中最大适应度值的个体的交叉率和变异率分别取为图6中所示的Pc2和Pm2,这就相应地提高了群体中表现优良的个体的交叉率和变异率,使得它们不会处于一种近似停滞不变的状态。为了保证每一代中的优良个体不被破坏,采用最优个体保存方法,使它们直接复制到下一代中。

,对应于图6所示的交叉率和变异率的改进公式如下:

c1c2Pc1-·(f'-favg)　　　　f≥'favgfmax-favg　　　　Pc=

Pc1f'<favg

m1m2Pm1-·(fmax-f)　　　　f≥favgfmax-favg　　　　Pm=

Pm1f'<favg

式中的各符号意义同前不变。其中Pc1=0.9,Pc2=0.6,Pm1=0.1,Pm2=0.001。

6　算例

为了与简单遗传算法(SGA)、自适应遗传算法(AGA)进行比较,本文对如下5种优化问题进行了计算。这5种问题均为极小化问题。在进行计算中,每种算法均采用前文所述的线性定标方法对适应度函数进行了变换;在选用轮盘赌选择方法的同时,对最优个体进行保留,直接复制到下一代。

a神经网络的权值训练。针对异或XOR问题,采用三层前传神经网络,取输入层节点数为2,隐含层节点数为2,输出层节点数为1,训练样本数为4。这样待训练的权值和阈值的个数为9。采用二进制编码方式,每个权值表示为8位的二进制码。群体数目为30。目标函数为

2∑　　f0=2∑(t(i,j)-y(i,j))j=1i=1

其中:　　　t(i,j):表示网络中第j个样本中输出层第i个节点的理想输出值;

　　　　y(i,j):表示网络中第j个样本中输出层第i个节点的实际输出值;　　　　　　np:训练样本数;

　　　　no:输出层的节点数。

3npno(4)(5)

b　f1(X)=∑i=2i　　　　　-6.0≤xi≤6.0x1

22*(x21-x2)+(1-x1)　　　　　-6.0≤xi≤6.0c　f2(X)=100

5

d　f3(X)=30+∑i=1[xi]　　　　　-6.0≤xi≤6.0

25

+e　f4(X)=0.002∑j=1j+∑2　　　　　-65.≤xi≤65.

i=1(xi-aij)6

其中,函数f1是简单平方求和函数,在点(0,0,0)具有极小值;f2称为Rosenbrock-Chebyquad函数,它是一个经典的单峰病态函数,难于极小化,对应于最小值的点是(1,1);f3中的[x]表示不大于x的最大整数,这使得f3成为一个平台型不连续函数,它在5维空f,[20]

　a1j={-32,-16,0,16,32,-32,-16,0,16,32,-32,-16,0,16,32,-32,-16,0,16,32,-32,-16,0,16,32}

　a2j={-32,-32,-32,-32,-32,-16,-16,-16,-16,-16,0,0,0,0,0,16,16,16,16,16,32,32,32,32,32}

计算结果如图7所示。从图7中可以看出,本文所提出的改进方法总是以很快的速度收敛到全局极小点。

图7　计算结果比较

7　结论

遗传算法作为一种基于自然选择和群体遗传机理的全局优化搜索算法,具有很多优点。但是简单遗传算法由于其交叉率和变异率保持恒定不变,使得算法收敛速度较慢,有可能会出现“早熟”现象。本文提出的改进的自适应遗传算法与简单遗传算法、自适应遗传算法相比,明显地提高了算法的收敛速度。通过对几种典型的优化问题的计算证明了这一点。

参考文献

1　D.E.Goldberg,GAsinSearch,OptimizationandMachineLearning,AddisonWesley,19892　张晓缋,戴冠中,徐乃平,一种新的优化搜索算法——遗传算法,控制理论与应用,Vol.12,No.3,Jun.,1995

3　周双喜,蔡虎,应用于无功优化的遗传算法中的编码问题,全国高等学校电力系统及其自动化专业第十二届学术年会论文集,1996,河北保定

4　文福拴,邱家驹,韩祯祥,只利用断路器信息诊断电力系统故障的高级遗传算法,电工技术学报,1996.4,Vol.11,No.2

5　恽为民,席裕庚,遗传算法的运行机理分析,控制理论与应用,1996.6,Vol.13,No.3

6　恽为民,席裕庚,遗传算法的全局收敛性和计算效率分析,控制理论与应用,1996.8,Vol.13,No.47　苏小林,阎晓霞,基于遗传算法的PID参数优化技术,电力系统及其自动化学报,1997.6,Vol.9,No.2

8　岑文辉,赵庆,戴文祥,基于遗传算法的外来电源落点选择,电力系统自动化,1995.2,Vol.19,No.29　张俊芳,王秀丽,王锡凡,遗传算法在电网规划应用中的改进,全国高等学校电力系统及其自动化专业第十二届学术年会论文集,1996,河北保定

10蔡超豪,王奇,电网优化规划的新算法——遗传算法,电力建设,1997年第3期

11周双喜,杨彬,实现无功优化的新算法——遗传算法,电力系统自动化,1995,11,Vol.19,No.1112马晋韬,i,杨以涵,遗传算法在电力系统无功优化中的应用,中国电机工程学报,1995.9,Vol.15,No.5

13　KenjiIba,ReactivePowerOptimazationbyGeneticAlgorithm,IEEETrans.onPowerSystems,Vol.9,No.2,May1994

14　KwangY.Lee,XianminBai,Young-MoonPark,OptimizationMethodforReactivePowerPlanningbyUsingaModifiedSimpleGeneticAlgorithm,IEEETrans.onPowerSystems,Vol.10,No.4,Nov.1995

15　M.Srinivas,L.M.Patnaik,AdaptiveProbabiltiesofCrossoverandMutationinGeneticAlgorithm,IEEETrans.onSMC,Vol.24,No.4,April1994

16　孟庆春,贾培发,关于Genetic算法的研究及应用现状,清华大学学报(自然科学版),1995年第35卷,第5期,第44～48页

17　焦李成,保铮,进化计算与遗传算法,系统工程与电子技术,1995年第6期

18　陈国良等,遗传算法及其应用,人民邮电出版社,1996

19　曾颖,具有FACTS设备的输电网络规划,天津大学硕士学位论文,1997年12月

20　文劲宇,华中理工大学博士学位论文,1998年3月

GENETICALGORITHMANDITSMODIFICATION

DuanYuqian　HeJiali

(DeptartmentofElectricalEngineering,TianjinUniversity,Tianjin,300072)

Abstract

Inthispaper,wefirstintroducedanddiscussedindetailtheGeneticAlgorithm(GA)onitsorigin,itsbasicprinciple,itsmathematicsmechanismanditscharacteristicsandap-plication.InordertoimprovetheconvergenceofGA,consideringthatitisdifficulttochoosetheprobabilityofcrossover(Pc)andmutation(Pm),anAdaptiveGeneticAlgo-rithm(AGA)inwhichPcandPmwerevarieddependingonthefitnessvaluesofthesolu-tionswassimplyintroduced.Afteranalyzingitsdeficiency,amodifiedmethod----Modi-fiedAdaptiveGeneticAlgorithm(MAGA)waspresentedinthispaper.Finally,wecom-paredtheperformanceoftheMAGAwiththoseoftheothermethodsusingseveralopti-mizationproblems.ResultsshowedthatMAGApresentedinthispapergreatlyimprovedtheperformanceofconvergencetotheglobaloptimum.

Keywords:　GeneticAlgorithm,　AdaptiveGeneticAlgorithm

本文来源：https://www.bwwdw.com/article/byc1.html