一种新型自适应遗传算法在多峰函数优化中的应用

张大科 钱谦

摘 要：为解决传统遗传算法在一维多峰函数优化中容易陷入局部极值、收敛概率低、稳定性不理想等问题，提出了一种新型的自适应遗传算法。结合自适应差分进化算法流程，提出了一种基于种群适应度变化程度而变化的非线性交叉算子和变异算子，使算法跳出局部极值，寻找到全局最优解，提升最优值迭代效率。函数测试实验表明，在一维多峰函数优化中，该算法在函数收敛概率、最优值迭代效率以及稳定性上比已有算法均有提高。

关键词：遗传算法；自适应；函数优化；变异概率；交叉概率

DOI：10.11907/rjdk.173028

中图分类号：TP312

文献标识码：A 文章编号：1672-7800（2018）006-0085-03

Abstract：Traditional genetic algorithm is easy to fall into the local extremum， its convergence probability and stability in one-dimensional multi-peak function optimization are also low. This paper presents an improved adaptive genetic algorithm. This algorithm uses a nonlinear crossover operator and mutation operator， which are based on the variation degree of population fitness values. Furthermore， the algorithm combines the process of the adaptive differential evolution algorithm. Two modifications can make the algorithm escape from the local extremum， find the global optimal solution and increase the iterative efficiency of the optimal value. Compared with other existing algorithms， the results of experiments show that the improved algorithm has good performance in improving the probability of convergence ， iterative efficiency of optimal value and algorithm stability .

Key Words：genetic algorithm； adaptive； function optimization； mutation probability； crossover probability

0 引言

遺传算法是美国Michigan大学的Holland提出，后来经过DeJong、Goldberg等人归纳总结形成的一类模拟进化算法[1-3]，它来源于达尔文进化理论和孟德尔的遗传变异理论[4]，作为一种自适应启发式全局意义上的搜索算法，具有很强的鲁棒性和通用的优化能力[5]。传统遗传算法拥有一个可以代表问题潜在解的种群，种群中的每个个体在选择、交叉、变异的作用下不断进化，以找到问题最优解。但传统遗传算法在解决函数优化问题上仍存在一些缺陷，故Srinivas[6]等人提出了自适应遗传算法（Adaptive Genetic Algorithms 以下简称AGA）。

在遗传算法中，交叉和变异两个控制参数是影响遗传算法性能的关键因素。具有自适应调节功能的交叉和变异算子，在种群演化过程中能随着种群的集中、分散而调节交叉和变异概率的大小。交叉概率的大小决定了种群的丰富度，交叉概率值越大，种群的丰富度就越高，种群中的优秀个体就越容易被破环。变异概率决定了产生新个体数量的多少，变异概率越高，产生的新个体就越多，就越容易跳出局部极值寻找到全局最优解。但是如果变异概率过大，很容易使遗传算法变成随机搜索算法[7]，所以自适应遗传算法通过对遗传参数的自适应调整，能够有效提高遗传算法的收敛精度和收敛速度。自适应遗传算法在保持种群多样性的同时，保证了算法的收敛性，有利于寻找到最优解[8]。

在自适应遗传算法发展初期，人们一直从交叉算子和变异算子基于种群个体适应度的线性变化进行分析优化。如Srinivas等人提出的AGA就是根据交叉概率和变异概率随着种群个体适应度中的平均适应度和最大适应度进行线性变换分析，如式（1）、式（2）所示。

在式（1）、 式（2）中， f-max表示种群中最大适应度，f-avg表示种群平均适应度。f-1表示参与交叉的两个个体中的较大适应度， f-2表示变异个体的适应度。

由式（1）、式（2）可知，交叉概率及变异概率随着种群适应度的分散和集中程度动态调整，当种群适应度较分散时，降低交叉概率和变异概率，当种群适应度较集中时，增大交叉概率和变异概率。在当前个体适应度和种群最大适应度无限接近时，交叉概率和变异概率的值也将无限趋近于零，这就导致在遗传算法进化初期，优秀的个体都处于一种稳定状态，所以此时的群体在进行全局寻优时很可能陷入局部极值，寻找不到全局最优解。由此可知，AGA的演化并不是非常理想[9]。

