一种改进的自适应遗传算法
来源:用户上传
作者: 刘晓霞 窦明鑫
［提要］ 为了提高遗传算法的搜索效率，给出了一种改进的遗传算法。该算法采用混合编码，改进适应度函数和变异操作，扩大搜索范围。通过四个经典函数的测试表明，改进算法与基本遗传算法和自适应遗传算法相比较，在函数最优值、平均收敛代数、收敛概率等方面都取得了令人满意的效果。
关键词：自适应遗传算法；适应度函数；变异操作；格雷编码；实数编码
中图分类号：TP3 文献标识码：A
收录日期：2012年1月12日
引言
遗传算法（GA）由美国Michigan大学的Holland教授于1975年首先提出，后经De Jong、GoldBerg等人改进推广，广泛应用于各类问题。它是一种模拟自然界生物进化过程与机制的全局概率优化搜索方法。
早期遗传算法在进化过程中易出现早熟收敛和局部收敛性差等问题，为了克服上述问题，人们提出了多种改进算法。本文对自适应算法进行改进，算法中不仅交叉和变异概率是自适应的，而且构造了一种自适应的适应度函数，以便更好地进行复制、交叉、变异操作，同时结合实数编码精度高、搜索范围大和二进制编码的收敛速度快、变异操作易实现的特点，算法还采用了实数与二进制编码相结合的方式，在防止早熟的同时还能提高全局搜索能力，最后利用改进算法进行仿真实验，结果表明本算法具有收敛概率高和平均收敛代数少的优点。
一、改进的遗传算法
1、改进的适应度函数。经典遗传算法由选择、交叉和变异三种基本操作构成，适应度函数通常都是用所求函数值表示，首先将函数定义为求最大值maxf，若求最小值则变换函数为max（-f），有时为了编程方便可以加一个足够大的正数M，即max（-f+M），使函数值恒为正，之后将个体按照它们的适应度大小进行选择。通常选择的目的是保留更多高适应度的个体，但为了达到全局最优，防止过早收敛，在选择过程中要尽量保持个体的多样性。通常选择操作采用比例选择法，这样适应度高的个体将有更大的概率被选择。此外，还将适应度函数调整为f'（xi）=f（xi）－，其中f（xi）是xi所对应的函数值，是群体的平均函数值，n为种群内个体数。这种调整使得原本函数值远离群体均值的个体适应度变大，使其被选择的概率增大，而对种群贡献较小的函数值处于中间位置的个体被选择的概率变小，使得在进化前期可以保证种群的多样性，避免产生模式欺骗问题或者过早陷入局部收敛。基于这种思想，为了使进化前期原本函数值低的个体有更大的概率被选择，保持种群多样性防止“早熟”，而在后期可以转成正常选择操作，开始局部求精的搜索。本文将适应度函数改进为：
f'（xi）=f（xi）－ t＜0.6Ttan（）・f（xi）＋fmax t＞0.6T （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=1.8505时，全局最大值为3.8503；f4是Schaffer函数，当（x1，x2）=（0，0）时有全局最小值0。
2、测试结果对比分析。用本文算法同基本遗传算法和自适应遗传算法进行比较，其中取种群规模m=200，基本遗传算法的交叉概率pc=0.85和变异概率pm=0.1，自适应遗传算法的交叉概率和变异概率分别为：
，pm2=0.05，f'为两个要交叉个体适应度大的个体适应度值，最大迭代次数设为T＝150，对各测试函数分别独立运行100次得到表1。（表1）
通过实验表明，本文的算法在对函数f1、f3、f4的测试中，达到最优值的收敛代数明显减少，得到了令人满意的效果，对函数f2的测试中虽然本文算法提高了算法的收敛概率，同时收敛的代数也明显减少，所以本文的算法在减少收敛代数方面和提高收敛概率方面是具有优越性的。
四、结束语
本文提出改进的适应度函数，使得在进化初期一些函数值差的个体也能有更高的概率参与到选择、交叉、变异操作中，保存了种群的多样性，同时在自适应交叉的过程也采用了新的方法，使得在避免“近亲繁殖”的基础上扩大了搜索范围，整个算法结合实数编码的全局能力强和格雷码局部收敛能力强的两个特点，在算法中使用了实数编码与格雷编码相结合的方法，使得收敛的迭代次数明显减小。虽然采用格雷编码会导致算法收敛速度慢，但是明显降低了不收敛的次数，大大提高了算法收敛速度和收敛概率，使本文算法具有较高的计算效率。
主要参考文献：
[1]王力，侯燕玲.基于遗传算法通用试题库系统研究[J].微计算机信息，2008.5.
[2]李敏强，寇纪淞，林丹等.遗传算法的基本理论与应用[M].北京：科学出版社，2004.
[3]杨晓华，陆桂华，郦建强.解非线性极大极小问题的格雷码加速遗传算法[J].河海大学学报，2003.31.1.
[4]魏平，熊伟清.一种改进的实数编码遗传算法[J].计算机应用研究，2004.21.9.
[5]王小平，曹立明.遗传算法――理论、应用与软件实现[M].西安：西安交通大学出版社，2002.
转载注明来源:https://www.xzbu.com/2/view-1661573.htm
