基于聚類錦標(biāo)賽與父代匹配的遺傳規(guī)劃算法

方 偉, 梁靜雯, 陸恒楊

(江南大學(xué)人工智能與計算機(jī)學(xué)院, 江蘇 無錫 214122)

0 引 言

遺傳規(guī)劃(genetic programming,GP)算法是典型的群體智能進(jìn)化算法之一[1-2],具有非線性、動態(tài)可變性等特點[3]。GP算法已在多個領(lǐng)域取得了較好的應(yīng)用效果,如分類預(yù)測[4-5]、圖像處理[6]、運籌學(xué)[7-9]等,但仍存在著許多不可忽視的缺陷,如易出現(xiàn)早熟收斂而影響其優(yōu)化性能,種群多樣性不能得到很好的控制在一定程度上造成了這種現(xiàn)象[10-11]。為此,研究人員從多樣性角度對GP算法開展了大量的研究。

根據(jù)達(dá)爾文的發(fā)散理論[12],有研究人員嘗試通過限制個體之間的競爭,劃分不同的環(huán)境以增加種群多樣性[13-16]。該方法主要分為分享策略和擁擠策略。分享策略通過避免整體趨同,允許小生境趨同維持種群多樣性。Ekárt等[14]將適應(yīng)值作為共享資源維持了種群多樣性。實驗結(jié)果表明這種算法雖然在不提高性能的情況下有助于控制程序規(guī)模,但由于需要計算樹間距離,算法需要較高的計算資源。擁擠策略通過替換相似個體, 提高成對父代的多樣性。Bartoli等[16]基于擁擠策略提出了利用語法引導(dǎo)保持多樣性的新方法,實驗結(jié)果表明在大多數(shù)情況下,促進(jìn)表型多樣性會產(chǎn)生更好的結(jié)果。

選擇壓力是影響算法多樣性的一個重要因素,高相似個體之間進(jìn)行遺傳操作有助于保留個體的優(yōu)良性狀, 加快算法的收斂速度;低相似個體間的遺傳操作可以引入多樣性,減少無效交叉。楊新武等[17]通過最小生成樹聚類選擇父代進(jìn)行交叉,通過選擇不同聚類中的父代保持種群多樣性。Helmuthet等[18]研究了選擇方法與種群多樣性之間的關(guān)系。通過比較不同選擇算子在保持兩種種群多樣性方面的表現(xiàn),論文指出錯誤多樣性是一個更好的適應(yīng)度指標(biāo),但并未指明如何利用這一發(fā)現(xiàn)來幫助GP算法進(jìn)行搜索。Chu等[19]將錦標(biāo)賽選擇與Wilcoxon Signed Rank檢測相結(jié)合,提出不同的選擇方法,這些方法通過避免統(tǒng)計學(xué)意義上相似個體的交叉保持了種群的多樣性。

最近,有學(xué)者嘗試?yán)枚嗄繕?biāo)方法維持種群多樣性。Burlacu等[20]通過引入基于哈希的樹距離度與非支配排序遺傳(non-dominated sorting genetic algorithm-II,NSGA-II)算法相結(jié)合,將搜索引向更高水平的多樣性。其中,最大化相關(guān)系數(shù)R2是算法的主要目標(biāo),最大化種群多樣性是算法的次要目標(biāo)。該算法利用樹散列將樹個體轉(zhuǎn)換為散列值序列,特別適合成對樹距離的大規(guī)模計算。

近幾年,不斷有學(xué)者嘗試從語義角度利用多樣性提高算法的優(yōu)化能力[21-23]。Day等[21]和Aslam等[22]利用個體的二進(jìn)制字符串適應(yīng)值特征(binary string fitness characterization, BSFC)分別提出了比較伙伴選擇(comparative partner selection, CPS)和多樣伙伴選擇(diverse partner selection, DPS)。CPS算法和DPS算法通過成對父代提高了種群多樣性。Chen等[23]基于語義提出了一種新的多樣性保持框架,該框架利用主成分分析(principle component analysis,PCA)對語義進(jìn)行降維,通過選擇角度與距離均屬不同種類的個體進(jìn)行交叉,有效降低了算法過擬合的趨勢,該多樣性保持方法更適合于從只有少量實例的高維數(shù)據(jù)中進(jìn)行學(xué)習(xí)。

為了進(jìn)一步提升GP算法的求解效果,有效控制種群多樣性,使算法的全局搜索能力和局部搜索能力達(dá)到更好的平衡,本文提出一種基于聚類匹配選擇的GP算法(GP algorithm based on cluster tournament selection and parent matching, CMGP)。CMGP算法利用聚類錦標(biāo)賽選擇(cluster tournament selection,CTS)和局部匹配提高算法的搜索能力。CTS可通過調(diào)整算法的選擇壓力維持種群多樣性,從而提升算法的全局搜索能力。此外,CMGP提取了個體的二進(jìn)制特征,基于二進(jìn)制特征的局部匹配幫助探索最優(yōu)解臨近區(qū)域,從而提升算法的局部搜索能力。

