浮点数编码的遗传算法及其应用
第32卷 第4期 哈
2000年8
尔 滨 工 业 大 学 学 报 Vol.32,No.4
月 JOURNALOFHARBININSTITUTEOFTECHNOLOGY Aug.,2000
文章编号:036726234(2000)0420059203
浮点数编码的遗传算法及其应用
张 彤,张 华,王子才
(哈尔滨工业大学控制工程系,黑龙江哈尔滨150001)
摘 要:对多极值函数的全局优化问题,采用十进制浮点数对遗传算法进行编码,综合设计出相应的选择、交叉与变异遗传操作,得到浮点数编码的遗传算法(Float2encodingGeneticAlgorithm,FGA).应用FGA对3个著名的优化方法测试函数进行优化计算.仿真结果表明FGA不易陷入局部极值,收敛速度快,并能得到较高的优化精度.
关键词:遗传算法;浮点数编码;遗传操作;测试函数中图分类号:TP301.6 文献标识码:A
FloatencodinggeneticalgorithmZHANGTong,i(,Technology,Harbin150001,China)
Abstract:algorithm(FGA)isadoptedforgeneticalgorithm,andcorrespondinggeneticop2
eration(,overandmutation)aredesigned.Threefamoustestfunctionsofoptimizationmethodarecal2culatedwithFGA.SimulationresultsdemonstratethatFGAconvergestotheglobaloptimummorequickly,hardlygetsstuckatanoptimums,andgetsmorepreciseresults.
Keywords:geneticalgorithm;floatencoding;geneticoperation;testfunction
遗传算法(GeneticAlgorithm,GA)是一种随机性优化方法,有很强的鲁棒性.GA的优化过程首先是对所求问题进行编码,然后初始化一个种群,接着对整个种群反复进行选择、交叉、变异等遗传操作,从而使整个种群不断朝最优值方向迈进.流行的遗传算法采用二进制编码.为什么采用二进制编码一直存在着争论.二进制编码的优点是遗传操作清晰,并有图式理论作引导.然而对多极值函数的全局优化问题,二进制编码难以得到高精度解并且在计算目标函数时需要把二进制码解码成十进制浮点数.一些学者研究过浮点数编码问题[1],它的主要困难在于难以设计好的遗传操作.本文研究了十进制浮点数编码的遗传算法,在分
收稿日期:1998-02-23
作者简介:张
彤(1971-),男,博士生;
王子才(1933-),男,教授,博士生导师.
析二进制遗传操作的基础上,设计了针对浮点数
编码的遗传操作.本文的基本思路是:从群体中个体所表示的寻优参数的数值变化角度来看,FGA的遗传操作与二进制编码的遗传操作有同样的效果:FGA追求操作结果的多样性及操作实现的简单方便.
1 浮点数编码及其遗传操作
1.1 编码
流行的观点认为二进制编码能在相同的范围内表示尽可能多的模式,能更充分地体现所谓的隐含的并行性.而有些人则认为采用二进制编码不过是因为它的理论分析方便及它的遗传操作更类似生物进化,另外还有历史的原因[2].从精度及使用方便的角度来看,多极值函数的优化问题更适合用十进制浮点数编码.本文正是采用这种编码方式.假定有n个待寻优变量,则n个导优范围
哈 尔 滨 工 业 大 学 学 报 第32卷・60・
内的十进制浮点数排列在一起成为一个个体.1.2 选择操作
FGA采用排序选择(RankingSelection)操作[3].假定最小化目标函数,这样对每一个体计算目标函数后需要对它们由小到大排序(若极大化目标函数则由大到小排序),用序号充当适值.序号为rank(x)的个体x的复制概率
P(x)=[Min+(Max-Min)
)表示均值为c,方差为σ的正态分布其中N(c,σ
的随机数.参数在[L,R]内范围内变化.可以看出,FGA对参数的变异操作即以当前值为中心,主要在一个小范围内进行随机扰动.式(2)的变异操作需要产生正态分布的随机数且需做边界处理,编程实现有些繁琐.大量仿真实验表明如下变异操作实现简便,效果同样很好:
γ,random(2)=0,c+k・(R-c)・
c′=
γ,random(2)=1,c-k・(c-L)・
(3)
]/Pop,
Pop-1
其中Pop为群体尺寸,Max∈(1,5,2),Max+Min=2.rank(x)=1,2,…,Pop.根据复制概率,
可以按轮盘赌方式来进行选择操作.大量仿真计算表明如下改进方式不仅极其简单方便,而且同样有效.即排序选择的结果实际是把序号在前的m个个体复制两份,淘汰序号在后面的m个个体,序号在中间Pop-2m个个体复制一份.这种做法能保证群体尺寸不变,编程实现非常容易.采用排序选择操作的意义在于它能保持一致的选择压力,能较好地抑制非成熟收敛[4].1.3 交叉操作
其中“0”“,1”代表变异的两个方向,γ为(0,1)区间上的随机数,k∈(0,1]为一系数.random(2)为C语言库函数调用,随机产生整数0或1.1.5 浮点数编码的遗传算法
对全局优化问题
minnf(X),
X∈R
∈[abi],,:
()作,a、bab=a′+b′,
.随机产生Pop个这样的个体作为初始种群;
(2)计算每一个体的目标函数值并对这Pop
个函数值由小到大排序,记录最优个体;
(3)淘汰m个较大函数值对应的个体并分别
一致交叉通常优于单点交叉,其原因在于一致交
叉可能得到更多的图式结果,基于上述两点,FGA采用如下的交叉方式:
)・a+βa′=(1-αb,)・b+αb′=(1-βa,0
(b′)
(b′)>Rthena′(b′)=R,ifa′
替换成m个较小函数值对应的个体;
(4)对这Pop个个体随机两两配对,按一指定
概率Pc进行式(1)的交叉操作;
(1)
(5)对每一个体中的每一参数,按一指定概
率Pm进行式(3)的变异操作;
(6)删除种群中一任意个体并替换成步骤(2)中记录的最优个体;
(7)若满足收敛条件则输出最优解并退出,
其中α,β为(0,r)区间上均匀分布的随机数,r≤1,L,R分别为寻优参数的左右边界.调节式(1)
中r的大小可以控制交叉操作的变化范围.当r较小时参数在原值附近小范围内变化,而当r较大时交叉结果可能离原值较远.采用这样的交叉操作方式可以得到多种可能结果,能充分地实现两个个体间的“信息交换”,对找到全局极值很有利.1.4 变异操作
否则转向步骤(2).
2 算例
本文将用提出的FGA与文献[5]提出的AGA比较.AGA采用自适应交叉、变异概率,是二进制编码遗传算法中较为优秀的.用FGA和AGA对如下三个著名的测试函数进行优化计算:
25
考察二进制编码的变异操作,它的最终效果是把某个体的参数c操作成域内另一值c′.FGA中的变异操作亦要达到这样的效果.FGA采用如
下的变异操作:
),c′=N(c,σ
ifc′Rthenc′=R,
(2)
F5=0.002+
j=1
j+
2i=1
,
i
∑(
x
0-32
-aij)
6
-65.536
其中,[aij]=
-32-32
-16-32
16-32
32-32
第4期 张 彤,等:浮点数编码的遗传算法及其应用 ・61・
-32-16
-16-16…01632
,
…3232F5取式(1)中r=0.1,式(3)中k=0.4;对F6、F7取式(1)中r=1.0,式(3)中k=0.04.对每一
2
22F6=0.5-22,(1+0.001(x21+x2))
-100
220.252220.1
F7=(x1+x2)[sin(50(x1+x2))+1.0],
测试函数,设置一定的最大遗传代数.若在最大遗
传代数内得到的最优目标函数值超过给定的阈值,则认为算法成功找到了全局最优解,否则认为算法阻滞于局部最优解.对每个测试函数,FGA和AGA都将进行100次寻优计算.表1给出了两种优化算法的性能比较.其中遗传代数为找到最优解的平均遗传代数.
从表1可以看出:(1)FGA在设定的最大遗传带数内全部找到了最优解,具有很强的跳出局部极值的能力;(2)FGA的收敛速度快,计算量明显少于AGA.另外,FGA的优化精度很高.例如对F6,FGA在遗传200代后能达到(10-8,10-8)数量级.二进制遗传算法要想达到这个精度,编码长度须从原来的44位增加到70位.,FGA还有()相结合,形成所谓.
-100
其中F5,F6求极大值,F7求极小值.DeJone的F5函数是具有25个稀疏尖峰的多极值函数,找寻该函数的最优点被称之为大海捞针.Schaffer的F6函数有无数个局部极大点,其中只有一个(0,0)为全局最大,最大值为1.此函数的最大值峰周围有一圈脊,它们的取值均为0.990284,因此很容易停滞在此局部极大点.F7函数与F6类似,全局极小点为(0,0).
对FGA和AGA,同样选择群体尺寸为100.AGA编码长度为44,其它参数详见文献[5].对FGA,取1.5节步骤(3)中m=15,步骤(4)中交叉概率Pc=0.8,步骤(5)中变异概率Pm=0.081AA的性能比较
1arisonofFGAwithAGAincharacteristics
函数
F5F6F7
≥1.0
≥0.999AGA阻滞次数
523AGA遗传代数
38.3105.6FGA阻滞次数
00FGA遗传代数
30.265.6最大遗传代数
100200
需要说明的是在优化过程中,注意到了对式
(1)及式(3)中参数r和k的选取问题.对这两个参数的不同选取,优化结果将大不一样.对待不同的优化问题,如何自适应确定这两个参数需要进一步研究.
[2]
K.Amodifiedgeneticalgorithmforoptimalcontrolprob2lems[J].ComputersMathApplic,1992,23(2):83294.JIMANTONISSE.Anewinterpretationofschemanotationthatoverturnsthebinaryencodingconstraint//.Proc3rdIntConfGeneticAlgorithms[C].1989.[3]
GREFENSTETTEJJ,BAKERJE.Howgeneticalgo2rithmswork:acriticallookatlmplicitparallelism//.Proc3rdntConfGeneticAlgorithms[C].1989.[4]
DARRELLWHITLEY.Thegenitoralgorithmandselectionpressure:whyrank2basedallocationofreproductivetrialsisbest//.Proc3rdIntConfGeneticAlgorithms[C].1989.[5]
SRINIVASM,PATNAIKLM.Adaptiveprobabilitiesofcrossoverandmutationingeneticalgorithms[J].IEEETransonSystemManandCybernetics,1994,24(4):6562667.
3
结论
对浮点数编码的遗传算法,本文融和、设计了
相应的选择、交叉及变异遗传操作,成为FGA.FGA编码直观,遗传操作非常简单,容易编程实现.对3个著名测试函数的优化实例表明,FGA不易陷入局部极值,收敛速度快并能得到很高的优化精度.对多极值函数的优化问题,FGA实用有效.
参考文献:
[1]
ZBIGNIEWMICHALEWICZ,CEZARYZJ,JACEKB
(责任编辑 王小唯)