Srinivas等人提出的AGA主要是基于交叉算子和变异算子的线性变化进行演化，但线性变化并不能很好地解决在群体中寻找到全局最优个体。石山、励庆孚等[10]提出了余弦型自适应遗传算法（Cosine Adaptive Genetic Algorithms以下简称CAGA），通过交叉概率和变异概率随着种群个体适应度中的平均适应度和最大适应度进行非线性变换，处理函数优化问题。

改进后的交叉概率和变异概率随着适应值的增大而增大，随适应值的减小而减小。当前适应度和平均适应度无限接近时，余弦值接近于1，交叉概率和变异概率的值为最大。当前适应度值和平均适应度值无限远离时，余弦值接近于0但始终不等于0。所以CAGA相对AGA等算法的线性变化而言，在种群的前期提高了种群的交叉概率和变异概率，在种群的后期又降低了种群的交叉概率和变异概率，这样便将优良个体保存在种群中。但当种群中的平均适应度和最大适应度相差较大时，CAGA与AGA等基于线性调整的算法相比性能相差不大[11]。无论是普通的遗传算法还是自适应遗传算法，如何确定交叉算子和变异算子便成为提高算法性能的重要因素之一。

本文提出一种新型的自适应遗传算法（Improved Adaptive Genetic Algorithms以下简称IAGA）。从遗传算法的交叉、变异算子入手，结合自适应差分进化算法，先执行变异操作，再执行交叉操作，最后执行选择操作，使该算法在一维多峰函数的优化中能够兼顾全局搜索性和收敛稳定性。实验结果表明，改进后的自适应遗传算法在函数优化中比AGA和CAGA的收敛度更高，最优值的迭代效果更明显，基本达到了预期目的。

1 改进的自适应遗传算法

1.1 算法基本步骤

改进的自适应遗体算法步骤如下：①确定编码策略，采用二进制编码，建立从自变量的实际值到二进制编码之间的一一映射关系；②初始化种群，选定种群规模、染色体规模，确定收敛条件；③适应度分析。计算种群中每个个体的适应度，按照适应度大小排序；④判断tanf-avgf-max≤0.5是否成立，如果成立，说明此种群的平均适应度和最大适应度比较接近，若小于0.5则说明此时种群的适应度比较集中在某个区域内。此时进入步骤⑤操作，如果不成立，说明此种群的平均适应度和最大适应度相差较远，大于0.5则说明此种群的适应度呈现一种较分散状态，此时进入步骤⑥的操作；⑤按照自适应差分进化算法流程，即先执行变异操作，再执行交叉操作，最后执行选择操作；⑥按照传统遗传算法流程，即先执行选择操作，再执行交叉操作，最后执行变异操作；⑦将得到的种群采取精英保留策略；⑧判断是否满足收敛条件，如果满足条件就进行下一步操作，否则进行步骤③；⑨以此循环往复操作，直到找到最优解，输出最优解。

1.2 改进算法的交叉算子和变异算子

在自适应差分进化算法中经常构造如式（3）这样的变异算子。该算子能够在种群初期保持个体的多样性。随着种群的发展，到种群后期又能够保留优良信息，避免了优良个体被破坏。

此算子在规定的区间内前期变化平缓，中间变化逐渐加快，后期又逐渐减慢速度。本文基于自适应差分进化算法的变异算子，设计出解决一维多峰函数优化问题的IAGA算子，如式（4）、式（5）所示。

在式（4）、式（5）中，f-max表示种群中最大适应度，f-avg表示种群平均适应度，f表示当前个体适应度，P-C1表示交叉概率中的较大概率，本文选取P-C1=0.9。P-C2表示交叉概率中的较小概率，本文选取P-C2=0.1。P-m1表示变异概率中的较大概率，本文选取P-m1=0.2。P-m2表示变异概率中的最小概率，本文选取P-m2=0.001。

由式（4）、式（5）可知，改进后的交叉概率和变异概率无论当前适应度变大还是变小，交叉概率和变异概率都不会等于零，不会出现AGA在演化初期结果不理想的状况，避免在演化初期走向局部最优解。在当前个体远离最优个体时，交叉概率和变异概率的值渐渐提高，便于尽快寻找到最优解。在当前个体比较接近最优个体时，交叉概率和变异概率值渐渐减小，以避免当前个体进入局部最优解。

1.3 精英保留策略