1 GP算法

1.1 算法簡介

GP繼承了進(jìn)化算法“優(yōu)勝劣汰”的基本思想,以適應(yīng)值為導(dǎo)向進(jìn)行自適應(yīng)搜索。然而,不同于傳統(tǒng)的編碼模式(固定長度基因),GP的個體是一個計算機(jī)程序,它通過一系列可行的函數(shù)對個體進(jìn)行表述,其結(jié)構(gòu)主要為樹型結(jié)構(gòu)。GP常用函數(shù)集和終止集描述個體。其中,函數(shù)集中主要包含一些函數(shù)符號,如+、-、*、/、sin、cos等,而終止集可視為特定問題的輸入,主要由一些實數(shù)和變量組成。算法最終演化得到的程序類似一個符號表達(dá)式,如y=f(x0,x1,x2,…,xn)。

GP算法的主要流程如下。

步驟 1利用函數(shù)集和終止集確定個體的表達(dá)方式;

步驟 2隨機(jī)產(chǎn)生初始種群;

步驟 3計算種群中個體的適應(yīng)值;

步驟 4以適應(yīng)值為導(dǎo)向進(jìn)行遺傳操作,如交叉、變異、選擇等;

步驟 5循環(huán)執(zhí)行步驟3和步驟4,直至算法滿足終止條件。

1.2 GP中的多樣性

在GP算法中,多樣性常用于描述種群結(jié)構(gòu)或行為的變化。其中,最簡單的衡量種群多樣性的方式為“基因唯一性”和“表型唯一性”,兩者分別計算“唯一結(jié)構(gòu)”和“唯一適應(yīng)值”在整個種群中的數(shù)量。近年來, 不斷有學(xué)者從基因型和表現(xiàn)型兩方面衡量種群的多樣性。Rosca[24]引入統(tǒng)計學(xué)中“熵”的理念, 利用適應(yīng)值衡量種群的多樣性。O’Reilly[25]通過引入字符串匹配的相關(guān)知識, 使用編輯距離衡量兩個個體結(jié)構(gòu)之間的多樣性。Ekárt等[14]針對編輯距離存在的不足, 引入權(quán)重對其進(jìn)行了改進(jìn)。

總體而言,在不同的多樣性評價方式中,多樣性評價結(jié)果中包含的信息越豐富,其所需的代價可能就越高。此外, 僅考慮基因型的衡量方式忽略了個體整體表現(xiàn)間的差異;僅考慮表現(xiàn)型的衡量方式則忽略了個體自身的進(jìn)化過程。BSFC通過二進(jìn)制邏輯運算, 利用個體的內(nèi)部信息拓展了表現(xiàn)型的概念。該評價方式計算簡單且信息豐富, 因此本文所提算法通過BSFC匹配個體,使得算法達(dá)到了更好的效果。

1.3 BSFC

BSFC提取個體內(nèi)部信息,并以二進(jìn)制字符串的形式表達(dá)個體特征。BSFC將個體表現(xiàn)優(yōu)秀的部分看作是該個體的“優(yōu)勢”, 而將表現(xiàn)不佳的部分看作是該個體的“劣勢”, 并分別以“1”、“0”表示。當(dāng)具有不同二進(jìn)制字符串的個體進(jìn)行交叉時, 這些“優(yōu)勢”和“劣勢”代表了個體對子代的改進(jìn)能力, 從而分別代表著好的多樣性和壞的多樣性。

對于二進(jìn)制問題, 個體的優(yōu)勢和劣勢可通過個體在訓(xùn)練案例上的正確與否進(jìn)行定義。若個體在某些訓(xùn)練案例上是正確的, 則可將這些訓(xùn)練案例看作是該個體的優(yōu)勢,否則可視為劣勢。對于其他領(lǐng)域(非二進(jìn)制)的問題,BSFC將采取另一種方式定義個體的優(yōu)劣。若一個個體的某個輸出與目標(biāo)輸出的誤差小于總體誤差的平均值, 則將該輸出定義為個體的優(yōu)勢,否則定義為劣勢。

圖1以符號回歸問題演示了一個示例。圖中變量x1、x2和x3分別代表著不同個體按給定輸入(訓(xùn)練案例)的輸出值。圖1右圖的二叉樹展示了目標(biāo)輸出個體的內(nèi)部結(jié)構(gòu),其代表符號表達(dá)式為“(x(x+1))+cosx”。通過計算個體輸出和目標(biāo)輸出的誤差平均值可得出在此情況下不同個體對應(yīng)的二進(jìn)制字符串, 即個體的BSFC。

圖1 符號回歸問題的BSFC計算示例Fig.1 BSFC computation example of a symbolic regression problem

2 CMGP算法

2.1 CTS

