基于高斯函数和自适应精英策略的遗传算法

李清霞

(东莞城市学院 计算机与信息学院，广东东莞 523419)

遗传算法(Genetic algorithms，简称GA)是由Holland等人提出的[1]，20世纪六七十年代最流行、应用最广泛的算法。它的灵感来源于达尔文的自然选择理论[2]。遗传算法是一种基于群体的，依赖于偶然搜索的优化方法。在遗传算法中，群体由一组称为染色体的n个个体组成，主要包括两种表示方式：1)基因型(二进制表示)或2)表型(实数表示)。由于遗传算法的参数简单，所以在解决优化问题具有较强的优势。然而，根据“没有免费的午餐”定理[3]，在解决不同的优化问题时，甚至在进化的不同阶段，任何算法都没有适合所有情况的特定参数设置或策略。因此，有大量的研究工作者致力于基于现有的遗传算法设计出新的变异和交叉操作算子，或者通过调整参数的方法来提高算法的鲁棒性和准确性。其中，大多数研究者提出的遗传算法变种旨在开发适应性或自适应性改进操作算子或控制参数设置方式来改进遗传算法性能[4-7]。

Srinivas等[8]首次提出了改进的自适应性遗传算法，该算法采用自适应性交叉和变异概率改进操作算子以实现种群的多样性，提高算法收敛速度。王储等[4]提出了一种基于精英策略的多种群自适应遗传算法，该算法通过融入一种混合精英策略，提高算法的收敛性能,精英选择算子选择当前种群的最优解并进行精英备份，不断迭代选出最优解。徐逸帆等[9]针对传统遗传算法具有收敛速度慢、易陷入局部最优解的问题，分析种群个体特别是精英个体的特征，使用最小一乘法重新定义适应度函数，提出了基于精英保留策略的遗传算法。袁帅鹏等[10]提出了一种基于自适应网格法的择优策略来改进带精英策略的快速非支配排序遗传算法，有效克服了使用传统Pareto支配法择优策略在解决离散问题时容易丢失有用信息的缺陷。郭军[11]指出带精英策略的非支配排序遗传算法是目前最流行的多目标优化算法之一，具有较高的求解效率，可在一次运行过程中得出多个高质量的解，成为了其它多目标优化算法进行性能对比的基准算法。王磊等[12]等通过分析简单遗传算法中精英个体的特征，提出了一种应用于功能验证的精英策略，该算法将本代优秀个体和本代适应度高的历史优秀个体视为精英个体，给予额外交叉机会。王福才等[13]提出了一种混合精英策略的元胞多目标遗传算法，该算法在分析元胞种群结构的特点基础上，融入一种混合精英策略，提高了算法的收敛性能。赵鑫宁等[14]提出了一种基于高斯分布和柯西分布的概率选择算子，该算法在执行选择操作时，分别根据当前种群生成高斯和柯西分布，通过对分布采样获得参加遗传操作的个体，从而保证了种群多样性，避免早熟收敛。

在遗传算法中，当子代不能代替当前个体进行多次迭代时，就会出现停滞现象，面对停滞现象，很多改进的遗传算法就会显得无能为力，这也意味着现有的改进机制可能会出现暂时性的失效。一般地，停滞的主要原因可能是缺乏多样性或陷入局部最优。

为了解决种群进化停滞问题，笔者提出一种基于高斯函和自适应精英策略的遗传算法，该算法基于标准遗传算法，采用精英种群选择策略以引导停滞个体继续进化，在交叉操作算子中引入高斯函数以实现种群的多样性。精英策略是指从动态变化的精英群体中随机抽取精英个体进行生存选择，高斯函数主要是采用高斯函数的正态分布交叉操作算子来实现种群的多样性。整个进化过程由全局和局部参数控制，这些参数能够适应整个种群和个体自身的变化。为了证明本文算法的健壮性和有效性，将本文算法和传统遗传算法及其变种、其他改进的进化算法对于CEC 2014基准函数和两个实际优化问题进行了实验测试，仿真结果表明，本文算法提高了遗传算法的多样性，具有更高的求解精度和更好的收敛性。

1 遗传算法

遗传算法是一种基于种群的算法，种群中的个体都被编码为二进制值的字符串或染色体，即0或1。每一个个体都代表了一个可能的解，并且可以用编码表示解的许多特征，包括数值、结构特征、备选解之间的选择等等。遗传算法通过种群的选择、交叉和变异操作产生后代及子代替换，使种群朝着目标函数定义的更好适应度值的方向发展。

遗传算法主要包括选择、交叉和变异操作算子，分别定义如下：

选择：定义哪些个体将把他们的遗传信息传递给下一代，一般采用基于概率的选择机制来决定群体中哪些个体被选择。目前比较流行的三种选择机制分别是：比例选择、基于排名的选择和锦标赛选择。

