基于语义聚类的遗传规划算法比较

王 菁，徐赐文，吕林旺

(中央民族大学 理学院，北京 100081)

0 引 言

遗传规划算法(genetic programming，GP)是基于树结构的进化算法[1]，具有形式灵活、可解释性强等优点，已经被成功应用于诸多领域，如：任务规划[2，3]、流行病学[4]、图像识别[5，6]、分类问题[7-9]、特征选择[10，11]等等。然而GP仍存在收敛速度太慢和容易陷入局部最优的问题。

针对这些不足，文献[12]提出几何语义GP(geometric semantic genetic programming，GSGP)，并验证了GSGP可以有效降低搜索难度。文献[13]通过估计最佳个体概率分布确定个体的选择概率。文献[14]划分细粒度的生态位，以此保持种群多样性。文献[15]提高相似性较低的父代之间的交叉概率，只保留更优的子代。文献[16]通过语义图示划分搜索空间，对重要性较高的图示执行局部搜索。这些方法有效的提高了算法效果。

但此类方法需要比较子代与父代的相似性，计算量巨大。为了避免该问题，常见的做法是构建基于个体语义聚类的选择算子(semantic-clustering selection，SCS)。传统的SCS只考虑了K均值聚类，但在现实应用中不同类型的问题适用于不同的聚类算法。因此，本文提出了一种基于语义聚类的锦标赛选择算子，并比较K均值聚类、密度聚类、层次聚类、谱聚类在其中的效果；其次，提出了一种自适应的适应度函数，提高优秀的个体入选锦标赛的概率；第三，构造了一种基于语义聚类的遗传规划算法，通过实验将其与标准GP、GSGP、SCS-GP进行比较，验证了算法的有效性。

1 遗传规划算法

1.1 算法简介

遗传规划的个体是存储在树结构中的计算机程序，在符号回归问题中，每个程序代表一个函数表达式。根节点和子节点的元素从函数符集内产生；叶子节点的元素从终止符集中产生，不同给定问题的终止符集不同，在符号回归问题中，终止符集由全体实数与变量构成。之后对树进行中序遍历，形成函数表达式。其遗传操作为对个体的子树进行互换、剪枝与随机生成等。其终止条件为达到实验设定的迭代次数或者适应度阈值。

1.2 个体语义

在遗传规划中，一般认为个体的语义为与输入向量相关的向量、编码、算子。本文将个体P的语义定义为：当输入向量为 (x1，x2，…，xn) 时P的输出向量，其适应度为S(P)=(P(x1)，P(x2)，…，P(xn))。

2 基于语义聚类的遗传规划算法

2.1 基于语义聚类的锦标赛选择算子

为了实现子种群的识别与子种群内部的遗传操作，本文提出基于语义聚类的锦标赛选择算子(tournament selection operator based on semantics clustering，TS-SC)，在子种群内部进行锦标赛选择。

具体流程为：首先在完整的父代种群中选择一个个体，假如需要对它交叉操作，则在其所在的子种群中通过锦标赛选择获取第二个个体。TS-SC算子基本步骤如算法1所示。

算法1：TS-SC

输入：Population，TourSize

输出：The winner individual

(1)ξn←Cluster(Population)// 生成子种群;

(2) A←RandomIndividual(Population,1)// 从完整的父代种群中随机抽取一个个体A;

(3)CA←ClusterContain (A);// 返回A所属于的子种群CA;

(4) {Bn}←RandomIndividual(CA,TourSize) // 从CA中随机抽取TourSize个个体形成集合;

(5) R=Bestfitness({Bn})// 选择{Bn}中适应度最好的个体;

(6) The winner individual←R //R即为锦标赛选择结果。

在该算子中，函数Cluster(Population)对给定种群聚类，返回子种群集合ξn，ξn={C1，C2，…，Cn}，Ci代表第i个子种群；函数RandomIndividual(Population，1)，从给定种群中，等概率、有放回的随机抽取一个个体，记为A；函数ClusterContain(A)，返回A所属于的子种群，记为CA； 从CA中等概率、有放回的随机选择TourSize个个体，选择出其中适应度表现最好的个体，记为R，R即为TS-SC的输出结果。

TS-SC利用个体语义划分不同的搜索空间，使得子代个体会向几个不同的局部最优解聚集，从而保证了种群多样性。然而TS-SC可能导致两个问题：首先，聚类效果受到相似度测度的影响，不同的任务适合不同的相似度测度，因此需要针对不同的任务为TS-SC选择不同的聚类算法。其次，聚类算法产生的子种群中，可能有包含较多个体的子种群，这些个体虽然在同一个局部最优解内，但是个体表达的质量不同，在锦标赛选择中，可能会丢失表达质量更好的个体。为了探索上述问题，在第3节中，设置了多种聚类方法在不同任务上的对比实验，为聚类方法的选择提供参考与指引。