聚類作為一種無監(jiān)督的機(jī)器學(xué)習(xí)方法,是從數(shù)據(jù)中理解和學(xué)習(xí)結(jié)構(gòu)信息的重要方法,有研究人員[26-28]利用聚類合并種群中相似的個體。通過聚類后的種群,研究人員能更好地把握種群的整體情況從而提升算法的優(yōu)化能力?；谠撍枷?本文提出了基于聚類的CTS算法。該算法將符合標(biāo)準(zhǔn)的個體分為一類,若類中個體表現(xiàn)較優(yōu),那么種群可能處于收斂階段;若類中個體表現(xiàn)較差,那么種群可能處于探索階段。

CTS算法將種群中具有相似表現(xiàn)的個體劃分為一類, 即將適應(yīng)值差值保持在一定閾值范圍內(nèi)的個體劃分為一類。在演化過程中, 當(dāng)種群產(chǎn)生優(yōu)秀但少量的個體時, 算法將這類個體選擇出來,通過對優(yōu)秀個體進(jìn)行遺傳操作,保留優(yōu)良性狀,從而促進(jìn)種群整體朝最優(yōu)方向發(fā)展。當(dāng)種群中產(chǎn)生具有相似表現(xiàn)且數(shù)量較多的個體時,算法將減少這類個體被選擇的概率, 以免陷入局部最優(yōu)。此外, 在選擇的過程中, 算法提高了當(dāng)前表現(xiàn)較差但具有潛力的個體被選擇的可能。

圖2展示了CTS算法的示例。假定種群規(guī)模為10,每個個體的適應(yīng)值如圖2所示,其中適應(yīng)值越小,代表個體表現(xiàn)越好。在根據(jù)適應(yīng)值進(jìn)行聚類后, 比較對原種群進(jìn)行隨機(jī)選擇和聚類后對種群進(jìn)行隨機(jī)選擇的結(jié)果, 從中可以看出, 適應(yīng)值為1的個體被選擇的概率由1/10上升為1/6,增加了最優(yōu)個體被選擇的概率,而適應(yīng)值為2的個體被選擇的概率由4/10減小到了1/6,減少了可能陷入局部最優(yōu)個體被選擇的概率。此外,適應(yīng)值為4、7、10的個體被選擇的概率由1/10上升為1/6,這些個體當(dāng)前表現(xiàn)較差,可能是受個體結(jié)構(gòu)中個別節(jié)點的影響。通過少量的交叉變異操作,這類個體可能獲得更好的性狀。比較算法前后不同個體被選擇的概率,可發(fā)現(xiàn)算法調(diào)整了不同種類個體被選擇的概率,從而提升了種群的多樣性水平。

圖2 種群聚類Fig.2 Population clustering

CTS算法中個體自下而上從底層根據(jù)閾值向上合并,直至種群中全部個體完成聚類。CTS算法用Si表示不同的類別,Ns表示種群聚類后的類別數(shù)量,S*表示參加CTS并表現(xiàn)最優(yōu)的類。S*中節(jié)點數(shù)最少的個體即為聚類錦標(biāo)賽所選擇的個體indkeep。由于Ns的值是根據(jù)每代種群中的情況自動調(diào)整的, 因此在大部分情況下, CTS算法能判斷出種群內(nèi)部不同的情況, 從而動態(tài)地調(diào)整選擇壓力, 選出更合適的個體。

在迭代過程中,種群中常出現(xiàn)一些適應(yīng)值異常的個體, 這些個體往往會被單獨分為一類,這導(dǎo)致Ns不斷增加, 并使 CTS算法性能受到影響。為了避免該問題,CTS引入了截斷操作,去除這些表現(xiàn)異常的個體。此外,同一個類中個體的適應(yīng)值表現(xiàn)相似,因此在從S*中選擇個體的過程中,若按照適應(yīng)值選取個體,對精度的提升存在一定的局限。然而,考慮到GP固有的“膨脹”問題[29],為了限制冗余節(jié)點的不斷增長,CTS算法在S*中選擇個體時通過比較個體節(jié)點個數(shù),在一定程度上避免了該問題。以下是CTS算法的詳細(xì)描述。

步驟 1初始化種群,計算個體適應(yīng)值;

步驟 2對種群進(jìn)行截斷操作,去除異常個體;

步驟 3將每個個體作為一個類,根據(jù)閾值不斷動態(tài)合并個體形成新的聚類,直至種群整體完成聚類操作,聚類完成后種群中每個類別記為Si;

步驟 4隨機(jī)選取不同聚類中的個體作為對應(yīng)聚類的評分,記為Sscore;

步驟 5隨機(jī)選取k個聚類,根據(jù)Sscore選出優(yōu)勝類S*;

步驟 6進(jìn)入S*中,選擇其中節(jié)點數(shù)最少的個體,將該個體記為indkeep。

2.2 基于BSFC的父代匹配選擇

2.2.1 多樣伙伴選擇

