杜玉平

(朔州师范高等专科学校 数学与计算机系，山西 朔州 036000)

自20世纪70年代受达尔文的进化论的启发,借鉴生物进化过程而得出了遗传算法(Genetic Algorithm,GA)[1],这是一种启发式搜索优化算法。由于算法简单易操作,因此经常用它去解决神经网络和函数优化方面的问题.

GA算法也存在缺点,如收敛慢,局部搜索性不强等问题，因此,文中提出一种基于黄金分割的改进遗传算法(IGA),IGA算法是先改进了黄金分割搜索,再将其结合到遗传算法中而得到的。IGA算法与标准GA算法相比具有很好的全局收敛性,能有效的抑制未成熟收敛。通过性能函数测试,新算法能有效进行全局寻优,且提高收敛进度和解的精确度,验证了本文算法改进的有效性。

图1 标准遗传算法流程图Fig.1 Standard Genetic Algorithm flow chart

1 标准遗传算法概述

John Holland结合生物进化机制总结出了遗传算法(GA),GA算法是坚持优胜劣汰原则,在一代代进化遗传过程中,去掉适应值低的,留下适应值高的,进而使种群慢慢趋于最优。GA算法应用于实际问题中,先结合问题找出适应度函数,然后建立一个初始群体,该群体是由多个解组成,每个解对应一个染色体即一个编码。接着结合适应度值大小进行群体的一系列遗传运算操作,衍生出下一代,经过代代进化获得适应度值最好的个体,它就是所求寻优问题的结果即最优解。标准遗传算法(Standard Genetic Algorithm,SGA)[2]的基本流程图如图1所示。

一般编码有二进制编码、实数编码等,因为二进制编码简单易实施,所以标准GA算法主要用二进制对染色体进行编码,寻优问题的一个解对应一个染色体。初始群体一般是随机给定的,其规模一般根据寻优问题而定,常取20～200个。选择个体交配时我们一般采取轮盘赌选择,也可采取比例或精英选择,可根据问题而定。遗传运算主要有两种:交叉和变异,交叉一般采用算术交叉,变异算子一般采用高斯变异,高斯变异的变异概率为pm,它的取值一般在0.001～0.100,变异和交叉运算可以预防早熟,提高全局寻优能力。

2 改进的遗传算法(IGA)

2.1 黄金分割的搜索操作

黄金分割法是一种优化方法,它是遵循保存好的,去掉坏的,等比收缩原则来逐渐缩小收缩区域,进而找到最优解。具体做法:在[a,b]中取值λ=a+0.382(b-a),μ=a+0.618(b-a),若f(λ)>f(μ),则令a=λ,重新开始。若f(λ)≤f(μ),则令b=μ,重新开始。这样一次次重复,每次将寻优范围缩小0.382倍或0.618倍,最后剩下一点,这一点就是寻优问题最优解。

IGA算法是将黄金分割做一个改进操作,然后将其结合到标准GA算法中。详细做法如下:

设可行区域D为n维,D:{(x1,x2,…,xn)|a1≤x1≤b1,…,an≤xn≤bn},任取属于D的一点,把它作为初始最优点,计算该点函数值,把它作为最优解。在纵横两个方向(即单数维和双数维的方向)分别以0.382倍和0.618倍划分D,把D划分成3n个小的区域块。计算每个区域块的中心的函数值,然后和已知的最优值比较,比如第i个小区域块的中心函数值优于已知的最优值,则把该值作为新的最优值和最优点;否则,我们估算一下该区域块的最优值,不优于我们已有的最优值,则把该区域块去掉;否则,将其再继续进行如上的分割操作,直到分割的直径达到我们所要求为止。最后留下来的那个点的函数值就是要求的最优值。

2.2 改进的遗传算法步骤

算法中,M表示群体的规模,{x1,x2，…,xM}表示群体中的个体,G(k)表示第k代群体,G表示群体的最大进化代数。

Step 1:随机给出初始化群体,设初始参数α,c∈(0,1)。

Step 2:将染色体的二进制编码转化成十进制,求出群体中每一个个体的适应度值fitness=f(x),然后进行群体个体适应度值的排序,把最好的那个个体记为fmax并保存下来,选6个最好的个体组成优秀者集合Y(k),也把他们保存下来,把群体适应度值记为favg并计算该值。

Step 3:求ps=fit/sumfit,然后对群体以概率ps实施轮盘赌选择。

Step 4:算术交叉,交叉概率为pc,将由选择算子挑出的pc×m对双亲作一个算术交叉操作,设A=d1d2…dm和B=e1e2…em表示一对双亲的染色体,则C=c1c2…cm就是二者产生的新个体(ci=ridi+(1-ri)ei,ri是[0,1]间随机数),更新群体个体,生成新群体。

Step 5: 高斯变异,取pm=0.1,Mr是随机生成的且符合正态分布的,若pm

Step 8:判断是否达到算法所规定的结束条件,若达到算法停止,并输出结果,该结果就是所求问题最优解,否则返回Step 3。

3 实例仿真

文中采用如下三个函数对IGA算法的收敛性进行检验,算法中pc=0. 7,pm=0. 1,L=12,其中L为编码长度,并将本文算法(IGA)、标准遗传算法和爬山法遗传算法[3]进行比较,验证了IGA算法的有效性。

例3f(xi,x2)=21.5+x1sin(4πx1)+x2sin(20πx2)，其中x1∈[-3.0,12.1],x2∈[4.1,5.8]

Rastrigin函数与Sphere函数二者最小值都为0, 例3函数实际最大值为38.8230。表1、表2给出了三种算法的数值结果比较和三种算法的收敛性的比较,图2、图3、图4给出三种算法对于三个函数最优值的进化曲线图。

从表1、表2以及图2、图3、图4可以得出,本文算法(IGA)求出解的精度更高,全局收敛性能好。IGA算法优于标准GA算法和爬山法混合遗传算法,文中将黄金分割与遗传算法相结合的改进策略是有效的,寻优成功率高。

表1 三种算法的数值结果比较Table 1 Comparison of numerical results of three algorithms

表2 三种算法的收敛性比较Table 2 Comparison of convergence of three algorithms

图2 例1函数种群最优值进化曲线图Fig.2 Example 1 evolution curve of optimal value of function population

图3 例2函数种群最优值进化曲线图Fig.3 Example 2 evolution curve of optimal value of function population

图4 例3函数种群最优值进化曲线图Fig.4 Example 3 evolution curve of optimal value of function population

4 结论

GA算法是一种应用广便于实施的的优化方法,标准的GA算法有受局部最优的影响而无法进行全局寻优的缺点。为了克服该缺点文中提出了一种改进的遗传算法(IGA),即将黄金分割进行改进操作,然后将其再与遗传算法结合而得到。测验函数得出了很好的数值效果,进而说明IGA算法的优越性,IGA算法能很好地抑制未成熟收敛现象,进而摆脱局部最优,很好地实施全局寻优,在全局收敛效果方面得到提高。