基于改进种群熵的遗传算法过渡收敛问题研究

基于改进种群熵的遗传算法过渡收敛问题研究

1种群多样性优化遗传算法是生物自然选择和进化机制发展起来的一种高度平行、随机的、适应性的搜索方法。ga提供了解决复杂优化问题的一般框架，不依赖于特定问题领域的知识，并具有很强的鲁棒性。遗传算法的参数中交叉概率和变异概率的选择时影响遗传算法行为和性能的关键所在。标准遗传算法采用固定的交叉、变异概率,对于不同的优化问题,很难找到适应于每个问题的最佳值,并且在对复杂函数进行寻优时,无法根据种群的当前状态对进化过程进行动态调整,往往导致种群多样性过早流失,算法陷入局部最优解,引起过早收敛。针对这一问题,国内外不少研究人员致力于标准遗传算法的改进,提出了多种交叉、概率可变的改进遗传算法,如Srinvivas等提出的一种自适应遗传算法(AdaptiveGA,简称AGA)。本文根据种群多样性与遗传操作之间的关系,提出了一种基于种群多样性评价的自适应遗传算法,通过种群多样性变化控制当前种群交叉率、变异率的范围,并对不同个体的操作概率在当前范围内进行微调。经实验证明,该方法在保持种群多样性,提高问题求解的精度等方面有较好的效果。2种群熵与种群最大熵遗传算法通过对大量个体实施遗传操作推动种群的进化,种群的规模越大,包含的不同个体越多,搜索到更优个体的几率就越大。而通常情况下,种群规模是一定的,种群多样性越大,种群就越有可能产生出更优子代,而种群多样性减小,种群个体间不断趋于一致,过早收敛现象就越容易发生。因此,保持种群多样性成为遗传算法有效运行的重要方法之一,正确评价种群的多样性程度对遗传算法性能的改进起着非常重要的作用。种群熵是种群的多样性定量评价的指标之一。其具体定义如下:定义1:假设P(t)为第t代种群,种群规模为N,根据个体的不同类型可将种群划分为m个部分:P1(t)、P2(t)…Pm(t),显然,∪i=1mPi(t)=P(t)并且对于∀i,j∈{1,2,…m}均有Pi(t)∩Pj(t)=Ø。设k1、k2…km分别为P1(t)、P2(t)…Pm(t)中个体的数目,则∑i=1mki=N。定义第t代种群的熵为:Et=−∑i=1mpilogpi,其中,pi=ki/N。由定义1可知,当种群中N个个体各不相同,即m=N时,熵取最大值Emax=logN;当种群中个体均相同,即m=1时,熵取最小值Emin=0。种群中个体类型越多,分布越均匀,熵越大。种群熵反映了种群中不同类型个体的分布情况。通过种群熵与种群最大熵的比较,可以衡量出当前种群的多样性程度,令α=Et/Emax,显然,α∈[0,1]并且α越大,种群中不同个体的数目越多,种群的多样性越大,反之,种群的多样性越小。但是过早收敛现象发生时,往往仅是适应度暂时较大的个体趋于一致,适应度较小的个体在种群空间中依然是离散分布的,此时,α值仍然较高,等到α的取值明显下降时,种群已经严重早熟收敛了,这说明种群熵对种群个体过早收敛程度的评价具有一定的滞后性。因此,本文采用较优个体熵作为判断种群过早收敛的指标,其定义如下:定义2:假设P(t)为第t代种群,f¯为当前种群的平均适应度,取适应度大于f¯的个体组成较优个体群,用定义1中的方法计算较优个体群的熵,即为当前种群的较优个体熵,记为E*t,并令E*max为较优个体最大熵,α*=E*t/E*max为第t代种群较优个体的多样性程度,α*∈[0,1]。根据定义2,较优个体群由适应度大于平均适应度的个体组成,排除了适应度小于平均适应度的差个体对种群分布带来的影响。α*与α相比,更能够及时反应种群当前多样性程度。3操作概率难以适应种群状态的变化遗传算法的参数中交叉概率和变异概率对算法的性能起着非常的重要。进化过程中,种群的状态不是一成不变的,采用固定的操作概率难以适应种群状态的变化,往往导致进化过程的停滞不前甚至倒退。本文根据种群中当前较优个体多样性程度及不同适应度个体在进化中的作用从宏观和微观两个方面对操作概率进行动态调整,宏观调整对当前种群操作概率的范围进行调整,微观调整则在宏观调整确定的操作概率范围内,对参与遗传操作的个体进行操作概率的确定,从而改善遗传算法的搜索性能。3.1回复突变体的多样性当种群多样性较高,即α*较大时,种群中个体包含的不同模式较多,搜索到更优个体的潜力较大,应适当的提高交叉概率,减小变异概率,保证个体间进行充分的模式重组,促进有效模式在个体中的传播,增加搜索的广度;而当种群多样性较低,即α*较小时,种群中较优个体逐渐趋于相同,应提高变异概率,引入新的个体,打破较优个体趋同的状态,避免陷入局部最优。具体调整方法如(1)(2)式:{pc1(t)=pc1+(pc2−pc1)2⋅α∗tpc2(t)=pc2(1)其中,pc1、pc2为初始交叉率范围,且pc2>pc1;α*t为第t代种群的多样性程度,α*t∈[0,1];pc1(t)、pc2(t)为第t代种群交叉率范围。由(1)式可知,当α*t=1时,pc1(t)=pc2+pc12,种群整体交叉率较大;当α*t=0,pc1(t)=pc1,种群的整体交叉率较小。{pm1(t)=pm1pm2(t)=pm2−pm2−pm12⋅α∗t(2)其中,pm1、pm2为初始变异概率范围,pm1(t)、pm2(t)为第t代种群变异概率范围,由(2)式可知,当α*t减小时,变异概率的上限pm2(t)增大,种群的整体变异率增大。3.2第t代种群适应度计算根据适应度大小可将种群中个体大致分为三类:较优个体、中等个体和较差个体。每类个体在种群进化过程中的作用各不相同,对应的操作概率应视个体适应度具体情况而定。较优个体适应度较高,拥有较优模式,但较优个体间一般差别不大,交叉率可适当取小,而较优个体与其他两类个体的交叉率可适当取大,有利于优秀模式在种群中的传递;中等个体适应度居中,包含丰富的模式信息,应使其以较大概率参加交叉操作。不同适应度个体具体交叉情况如表1。根据表1中的交叉情况,可得参加交叉的两父个体平均适应度与其交叉率的关系如图1。由此可得,第t代种群中参加交叉操作的两父代个体交叉概率如(3)式:pc=⎧⎩⎨⎪⎪⎪⎪⎪⎪pc2(t)−(pc2(t)−pc1(t))⋅f(t)avg−f¯f(t)avg−f(t)min,f¯≤f(t)avgpc2(t)−(pc2(t)−pc1(t))⋅f¯−f(t)avgf(t)max−f(t)avg,f¯>f(t)avg(3)其中,f¯为两父代个体的平均适应度,f(t)avg为第t代种群平均适应度,f(t)min为第t代种群中个体最低适应度,f(t)max为最高适应度。pc2(t)、pc1(t)为经宏观调整后第t代种群交叉率的上限和下限。对于参加变异操作的个体,若其适应度较高于平均适应度的应采用较小的变异率,以防止优秀个体被破坏;若适应度低于平均适应度则应对应于较高的变异率。具体方法如(4)式:pm=⎧⎩⎨⎪⎪pm1(t)+(pm2(t)−pm1(t))⋅f(t)max−ff(t)max−f(t)avg,f≥f(t)avgpm2(t),f<f(t)avg(4)其中,f为个体适应度,pm1(t)、pm2(t)为经宏观调整后第t代种群交叉率的上限和下限。4模拟实验4.1局部寻优函数为了评价改进算法的搜索性能,本文将改进算法与自适应遗传算法(AGA)、标准遗传算法进行对比实验,并选用3个难度较大的测试函数:f1:Rosenbrock函数minf1(x,y)=100(x2-y)2+(1-x)2,-2.048≤x,y≤2.048f1是单极值的非二次函数,但它是病态的,在y=x2处有一狭长深谷,很难极小化,寻优中可能陷入局部解,其在(1,1)处有全局最小值0;f2:Shubert函数minf2(x,y)={∑i=15icos[(i+1)x+i]}×{∑i=15icos[(i+1)y+i]}+0.5[(x+1.42513)2+(y+0.80032)2],−10≤x,y≤10f2在(0,0)处有最大值为1,该函数最大值峰周围有一圈脊,它们的取值均为0.990283,因此很容易陷入局部最大点;f3:Schaffer函数maxf3(x,y)=0.5−(sinx2+y2√)2−0.5[1+0.001(x2+y2)]2,−100≤x,y≤100f3有760个局部极小点,其中只有一个(-1.42513,-0.80032)为全局最小,最小值为-186.7309,此函数容易陷入局部极小值-186.3405。4.2改进算法仿真实验实验中,三种算法均采用确定式采样选择和单点交叉,标准遗传算法的交叉率为0.7、变异率为0.05;AGA和改进算法的交叉率均为pc1=0.4,pc2=0.9,变异率为pm1=0.01,pm2=0.1;种群规模为100,最大运行代数为1000。将每种算法对不同的函数连续运行50次,记录每次运行结束时的最优解与理想值的平均误差,搜寻到的最优解及搜索到理想值的次数,具体结果如下表。以上仿真实验表明,SGA极易陷入局部最优,而且跳出局部最优的几率很小,并且寻优结果较理想值的平均误差较大。AGA和改进算法在全局搜索性能上较SGA有较大提升,但相比之下,改进算法寻优结果较理想值的平均误差很小,问题求解