DPS算法[22]利用BSFC選擇成對父代進(jìn)行交叉操作以提高父代的成對多樣性,進(jìn)而提高算法的性能。

DPS算法在執(zhí)行交叉操作前,會隨機(jī)選擇兩個個體,根據(jù)BSFC將這兩個個體分別定義為“捐贈者”和“受贈者”。DPS算法在固定類別為“受贈者”的個體后,若“捐贈者”個體不滿足與“受贈者”個體的交叉條件,那么算法會在種群范圍內(nèi)重新挑選個體,直至被挑選的個體滿足交叉條件。若在全局內(nèi)未找到合適的“捐贈者”個體,那么算法會隨機(jī)選擇個體作為“捐贈者”,并調(diào)整當(dāng)前迭代過程中的交叉概率和變異概率。

(1)

(2)

DPS算法根據(jù)式(1)和式(2)判斷個體是否進(jìn)行交叉操作。其中,式(1)用于計算“捐贈者”個體對“受贈者”個體的改進(jìn)空間,b1為“受贈者”個體的二進(jìn)制字符串,b2為“捐贈者”個體的二進(jìn)制字符串。式(2)用于計算“受贈者”個體的改進(jìn)空間。若α>β,則DPS算法執(zhí)行交叉操作,否則不執(zhí)行交叉操作。

2.2.2 改進(jìn)的二進(jìn)制字符串適應(yīng)值特征

在文獻(xiàn)[21-22]中,針對非二進(jìn)制問題,如符號回歸問題,BSFC利用總體誤差的平均值定義個體的優(yōu)勢、劣勢。然而,在種群的迭代過程中,常出現(xiàn)適應(yīng)值偏離種群整體水平的極端個體。這些極端個體往往會影響其他個體“1”“0”的定義。因此,本文提出用誤差中位數(shù)定義個體的BSFC。

圖3展示了以誤差平均值定義個體BSFC和以誤差中位數(shù)定義個體BSFC的不同情況。從圖3可以看出,對于個體3的 BSFC的定義受到了個體4的極大影響。由于個體4的適應(yīng)值誤差過大,導(dǎo)致誤差平均值整體偏大,處于中間水平個體的BSFC定義因此受到影響。本文將誤差平均值換為誤差中位數(shù),從而解決了該問題?？傮w而言,誤差中位數(shù)可以更好地定義處于中間水平的個體,在一定程度上避免其受到極端值的影響,使得算法對于BSFC的定義更加準(zhǔn)確,以便進(jìn)一步優(yōu)化算法。

圖3 BSFC不同計算方式的對比舉例Fig.3 Comparison examples of different calculation methods of BSFC

2.2.3 匹配伙伴選擇

在算法初期,DPS算法很難找到兩個符合交叉條件的個體,因此算法的交叉變異概率會不斷發(fā)生變化。在GP算法中,不斷改變的交叉概率會影響部分個體的演化,而不斷增長的變異概率雖然能讓算法在更大的范圍內(nèi)進(jìn)行搜索,但會破壞已具有較好表現(xiàn)的個體。變異概率不斷變化的算法產(chǎn)生同等或更優(yōu)適應(yīng)值后代的可能性遠(yuǎn)低于固定變異概率產(chǎn)生相同適應(yīng)值后代的可能性[30]。此外,DPS算法雖然關(guān)注到了優(yōu)秀個體對于種群整體的重要作用,然而算法對于被改進(jìn)個體的選擇不夠明確。因此,本文在通過CTS算法選擇具有較高多樣性的優(yōu)秀個體后,對其進(jìn)行了針對性改進(jìn)。

受DPS算法啟發(fā),針對交叉操作,本文提出了新的基于BSFC的父代匹配選擇(match parent selection, MPS)算法。MPS算法首先隨機(jī)選擇部分個體,接著根據(jù)種群整體水平動態(tài)地篩選部分節(jié)點較小的個體,最后通過BSFC觀察個體的內(nèi)部情況,尋找一個與通過CTS挑選出的個體indkeep最匹配的個體indfit并與之進(jìn)行交叉。由于引入了BSFC,每個個體不僅可以適應(yīng)值描述個體的整體表現(xiàn),還可以以二進(jìn)制字符串描述個體的內(nèi)部情況。MPS算法將兩者進(jìn)行了聯(lián)系,提高了父代的成對多樣性。

MPS算法并不要求兩個個體的整體表現(xiàn)都十分優(yōu)秀,而是希望用一個個體去改進(jìn)另一個個體,通過改進(jìn)優(yōu)秀個體表現(xiàn)較差的部分促進(jìn)種群整體的優(yōu)化。也就是說,個體indfit的整體表現(xiàn)不必十分優(yōu)秀,但其二進(jìn)制特征需要對indkeep表現(xiàn)較差的部分具有改進(jìn)能力。MPS算法將挑選出與indkeep匹配的父代,充分發(fā)揮較好多樣性父代的優(yōu)勢, 通過較高且穩(wěn)定的交叉概率,不斷產(chǎn)生新的子代。

