基于語義聚類的遺傳規(guī)劃算法比較

王 菁，徐賜文，呂林旺

(中央民族大學(xué) 理學(xué)院，北京 100081)

0 引 言

遺傳規(guī)劃算法(genetic programming，GP)是基于樹結(jié)構(gòu)的進化算法[1]，具有形式靈活、可解釋性強等優(yōu)點，已經(jīng)被成功應(yīng)用于諸多領(lǐng)域，如：任務(wù)規(guī)劃[2，3]、流行病學(xué)[4]、圖像識別[5，6]、分類問題[7-9]、特征選擇[10，11]等等。然而GP仍存在收斂速度太慢和容易陷入局部最優(yōu)的問題。

針對這些不足，文獻[12]提出幾何語義GP(geometric semantic genetic programming，GSGP)，并驗證了GSGP可以有效降低搜索難度。文獻[13]通過估計最佳個體概率分布確定個體的選擇概率。文獻[14]劃分細粒度的生態(tài)位，以此保持種群多樣性。文獻[15]提高相似性較低的父代之間的交叉概率，只保留更優(yōu)的子代。文獻[16]通過語義圖示劃分搜索空間，對重要性較高的圖示執(zhí)行局部搜索。這些方法有效的提高了算法效果。

但此類方法需要比較子代與父代的相似性，計算量巨大。為了避免該問題，常見的做法是構(gòu)建基于個體語義聚類的選擇算子(semantic-clustering selection，SCS)。傳統(tǒng)的SCS只考慮了K均值聚類，但在現(xiàn)實應(yīng)用中不同類型的問題適用于不同的聚類算法。因此，本文提出了一種基于語義聚類的錦標賽選擇算子，并比較K均值聚類、密度聚類、層次聚類、譜聚類在其中的效果；其次，提出了一種自適應(yīng)的適應(yīng)度函數(shù)，提高優(yōu)秀的個體入選錦標賽的概率；第三，構(gòu)造了一種基于語義聚類的遺傳規(guī)劃算法，通過實驗將其與標準GP、GSGP、SCS-GP進行比較，驗證了算法的有效性。

1 遺傳規(guī)劃算法

1.1 算法簡介

遺傳規(guī)劃的個體是存儲在樹結(jié)構(gòu)中的計算機程序，在符號回歸問題中，每個程序代表一個函數(shù)表達式。根節(jié)點和子節(jié)點的元素從函數(shù)符集內(nèi)產(chǎn)生；葉子節(jié)點的元素從終止符集中產(chǎn)生，不同給定問題的終止符集不同，在符號回歸問題中，終止符集由全體實數(shù)與變量構(gòu)成。之后對樹進行中序遍歷，形成函數(shù)表達式。其遺傳操作為對個體的子樹進行互換、剪枝與隨機生成等。其終止條件為達到實驗設(shè)定的迭代次數(shù)或者適應(yīng)度閾值。

1.2 個體語義

在遺傳規(guī)劃中，一般認為個體的語義為與輸入向量相關(guān)的向量、編碼、算子。本文將個體P的語義定義為：當(dāng)輸入向量為 (x1，x2，…，xn) 時P的輸出向量，其適應(yīng)度為S(P)=(P(x1)，P(x2)，…，P(xn))。

2 基于語義聚類的遺傳規(guī)劃算法

2.1 基于語義聚類的錦標賽選擇算子

為了實現(xiàn)子種群的識別與子種群內(nèi)部的遺傳操作，本文提出基于語義聚類的錦標賽選擇算子(tournament selection operator based on semantics clustering，TS-SC)，在子種群內(nèi)部進行錦標賽選擇。

具體流程為：首先在完整的父代種群中選擇一個個體，假如需要對它交叉操作，則在其所在的子種群中通過錦標賽選擇獲取第二個個體。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}中適應(yīng)度最好的個體;

(6) The winner individual←R //R即為錦標賽選擇結(jié)果。