交叉：用来混合父代的遗传信息，而不引入任何新的信息。交叉操作一般包括单点交叉、两点交叉和均匀交叉。在单点交叉中，选择染色体中的一个点，交换它们的尾部。在两点交叉中，选择两个点，个体交换中间部分。在均匀交叉中，每一个比特都可以从一个父节点或另一个节点中选择。

变异：对种群中个体的基因信息进行变动，以增加算法的局部搜索能力。根据个体编码方式，可以把变异操作分为实数变异和二进制变异。一般来说，变异操作的基本步骤包括：1)对群中所有个体以事先设定的变异概率判断是否进行变异；2)对进行变异的个体随机选择变异位进行变异。

2 基于高斯函数和自适应精英策略的遗传算法

2.1 算法思想

基于高斯函数和自适应精英策略的遗传算法(ESG-GA)的主要思想是利用动态变化的精英个体和基于高斯分布的交叉操作算子来更新停滞的个体，以平衡开发和探索能力。

为了检测进化过程的状态，引入了一个全局控制参数GCP和个体状态参数ISP，其中GCP用来控制种群的搜索空间，ISP用来统计个体在整个种群中的适应度情况，这两个定义为

(1)

(2)

其中，Tmax是最大的代数，t表示当前代数。GCP的值随着迭代的进行而减小。f(xi,t)是t代第i个个体目标函数的值，fmax和fmin是当前种群目标函数的最大值和最小值。对于最小值优化，ISP值越小就表示个体更优。对于这两个检测参数，GCP用于全局控制，ISP用于局部控制，同时GCP也直接决定了精英个体的规模。

在自适应精英策略中，是从精英种群中随机选择一个精英个体，而不是从当前种群中择优选择个体。精英种群是由当前种群中具有最佳适应度值的个体组成的种群。精英种群的大小ENP根据全局控制参数GCP的变化而动态地变化。

ENP=floor((GCP-1)*Tmax+NP),

(3)

其中NP是种群大小，floor函数用于保证ENP是整数。当前的精英种群是根据适应度值从当前种群中选择最优秀的ENP个个体组成的。需要注意的是，每次使用当前GCP值计算ENP值时，精英种群都会被重建，因此精英种群能够始终保持最新，也就不需要再保存历史精英种群。随着迭代次数的增加，ENP动态减少，种群多样性降低，搜索的重心将逐渐从全局探索转移到局部开发，从而提高算法后期的搜索精度。还需注意的是，一个精英个体是从精英种群中随机挑选出来的，而不是从精英种群中择优选择的最优个体，这样做主要是为了减少贪婪，增加除了最优个体之外发现有用信息的机会。

为了创建一个更多样化的后代种群以提高遗传算法的性能，在遗传算法的迭代中，通过应用一个基于高斯函数的正态分布交叉操作算子来实现种群的多样性。

(4)

其中μ表示适应度值，σ2表示变量。

σ2可由下式计算：

σ2=(GCP×(xi,t-ej,t))2，

(5)

其中xi,t表示第t代的个体，ej,t表示第t代精英种群中随机选择的个体。全局控制参数GCP可以保证搜索空间逐渐缩小，意味着进化是朝向精英区域发展，这有助于提高收敛精度。

针对μ的计算，如果当前个体优于精英个体，则μ用当前个体代替，否则μ用精英个体代替，定义如下：

(6)

ESG-GA算法在最初的进化阶段，搜索过程集中在对当前个体的开发上，随着代数的增加，搜索的焦点转移到精英个体上。当前个体越好，它所占的权重就越大，因此ESG-GA算法可以有效地利用个体的信息。

ESG-GA算法的自适应精英策略主要表现为：在进化的早期阶段，精英策略并没有过多的干扰种群的选择过程，当种群个体开始停滞不前时，精英策略逐步占主导作用，给予个体进化更多的引导，使进化朝着精英区域发展。因此ESG-GA算法比其他改进的GA算法能够发挥更好的收敛精度。

2.2 算法描述

根据算法思想，ESG-GA算法执行过程的伪代码如下。

输入:初始种群初始化种群P(种群大小为NP);while t

采用式(6)计算个体状态参数ISP;采用式(7)计算精英种群的大小ENP;按照适应度值优先级从种群个体中选择出EPN个精英个体组成精英种群;for i=NP do 采用式(6)计算μ; 采用式(5)计算变量σ2; 采用式(4)执行交叉操作产生高斯分布的个体; 执行变异操作; 产生下一代种群;endend输出:最优种群

2.3 算法复杂度分析

由于ESG-GA算法主要是针对传统遗传算法的交叉算子进行改进，并没有增加迭代次数，也没有增加适应度评估数量，因此ESG-GA算法的时间复杂度与传统GA算法基本上一致。具体分析如下：