(3)

根據(jù)式(3),算法可計算出一個個體對于另一個個體的改進(jìn)值。其中,bkeep、bfit分別代表著個體indkeep和個體indfit的二進(jìn)制字符串。

圖4展示了符號回歸問題中根據(jù)二進(jìn)制字符串選擇個體的示例,其中每個個體“1”的個數(shù)越多,代表該個體的內(nèi)部表現(xiàn)越好。算法需要從b2和b3中選出一個個體與b1進(jìn)行交叉。根據(jù)式(3),b2對b1的改進(jìn)值為0,而b3對b1的改進(jìn)值為2,算法更可能選擇讓b3與b1進(jìn)行交叉。雖然b2和b3的整體表現(xiàn)相近,但是算法可以根據(jù)公式快速選出有針對性的個體并將其與較優(yōu)個體進(jìn)行交叉。

圖4 MPS示意圖Fig.4 MPS skematic diagram

以下給出了MPS方法的詳細(xì)描述。

步驟 1隨機(jī)挑選部分個體直至個體數(shù)達(dá)到聚類錦標(biāo)賽規(guī)模k, 這部分個體記為個體池inds。

此時,個體池inds中個體數(shù)目與聚類錦標(biāo)賽規(guī)模相同,均為規(guī)模k;

步驟 2根據(jù)平均節(jié)點數(shù),保留inds中節(jié)點數(shù)較小的個體,去除節(jié)點數(shù)較大的個體。經(jīng)過該操作,inds中的個體數(shù)小于等于規(guī)模k。若inds中的個數(shù)小于k,則執(zhí)行步驟3;

步驟 3從種群中隨機(jī)選擇個體加入inds直至inds中個體值達(dá)到規(guī)模k。新加入的個體無需經(jīng)過節(jié)點篩選。此時個體池記為indnew;

步驟 4利用式(3)計算indnew中每個個體對個體indkeep的改進(jìn)值;

步驟 5選擇indnew中改進(jìn)值最大的個體成為indfit;

步驟 6個體indfit和個體indkeep進(jìn)行交叉操作。

2.3 基于父代聚類匹配的GP算法

基于第2.1節(jié)和第2.2節(jié)的分析,本文提出了CMGP算法。該算法從選擇壓力和成對多樣性兩個角度保持種群多樣性,以提升算法的尋優(yōu)能力。通過動態(tài)調(diào)整選擇壓力和基于BSFC的局部匹配,CMGP挑選具有較高多樣性的優(yōu)秀個體和對其有改進(jìn)能力的個體,并進(jìn)行交叉操作,通過改善優(yōu)秀個體引導(dǎo)算法優(yōu)化。此外,通過對個體節(jié)點的控制,算法在一定程度上緩解了GP算法的膨脹問題。圖5給出了CMGP算法的流程圖。

圖5 CMGP算法流程圖Fig.5 CMGP algorithm flowchart

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

本文采用了兩個不同領(lǐng)域的問題來分析算法的性能,包括符號回歸問題和分類問題。其中,符號回歸實驗(symbolic regression, SR)采用文獻(xiàn)[31]所給出的不同基準(zhǔn)問題,分類實驗采用來自加州大學(xué)歐文分校(University of California Irvine,UCI)機(jī)器學(xué)習(xí)庫的不同數(shù)據(jù)集[32]。符號回歸實驗和分類實驗的終止條件為達(dá)到預(yù)定的迭代次數(shù)。用于符號回歸問題的適應(yīng)值函數(shù)是預(yù)測值和訓(xùn)練值的絕對差值之和,分類問題的適應(yīng)值函數(shù)如下所示:

(4)

式中:EA代表個體被錯誤分類為Class A的數(shù)量;TA代表個體應(yīng)被正確分類為Class A的數(shù)量;EB代表個體被錯誤分類為class B的數(shù)量;TB代表個體應(yīng)被正確分類為Class B的數(shù)量。分類實驗將數(shù)據(jù)集的兩個類別分別稱為Class A和Class B。理想情況下, 所有個體都被正確分類,那么Error的值為0。

表1給出了不同問題中的算法參數(shù)。其中,為避免節(jié)點無限制的增加,實驗設(shè)定了個體的最大深度。為了使種群更多樣化,實驗采用了“ramped half and half”[1]的方式初始化種群。此外,為了保留每代演化出的優(yōu)秀個體,實驗添加了精英選擇的操作,被選出的“精英”個體無需進(jìn)行交叉變異操作,直接進(jìn)入下一代種群。符號回歸問題和分類問題的縮寫、名稱、特征數(shù)量、訓(xùn)練樣本和測試樣本數(shù)量如表2所示。表3給出了符號回歸問題和分類問題的函數(shù)集。

表1 算法參數(shù)設(shè)置

表2 不同實驗的具體描述

表3 SR和分類問題的函數(shù)集