2.2 基于子种群规模的自适应适应度函数

为了提高算法的局部搜索能力，本文提出了一种基于子种群规模的自适应适应度，具体形式如式(1)所示

AdaptiveFitness=RawFitess+f(Sizec)

(1)

其中，Sizec表示每个个体所属子种群的规模，使子种群内个体数目少的个体具有较优秀的适应度，提高其被选择的概率，以此保持种群多样性。根据原始适应度函数方向的不同，可以构造为减函数或者增函数。

由于基准问题都采用下降型的fitness并且其收敛阶段的fitness量级各不相同，因此将其构造为

AdaptiveFitness=(1+0.1×Sizec)×RawFitness

(2)

使得更为独特且适应度优秀的个体在下一代的选择中占据优势，从而避免遗漏某些与其它个体都不相似的局部最优解。

2.3 基于语义聚类的遗传规划算法

在GSGP与SCS选择算子的基础上，本文提出了一种基于语义聚类的遗传规划算法(genetic programming algorithm based on semantic clustering，SCGP)。SCGP通过欧式距离计算个体间的语义距离，以语义距离测度语义相似度，并通过聚类将种群划分为多个不同的子种群。在子种群内部进行锦标赛选择、交叉、变异，既可以使语义相似的父代个体进行交叉，使子代个体有更可能满足GSGP对语义的要求，实现全局搜索能力的提升；同时也可以避免属于不相似的个体进行交叉，避免破坏现有的优良结构。

SCGP的流程如图1所示。

图1 基于语义聚类的遗传规划算法流程

3 实验与结果分析

3.1 实验设置

在不同的任务中，为了获得较好的效果，需要为SCGP选择不同的聚类算法。聚类算法按照原理不同可分为：划分聚类、密度聚类、层次聚类与其它。本文从4类中分别选择一个：K-means聚类、DBSCAN、Agglomerative Cluster、谱聚类，测试其在SCGP中的效果。实验在10个基准问题上开展，F1-F6为符号回归问题，F8为数值回归问题，其余为二分类问题，问题细节见表1。回归问题的原始适应度函数为平均绝对误差(MAE)，二分类问题的原始适应度函数为二分类交叉熵

表1 基准问题的详细信息

(3)

实验的参数设置见表2，为了使初始种群更有可能覆盖到全局最优解，实验采用“Ramped half and half”方式初始化种群。此外，为了保留每代演化出的优秀个体，实验添加了精英保留的操作。

表2 SCGP的参数设置

在下文表格中，如果一种方法的结果优于标准锦标赛选择的GP(以下简称为GP)，则在末尾标记“+”；如果它与GP相比更差，则此结果标记为“-”。每个实验均使用相同的计算平台(操作系统：Windows 11家庭中文版(64 bit)，RAM 16.0 GB，AMD Ryzen 5 5600H with Radeon Graphics CPU@3.30 GHz)。

为了更全面分析SCGP的性能，实验为SCGP分别嵌入了K-means聚类、DBSCAN、Agglomerative Cluster、谱聚类4种聚类方法，比较其在拟合、泛化和运行时间方面的表现。实验中每种算法均采用相同的随机初始种群，以避免由不同初始种群所引起的结果差异。本文将在每一个问题上测试分别基于上文提到的4种聚类方法的SCGP并将其与GSGP和SCS-GP进行对比。

3.2 拟合表现分析

通过训练误差来分析各个算法的拟合能力，各个算法训练100次时的误差中位数见表3。回归问题用MAE、分类问题用F1-score测度误差。

表3 不同算法在训练集上的实验结果

在大多数任务中SCGP优于标准GP，这说明通过聚类生成子种群并在子种群内部进行遗传操作的可以提高GP的性能。在6个符号回归问题中，除F6外，其余问题中的SCGP都显著优于标准GP；SCGP在F6问题中表现不佳，可能是因为问题特征数较多且训练样本量较少，聚类效果不佳，未能准确的划分子种群。SCGP虽然利用个体语义进行了聚类，但是忽略了个体结构蕴含的信息，无法较好识别语义差异较小但位于不同局部最优解附近的个体，这在一定程度上影响了算法的性能。与GSGP和SCS-GP相比，层次聚类嵌入的SCGP在符号回归任务中的表现都优于或等同于两个现有算法；谱聚类嵌入的SCGP在达到收敛的所有的分类任务中，优于两个现有的算法。这说明通过选择适当的聚类方法，可以有效获得相比现有语义GP更优的拟合能力。

