第27卷第4期2006年7月 微计算机应用
MICROCOMPUIERAPPLICATIONS
July.2006
Vol.27No.4
自适应遗传算法的改进与应用
史明霞1,2 陶林波1 沈建京1
(1信息工程大学理学院电子信息工程系 郑州 450007
2
河南省轻工业职工大学 郑州 450002)
摘 要:针对遗传算法易出现早熟现象,通过对标准遗传算法和自适应遗传算法的分析研究,本文对自适应遗传算法
进行了改进。即在保留以往自适应遗传算法优点的同时,设计了与种群个体分布及种群规模的波动情况相关的自适应遗传算子。实验结果表明:该算法不易陷入局部极值,收敛速度快。关键词:遗传算法 早熟现象 自适应遗传算子 改进的自适应遗传算法 中间区域
ImprovementandApplicationofaSelf-GeneticSHIMingxia1,2,TAOLinbo11
(1InformationEngineeringUniversity,Zhengzhou,,Zhengzhou,450002,China)
Abstract:Aninpaper,forstandardgeneticalgorithmbringseasily-geneticoperatorconcerningpopulationsizeandpopula2tionongeneticalgorithm.Ithasincreasedthealgorithm‘scapacityofglobalconvergence.Experimentaldemonstratethatitdoesnoteasilygetstuckatalocaloptimum,andthatitisfastinconvergence.Keywords:geneticalgorithm,prematureconvergence,self-adaptivegeneticoperator,improvedadaptivegeneticalgo2rithm,middlearea
1 引言
在简单遗传算法中,其运行参数都人为地预先指定,这样使得遗传操作的适应性较差,在解决复杂问题或解空间很大时,会发生收敛速度慢或局部收敛的情况。为此,提出了自适应遗传算法,主要思想是在进化的过程中根据进化的不同阶段建立相应的交叉概率及变异概率,这种做法在一定程度上改善了算法的搜索能力和收敛速度,但很多具体的问题还没有考虑,以致于对问题的解决过于固定化。这里我们在原有的基础上又考虑了种群中个体的分布情况以及种群规模的变化情况。从而真正在进化的过程中动态调整交叉概率与变异概率,以达到克服过早收敛以及加快搜索速度的目的。
2 遗传算法的主要要素及分析
基本遗传算法的构成要素:①染色体编码方法;②个体适应度的评价;③设计遗传算子;④基本遗传算法有关的运行参数的确定。
可见,编码方法、遗传算子的设计及运行参数是构造遗传算法时需要考虑的主要问题。编码方法对遗传操作中的交叉和变异算子的搜索能力都具有一定的影响。选择算子就是从
本文于2006-03-29收到,2006-05-15收到修改稿。
父代群体中选择个体遗传到下一代。选择策略对算法有着举足轻重的作用,不同选择策略导致不同的选择压力。较大的选择压力使最优个体具有较高的复制数目,适应值较小的个体迅速死亡,种群的多样性遭到破坏,从而使得算法的搜索空间减小,容易出现早熟现象。较小的选择压力使群体保持足够的多样性,提高算法收敛到全局最优解的概率。可是算法的随机性增强,收敛速度较慢。交叉算子的作用非常重要。一方面,它使得在原来的群体中的优良个体的特性能够在一定程度上保持;另一方面,它使得算法能够探索新的基因空间,从而使新的群体中的个体具有多样性。变异算子使得遗传算法有局部的随机搜索能力,且可使遗传算法维持群体的多样性。另外,群体规模对遗传算法效能的发挥也有影响。群体规模越大,群体中个体的多样性越高,算法陷入局部解的危险越小。但群体规模太大,算法的计算量也增大。但在影响遗传算法的诸多因素中交叉和变异概率对遗传算法的影响最大。较大的交叉概率会以较大的速度引入新解到群体中,同时又很可能破坏群体中已经产生的优质解。大的变异概率会表现为随机漫游,小的变异概率又会有早熟收敛的风险。算法的开发和利用能力一定程度上由交叉概率和变异概率所控制。算法的开发能力和利用能力的协调是一个动态的过
406
微计算机应用
2006年程,交叉概率和变异概率需要随着算法的进行而动态变化。
3 自适应遗传算法
简单遗传算法由于交叉与变异概率不能反映进化的过程,从而容易出现早熟或随机漫游的现象。
检测算法收敛的一个可行的方法是观察群体的平均适应度 f与最大适应度fmax的差值fmax- f,群体收敛到一个最优解时的fmax- f比群体中个体分散时的fmax- f要大。因为群体收敛到一个局部最优解时交叉和变异概率要增大才能使群体从局部最优解中尽快摆脱出来。所以有
pc=
pm=
fmax- ffmax- f
针对遗传算法的早熟问题,对自适应遗传算法做以下改
进。算法主要是对前面的自适应遗传算法的交叉概率和变异概率加以改进,但还考虑了它们与种群规模、编码方式、以及基因位上各种模式的关系。同时本文除了考虑采用动态的交叉与变异概率外,还考虑了每代个体的分布情况,通常的做法是保留优秀的个体到下一代,我们也继承这个原则,不过我们还要考虑在平均值附近分布的个体的去留问题,因为以往的文章很少考虑这点,原因在于过多的考虑优点比较突出的个体,其实有些适应度略低于平均适应度的个体,仍有保留的价值,
至少有交配到下一代的机会。
当群体进入局部最优解时,pc,pm增大,又有可能破坏群体中优质解,算法不易收敛到最优解。因此,的个体其交叉和变异概率应该不同。和变异概率应该较小,该较大。,ffmax的差越小,,能保护优质解。和全局收敛性之间的矛盾,提出了一种新的改进遗传算法。该改进算法设计了与进化代数相关的交叉概率,与个体适应度相关的变异概率。
其中f′是两个交叉个体中适应度较大的个体的适应度,为防止交叉和变异概率大于1,将交叉和变异概率修改为
pc= f′≥ f
fmax- f
pc=k2 f′
l
图1 群体中个体的分布情况图
图1是一群体中个体的分布情况,可见大部分个体都分
布在一个狭长的区域内,说明这是一个稳定的群体,如果要想在这个群体中找到优质解是很困难的,但并不排除它的后代能产生优质解。我们可采用轮盘赌的方法在中间区域随机抽取父代进行交配,同时采用多点交叉来产生子代1和子代2。如果产生的子代的适应度已高出中间区域而接近上界,则说明该父代含有优秀的模式,可以复制到下一代中继续进行交配;如果没有产生明显的优秀子代,则说明它们的子代不会很突出,从而淘汰这样的父代及它们产生的子代。
至于前面谈到的分布情况与交叉概率和变异概率的关系,我们可以这样想,如果中间个体很少或分布很稀疏,说明它们不是一个稳定的集中的群体,它们被考虑的概率要减小,同样它们被交叉和变异的概率也要减小,不然可能会产生很多不必要的干扰。相反,如果中间区域的个体很多或分布比较集中,则说明该群体比较稳定、集中,则它们被考虑的概率也要相应增大,即增大该区域值的选择概率。但我们要从中得到突出的解,就必须破坏它们的这种稳定性,必须采用比较大的交叉概率和变异概率。
综上所述,我们对自适应遗传算法作如下改进:
首先定义群体的直径:H=fmax-fmin;然后定义个体到平均值点的距离:h=f- f
然后重点考虑这些点在中间区域的分布情况,所谓中间
)(δ是邻域半径)。通过计算h与δ的关区域就是邻域U( f,δ
系来确定该点是否在中间区域,然后确定中间区域点的数量
N,中间区域在群体中的密度d=
和中间区域外的密度d1M
pm=
n
其中k1,k2≤1
但这种算法同样存在它不利的一面,因为这种算法对于进化后期还比较合适,而对于进化的前期就很不利。因为在进化的一开始,一些适应度较为突出的个体就处于一种几乎不变化的状态,从而使群体中的其他个体很快被淘汰,加快了群体的收敛速度,但群体很难收敛到最优解,从而出现早熟收敛。因此将交叉概率与变异概率修改为
pc=pc1-,f′≥favg
fmax-favg
pc=pc1,f′
pm=pm1-,f≥favg
fmax-favgpm=pm1,f
这里0
4 改进的自适应遗传算法4.1 算法的改进
=
。可通过d得出群体中个体在中间区域及中间区域M
3期史明霞等:自适应遗传算法的改进与应用
ρρ
ρρ
ρρ
ρρ
407
外部的密度。因此将交叉概率和变异概率修改为
其中f′是两个交叉个体中适应度较大的个体的适应度,为防止交叉和变异概率大于1,将交叉和变异概率修改为
pc=, d≈d1,f′≥ f
fmax- f
pc=k2,f′
pc=d,
fmax- f
δ,d>>d1或d1>>d f′≤ h≤f
(1-d),pc=
fmax- f
h>δ,d>>d1或d1>>d f′≤ f
δ,d>>d1或d1>>d,f′
pc=k2(1-d),h>δ,d>>d1或d1>>d,f′
l
)P{X(n+1)IBC≠Φ/X(n)=X}≤ an (XIBC=Φ)P{X(n+1)IBC≠Φ/X(n)=X}≤ an (XIBC=Φ
且满足条件:
∞
(1)
n=1
∑(1-
b n)=∞
(2) an(1-b n)→0
ρ
则{X(n)}概率强收敛到全局最优解集M.
该定理由定理1和本定理的条件可证出。
ρ
定理3:对于最佳个体选择遗传算法,{X(n)}概率强收敛到全局最优解集的条件是:
∞
pm=
l
n
()
,d≈d1
n=( an)pm=
l
n
δ,d1>dd,h≤
NN1
nan>0
n→∞
pm=
(
>>d1或d1>>dn
(3)lim
=0,lim=0
n→∞dnn→∞dn
n
(X,X);X:S}其中,an=min{Pm
n
(X,Y);X≠Y}dn=min{Pm
n
(X,Y);X≠Y}bn=max{Pm
n
(X Y,X);X,Y:S} an=min{Pm
在本文的算法中,对于最佳个体选择遗传算法
nd(X,Y)(X,Y)=pn取 Pm・(1-pn)l-d(X,Y)d(X,Y)=|{k∶Xk≠Yk(k≤l)}|(l为个体的长度)
其中k1,k2≤1。
4.2 算法的收敛性证明
设S为个体空间,N为种群规模,E=SN为种群空间,P为SN上的概率分步,{X(n)}为SN上的种群马尔可夫链序列,M为全局最优解集,B为任意满意解集,BC为非满意解。记
BCα≠Φ/X(n)IBC=Φ}n=P{X(n+1)IB
BCβ≠Φ/X(n)IBC≠Φ}n=P{X(n+1)IB
Bα n是指在X(n)已进入满意解集时下一步脱离满意解集B
的概率,βn是指在X(n)未进入满意解集时下一步仍未进入满意解集的概率。
ρ
ρρ
ρρ
ρ
ρ
显然,bn=pm(1-pm)l-1;dn=(pm)l;an=1-pm对于单点随机杂交
hpc/l, Z≠Xn
Pc{X Y,Z}=
(1-pc)+hpc/l,Z=X
)有 an=1-pc,(pc是交叉概率,pm是变异概率。
根据上述定理3知,当满足下列条件
(1)limpm=0
n→∞
ρ
n→∞
ρ
定义:若limP{[X(n)
ρ
(2)N>l
∞
到全局最优解集。记作X(n)→M(P.S)。
BBαβ定理1:若{n},{n}满足
∞
(3)(4)
ρ
n=1
∑p
∞
c
(1)
n=1
∑(1-β)
B
n
=∞
n=1
∑p
lm
Bα(2)lim=0Bn→∞1-βn
ρ
时,{X(n)}概率强收敛到全局最优解集。
本文的遗传算法中,
pc=
ρ
则{X(n)}概率强收敛到满意解集B,即
ρ
limP{[X(n)
n→∞
,d≈d1,f′≥ f
fmax- fpc=k2,f′
d,
fmax- f
ρ
若对任意满意解集B,{X(n)}概率强收敛,则,{X(n)}概率强
收敛到全局最优解集M.
定理2:若对于任意满意解集B有
δ,d>>d1或d1>>d,f′≥ h≤f
408
pc=
(1-d),
fmax- f
微计算机应用
2006年h>δ,d>>d1或d1>>d,f′≥ f
δ,d>>d1或d1>>d,f′
pc=k2(1-d),h>δ,d>>d1或d1>>d,f′
l
pm=
l
n
,d≈d1
pm=
l
n
δ,d>>d1或d1>>dd,h≤
异。为了比较,算法中取种群规模m=80,最大进化代数T=
200进行计算100次,89次都可搜索到全局最优解,平均进化到185代就可得到最优解,平均计算时间为0.7秒。
采用本文改进的自适应遗传算法,其特点是浮点数编码、比例选择和最佳保留策略、随机配对、单点交叉、自适应遗传算子、均匀变异。为了比较,算法中,取种群规模m=80,最大进化代数T=200进行计算100次,每次都可搜索到全局最优,平均进化到165代就可得到最优解,平均计算时间为0.3秒。
6 结束语
pm=
(
1-d),h>δ,d>>d1或d1>>dn
k1,k2,≤1.其中f′是两个交叉个体中适应度较大的个体的
适应度.随着迭代步数n的不断增加,f愈来愈接近于fmax,所以
limpm=0成立。N>l容易满足。
n→∞
取k1=k2=因为级数
2
。
∞
n=1
n
∞
n=1
,n=1
p
lm=∞成立;
又因为级数
∞
n=1
∑n
p
当p>1时收敛,而pcn2
,所以
∑p
c
5 仿真实验分析
实例Shubert函数的全局最优化计算
5
minf(x1,x2)={
5
i=1
∑i・cos[(i+1)x
2
1
+i]}×
{
i=1
∑i・cos[(i+1)x
+i]}
s.t.-10≤xi≤10 (i=1,2)
该函数的最优解为-186.731,Holland建立的标准(或简单)遗传算法,其特点是二进制编码、赌轮选择方法、随机配对、一点交叉、群体内允许有相同的个体存在。取种群规模m=80,交叉概率pc=0.95、变异概率pm=0.05,最大进化代数T=200,每个变量用串长为L=16的二进制子串表示。二进制编码比浮点编码遗传算法计算精度低,对于标准遗传算法在规定的进化代数内,根本得不到最优解。若以目标函数小于-100为搜索成功,标准遗传算法运行100次。当取最大进化代数为T=200时,11次搜索到全局最优,平均计算时间为0.51秒;当取T=500时,51次(以概率0.51)搜索到全局最优,平均计算时间为1.13秒。
采用自适应遗传算法,其特点是浮点数编码、比例选择和最佳保留策略、随机配对、单点交叉、自适应遗传算子、均匀变
实验结果表明,,收敛速度快,
且实现简单。。algorithmpa2
logiccontrollers.In:HerreraF,JL,eds.GeneticAlgorthmsandSoftCompu2ting.Physica-Verlag(StudiesinFuzzinessandSoftCom2puting,Vol.8),1996.95～125
2 AnfelinePJ.Adaptiveandself-adaptiveevolutionary
computations.In:PalaniswamiM.AttikiouzelY,MarksR,FogelDB,FukudaT,eds.ComputationalIntelli2gence:ADynamicsystemsPerspetive.IEEEPress,1995.152～1633 周明,孙树东.遗传算法原理及应用.北京:国防工业出版社,200214 阎平凡,张长水.人工神经网络与模拟进化计算.北京:清华大学出版社,20021
5 KalyanmoyDebandHans-GeorgBeyerSelf-adaptive
GeneticAlgorithmswithSimulatedBinaryCrossover,Ev2olutionaryComputation,2001,9[2]
6 HajimeKita,AComparisonStudyofSelf-Adaptionin
EvilutionStrategizesandReal-CodedGeneticAlgo2rithms.EvolutionaryComputation,2001,9[2]7 韩万林,张幼蒂.遗传算法的改进.中国矿业大学学报,
2000,1,102～105作者简介
史明霞,女,(1967-),硕士研究生,主要从事计算智能及运筹学方面的研究。
陶林波,男,(1979-),硕士研究生,主要从事计算智能及语义分析方面的研究。
沈建京,男,(1961-),教授、博士生导师,研究方向为人工智能。