為更全面地分析比較CMGP算法的性能,實驗采用了5種不同的GP算法作為對比算法,包括標(biāo)準(zhǔn)GP(standard GP, SGP)算法、基于適應(yīng)度的群體聚類的錦標(biāo)賽選擇(clustering tournament selection with the fitness-based population clustering, FCGP)算法[28]、DPS算法[22]、具有規(guī)模的統(tǒng)計錦標(biāo)賽選擇(statistics tournament selection with size, TS-S)算法[19]、基于交叉模型的改進(jìn)遺傳GP (improved GP based on crossover model, GACM)算法[17]。文獻(xiàn)[17]和文獻(xiàn)[28]是利用聚類選擇個體的算法,文獻(xiàn)[22]提出了基本的MPS操作,文獻(xiàn)[19]為最新的GP改進(jìn)算法,提出了控制膨脹的新算法。實驗中,每種算法均采用相同的隨機(jī)初始種群,以避免不同初始種群引起結(jié)果差異。其中,文獻(xiàn)[22]中添加了重組操作(brood rombination, BR)[33]。BR操作即選定兩個父代進(jìn)行5次交叉,父代共產(chǎn)生10個后代,選擇后代中的兩個最優(yōu)適應(yīng)值子代進(jìn)入下一代種群。

3.1 訓(xùn)練誤差分析

訓(xùn)練誤差有助于分析GP算法的學(xué)習(xí)過程。本文提出的CMGP算法以及對比算法在不同測試函數(shù)上的實驗結(jié)果如表4所示。表4中的值由平均最優(yōu)適應(yīng)值組成(F5的適應(yīng)值取‰,F6、F7、F8的適應(yīng)值取%)。

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

在不同的問題中,FCGP算法和DPS+BR算法的表現(xiàn)各有優(yōu)劣,但總體均優(yōu)于標(biāo)準(zhǔn)GP算法,這說明通過聚類選擇個體和利用BSFC進(jìn)行交叉均可提升算法的性能。TS-S算法在SR問題(F1、F2、F3、F4)上表現(xiàn)不佳,這是因為問題特征數(shù)和樣本數(shù)較少,算法未能充分發(fā)揮統(tǒng)計檢測的良好性能,導(dǎo)致算法不斷篩選節(jié)點,無法根據(jù)個體適應(yīng)值進(jìn)行有效選擇。GACM算法雖然利用最小生成樹進(jìn)行了聚類,但其在拆分最小生成樹生成聚類時,無法較好地識別差異較小的個體,這在一定程度上影響了算法的性能(F1、F2、F5)。

從表4可以看出,CMGP算法在基準(zhǔn)測試函數(shù)上的優(yōu)化性能總體上優(yōu)于其他算法。DPS+BR算法雖然使得個體的適應(yīng)值有所提升,但可以預(yù)見,隨著問題特征數(shù)的增加,BR操作將會花費較多的精力在個體適應(yīng)值計算上。此外,在F1, F4實驗中,相對于其他算法,DPS算法表現(xiàn)較差,這是因為在SR這類連續(xù)實值問題上,對于個體BSFC的劃分不夠準(zhǔn)確,導(dǎo)致交叉不夠具有針對性。相對而言,在SR實驗中,CMGP算法重新定義了處于中間部分個體的BSFC,這使得算法在選擇個體進(jìn)行交叉時更具針對性,因而表現(xiàn)優(yōu)于DPS+BR算法。在分類實驗部分(F5、F6、F7、F8),CMGP算法的表現(xiàn)較優(yōu),在F5這個實驗上,其訓(xùn)練適應(yīng)值已達(dá)到了較高的水平。雖然在部分實驗中,CMGP算法未能取得最佳適應(yīng)值,但其結(jié)果與最佳適應(yīng)值相近。CMGP算法利用CTS算法動態(tài)調(diào)整選擇壓力,交叉的父代因此具有較高的多樣性水平, 通過在全局范圍內(nèi)進(jìn)行有針對性的交叉,算法能較好地提升種群的整體水平,引領(lǐng)算法朝更優(yōu)秀的方向演化。

3.2 種群多樣性分析

CMGP算法希望在提高種群多樣性的同時,利用針對性交叉提高算法性能,為進(jìn)一步觀察不同算法的優(yōu)化性能,圖6給出了各種算法在優(yōu)化不同測試函數(shù)時的收斂曲線圖, 圖7給出了部分多樣性曲線。實驗采用表現(xiàn)型多樣性衡量種群多樣性水平。

圖6 各算法在不同問題上的收斂曲線Fig.6 Convergence curves of each algorithm on different problems

圖7 各算法在不同問題上的多樣性表現(xiàn)Fig.7 Diversity performance of each algorithm on different problems