在該算子中，函數(shù)Cluster(Population)對給定種群聚類，返回子種群集合ξn，ξn={C1，C2，…，Cn}，Ci代表第i個子種群；函數(shù)RandomIndividual(Population，1)，從給定種群中，等概率、有放回的隨機抽取一個個體，記為A；函數(shù)ClusterContain(A)，返回A所屬于的子種群，記為CA； 從CA中等概率、有放回的隨機選擇TourSize個個體，選擇出其中適應(yīng)度表現(xiàn)最好的個體，記為R，R即為TS-SC的輸出結(jié)果。

TS-SC利用個體語義劃分不同的搜索空間，使得子代個體會向幾個不同的局部最優(yōu)解聚集，從而保證了種群多樣性。然而TS-SC可能導(dǎo)致兩個問題：首先，聚類效果受到相似度測度的影響，不同的任務(wù)適合不同的相似度測度，因此需要針對不同的任務(wù)為TS-SC選擇不同的聚類算法。其次，聚類算法產(chǎn)生的子種群中，可能有包含較多個體的子種群，這些個體雖然在同一個局部最優(yōu)解內(nèi)，但是個體表達的質(zhì)量不同，在錦標賽選擇中，可能會丟失表達質(zhì)量更好的個體。為了探索上述問題，在第3節(jié)中，設(shè)置了多種聚類方法在不同任務(wù)上的對比實驗，為聚類方法的選擇提供參考與指引。

2.2 基于子種群規(guī)模的自適應(yīng)適應(yīng)度函數(shù)

為了提高算法的局部搜索能力，本文提出了一種基于子種群規(guī)模的自適應(yīng)適應(yīng)度，具體形式如式(1)所示

AdaptiveFitness=RawFitess+f(Sizec)

(1)

其中，Sizec表示每個個體所屬子種群的規(guī)模，使子種群內(nèi)個體數(shù)目少的個體具有較優(yōu)秀的適應(yīng)度，提高其被選擇的概率，以此保持種群多樣性。根據(jù)原始適應(yīng)度函數(shù)方向的不同，可以構(gòu)造為減函數(shù)或者增函數(shù)。

由于基準問題都采用下降型的fitness并且其收斂階段的fitness量級各不相同，因此將其構(gòu)造為

AdaptiveFitness=(1+0.1×Sizec)×RawFitness

(2)

使得更為獨特且適應(yīng)度優(yōu)秀的個體在下一代的選擇中占據(jù)優(yōu)勢，從而避免遺漏某些與其它個體都不相似的局部最優(yōu)解。

2.3 基于語義聚類的遺傳規(guī)劃算法

在GSGP與SCS選擇算子的基礎(chǔ)上，本文提出了一種基于語義聚類的遺傳規(guī)劃算法(genetic programming algorithm based on semantic clustering，SCGP)。SCGP通過歐式距離計算個體間的語義距離，以語義距離測度語義相似度，并通過聚類將種群劃分為多個不同的子種群。在子種群內(nèi)部進行錦標賽選擇、交叉、變異，既可以使語義相似的父代個體進行交叉，使子代個體有更可能滿足GSGP對語義的要求，實現(xiàn)全局搜索能力的提升；同時也可以避免屬于不相似的個體進行交叉，避免破壞現(xiàn)有的優(yōu)良結(jié)構(gòu)。

SCGP的流程如圖1所示。

圖1 基于語義聚類的遺傳規(guī)劃算法流程

3 實驗與結(jié)果分析

3.1 實驗設(shè)置

在不同的任務(wù)中，為了獲得較好的效果，需要為SCGP選擇不同的聚類算法。聚類算法按照原理不同可分為：劃分聚類、密度聚類、層次聚類與其它。本文從4類中分別選擇一個：K-means聚類、DBSCAN、Agglomerative Cluster、譜聚類，測試其在SCGP中的效果。實驗在10個基準問題上開展，F(xiàn)1-F6為符號回歸問題，F(xiàn)8為數(shù)值回歸問題，其余為二分類問題，問題細節(jié)見表1。回歸問題的原始適應(yīng)度函數(shù)為平均絕對誤差(MAE)，二分類問題的原始適應(yīng)度函數(shù)為二分類交叉熵

