一种改进的自适应遗传算法

文/刘晓霞 窦明鑫

（1.河北金融学院；2.中国地质大学长城学院 河北·保定）

引言

遗传算法（GA）由美国Michigan大学的Holland教授于1975年首先提出，后经De Jong、GoldBerg等人改进推广，广泛应用于各类问题。它是一种模拟自然界生物进化过程与机制的全局概率优化搜索方法。

早期遗传算法在进化过程中易出现早熟收敛和局部收敛性差等问题，为了克服上述问题，人们提出了多种改进算法。本文对自适应算法进行改进，算法中不仅交叉和变异概率是自适应的，而且构造了一种自适应的适应度函数，以便更好地进行复制、交叉、变异操作，同时结合实数编码精度高、搜索范围大和二进制编码的收敛速度快、变异操作易实现的特点，算法还采用了实数与二进制编码相结合的方式，在防止早熟的同时还能提高全局搜索能力，最后利用改进算法进行仿真实验，结果表明本算法具有收敛概率高和平均收敛代数少的优点。

一、改进的遗传算法

其中，fmax为上一代最优解所对应的函数值，t为当前代数，T为预先设置好的最大迭代次数。

2、格雷码周期变异。由于二进制变异容易控制，可以避免考虑实数变异涉及的变异方向，所以本文在变异操作中采用二进制格雷编码，格雷编码的定义见（2）式，

其中，p为原二进制编码，l为编码长度。格雷编码不仅具有良好的局部搜索能力，还能克服二进制编码Hamming悬崖，之后将变异概率设定成一个周期性变化的函数，见（3）式：

其中，a，b是待定值，此函数在一个周期内是单调递减的，在进化后期种群趋于稳定时，降低选择压的同时应该采取大概率变异，保持种群的多样性，防止陷入局部解。经测试，当a=3，b=19时算法性能较好。

二、算法步骤

Step1 采用实数编码产生初始种群，在函数定义域内按照均匀分布随机产生n个个体，｛xi｝（1，2，…n）设定最大进化代数设为T。

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，自适应遗传算法的交叉概率和变异概率分别为：

表1 三种算法对测试函数的运行结果

其中，pc1=0.85，pc2=0.65，pm1=0.15，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.