为了保证每一代中的优良个体不被破坏，采取精英保留策略是非常必要的。精英保留策略即：如果下一代群体中的最佳个体适应度小于当前群体的最佳个体适应度，就将当前种群的最佳适应度或比下一代更优秀的个体保留下来，替代下一代中最差的个体。所以精英保留策略是群体收敛优化问题中群体寻优的一种保障。

为了体现出算子性能分析的准确性，本文采用最基本的选择、交叉、变异方法。其中选择操作选用经典的轮盘赌方法，交叉和变异操作选择单点交叉和单点变异。下面通过不同的实验论证本文优化算法。

2 改进算法实验结果及分析

2.1 测试函数

由于遗传算法中存在大量随机操作，为了分析改进算法的搜索性能，通常采用一些典型的一维多峰函数检验算法的实际效率。本文选取2个具有代表性的测试函数对改进的算法进行性能测试。

2.2 算法性能指标评价

将上述两个函数对IAGA、AGA和CAGA进行性能比较，然后将本文的IAGA和CAGA进行迭代结果比较，每個函数每种算法分别运算50次，群体规模100，进化代数500，交叉概率0.6，变异概率0.01，实验结果见表1～表3。

综合表1、表2、表3实验数据可知，本文提出的IAGA在2个测试函数中分别运算50次，收敛次数最多，并且0每

个函数的收敛概率都达到0.8以上，尤其在f-1（x）测试函数下，函数的收敛概率达到了0.98，比AGA收敛概率高出0.2以上，比CAGA的收敛概率高出0.1以上。在迭代次数方面，本文的IAGA比AGA提前20代达到最优值，比CAGA提前100多代达到最优值。通过对比可以看出，本文的IAGA在全局收敛和迭代代数上均有提高，结果理想。

由图1、图2的函数迭代结果可知，图1中的CAGA在达到最大值前进入了局部极值，而本文的IAGA则进行了正常的搜索，最后趋向最大值。图2中的CAGA在迭代过程中一直趋向最大值，而且迭代过程不稳定，而本文的IAGA则依然维持在6 400左右的均值水平。由此可见，新算法在收敛概率和迭代次数方面有所提高，更具稳定性。

3 结语

本文通过对Srinivas等提出的AGA以及石山等提出的CAGA交叉算子和变异算子的分析，指出了AGA和CAGA在函数优化中存在的不足。结合自适应差分进化算法运算过程，同时基于自适应差分进化算法的变异算子，设计并改进出一种新型的自适应遗传算法。算法实现方案简单，种群适应度随着基于改进的遗传算法的交叉算子和变异算子进行非线性动态变化。IAGA与AGA和CAGA相比，本文的IAGA收敛概率更高，最优值的迭代次数也有所提升，具有更可靠的稳定性，所以本文的IAGA在一维多峰函数优化中是一种有效算法。

参考文献：

[1] DEJONG K A. The analysis of the behavior of a class of genetic adaptive systems[D]. Ann Arbor： University of Michigan Press，1975.

[2] 席裕庚，柴天佑.遗传算法综述[J].控制理论与应用，1996，13（6）：697-708.

[3] 吉根林.遗传算法研究综述[J].计算机应用与软件，2004，21（2）：69-73.

[4] 葛继科，邱玉辉.遗传算法研究综述[J].计算机应用与研究，2008，25（10）：2911-2916.

[5] 欧阳森，王建华.一种新的改进的遗传算法及其应用[J].系统仿真学报，2003，15（8）：1066-1068.

[6] SRINIVAS M ， PATNAIKL M . Adaptive probabilities of crossover and mutation in genetic algorithms[J]. IEEE Trans on Systems， Man and Cybernetics，1994，24（4）：656-667.

[7] 王思艳.自适应遗传算法的研究[D].北京：华北电力大学，2009.

[8] CONGRUI YANG， QIAN QIAN. An improved adaptive genetic algorithm for function optimization[C]. IEEE International Conference on Information and Automation，2017：675-680.

[9] 金晶，蘇勇.一种改进的自适应遗传算法[J].计算机工程与应用，2005（18）：64-69.

[10] 石山，励庆孚.基于自适应遗传算法的无刷直流电机的优化设计[J].西南交通大学学报，2002，36（12）：1215-1218.

[11] 邝航宇，金晶.自适应遗传算法交叉变异算子的改进[J].计算机工程与应用，2006（12）：93-96.

（责任编辑：杜能钢）