表1 基準問題的詳細信息

(3)

實驗的參數(shù)設(shè)置見表2，為了使初始種群更有可能覆蓋到全局最優(yōu)解，實驗采用“Ramped half and half”方式初始化種群。此外，為了保留每代演化出的優(yōu)秀個體，實驗添加了精英保留的操作。

表2 SCGP的參數(shù)設(shè)置

在下文表格中，如果一種方法的結(jié)果優(yōu)于標準錦標賽選擇的GP(以下簡稱為GP)，則在末尾標記“+”；如果它與GP相比更差，則此結(jié)果標記為“-”。每個實驗均使用相同的計算平臺(操作系統(tǒng)：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種聚類方法，比較其在擬合、泛化和運行時間方面的表現(xiàn)。實驗中每種算法均采用相同的隨機初始種群，以避免由不同初始種群所引起的結(jié)果差異。本文將在每一個問題上測試分別基于上文提到的4種聚類方法的SCGP并將其與GSGP和SCS-GP進行對比。

3.2 擬合表現(xiàn)分析

通過訓(xùn)練誤差來分析各個算法的擬合能力，各個算法訓(xùn)練100次時的誤差中位數(shù)見表3。回歸問題用MAE、分類問題用F1-score測度誤差。

表3 不同算法在訓(xùn)練集上的實驗結(jié)果

在大多數(shù)任務(wù)中SCGP優(yōu)于標準GP，這說明通過聚類生成子種群并在子種群內(nèi)部進行遺傳操作的可以提高GP的性能。在6個符號回歸問題中，除F6外，其余問題中的SCGP都顯著優(yōu)于標準GP；SCGP在F6問題中表現(xiàn)不佳，可能是因為問題特征數(shù)較多且訓(xùn)練樣本量較少，聚類效果不佳，未能準確的劃分子種群。SCGP雖然利用個體語義進行了聚類，但是忽略了個體結(jié)構(gòu)蘊含的信息，無法較好識別語義差異較小但位于不同局部最優(yōu)解附近的個體，這在一定程度上影響了算法的性能。與GSGP和SCS-GP相比，層次聚類嵌入的SCGP在符號回歸任務(wù)中的表現(xiàn)都優(yōu)于或等同于兩個現(xiàn)有算法；譜聚類嵌入的SCGP在達到收斂的所有的分類任務(wù)中，優(yōu)于兩個現(xiàn)有的算法。這說明通過選擇適當(dāng)?shù)木垲惙椒ǎ梢杂行Й@得相比現(xiàn)有語義GP更優(yōu)的擬合能力。

由圖2可知，除DBSCAN-SCGP外，所有算法都達到了收斂。在F1、F7、F10中，標準GP收斂速度最快，但是各個SCGP的收斂適應(yīng)度值都達到了相較于標準GP、SCS-GP、GSGP相當(dāng)或者更優(yōu)秀的值。這是由于語義聚類分散了初期的個體適應(yīng)度。并且較之標準GP和GSGP，SCGP明顯波動幅度更大，說明SCGP是受過擬合影響較小的技術(shù)。

圖2 各個算法在不同問題上的收斂曲線

3.3 泛化表現(xiàn)分析

實驗采用在測試集上的誤差來測度其泛化性能。表4給出了不同實驗在測試集上的最佳適應(yīng)值的中位數(shù)。由表4可知，SCGP在大部分問題測試集上的泛化精度表現(xiàn)都由于標準GP。除F6外，SCGP的泛化能力都等同或者優(yōu)于標準GP。

表4 不同算法在測試集上的實驗結(jié)果

