文档介绍：一种改进的自适应遗传算法
刘晓霞窦明鑫 [提要] 为了提高遗传算法的搜索效率,给出了一种改进的遗传算法。该算法采用混合编码,改进适应度函数和变异操作,扩大搜索范围。通过四个经典函数的测试表明,改进算法与基本遗传算法和自适应遗在进化前期可以保证种群的多样性,避免产生模式欺骗问题或者过早陷入局部收敛。基于这种思想,为了使进化前期原本函数值低的个体有更大的概率被选择,保持种群多样性防止“早熟”,而在后期可以转成正常选择操作,开始局部求精的搜索。本文将适应度函数改进为:
f'(xi)=f(xi)- t<()?f(xi)+fmax t> (1)
其中,fmax为上一代最优解所对应的函数值,t为当前代数,T为预先设置好的最大迭代次数。
2、格雷码周期变异。由于二进制变异容易控制,可以避免考虑实数变异涉及的变异方向,所以本文在变异操作中采用二进制格雷编码,格雷编码的定义见(2)式,
gray[0]=p[0]if(p[j-1])=p[j] gray[j]=0else gray[j]=1 (j=1,2,…,l-1)(2)
其中,p为原二进制编码,l为编码长度。格雷编码不仅具有良好的局部搜索能力,还能克服二进制编码Hamming悬崖,之后将变异概率设定成一个周期性变化的函数,见(3)式:
(3)
其中,a,b是待定值,此函数在一个周期内是单调递减的,在进化后期种群趋于稳定时,降低选择压的同时应该采取大概率变异,保持种群的多样性,防止陷入局部解。经测试,当a=3,b=19时算法性能较好。
二、算法步骤
Step1 采用实数编码产生初始种群,在函数定义域内按照均匀分布随机产生n个个体,xi(1,2,…n)设定最大进化代数设为T。
Step2 计算每个个体的函数值,之后根据计算种群函数的平均值,最后按照本文设定的适应度函数,即(1)式计算当前种群中每个个体的适应度。
Step3 根据每个个体的适应度,采用比例选择法。通过这种适应度转换,使得在进化前期原本函数值小的个体将有更大的概率被选择,保持了种群的多样性。
Step4 按照概率pc在种群中随机选择父代个体进行交叉操作。
Step5 首先依据变异概率pm选定变异个体,然后利用格雷码周期变异操作进行编码、变异、最后解码。
Step6 最优保存策略。本文将最优保存策略算法做如下修改:第一步,计算每个个体的函数值,然后排序,找出最优解,最差解;第二步,若上一代最优解的函数值比当前最优解的函数值大,则用上一代的最优解替换当前最优解;若上一代的最优解函数值小,则用上一代的最优解替换当前中的最差解。这样,基于Markov链的数学理论分析表明,保留最优个体策略的遗传算法就能够以概率1收敛于最优解。
Step7 满足迭代次数即停止,否则代数加1,转入Step2。
三、仿真试验
1、测试函数。选取文献[3、6、7]的测试函数为:
其中,f1为单峰二次函数,当(x1+x2+x3)=(0,0,0)时有全局最小值0;f2有无数个局部最大值,只有一个全局最大点(0,0),最大值为1;f3是一维连续且含三角函数的多峰函数,当x=