基于語義聚類的遺傳規劃算法比較

王 菁，徐賜文，呂林旺

(中央民族大學 理學院，北京 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算法顯著優于其它的聚類嵌入。