Agglomerative Cluster-SCGP與譜聚類-SCGP在不同問題上的表現(xiàn)均較好。在3個符號回歸任務(wù)中，SCGP的泛化能力不如GSGP，只在一個符號回歸問題中SCGP優(yōu)于GSGP。但是在分類任務(wù)中，SCGP的泛化能力顯著優(yōu)于GSGP與SCS-GP。說明由于符號回歸任務(wù)的復(fù)雜度較低，SCGP出現(xiàn)了過擬合；在樣本數(shù)較多的分類問題中，相較于SCGP與SCS-GP，SCGP能夠更好利用數(shù)據(jù)的特征，在測試集中能取得更優(yōu)秀的精度。這說明只要選擇到合適的聚類方法，語義聚類劃分子種群的思想有助于提升算法的泛化表現(xiàn)。同時，由于許多聚類算法不能做到根據(jù)不同的種群自適應(yīng)的選擇子種群的數(shù)目，因此K均值聚類與密度聚類嵌入的SCGP在實驗中的泛化表現(xiàn)處于劣勢。而不需要提前指定子種群數(shù)目的層次聚類與譜聚類嵌入的SCGP的泛化能力較優(yōu)。

3.4 運行速度分析

在運行速度方面，本文實驗采用10次運行的平均運行時間來測度運行速度的快慢。可以預(yù)見的是，由于需要進行計算子種群分類，SCGP的運行速度必然比標準GP慢。每個算法的平均運行時間見表5，因為DBSCAN算法并未收斂，因此不具參與討論。除問題F3外，SCGP的運行時間長于標準GP，其中K均值與層次聚類嵌入的SCGP由于其聚類算法的復(fù)雜度低，運行時間雖然高于標準GP但是仍在可接受的范圍內(nèi)。相比之下，譜聚類算法的時間復(fù)雜度過高，因此運行時間極長。與GSGP相比，由于基于聚類的算法不需要對每個可能的交叉組合進行遍歷試錯，因此其運行時間顯著低于GSGP。在問題F3中，SCGP的運行時間顯著低于標準GP，可能是由于通過劃分語義子種群，降低了個體深度的膨脹，從而降低了計算成本。

表5 不同算法解決問題時的運行時間比較/s

3.5 實驗總體結(jié)果分析

本文通過在符號回歸、真實數(shù)據(jù)集回歸、分類等基準問題上分別運行標準GP、GSGP、SCS-GP、KMeans-SCGP、DBSCAN-SCGP、AgglomerativeCluster-SCG、SpectralCluster-SCGP，并對SCGP的性能進行了分析。并且分別從擬合表現(xiàn)、泛化表現(xiàn)、運行速度3個角度，對不同聚類算法嵌入的SCGP、標準GP、GSGP、SCS-GP進行了對比分析。

廣泛的實驗結(jié)果表明，SCGP在分類問題中具備優(yōu)于標準GP、GSGP與SCS-GP的擬合與泛化能力；在回歸問題中略差于GSGP，但優(yōu)于GP與SCS-GP。并且SCGP在運行速度上優(yōu)于GSGP和SCGP，但差于標準GP。從實驗結(jié)果來看，這些增長的計算量有助于提高擬合與泛化能力。在不同聚類算法嵌入的對比方面，層次聚類嵌入的SCGP在多數(shù)問題中優(yōu)于其它SCGP與標準GP。這表明通過語義劃分子種群有助于算法的改進。

4 結(jié)束語

本文提出的基于語義聚類的遺傳規(guī)劃算法(GSGP)，在標準GP的基礎(chǔ)上，添加了基于語義聚類的錦標賽選擇算子、自適應(yīng)的適應(yīng)度函數(shù)。

該選擇算子，利用個體語義信息劃分子種群，使得個體向幾個不同的局部最優(yōu)聚集，保證了種群的多樣性。同時，利用子種群規(guī)模構(gòu)造自適應(yīng)的適應(yīng)度函數(shù)，提高優(yōu)秀個體被選擇的概率，提高了搜索能力。實驗結(jié)果表明，相較于標準GP、SCS-GP，本文算法的擬合和泛化能力均得到了提高；在多數(shù)基準問題中，層次聚類嵌入的SCGP算法顯著優(yōu)于其它的聚類嵌入。