由图2可知，除DBSCAN-SCGP外，所有算法都达到了收敛。在F1、F7、F10中，标准GP收敛速度最快，但是各个SCGP的收敛适应度值都达到了相较于标准GP、SCS-GP、GSGP相当或者更优秀的值。这是由于语义聚类分散了初期的个体适应度。并且较之标准GP和GSGP，SCGP明显波动幅度更大，说明SCGP是受过拟合影响较小的技术。

图2 各个算法在不同问题上的收敛曲线

3.3 泛化表现分析

实验采用在测试集上的误差来测度其泛化性能。表4给出了不同实验在测试集上的最佳适应值的中位数。由表4可知，SCGP在大部分问题测试集上的泛化精度表现都由于标准GP。除F6外，SCGP的泛化能力都等同或者优于标准GP。

表4 不同算法在测试集上的实验结果

Agglomerative Cluster-SCGP与谱聚类-SCGP在不同问题上的表现均较好。在3个符号回归任务中，SCGP的泛化能力不如GSGP，只在一个符号回归问题中SCGP优于GSGP。但是在分类任务中，SCGP的泛化能力显著优于GSGP与SCS-GP。说明由于符号回归任务的复杂度较低，SCGP出现了过拟合；在样本数较多的分类问题中，相较于SCGP与SCS-GP，SCGP能够更好利用数据的特征，在测试集中能取得更优秀的精度。这说明只要选择到合适的聚类方法，语义聚类划分子种群的思想有助于提升算法的泛化表现。同时，由于许多聚类算法不能做到根据不同的种群自适应的选择子种群的数目，因此K均值聚类与密度聚类嵌入的SCGP在实验中的泛化表现处于劣势。而不需要提前指定子种群数目的层次聚类与谱聚类嵌入的SCGP的泛化能力较优。

3.4 运行速度分析

在运行速度方面，本文实验采用10次运行的平均运行时间来测度运行速度的快慢。可以预见的是，由于需要进行计算子种群分类，SCGP的运行速度必然比标准GP慢。每个算法的平均运行时间见表5，因为DBSCAN算法并未收敛，因此不具参与讨论。除问题F3外，SCGP的运行时间长于标准GP，其中K均值与层次聚类嵌入的SCGP由于其聚类算法的复杂度低，运行时间虽然高于标准GP但是仍在可接受的范围内。相比之下，谱聚类算法的时间复杂度过高，因此运行时间极长。与GSGP相比，由于基于聚类的算法不需要对每个可能的交叉组合进行遍历试错，因此其运行时间显著低于GSGP。在问题F3中，SCGP的运行时间显著低于标准GP，可能是由于通过划分语义子种群，降低了个体深度的膨胀，从而降低了计算成本。

表5 不同算法解决问题时的运行时间比较/s

3.5 实验总体结果分析

本文通过在符号回归、真实数据集回归、分类等基准问题上分别运行标准GP、GSGP、SCS-GP、KMeans-SCGP、DBSCAN-SCGP、AgglomerativeCluster-SCG、SpectralCluster-SCGP，并对SCGP的性能进行了分析。并且分别从拟合表现、泛化表现、运行速度3个角度，对不同聚类算法嵌入的SCGP、标准GP、GSGP、SCS-GP进行了对比分析。

广泛的实验结果表明，SCGP在分类问题中具备优于标准GP、GSGP与SCS-GP的拟合与泛化能力；在回归问题中略差于GSGP，但优于GP与SCS-GP。并且SCGP在运行速度上优于GSGP和SCGP，但差于标准GP。从实验结果来看，这些增长的计算量有助于提高拟合与泛化能力。在不同聚类算法嵌入的对比方面，层次聚类嵌入的SCGP在多数问题中优于其它SCGP与标准GP。这表明通过语义划分子种群有助于算法的改进。

4 结束语

本文提出的基于语义聚类的遗传规划算法(GSGP)，在标准GP的基础上，添加了基于语义聚类的锦标赛选择算子、自适应的适应度函数。

该选择算子，利用个体语义信息划分子种群，使得个体向几个不同的局部最优聚集，保证了种群的多样性。同时，利用子种群规模构造自适应的适应度函数，提高优秀个体被选择的概率，提高了搜索能力。实验结果表明，相较于标准GP、SCS-GP，本文算法的拟合和泛化能力均得到了提高；在多数基准问题中，层次聚类嵌入的SCGP算法显著优于其它的聚类嵌入。