從圖6可看出大部分算法在面對不同問題時,都進(jìn)行了較好的收斂,CMGP算法一直保持著較快的收斂速度。TS-S算法在特征數(shù)較多的分類實驗中表現(xiàn)較優(yōu)。GACM算法在個體差異較為明顯時,可以進(jìn)行較好的收斂,而在算法后期收斂速度有所下降。在F1、F3的SR問題上,CMGP算法保持著較快的收斂速度,并不斷朝最優(yōu)解優(yōu)化,這說明了CMGP算法針對較優(yōu)個體的匹配交叉能夠引領(lǐng)種群有效地搜索最優(yōu)解。

圖7給出了SGP算法和CMGP算法的多樣性情況,其中陰影部分代表著方差浮動的范圍。從圖7可以看出,相對于SGP算法,CMGP算法較好地維持了種群的多樣性。根據(jù)圖7,在大約10代前的種群迭代初期,種群大都經(jīng)歷過快速喪失多樣性的過程。然而,雖然CMGP算法在該過程中多樣性水平有所降低,但其通過CTS算法又重新獲得了多樣性,將種群多樣性維持在了一個較高的水平,促使算法不斷探索更多更有效的區(qū)域,為算法提供了更多的可能性。

3.3 泛化能力分析

泛化能力對于算法而言至關(guān)重要,可以評價算法是否學(xué)習(xí)到了隱含在數(shù)據(jù)背后的聯(lián)系。在此部分,實驗采用測試誤差來觀察算法的泛化性能。表5給出了不同實驗在測試集上的最佳平均適應(yīng)值。

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

根據(jù)表5,FCGP算法、GACM算法、DPS+BR算法和CMGP算法在測試集上的精度總體都優(yōu)于SGP算法, 而CMGP算法在大部分測試集上表現(xiàn)最優(yōu)。FCGP算法、GACM算法和DPS+BR算法在不同實驗中的表現(xiàn)各有優(yōu)劣,這說明聚類選擇的思想和BSFC匹配交叉的思想有助于提升算法的泛化能力。觀察TS-S算法,其在面對更多問題特征數(shù)的情況下表現(xiàn)較優(yōu),這代表著統(tǒng)計檢測在面對較復(fù)雜問題時會更有優(yōu)勢。CMGP算法在F1、F2、F8等問題上表現(xiàn)較優(yōu),這說明CMGP算法在訓(xùn)練集上獲得的優(yōu)勢在測試集上也有所體現(xiàn), 在訓(xùn)練集上演化出的個體在測試集上表現(xiàn)較優(yōu)。

3.4 膨脹問題分析

GP算法常伴隨“膨脹”問題。“膨脹”問題指種群中個體的節(jié)點數(shù)不斷增加而適應(yīng)值卻并未相應(yīng)提高的情況。膨脹控制的主要目標(biāo)是減少冗余節(jié)點,降低解決方案的復(fù)雜性。為了驗證CMGP算法是否實現(xiàn)了這一目標(biāo),實驗記錄了不同算法解決問題的平均規(guī)模,即解決問題的最優(yōu)個體的平均節(jié)點數(shù),不同算法的實驗結(jié)果如表6所示。

表6 不同算法解決問題時的節(jié)點個數(shù)比較

從表6中可以較為明顯地看出,TS-S算法和CMGP算法對種群個體的節(jié)點數(shù)控制較好,相比于SGP算法,這兩種算法極大地緩解了算法的膨脹問題。在SR實驗上,雖然TS-S算法相對于CMGP算法在控制節(jié)點方面的表現(xiàn)較好,但正如第3.1節(jié)的分析,TS-S在該部分的優(yōu)秀表現(xiàn)是以犧牲精度換來的,TS-S算法的訓(xùn)練誤差表現(xiàn)較差。在TS-S算法表現(xiàn)較為均衡的分類問題上,雖然其在控制膨脹部分比FCGP算法和DPS+BR算法的表現(xiàn)更優(yōu),但都不如CMGP算法。因此,通過分析,可以得知CMGP算法在不同情況下的表現(xiàn)都相對較優(yōu)。在CTS算法和MPS算法中添加的控制膨脹策略有助于算法緩解“膨脹”問題,使得算法得到的個體結(jié)構(gòu)更優(yōu)。

3.5 運行時間分析

此部分主要分析了不同實驗所用的平均運行時間,具體計算時間如表7所示。由表7可以看出,DPS+BR算法和GACM算法所用時間較長。在DPS+BR算法中,由于使用了BR操作,算法將耗費大部分時間用于個體的交叉及計算個體的適應(yīng)值。父代不斷交叉并挑選下一代子代的方式固然提高了算法的尋優(yōu)能力,卻也大大增加了計算時間。特別是當(dāng)面對特征數(shù)、樣本數(shù)較多的分類問題時,計算個體適應(yīng)值將耗費大量計算資源。GACM算法將大部分時間用于計算個體的鄰接矩陣和最小生成樹,在選擇個體時,其選擇策略為通過父代的多次交叉進(jìn)行擇優(yōu)選擇,因而浪費了部分時間。

表7 不同算法在解決問題時的運行時間比較

