第34卷第4期
东南大学学报(自然科学版)
Vol.34No.4变异率和种群数目自适应的遗传算法
熊 军 高敦堂 都思丹 沈庆宏
(南京大学电子科学与工程系,南京210093)
摘要:提出了针对个体变异率和种群数目的2种自适应方法.算法中个体变异率根据其适度值
在种群中的排序自适应调整,使优良个体具有较小的变异率继续进化,而使种群中较差个体具有较大变异率,增强了种群搜索能力.同时根据种群个体适度值方差动态调整变异率曲线,种群数目调整则根据最优个体更新率动态增大,以动态适应解空间的规模避免采样误差造成的进化停滞.通过在不同尺度的NKLandscape上与传统的简单遗传算法(SGA)比较可得的引入对遗传算法的寻优能力有了明显改进.关键词:遗传算法;变异率;种群数;自适应中图分类号:O224 文献标识码:A :-0505(204
Gprobability
sizeadaptation
XJun GaoDuntang DuSidan ShenQinghong
(DepartmentofElectronicScienceandEngineering,NanjingUniversity,Nanjing210093,China)
Abstract:Twoparameteradaptationmethodsarepresentedforgeneticalgorithm.Mutationprobabilityis
assignedtoeachindividualaccordingtoitssortorderoffitnessinthepopulation.Individualswithaboveaveragefitnesshavelowermutationprobabilitiesandcontinuallyevolvetobetterones,whilelessfitindividualsareassignedwithhighermutationprobabilitiestosearchwiderarea.Meanwhile,thepopulationπsfitnessvarianceisusedtoadjusttheprobabilitycurve.Populationsizeisdoubledwhennobestindividualisupdatedaftercertainnumbersofgenerations.Experimentsarecarriedoutbycomparingmulti2scaleNKLandscapeswithsimplegeneticalgorithm(SGA).Resultsshowthattheoptimizationabilityofgeneticalgorithmisimprovedremarkablybyintroducingthepresentedparameteradaptationmethods.Keywords:geneticalgorithm;mutationprobability;populationsize;adaptationmethods
遗传算法(geneticalgorithm,GA)是1975年Holland提出的一种基于达尔文物种进化和孟德尔
确定都和具体问题直接相关,比如对TSP问题的GA方法一般采用排列编码,并使用PMX,OX等交
基因学说的通用随机优化算法,由于其简单、高效的特点,近30年来在各个领域都得到了广泛的应用.遗传算法本身只是提供了一种基于种群进化的随机优化框架,其具体实现还包括解空间编码、适度函数构造、算子选择和参数选取等4部分工作.其中编码选择、适度函数构造以及交叉变异算子的
收稿日期:2003212224.
基金项目:国家自然科学基金资助项目(60275041)、南瑞继保研究
生论文基金资助项目(2003).
),男,博士生;高敦堂(联系人),男,教作者简介:熊 军(1976—
授,博士生导师,[email protected].
叉算子;而对于一般的函数优化则可以采用实数或二进制编码,并使用单点或多点交叉算子.
另一方面,遗传算法的实际性能受控制参数(如种群数目、交叉概率、变异概率等)的影响,如何选取合适的参数组合使遗传算法获得更好的优化性能受到了研究者广泛的关注[1].本文通过对遗传算法参数自适应研究的简单回顾,提出了个体变异率和种群数目的自适应方法,在NKLandscape上的测试结果表明新算法的寻优能力和问题尺度适应能力都要优于传统的简单遗传算法(SGA).
554
东南大学学报(自然科学版) 第34卷
进化的决定性力量,较差个体在种群中是一个不断被淘汰的过程.因此,可以对种群中的不同个体采用不同的变异率:一方面使种群中的优良个体具有较小的变异率从而能够得到较好的保持并通过交叉重组进行优良模式的累积;另一方面,对于种群中较差的个体能够通过较大的变异率增强种群的探索能力.为了使种群中个体变异率调整具有平滑的特性,调整曲线采用渐变的Sigmoid函数,即
(i-N) i
(1)Pm=
α() i≥Ns
1+e-2i-Ns
i
式中,Pm列后第i个个体的变异率;2个参数控制,αi.Ns用于控制.1,(
α1,α2,Ns)为(0.2,0.,.,b参数为(0.1,0.3,0.8).
1 参数自适应研究背景
遗传算法的控制参数主要有种群数目Npop、交叉概率Pc和变异概率Pm,不同的参数设定对遗传算法的实际运行性能有明显的影响,多年来许多研究者对参数的选取和调整方法进行了一系列的研究.
deJong[2]首先系统研究了不同的参数组合对遗传算法的性能影响,他在5个测试函数的基础上提出了一组建议的参数选择范围:Npop=50,Pc=0.6,Pm=0.001,这一组建议参数值后来被作为标
准参数广泛使用.
Grefenstette[3]采用了2个层次遗传算法的参数优化方法,使用上层遗传算法优化下层遗传算法的控制参数,下层遗传算法的参数组合作为上层遗传算法的编码个体,适度值计算时使下层遗传算法按照该个体参数组合运行一次,度值.于deJong,,效率很低,.
Pham等[4]群竞争的参数优化方法,让多个具有不同参数设定的种群同时进化,性能越好的种群获得更多的处理器时间.Lis等[5]采用了类似的多种群竞争方法,不同的是种群竞争的结果使性能较差的种群的变异率向着性能最好的种群变异率的方向调整.多种群竞争的优点是参数调整法则简单,但是同时进化多个种群计算量很大.
图1 变异率调整曲线
2 2种参数的自适应方法
Deb等[6]研究了种群数Npop、交叉概率Pc和
为了保证种群的多样性防止提前收敛,本文中
分界点Ns的确定在算法中也是动态调整的,其调整原则是当种群具有足够的多样性时,Ns取较大的值,使种群中的绝大部分个体具有较小的变异率,并使种群中的个体能够通过交叉算子充分混合,而当种群趋于收敛时,减小Ns使种群中较多的个体具有大变异率,能够增强种群探索能力.如图1中,当曲线a分界点为0.5时就有50%的个体变异概率大于0.25,而曲线b中只有20%的个体变异率大于0.25.本文采用种群适度值的方差的方法判断种群收敛程度[7],为了简化计算,将方差计算中的平方项改为绝对值计算,即
N
变异率Pm的相互作用对遗传算法的影响,结果表明算法的实际性能在很大程度上依赖于合适的种群大小的选取,而且交叉概率Pc对遗传算法性能的影响远比变异率Pm小.因此,种群数和变异率这2个参数的调整对遗传算法性能有重要的影响.2.1 变异率的自适应方法
根据模式定理,变异算子在遗传算法中的作用主要是使种群保持一定的多样性,使遗传算法在提前收敛时具有跳出局部最优点的能力.在一般遗传算法中种群使用的是固定的全局变异率,而且为了降低变异算子对模式的破坏作用,变异率一般都很小(小于0.1).然而种群中的不同个体对整体进化的作用是不同的,优良个体之间的基因重组是群体
δ=
f(pi)-fN
-
(2)
2.2 种群数目自适应方法
实际应用遗传算法解决问题时,由于问题解的空间大小可能有很大差别,种群数目对遗传算法性能影响不容忽视:一方面太小的种群数目容易产生
第4期熊 军,等:变异率和种群数目自适应的遗传算法555
较大的采样误差,而被误导或产生遗传漂移无法收
敛;另一方面太大的种群数目则导致计算资源的浪费.通常种群大小设定都是由使用者主观选定,在实际应用中常常会产生较大偏差.Harik等[7]从理论上研究了种群数目设定的问题,给出了估算种群数目的公式为
N=
k
2
mσ组合函数非线性的问题模型,它被广泛应用于遗传算法算子性能测试的实验研究中.选取NK问题作为算法性能测试有2个优点:①NK问题具有足够的复杂度,可以证明[10]当K≥2时的NK问题是一个NP完全问题;②NKLandscape具有可调参数N和K,可以根据测试的需要对问题难度和规模方便
地进行调整.数值试验分别选取3种规模的(F1,F2,F3)NKLandscape(K=3)进行测试,结果如表1所
2d
lnα(3)
式中,k为积木块模式(buildingblock)的大小;m
2
为积木块模式的数目;σBB为积木块模式适度值的方差;d为积木块模式的适度值大小;α为在遗传算法进行模式累积时可能发生错误的概率.然而式(3)在实际使用中并不实用,由于实际问题的多样性,积木块模式的大小及其他参数很难事先进行估计.
对遗传算法的一类重要改进方法是防止种群早熟[8].,的发生,.
一种根据种群最优个体更新率自适应增大种群数目的方法:对于连续20代内种群都没有最优个体更新时,将种群数增大一倍继续运行,直至满足算法停止条件.通过使用最优更新率来进行判断,可以有效检测因为初始种群数过小产生的遗传漂移而无法收敛的现象,同时自适应增大种群数反过来又能避免该现象的继续存在.2.3 算法流程
综合了个体自适应变异率和种群数目调整的改进自适应遗传算法运行流程如下:
①种群初始化,个体数目取为N0;
②判断是否满足算法停止条件,是则转入第⑥步;
③应用选择算子和交叉算子生成过渡子代种群Ctmp;
④计算过渡子代种群Ctmp的种群多样性δ,并确定分界点Ns,根据Pm曲线对不同个体以不同的变异率执行变异操作,生成下代种群;
⑤判断是否有最优个体更新,若连续20代未更新则Nt+1=2Nt,转入②继续运行;
⑥将当前最优解作为计算结果输出.
示.
表1 3种规模测试模型
NK模型
N
F124
F236
F350
,3种遗传算:;应变异率的遗传算法(withmutationadaptation,GAMA);
③同时加入变异率自适应和种群数目自适应的改
进自适应遗传算法(geneticalgorithmwithcombinedadaptation,GACA).
3种遗传算法的其他设置统一为:交叉算子采
用均匀交叉,交叉概率设为0.7;初始种群数目都设为100,算法终止条件设为进化100代后停止.对SGA,分别使用2种固定变异率0.01(SGA1)和0.1(SGA2),比较简单改变变异率对其性能的影响.GAMA和GACA采用的变异率调整曲线如图1中
的曲线a和曲线b,多样性参数δt的阀值为0.1.为了避免可能出现的随机性,每种算法在随机初始化的条件下运行100次,统计结果如表2、表3所示.
表2 F1测试结果
算法
SGA1SGA2GAMAGACA
次数
38/10020/10059/10076/100
所得解
0.73980.72470.74210.7483
优化度/%
98.396.398.699.5
注:最优解为0.7523.
表3 F2测试结果
算法
SGA1SGA2GAMAGACA
次数
2/1000/10012/10037/100
所得解
0.73640.68020.74260.7521
优化度/%
96.489.197.298.5
注:最优解为0.7636.
3 实验结果
Kauffman[9]的NKLandscape是一类用于研究
由表
2和表3数据可以看出,对于简单遗传算法SGA,虽然算法收敛速度较快,但是解的质量不高,属于算法早熟,而单纯提高其变异率(从0.01
556
东南大学学报(自然科学版) 第34卷
需要注意的是,自适应方法本身也是受参数控制的,如选取的最优更新率阀值、变异率调整曲线的参数等.由于本文关注对象是自适应方法对遗传算法的改进作用,因此文中参数使用的是经验值,自适应方法本身参数的最优选取,是值得进一步研究的内容.
提高到0.1)并不能提高算法的性能,反而降低了种群中优良个体的稳定性,使算法趋向于随机搜索.而具有个体自适应变异率的GAMA算法的性能明显提高,GACA加入种群数目自适应虽然降低了算法收敛速度,但是有效地提高了最优解的质量.
从以上实验也看出问题规模的扩大使算法的求解性能都有了明显下降,因此对于解空间非常巨大的NK测试模型F3,将初始种群数和进化代数都提高到200(其中GACA初始种群数仍设为100),而SGA不再作变异率的对比,而是将SGA的进化代数分别设为200(SGA1)和400(SGA2),实验结果如表4所示.
表4 F3测试结果
算法
SGA1SGA2GAMAGACA
参考文献(References)
[1]EibenAE,HinterdingR,MichalewiczZ.Parametercontrol
inevolutionaryalgorithms[J].IEEETransonEvolutionary
Computation,1999,3(2):124141.
[2]deJongKA.Ananalysisofthebehaviorofaclassof
geneticadaptivesystems[D].USA:UniversityofMichigan,1975.
[3]GJJ.
controlparametersfor
Progressinin
Artificial
次数
0/1000/1000/10012/100
所得解
0.74210.74320.75720.7683
优化度/%
94.894.996.7Systems,Manand,1986,(1)T.evolution:anaturalapproachto
selection[A].In:YaoX,ed.Evolutionary
Computation,
Lecture
Notes
注:最优解为0.7829.
Intelligence[C].Heidelberg:Springer2Verlag,1995.49
F3,在初倍的条件下,4种算法,即使SGA将进化代数提高到400仍然没有明显的改善.而采用了自适应变异率和自适应种群数的GACA,由于能够自适应增大种群数目,对问题的规模具有较好的自适应能力,虽然初始种群数仍然取为100,但在4种算法中是惟一能够搜索到全局最优解的算法,有效地提高了遗传算法的优化质量.
60.
[5]LisJ.Parallelgeneticalgorithmwiththedynamiccontrol
parameter[A].In:Proceedingsofthe3rdIEEEConferenceonEvolutionaryComputation[C].Nagoya:IEEEPress,
1996,324329.
[6]DebK,AgrawalS.Understandinginteractionsamonggenetic
algorithmparameters[A].In:BanzhafW,ReevesC,eds.FoundationsofGeneticAlgorithms5[C].SanFrancisco:
MorganKauffman,1998.265286.
[7]HarikGR,Cantú2PazE,GoldbergDE,etal.The
gamblerπsruinproblem,geneticalgorithmsandthesizingofpopulations[A].In:B ckT,ed.Proceedingofthe4thInternationalConferenceonEvolutionaryComputation[C].
4 结 论
本文提出了遗传算法中个体变异率和种群数
目的2种自适应方法,通过在NKLandscape模型上试验表明,自适应变异率方法通过区分种群中的不同个体较好地解决了遗传算法局部寻优与全局搜索的平衡,而自适应种群数目的方法不仅能够解决遗传漂移现象带来的种群收敛判断失效的问题,在解决大尺度问题时也对算法性能有明显的改善.2种自适应方法对于遗传算法寻优能力的改进效果是明显的.
NewYork:IEEEPress,1997.712.
[8]YuanXH,
CaoL,XiaLZ.Adaptivegeneticalgorithmwith
thecriterionofprematureconvergence[J].JournalofSoutheastUniversity(EnglishEdition),2003,19(1):4043.
[9]KauffmanSA.
Originsoforder[M].
Oxford:OxfordKauffmanπsNK
UniversityPress,1993.3369
[10]WeinbergerED.NPcompletenessof
model,atunableruggedfitnesslandscape[R].NewMexico:SantafeInstituteTechnicalReport962022003,1996.
第34卷第4期
东南大学学报(自然科学版)
Vol.34No.4变异率和种群数目自适应的遗传算法
熊 军 高敦堂 都思丹 沈庆宏
(南京大学电子科学与工程系,南京210093)
摘要:提出了针对个体变异率和种群数目的2种自适应方法.算法中个体变异率根据其适度值
在种群中的排序自适应调整,使优良个体具有较小的变异率继续进化,而使种群中较差个体具有较大变异率,增强了种群搜索能力.同时根据种群个体适度值方差动态调整变异率曲线,种群数目调整则根据最优个体更新率动态增大,以动态适应解空间的规模避免采样误差造成的进化停滞.通过在不同尺度的NKLandscape上与传统的简单遗传算法(SGA)比较可得的引入对遗传算法的寻优能力有了明显改进.关键词:遗传算法;变异率;种群数;自适应中图分类号:O224 文献标识码:A :-0505(204
Gprobability
sizeadaptation
XJun GaoDuntang DuSidan ShenQinghong
(DepartmentofElectronicScienceandEngineering,NanjingUniversity,Nanjing210093,China)
Abstract:Twoparameteradaptationmethodsarepresentedforgeneticalgorithm.Mutationprobabilityis
assignedtoeachindividualaccordingtoitssortorderoffitnessinthepopulation.Individualswithaboveaveragefitnesshavelowermutationprobabilitiesandcontinuallyevolvetobetterones,whilelessfitindividualsareassignedwithhighermutationprobabilitiestosearchwiderarea.Meanwhile,thepopulationπsfitnessvarianceisusedtoadjusttheprobabilitycurve.Populationsizeisdoubledwhennobestindividualisupdatedaftercertainnumbersofgenerations.Experimentsarecarriedoutbycomparingmulti2scaleNKLandscapeswithsimplegeneticalgorithm(SGA).Resultsshowthattheoptimizationabilityofgeneticalgorithmisimprovedremarkablybyintroducingthepresentedparameteradaptationmethods.Keywords:geneticalgorithm;mutationprobability;populationsize;adaptationmethods
遗传算法(geneticalgorithm,GA)是1975年Holland提出的一种基于达尔文物种进化和孟德尔
确定都和具体问题直接相关,比如对TSP问题的GA方法一般采用排列编码,并使用PMX,OX等交
基因学说的通用随机优化算法,由于其简单、高效的特点,近30年来在各个领域都得到了广泛的应用.遗传算法本身只是提供了一种基于种群进化的随机优化框架,其具体实现还包括解空间编码、适度函数构造、算子选择和参数选取等4部分工作.其中编码选择、适度函数构造以及交叉变异算子的
收稿日期:2003212224.
基金项目:国家自然科学基金资助项目(60275041)、南瑞继保研究
生论文基金资助项目(2003).
),男,博士生;高敦堂(联系人),男,教作者简介:熊 军(1976—
授,博士生导师,[email protected].
叉算子;而对于一般的函数优化则可以采用实数或二进制编码,并使用单点或多点交叉算子.
另一方面,遗传算法的实际性能受控制参数(如种群数目、交叉概率、变异概率等)的影响,如何选取合适的参数组合使遗传算法获得更好的优化性能受到了研究者广泛的关注[1].本文通过对遗传算法参数自适应研究的简单回顾,提出了个体变异率和种群数目的自适应方法,在NKLandscape上的测试结果表明新算法的寻优能力和问题尺度适应能力都要优于传统的简单遗传算法(SGA).
554
东南大学学报(自然科学版) 第34卷
进化的决定性力量,较差个体在种群中是一个不断被淘汰的过程.因此,可以对种群中的不同个体采用不同的变异率:一方面使种群中的优良个体具有较小的变异率从而能够得到较好的保持并通过交叉重组进行优良模式的累积;另一方面,对于种群中较差的个体能够通过较大的变异率增强种群的探索能力.为了使种群中个体变异率调整具有平滑的特性,调整曲线采用渐变的Sigmoid函数,即
(i-N) i
(1)Pm=
α() i≥Ns
1+e-2i-Ns
i
式中,Pm列后第i个个体的变异率;2个参数控制,αi.Ns用于控制.1,(
α1,α2,Ns)为(0.2,0.,.,b参数为(0.1,0.3,0.8).
1 参数自适应研究背景
遗传算法的控制参数主要有种群数目Npop、交叉概率Pc和变异概率Pm,不同的参数设定对遗传算法的实际运行性能有明显的影响,多年来许多研究者对参数的选取和调整方法进行了一系列的研究.
deJong[2]首先系统研究了不同的参数组合对遗传算法的性能影响,他在5个测试函数的基础上提出了一组建议的参数选择范围:Npop=50,Pc=0.6,Pm=0.001,这一组建议参数值后来被作为标
准参数广泛使用.
Grefenstette[3]采用了2个层次遗传算法的参数优化方法,使用上层遗传算法优化下层遗传算法的控制参数,下层遗传算法的参数组合作为上层遗传算法的编码个体,适度值计算时使下层遗传算法按照该个体参数组合运行一次,度值.于deJong,,效率很低,.
Pham等[4]群竞争的参数优化方法,让多个具有不同参数设定的种群同时进化,性能越好的种群获得更多的处理器时间.Lis等[5]采用了类似的多种群竞争方法,不同的是种群竞争的结果使性能较差的种群的变异率向着性能最好的种群变异率的方向调整.多种群竞争的优点是参数调整法则简单,但是同时进化多个种群计算量很大.
图1 变异率调整曲线
2 2种参数的自适应方法
Deb等[6]研究了种群数Npop、交叉概率Pc和
为了保证种群的多样性防止提前收敛,本文中
分界点Ns的确定在算法中也是动态调整的,其调整原则是当种群具有足够的多样性时,Ns取较大的值,使种群中的绝大部分个体具有较小的变异率,并使种群中的个体能够通过交叉算子充分混合,而当种群趋于收敛时,减小Ns使种群中较多的个体具有大变异率,能够增强种群探索能力.如图1中,当曲线a分界点为0.5时就有50%的个体变异概率大于0.25,而曲线b中只有20%的个体变异率大于0.25.本文采用种群适度值的方差的方法判断种群收敛程度[7],为了简化计算,将方差计算中的平方项改为绝对值计算,即
N
变异率Pm的相互作用对遗传算法的影响,结果表明算法的实际性能在很大程度上依赖于合适的种群大小的选取,而且交叉概率Pc对遗传算法性能的影响远比变异率Pm小.因此,种群数和变异率这2个参数的调整对遗传算法性能有重要的影响.2.1 变异率的自适应方法
根据模式定理,变异算子在遗传算法中的作用主要是使种群保持一定的多样性,使遗传算法在提前收敛时具有跳出局部最优点的能力.在一般遗传算法中种群使用的是固定的全局变异率,而且为了降低变异算子对模式的破坏作用,变异率一般都很小(小于0.1).然而种群中的不同个体对整体进化的作用是不同的,优良个体之间的基因重组是群体
δ=
f(pi)-fN
-
(2)
2.2 种群数目自适应方法
实际应用遗传算法解决问题时,由于问题解的空间大小可能有很大差别,种群数目对遗传算法性能影响不容忽视:一方面太小的种群数目容易产生
第4期熊 军,等:变异率和种群数目自适应的遗传算法555
较大的采样误差,而被误导或产生遗传漂移无法收
敛;另一方面太大的种群数目则导致计算资源的浪费.通常种群大小设定都是由使用者主观选定,在实际应用中常常会产生较大偏差.Harik等[7]从理论上研究了种群数目设定的问题,给出了估算种群数目的公式为
N=
k
2
mσ组合函数非线性的问题模型,它被广泛应用于遗传算法算子性能测试的实验研究中.选取NK问题作为算法性能测试有2个优点:①NK问题具有足够的复杂度,可以证明[10]当K≥2时的NK问题是一个NP完全问题;②NKLandscape具有可调参数N和K,可以根据测试的需要对问题难度和规模方便
地进行调整.数值试验分别选取3种规模的(F1,F2,F3)NKLandscape(K=3)进行测试,结果如表1所
2d
lnα(3)
式中,k为积木块模式(buildingblock)的大小;m
2
为积木块模式的数目;σBB为积木块模式适度值的方差;d为积木块模式的适度值大小;α为在遗传算法进行模式累积时可能发生错误的概率.然而式(3)在实际使用中并不实用,由于实际问题的多样性,积木块模式的大小及其他参数很难事先进行估计.
对遗传算法的一类重要改进方法是防止种群早熟[8].,的发生,.
一种根据种群最优个体更新率自适应增大种群数目的方法:对于连续20代内种群都没有最优个体更新时,将种群数增大一倍继续运行,直至满足算法停止条件.通过使用最优更新率来进行判断,可以有效检测因为初始种群数过小产生的遗传漂移而无法收敛的现象,同时自适应增大种群数反过来又能避免该现象的继续存在.2.3 算法流程
综合了个体自适应变异率和种群数目调整的改进自适应遗传算法运行流程如下:
①种群初始化,个体数目取为N0;
②判断是否满足算法停止条件,是则转入第⑥步;
③应用选择算子和交叉算子生成过渡子代种群Ctmp;
④计算过渡子代种群Ctmp的种群多样性δ,并确定分界点Ns,根据Pm曲线对不同个体以不同的变异率执行变异操作,生成下代种群;
⑤判断是否有最优个体更新,若连续20代未更新则Nt+1=2Nt,转入②继续运行;
⑥将当前最优解作为计算结果输出.
示.
表1 3种规模测试模型
NK模型
N
F124
F236
F350
,3种遗传算:;应变异率的遗传算法(withmutationadaptation,GAMA);
③同时加入变异率自适应和种群数目自适应的改
进自适应遗传算法(geneticalgorithmwithcombinedadaptation,GACA).
3种遗传算法的其他设置统一为:交叉算子采
用均匀交叉,交叉概率设为0.7;初始种群数目都设为100,算法终止条件设为进化100代后停止.对SGA,分别使用2种固定变异率0.01(SGA1)和0.1(SGA2),比较简单改变变异率对其性能的影响.GAMA和GACA采用的变异率调整曲线如图1中
的曲线a和曲线b,多样性参数δt的阀值为0.1.为了避免可能出现的随机性,每种算法在随机初始化的条件下运行100次,统计结果如表2、表3所示.
表2 F1测试结果
算法
SGA1SGA2GAMAGACA
次数
38/10020/10059/10076/100
所得解
0.73980.72470.74210.7483
优化度/%
98.396.398.699.5
注:最优解为0.7523.
表3 F2测试结果
算法
SGA1SGA2GAMAGACA
次数
2/1000/10012/10037/100
所得解
0.73640.68020.74260.7521
优化度/%
96.489.197.298.5
注:最优解为0.7636.
3 实验结果
Kauffman[9]的NKLandscape是一类用于研究
由表
2和表3数据可以看出,对于简单遗传算法SGA,虽然算法收敛速度较快,但是解的质量不高,属于算法早熟,而单纯提高其变异率(从0.01
556
东南大学学报(自然科学版) 第34卷
需要注意的是,自适应方法本身也是受参数控制的,如选取的最优更新率阀值、变异率调整曲线的参数等.由于本文关注对象是自适应方法对遗传算法的改进作用,因此文中参数使用的是经验值,自适应方法本身参数的最优选取,是值得进一步研究的内容.
提高到0.1)并不能提高算法的性能,反而降低了种群中优良个体的稳定性,使算法趋向于随机搜索.而具有个体自适应变异率的GAMA算法的性能明显提高,GACA加入种群数目自适应虽然降低了算法收敛速度,但是有效地提高了最优解的质量.
从以上实验也看出问题规模的扩大使算法的求解性能都有了明显下降,因此对于解空间非常巨大的NK测试模型F3,将初始种群数和进化代数都提高到200(其中GACA初始种群数仍设为100),而SGA不再作变异率的对比,而是将SGA的进化代数分别设为200(SGA1)和400(SGA2),实验结果如表4所示.
表4 F3测试结果
算法
SGA1SGA2GAMAGACA
参考文献(References)
[1]EibenAE,HinterdingR,MichalewiczZ.Parametercontrol
inevolutionaryalgorithms[J].IEEETransonEvolutionary
Computation,1999,3(2):124141.
[2]deJongKA.Ananalysisofthebehaviorofaclassof
geneticadaptivesystems[D].USA:UniversityofMichigan,1975.
[3]GJJ.
controlparametersfor
Progressinin
Artificial
次数
0/1000/1000/10012/100
所得解
0.74210.74320.75720.7683
优化度/%
94.894.996.7Systems,Manand,1986,(1)T.evolution:anaturalapproachto
selection[A].In:YaoX,ed.Evolutionary
Computation,
Lecture
Notes
注:最优解为0.7829.
Intelligence[C].Heidelberg:Springer2Verlag,1995.49
F3,在初倍的条件下,4种算法,即使SGA将进化代数提高到400仍然没有明显的改善.而采用了自适应变异率和自适应种群数的GACA,由于能够自适应增大种群数目,对问题的规模具有较好的自适应能力,虽然初始种群数仍然取为100,但在4种算法中是惟一能够搜索到全局最优解的算法,有效地提高了遗传算法的优化质量.
60.
[5]LisJ.Parallelgeneticalgorithmwiththedynamiccontrol
parameter[A].In:Proceedingsofthe3rdIEEEConferenceonEvolutionaryComputation[C].Nagoya:IEEEPress,
1996,324329.
[6]DebK,AgrawalS.Understandinginteractionsamonggenetic
algorithmparameters[A].In:BanzhafW,ReevesC,eds.FoundationsofGeneticAlgorithms5[C].SanFrancisco:
MorganKauffman,1998.265286.
[7]HarikGR,Cantú2PazE,GoldbergDE,etal.The
gamblerπsruinproblem,geneticalgorithmsandthesizingofpopulations[A].In:B ckT,ed.Proceedingofthe4thInternationalConferenceonEvolutionaryComputation[C].
4 结 论
本文提出了遗传算法中个体变异率和种群数
目的2种自适应方法,通过在NKLandscape模型上试验表明,自适应变异率方法通过区分种群中的不同个体较好地解决了遗传算法局部寻优与全局搜索的平衡,而自适应种群数目的方法不仅能够解决遗传漂移现象带来的种群收敛判断失效的问题,在解决大尺度问题时也对算法性能有明显的改善.2种自适应方法对于遗传算法寻优能力的改进效果是明显的.
NewYork:IEEEPress,1997.712.
[8]YuanXH,
CaoL,XiaLZ.Adaptivegeneticalgorithmwith
thecriterionofprematureconvergence[J].JournalofSoutheastUniversity(EnglishEdition),2003,19(1):4043.
[9]KauffmanSA.
Originsoforder[M].
Oxford:OxfordKauffmanπsNK
UniversityPress,1993.3369
[10]WeinbergerED.NPcompletenessof
model,atunableruggedfitnesslandscape[R].NewMexico:SantafeInstituteTechnicalReport962022003,1996.