在算法中，对于外层循环，最多执行Tmax次，对于内层循环，需要执行NP次。由于在两个嵌套循环内的其他操作都是顺序执行语句，所以ESG-GA算法时间复杂度为O(Tmax·NP)。

3 实验结果与分析

为了验证ESG-GA算法的有效性，在软件环境为MATLAB 2018b，硬件环境为8G内存、64位Intel(R)I5 2.60GHz处理器上对该算法进行了仿真实验。将ESG-GA算法与传统遗传算法及7种改进进化算法对于CEC 2014基准函数和2个实际优化问题进行比较实验。

对比实验中的8种进化算法包括标准GA和3种具有竞争力的GA变种算法(GCSGA[11]，NRGA[15]，GA-RTS[16])以及4种其他进化算法(JADE-sort[17]，M_PSO_MA[18]，MABCM[19]和EIR-DE[20])。CEC 2014的30个基准函数根据功能可分为4类：

1)f1-f3：单峰函数；

2)f4-f16：简单多峰函数；

3)f17-f22：混合函数；

4)f23-f30：合成函数。

实验中的实际优化问题为文献[21]中常用于评价各种算法性能的两个现实优化问题：调频声波参数估计(rf1)和扩频雷达多相码设计(rf2)。所有问题都经过测试，最大评估次数设置为5×105。对于统一性，所有算法的种群大小都相同，即NP=100。一般情况下，设交叉概率为0.4，变异概率为0.005。对于基准测试函数，其维度分别等于50D和100D。当最大评估次数用完或者到达最大的迭代代数时，进化过程将终止。每种算法运行50次，得到误差值的平均值和标准差用表格数据显示。

3.1 基准函数的仿真结果

表1记录了标准GA、3种GA变体算法在50D基准函数与ESG-GA算法的比较统计。对于每一种算法，适应度值误差较小的平均值以粗体显示。

表1 GA及其变种算法与ESG-GA算法在50D基准函数上的比较

从表1可以看出，ESG-GA算法只有在函数f3、f17处于劣势(其中在函数f23中相等)，在其他27个函数中均超越了其他4种算法。

由于篇幅限制，随机地选择了两个50D基准函数画出了算法的收剑图，如图1和图2所示，分别显示了所有算法对于50D基准函数f3和f20的收敛图。从图1和图2明显可以看出，ESG-GA算法的收敛速度和收敛精度明显高于其他4种算法。

图1 各算法对于50D基准函数f1的收敛图

图2 各算法对于50D基准函数f20的收敛图

表2显示了其他4种进化算法在100D基准函数与ESG-GA算法的比较统计。同样，对于每一种算法，适应度值误差较小的平均值以粗体显示。

从表2可以看出，ESG-GA算法在函数f8、f17、f23、f26和f28上分别与MABCM、JADE-sort和EIR-DE算法取得相等成绩，只有在函数f4、f12和f22上比MABCM、JADE-sort和EIR-DE算法稍处于劣势，但在其他23个基准函数上，都超越了MABCM、JADE-sort和EIR-DE算法。另外，ESG-GA算法在所有基准函数上都超越了M_PSO_MA算法。

表2 其他进化算法与ESG-GA算法在100D基准函数上的比较

图3和图4分别显示了所有算法对于100D基准函数f5和f30的收敛图，从图3和图4明显可以看出，与其他4种算法相比，ESG-GA算法虽然收敛精度相差不大，但收敛速度还是明显占优。

图3 各算法对于100D基准函数f5的收敛图

图4 各算法对于100D基准函数f30的收敛图

3.2 真实问题的仿真结果

从表3总结的仿真结果可以看出，ESG-GA算法在处理第一个实际优化问题中，远超于其他进化算法，具有显著的优势。在处理第二个问题时，与某些进化算法差距不算太明显，但也优于其他进化算法。

表3 ESG-GA算法与8种进化算法与在实际优化问题上的比较

实验结果表明，ESG-GA算法能够适应整个种群和个体自身的变化，引导个体进化到潜在的搜索空间。

4 结语

针对遗传算法中存在的停滞问题，提出了一种基于高斯函数和自适应精英策略的遗传算法，该算法先是基于种群个体适应度值排序，然后从排好序的种群个体中随机选择一些精英个体组成精英种群，用来引导停滞的个体继续进化以解决遗传算法中存在的个体进化停滞问题，最后在交叉操作算子中引入高斯函数以实现种群的多样性。在测试CEC 2014中50D、100D和两个实际优化问题的基准函数后，验证了ESG-GA算法相对于其他8种进化算法的优越性，同时给出了适应度值误差的均值、标准差和收敛图的比较。所有的实验结果表明，所提出的算法能够有效地帮助处于停滞状态的个体继续进化，具有更高的求解精度和更好的收敛性。