相比于DPS+BR算法和GACM算法,FCGP算法和TS-S算法耗費的時間較少。FCGP算法由于聚類算法的操作較為簡單,因而耗費時間較少。而TS-S算法采用了Wilcoxon signed rank檢測方法,該檢測方法同時考慮了差異的方向和差異的大小,根據(jù)假定值p快速確定交叉的父代。CMGP算法在面對多特征的分類問題時,將時間耗費在了計算個體的BSFC上,并且在聚類上花費了部分時間,導(dǎo)致了算法整體計算時間的增加。

3.6 聚類錦標(biāo)賽截斷分析

在第2.1節(jié)中,CTS算法為了避免異常個體的影響引入了截斷操作。截斷操作即按照適應(yīng)值排序,保留部分個體,舍去剩余個體。以實驗F1為例,在給定參數(shù)的情況下,算法通過演化迭代,通?？稍谟?xùn)練集中將個體適應(yīng)值降低在1以內(nèi),但在實驗中,由于算法交叉變異的隨機(jī)性,可能會演化出適應(yīng)值較大的個體,如109 294 098.66等,此時該個體被稱為異常個體。為了觀察截斷操作對算法的影響,此部分給出了在不同截斷系數(shù)下的對比實驗。具體結(jié)果如表8所示,其中截斷系數(shù)為1.0代表不進(jìn)行截斷操作。

表8 CTS算法中不同截斷系數(shù)的實驗結(jié)果比較

從表8可以看出,當(dāng)截斷系數(shù)為0.99時,CMGP算法的訓(xùn)練誤差和測試誤差表現(xiàn)較好,而節(jié)點規(guī)模受截斷操作的影響較小。這說明,異常個體的存在會在一定程度上影響CTS算法的尋優(yōu)能力。通過截斷異常個體,算法性能得以提升。當(dāng)截斷系數(shù)偏大(如表中的0.95時),受種群規(guī)模影響,會使截斷的個體數(shù)目偏大,種群多樣性因此受到影響,從而導(dǎo)致算法精度變差。此外,該實驗也說明了保留部分較有潛力的個體會在一定程度上提升算法的精度。

3.7 實驗總體分析

在符號回歸和分類問題這兩類基準(zhǔn)問題上,本文算法與SGP算法、FCGP[28]算法、DPS[22]算法、TS-S[19]算法、GACM[17]算法這5種算法進(jìn)行了對比。本文從訓(xùn)練誤差、測試誤差、收斂速度、解決問題的規(guī)模及運行時間等多個角度對各種算法進(jìn)行了分析。分析結(jié)果表明,CMGP算法在保持多樣性的同時能夠進(jìn)行較好的收斂。此外,通過CMGP算法尋找到的個體不僅泛化能力較好且結(jié)構(gòu)較為簡潔。雖然CMGP算法在挑選優(yōu)秀個體和計算BSFC時耗費了一些時間,但是從實驗結(jié)果來看,這些計算量的消耗能夠幫助算法進(jìn)行快速收斂。

在SR實驗中,通過對比算法,可以看出誤差中位數(shù)有助于提升算法的優(yōu)化能力,這也證明了通過聯(lián)系個體整體表現(xiàn)和內(nèi)部表現(xiàn)有助于算法的改進(jìn)。在分類問題這種更具實際意義的問題上,CMGP算法較其他算法也有了一定的提升。

4 結(jié) 論

本文提出了一種針對選擇機(jī)制改進(jìn)的新方法CMGP,通過促進(jìn)不同個體之間的交叉,從多樣性角度引導(dǎo)算法搜索到最優(yōu)解。CMGP算法通過基于聚類的錦標(biāo)賽選擇算法,動態(tài)地調(diào)整選擇壓力,根據(jù)個體的適應(yīng)值和內(nèi)部表現(xiàn)進(jìn)行有針對性的交叉。對于非二進(jìn)制問題,本文提出了定義個體二進(jìn)制特征的新方法。此外,CMGP算法在各個環(huán)節(jié)中引入了控制膨脹的策略,以幫助算法找到具有更優(yōu)結(jié)構(gòu)的個體。該方法在被應(yīng)用于基準(zhǔn)問題時,不僅在尋優(yōu)精度上優(yōu)于其他方法,并且在收斂速度上也有了一定的提升。當(dāng)將所提出的方法應(yīng)用于具體的分類問題時,與其他方法相比,該方法表現(xiàn)出了更好的分類精度和收斂速度。

然而,算法還有待進(jìn)一步提升。面對實值問題和分類問題,特別是多分類問題時,算法需要對個體進(jìn)行更好的定義,希望能找到更好地區(qū)分個體內(nèi)部“優(yōu)勢”與“劣勢”的方法,更清晰、直觀地顯示出個體的內(nèi)部情況,從而進(jìn)一步找出更具針對性的父代進(jìn)行交叉,提高產(chǎn)生良好子代的可能。