基于蒙特卡洛樹搜索的符號回歸算法

魯 強，張 洋

(1.中國石油大學(xué)(北京) 石油數(shù)據(jù)挖掘北京市重點實驗室，北京 102249；2.中國石油大學(xué)(北京) 地球物理與信息工程學(xué)院，北京 102249)

0 引 言

符號回歸[1]問題是“在符號空間中尋找合適的公式，以使得它能夠描述指定的數(shù)據(jù)集”。目前解決符號回歸問題的常用算法是基于進化思想Genetic Programming-GP算法[2]。它將種群中每個個體表示為一個公式，通過個體之間的交叉、變異和選擇等操作，在符號空間內(nèi)尋找適應(yīng)度最優(yōu)的公式。由于這些操作僅是根據(jù)初始概率來隨機改變種群個體，因此GP算法存在以下的問題：①不能利用數(shù)據(jù)集的特征(例如周期性，對稱性等)來構(gòu)建和搜索合適的個體，從而導(dǎo)致搜索過程過長，搜索效率較低；②不能保存和利用已搜索空間的信息，從而導(dǎo)致容易陷入局部最優(yōu)。

針對上述問題，文獻[3]使用深度學(xué)習(xí)指導(dǎo)GP算法種群個體的初始函數(shù)選擇，減少GP算法的搜索范圍；文獻[4]使用強化學(xué)習(xí)動態(tài)優(yōu)化進化算法參數(shù)，使得算法更易跳出局部最優(yōu)；文獻[5]優(yōu)化了GP算法種群的初始化方法，減小了陷入局部最優(yōu)的可能。但是以上改進還是基于演化計算本身的改進，不能從根本上克服上述的兩個問題。

為了更好解決GP算法存在的上述問題，本文提出了一種基于深度學(xué)習(xí)[6]的蒙特卡洛樹搜索[7]符號回歸算法(MCTS-SR)。MCTS-SR算法首先將待搜索的符號空間劃分為兩個不同層次的子空間：模型空間和系數(shù)空間。本文使用模型空間樹表示模型空間，樹中添加的節(jié)點為已經(jīng)搜索過的公式模型。由于系數(shù)空間巨大，本文并沒有單獨對系數(shù)空間進行保存和劃分，僅是在每個公式模型下保存了其最優(yōu)的系數(shù)。

然后，根據(jù)數(shù)據(jù)集特征，將在模型空間中搜索(生成)公式模型的過程看作一個強化學(xué)習(xí)過程。將數(shù)據(jù)集和模型空間樹中的節(jié)點作為生成公式模型的當(dāng)前環(huán)境，利用強化學(xué)習(xí)中的策略函數(shù)π來選擇合適的基本符號(+、-和*等)以生成下一個公式模型。為生成此策略函數(shù)π，本文提出一種基于卷積神經(jīng)網(wǎng)絡(luò)(convolutional neural network-CNN)和循環(huán)神經(jīng)網(wǎng)絡(luò)(recurrent neural network-RNN)的深度策略網(wǎng)絡(luò)。該網(wǎng)絡(luò)使用CNN來獲取數(shù)據(jù)集的空間特征；使用RNN來獲取公式模型的序列特征；使用全連接層將上述兩類特征進行融合，并與基本符號建立映射。通過使用該網(wǎng)絡(luò)來指導(dǎo)并生成下一個公式模型。

最后，將蒙特卡洛樹搜索過程看作模型空間的探索與利用問題。根據(jù)上述深度策略網(wǎng)絡(luò)的輸出和當(dāng)前節(jié)點的搜索次數(shù)，使用上置信算法[8](upper confidence bound-UCB1)來指導(dǎo)對模型空間的搜索。同時在生成一個新公式模型(新節(jié)點)后，使用粒子群算法[9](particle swarm optimization-PSO)在該公式模型的系數(shù)空間內(nèi)尋找最佳系數(shù)，以得到最能描述數(shù)據(jù)集的公式。

1 背景知識

1.1 特征提取

蒙特卡洛樹搜索[10](Monte Carlo tree search-MCTS)是在決策空間中通過隨機取樣尋找最優(yōu)決策并建立搜索樹的方法。本文使用MCTS算法來解決模型空間搜索問題。MCTS算法可以在只有基本規(guī)則的情況下對搜索空間巨大的問題進行有效搜索，而不需要領(lǐng)域內(nèi)的經(jīng)驗輔助。MCTS算法主要流程分為4步：

第一步，選擇：在選擇階段需要根據(jù)當(dāng)前蒙特卡洛樹狀態(tài)依次選擇當(dāng)前最適合拓展的節(jié)點，直到達到樹的終結(jié)節(jié)點；第二步，拓展：把第一步選中的尚未添加到蒙特卡洛樹中的節(jié)點添加到蒙特卡洛樹中；第三步，模擬：根據(jù)每一個節(jié)點的適應(yīng)度函數(shù)得到一個該節(jié)點的評分，適應(yīng)度函數(shù)越小則該節(jié)點評分越高；第四步，反向傳播：在模擬過程結(jié)束之后，更新此次搜索過程中節(jié)點的狀態(tài)。

因為MCTS算法的搜索次數(shù)有限，不能搜索到樹中的每一個節(jié)點，所以存在空間探索與利用沖突的問題，其中探索是指搜索新的區(qū)域以獲得更多回報信息；利用是指使用已有的回報信息，在選擇節(jié)點之后使可能獲得的“回報”最大。為了平衡空間探索與利用問題，在MCTS算法中引入了UCB1，核心公式如下

(1)

1.2 強化學(xué)習(xí)

強化學(xué)習(xí)[11]是指智能系統(tǒng)從環(huán)境到行為映射的學(xué)習(xí)，以使得整個環(huán)境的累計獎勵值最大。強化學(xué)習(xí)通常使用馬爾科夫決策過程描述[12]：機器處于環(huán)境E中，狀態(tài)s是對當(dāng)前環(huán)境的描述，其集合構(gòu)成狀態(tài)空間S。動作a可以使?fàn)顟B(tài)si跳轉(zhuǎn)到下一狀態(tài)si+1， 其集合構(gòu)成動作空間A。每次狀態(tài)轉(zhuǎn)移之后可以獲得一個獎勵值r，體現(xiàn)本次轉(zhuǎn)移效果的測度。由此，強化學(xué)習(xí)要找到一條最優(yōu)“狀態(tài)-動作”序列，使得整體獎勵值最大。每一個狀態(tài)s總能根據(jù)策略函數(shù)π找到一個最優(yōu)動作a，使整體的累計獎勵值最大，其中策略函數(shù)π如式(2)所示

a=π(s)

(2)

2 問題和相關(guān)概念定義

將用于生成公式的基本函數(shù)稱為基本符號。例如，二元函數(shù)+，-、一元函數(shù)sin、自變量x等。這些基本符號組成的公式稱為公式模型。一個公式由公式模型和對應(yīng)的系數(shù)組成。將所有公式模型的可選擇系數(shù)范圍稱為系數(shù)空間。將由所有公式所形成的集合稱為符號空間，其包括模型空間和系數(shù)空間。例如符號空間中的公式 “0.3*cos(x)+0.5*x” 和 “0.4*x”， 其中 “cos(x)+x” 和“x”是模型空間中的公式模型，“0.3、1、0.5”和“0.4”是它們系數(shù)空間中對應(yīng)的系數(shù)。

本文使用模型空間樹來表示模型空間，其數(shù)據(jù)結(jié)構(gòu)如圖1所示。

圖1 模型空間樹

其中，此樹中的節(jié)點表示公式模型，每個公式模型使用二叉樹結(jié)構(gòu)進行表示和存儲；邊表示父節(jié)點公式模型到子節(jié)點公式模型的變化操作。此操作表示為，其中sym表示基本符號；pos表示sym的作用位置，pos的編碼形式為滿二叉樹層序遍歷的次序。例如圖1中節(jié)點為公式模型 “x+x”， 其經(jīng)過邊的操作(如圖2所示，使用基本符號cos作用在位置3上)形成新節(jié)點(公式模型 “cos(x)+x”)。 通過以上定義，可知此模型空間樹可以表示整個模型空間。但如果選取的初等函數(shù)種類過多，會使得模型空間樹過大，影響搜索的效率與準(zhǔn)確率，所以本文只選取了+，-，*，sin，cos，x2初等函數(shù)。

圖2 公式模型生成

構(gòu)建此模型空間樹的過程就是對模型空間的探索過程。因此，添加子節(jié)點的位置次序直接關(guān)系到在符號空間中搜索答案的速度。例如，圖1中加粗路徑是公式模型 “cos(x)-sin(x)” 的生成過程。但若是在公式模型生成時先搜索節(jié)點 “x+x”， 則必須搜索更多的子節(jié)點才可以探索到正確的公式模型，使得搜索效率降低。為得到合理的子節(jié)點位置次序，將此樹的構(gòu)建看作一個強化學(xué)習(xí)過程。將節(jié)點作為狀態(tài)，邊作為動作，則從根節(jié)點到葉子節(jié)點的一條路徑作為強化學(xué)習(xí)中“狀態(tài)-動作”序列。在已知這些序列的基礎(chǔ)上，通過強化學(xué)習(xí)獲得符合數(shù)據(jù)集特征的生成節(jié)點次序，以得到最大“累計獎勵值”。

每創(chuàng)建一個節(jié)點，就對此節(jié)點表示的公式模型使用PSO算法進行系數(shù)空間搜索，以得到較優(yōu)的系數(shù)，并將此系數(shù)進行保存。例如，如果公式模型為 “x+sin(x)”， 經(jīng)過PSO算法生成系數(shù)后的具體公式為 “0.3*x+0.2*sin(0.5*x)”。 在PSO算法進行系數(shù)空間搜索時，使用適應(yīng)度函數(shù)(式(3))來衡量系數(shù)的“好壞”

(3)

式中：yn為測試數(shù)據(jù)集的結(jié)果，y′n是當(dāng)前公式使用測試數(shù)據(jù)集計算的結(jié)果。式(3)表示絕對值誤差和，也就是測試數(shù)據(jù)集中每個結(jié)果和公式預(yù)測的每個結(jié)果的差的絕對值累積和。

根據(jù)上面的描述，本文將符號回歸問題轉(zhuǎn)換為模型空間樹的搜索過程。首先，利用數(shù)據(jù)集特征和已搜索空間信息，使用MCTS算法完成模型空間的搜索。再使用PSO算法完成系數(shù)空間的搜索。在搜索過程中，當(dāng)找到適應(yīng)度低于設(shè)定閾值的公式或者到達指定搜索路徑次數(shù)時，搜索停止。

3 算 法

MCTS-SR算法由3部分組成：深度策略網(wǎng)絡(luò)模塊、模型空間探索模塊和系數(shù)空間探索模塊。①深度策略網(wǎng)絡(luò)模塊：其為預(yù)訓(xùn)練模塊，根據(jù)大量的訓(xùn)練數(shù)據(jù)獲得公式模型生成信息(當(dāng)前狀態(tài)的所有可能的下一步動作選擇概率)，以指導(dǎo)MCTS算法；②模型空間探索模塊：其通過MCTS算法來選擇或生成樹節(jié)點(即公式模型)，在搜索過程中，使用UCB1整合以下兩個方面的信息：深度策略網(wǎng)絡(luò)模塊提供的公式生成信息和蒙特卡洛樹自身包含的模型空間探索信息，指導(dǎo)樹節(jié)點的選擇或生成；并設(shè)計相關(guān)的剪枝規(guī)則，提高搜索效率；③系數(shù)空間探索模塊：其為對上一步獲得的每一個公式模型運行指定代數(shù)的PSO算法，以得到適合此公式模型的系數(shù)。

此算法流程如圖3所示。當(dāng)算法滿足停止條件：到達設(shè)定的循環(huán)次數(shù)或者適應(yīng)度函數(shù)小于設(shè)定閾值，則算法停止。

圖3 MCTS-SR算法流程

3.1 深度策略網(wǎng)絡(luò)模塊

如第2節(jié)問題描述所示，每次蒙特卡洛樹搜索過程是強化學(xué)習(xí)中的一個“狀態(tài)-動作”序列生成過程，所以可通過強化學(xué)習(xí)的方法獲得公式模型生成的策略函數(shù)π，從而指導(dǎo)蒙特卡洛樹搜索。如式(4)所示，本文中使用深度策略網(wǎng)絡(luò)表示策略函數(shù)

π(a|s)=p(a|s)

(4)

式中：s表示當(dāng)前狀態(tài)，包含數(shù)據(jù)集和當(dāng)前公式模型，a代表可選擇的動作。由于式(4)中s與a之間的關(guān)系很難進行量化建模，因此設(shè)計了一種基于CNN與RNN的深度策略網(wǎng)絡(luò)，通過訓(xùn)練大量“狀態(tài)-動作”序列，來得到最佳的策略函數(shù)。式(4)中的p(a|s) 使用式(5)、式(6)來計算

p(a|s)=softmax(v)

(5)

v=Network(s)

(6)

其中，Network表示CNN-RNN聯(lián)合提取公式模型生成特征網(wǎng)絡(luò)，v表示動作特征，softmax表示動作選擇概率函數(shù)。在計算深度策略網(wǎng)絡(luò)輸出時，首先使用神經(jīng)網(wǎng)絡(luò)Network提取動作特征v，再使用softmax輸出動作選擇概率。

深度策略網(wǎng)絡(luò)結(jié)構(gòu)如圖4所示。該網(wǎng)絡(luò)使用CNN來提取數(shù)據(jù)訓(xùn)練集中的空間特征，這是因為CNN對于提取數(shù)據(jù)的空間關(guān)系有較好的效果[13]；使用RNN來提取公式模型的序列特征，這是因為公式模型使用樹結(jié)構(gòu)進行表示，樹節(jié)點之間有較強序列關(guān)系，而RNN能夠較好地學(xué)習(xí)序列關(guān)系之間的特征[14]。最后使用Merge層融合CNN和RNN提取的特征，并通過輸出層來得到當(dāng)前環(huán)境(當(dāng)前數(shù)據(jù)集和公式模型)下動作選擇概率。

圖4 深度策略網(wǎng)絡(luò)結(jié)構(gòu)

3.2 模型空間探索模塊

本模塊使用MCTS算法在模型空間中搜索較優(yōu)公式模型。MCTS算法根據(jù)深度策略網(wǎng)絡(luò)的公式生成信息和蒙特卡洛樹包含的模型空間探索信息，來指導(dǎo)樹節(jié)點的選擇和生成。相較于使用隨機策略的MCTS算法，MCTS-SR算法會根據(jù)上述信息優(yōu)先搜索可能找到較優(yōu)公式模型的局部空間，提高搜索效率。

蒙特卡洛樹中的節(jié)點表示模型空間中的子空間，此節(jié)點下的子樹是對子空間的探索；同時這些探索過程又生成了該子空間的“利用信息”。如果僅使用“利用信息”在該子空間下進行搜索，搜索結(jié)果容易陷入局部最優(yōu)；如果不考慮“利用信息”，將使得搜索效率下降。

為平衡在模型空間探索中的搜索與利用問題，使用式(7)在所有可選擇的動作中選取一個當(dāng)前最優(yōu)動作

(7)

式中：c為搜索與利用平衡系數(shù)，nj為子節(jié)點j的搜索次數(shù)，p(a|si) 為狀態(tài)si下深度策略網(wǎng)絡(luò)輸出的動作選擇概率，paj為第j個動作(也是選擇第j個子節(jié)點)的動作值。其中c的數(shù)值越大，蒙特卡洛樹就可以盡可能多地探索未被搜索過的子節(jié)點；c的數(shù)值越小，蒙特卡洛樹就可以使用更多的“利用信息”。式(7)可以較好平衡搜索與利用問題，在保證有效利用“利用信息”的基礎(chǔ)上，兼顧搜索未添加過的節(jié)點，以較高的效率搜索到較優(yōu)的公式模型。

MCTS算法主要流程如圖5所示。

(1)根據(jù)式(7)對路徑中每一個狀態(tài)(節(jié)點)選擇一個paj最大的動作，進行下一個子節(jié)點的選擇或者拓展。當(dāng)公式模型中再無位置可被基本符號替換時，則為完成一次蒙特卡洛樹搜索。此步驟對應(yīng)圖5中(4)-(6)行。

(2)根據(jù)paj生成下一個狀態(tài)的公式模型。如果下一個狀態(tài)的公式模型不在蒙特卡洛樹中，就把此公式模型添加到子節(jié)點中。此步驟對應(yīng)圖5中(7)行。

(3)使用本文3.3節(jié)系數(shù)空間探索模塊對每一個新生成的公式模型完成系數(shù)空間搜索，已在蒙特卡洛樹中的公式模型跳過此步。此步驟對應(yīng)圖5中(8)行。

(4)更新整條路徑上的搜索信息。新添加的節(jié)點搜索次數(shù)置為1，其余節(jié)點的搜索次數(shù)加1。此步驟對應(yīng)圖5中(9)行。MCTS-SR算法循環(huán)運行上述步驟，直到達到最大搜索路徑次數(shù)或適應(yīng)度小于設(shè)定閾值。

Algorithm: Model Space Exploration AlgorithmInput: Test Set,DY={d1,d2,..dn}, Model POutput: bestF_fitness(1) initMCTS(mct)(2) Fori=1,2,3,…,Ndo:(3) Repeat(4) ST=mctTostate(mct)(5) pa=predictByPolicy(P,ST,DY)(6) a=argmax(pa)(7) ExpandNode(mct)(8) bestF_fitness=CSA(DS,ST)(9) update(mct)(10) until mct can not grow(11) end fors

為了加快MCTS算法的搜索效率，在搜索過程中增加剪枝操作，以避免重復(fù)搜索同一子空間。其剪枝規(guī)則如下：①在蒙特卡洛樹搜索過程中，如果葉子節(jié)點已經(jīng)被搜索過，則把此節(jié)點標(biāo)記為不可搜索節(jié)點；②如果某節(jié)點的所有子節(jié)點全部被標(biāo)記為不可搜索節(jié)點，則此節(jié)點同樣會被標(biāo)記為不可搜索節(jié)點。在MCTS算法中加入剪枝操作可以避免蒙特卡洛樹多次搜索同一條路徑，提高搜索效率。

3.3 系數(shù)空間探索模塊

在每添加一個節(jié)點后，需要對此節(jié)點表示的公式模型進行系數(shù)搜索。系數(shù)空間搜索使用PSO算法進行實現(xiàn)。首先，PSO算法隨機初始化種群中粒子位置。本文將PSO算法的粒子表示指定公式模型的系數(shù)，其編碼方式為Coe=， 其中coei為公式模型中的第i個基本符號(除去二元基本符號)對應(yīng)的系數(shù)。例如，公式模型為 “x+sin(x)”， 因為其有x、sin和x這3個基本符號，則與之對應(yīng)的系數(shù)可以是Coe=<0.5,0.1,0.8>。 將系數(shù)與對應(yīng)的基本符號相乘，公式模型和對應(yīng)系數(shù)結(jié)合而成的公式則為 “0.5*x+0.1*sin(0.8*x)”。

其次，粒子的速度(系數(shù)的變化大小)決定粒子移向何處。在PSO算法中粒子的速度主要由種群中最優(yōu)粒子和各個粒子自身的歷史位置決定的。式(8)為粒子的速度計算公式

vi=vi+c1*rand()*(Coepbesti-Coei)+
c2*rand()*(Coegbest-Coei)

(8)

式中：vi表示第i個粒子中系數(shù)的變化值，rand()是[0,1]之間的隨機數(shù)，Coei表示第i個粒子表示的系數(shù)值，c1和c2是學(xué)習(xí)因子，Coepbesti是第i個粒子保存的自身的歷史最優(yōu)系數(shù)，Coegbest是整個種群中保存的歷史最優(yōu)系數(shù)。使用式(8)可以得到系數(shù)的變化值，再使用式(9)更新粒子的位置，得到新的一組系數(shù)值

Coei=Coei+vi

(9)

式中：Coei表示第i個粒子的當(dāng)前位置(系數(shù)值)。不斷迭代運行式(8)、式(9)使粒子(系數(shù))趨近于最優(yōu)解。

最后，在每更新完粒子一次位置后，使用適應(yīng)度函數(shù)(式(3))評價當(dāng)前系數(shù)是否為該公式模型的最優(yōu)系數(shù)。當(dāng)達到最大迭代次數(shù)或者搜索到最優(yōu)解時搜索停止，再判斷該公式模型與對應(yīng)系數(shù)是否為符號空間中最優(yōu)公式，如果是則標(biāo)記出來。系數(shù)空間探索模塊流程如圖6所示。

圖6 系數(shù)空間探索模塊流程

3.4 算法分析

相比GP算法從符號空間中直接生成種群個體，MCTS-SR算法是在符號空間劃分出的模型空間和系數(shù)空間中交替搜索，這樣可以避免兩個空間相互干擾，提高搜索效率。

在本文中假設(shè)非終結(jié)符號f={+，-，*，sin，cos，x2}， 其中一元函數(shù)f1={sin，cos，x2}， 二元函數(shù)f2={+，-，*}。 終結(jié)符號T={x,c}， 常數(shù)c的精度是0.001，根據(jù)式(10)可以迭代計算出第d層公式樹可以表示的公式數(shù)

(10)

式中：Ld為第d層公式樹可以表達的公式數(shù)目。相較于GP算法MCTS-SR算法在搜索模型空間時無需引入常數(shù)c，所以搜索空間會小很多。例如根據(jù)本文選用的上述基本符號，可算出 |T|=1001、 |f1|=3、 |f2|=3，L0=1007。 由式(10)可以計算出當(dāng)深度d為4時，則符號空間中可以選擇的公式個數(shù)大約為1.47*1055。

在只考慮模型空間的情況下，當(dāng)深度d也為4時，MCTS-SR算法的符號空間可以選擇的公式個數(shù)約為7.93*1010。這比直接在符號空間中搜索的復(fù)雜度要小很多，所以可以使得搜索效率提高。并且一個公式模型只需記錄一組對應(yīng)的最優(yōu)系數(shù)，使得無需使用額外空間記錄系數(shù)空間中的系數(shù)。

4 實驗結(jié)果

4.1 數(shù)據(jù)集與環(huán)境

本實驗選用的符號空間中的基本符號共有8個，分別為：1，x，+，-，*，sin，cos，x2。其中終結(jié)符號為1，x；非終結(jié)符號為+，-，*，sin，cos和x2。

深度策略網(wǎng)絡(luò)的訓(xùn)練數(shù)據(jù)通過以下過程來生成：①隨機生成6000個不同的公式模型；②針對每個公式模型，隨機生成20組系數(shù)，系數(shù)范圍為[0,1]。每個隨機生成的公式模型包含7種基本符號種類(“+”擁有1+x和x+x兩種)，并且每個公式模型最多有7個基本符號的作用位置(非葉節(jié)點)可以選擇，所以深度策略網(wǎng)絡(luò)共有49個動作可以選擇。其中正確動作選擇對應(yīng)的標(biāo)簽(獎勵值)為1，其余動作選擇對應(yīng)的標(biāo)簽(獎勵值)為0。依據(jù)上述方法，最終生成46.5萬條訓(xùn)練數(shù)據(jù)。

深度策略網(wǎng)絡(luò)使用Keras深度學(xué)習(xí)開發(fā)平臺，其訓(xùn)練參數(shù)如下：RNN的輸入維數(shù)為15，CNN的輸入維數(shù)為(10,20,1)。其中CNN共擁有卷積層4層，其卷積核個數(shù)分別為64、32、32、32，池化層一層；RNN中有兩層LSTM，其單元個數(shù)分別為64、32。CNN與RNN都與有1024個節(jié)點的全連接層相連，再使用Merge層進行合并，最后與兩層分別有512、256個節(jié)點的全連接網(wǎng)絡(luò)相連。本實驗采用基于mini-batch的Adam優(yōu)化方式訓(xùn)練參數(shù)，學(xué)習(xí)率設(shè)為0.001。損失函數(shù)為多類的對數(shù)損失(categorical crossentropy)。

4.2 實驗結(jié)果分析

使用上述的訓(xùn)練集對深度策略網(wǎng)絡(luò)進行訓(xùn)練，在整個訓(xùn)練集上訓(xùn)練200代，得到訓(xùn)練集的準(zhǔn)確率為56.4%，準(zhǔn)確率變化如圖7所示；在保留的測試集中測試的準(zhǔn)確率為41.2%。本實驗結(jié)果表明：在上述深度策略網(wǎng)絡(luò)的訓(xùn)練準(zhǔn)確率下，可以高效搜索到較優(yōu)公式。

圖7 深度策略網(wǎng)絡(luò)準(zhǔn)確率

本實驗使用表1中的隨機公式生成的測試數(shù)據(jù)集對MCTS-SR算法進行測試，并與GP算法進行比較，其中GP算法參數(shù)設(shè)置見表2。

由于GP算法是不穩(wěn)定的算法，每次運行結(jié)果不一定一樣，所以在每個測試數(shù)據(jù)集上運行10次，每次運行1000代。MCTS-SR算法是一種較穩(wěn)定的算法，只運行1次，在蒙特卡洛樹中搜索1000條路徑。比較兩種算法的適應(yīng)度高低，越低代表越貼近所給函數(shù)的特征。圖8是10次GP算法適應(yīng)度與MCTS-SR算法適應(yīng)度的對比圖。表3是MCTS-SR算法的適應(yīng)度依次與10次GP算法中的最優(yōu)適應(yīng)度、平均適應(yīng)度和最差適應(yīng)度進行對比。

表1 測試公式

表2 GP算法參數(shù)

圖8 MCTS-SR算法與GP算法比較

通過表3可以看出，MCTS-SR算法在全部的測試數(shù)據(jù)集中的適應(yīng)度都小于GP算法的平均適應(yīng)度，在公式F1中甚至要比GP算法中最優(yōu)的適應(yīng)度還要更好。這說明了MCTS-SR算法可以在符號空間中找到較優(yōu)的公式。

MCTS-SR算法在算法穩(wěn)定性上要優(yōu)于GP算法。GP算法是一種不穩(wěn)定的算法，受種群初始化、交叉變異參數(shù)選擇的影響較大，不能保證每次運行都能得到最優(yōu)的結(jié)果。如表3中公式F5所示，GP算法最優(yōu)和最差適應(yīng)度可以相差380倍左右，即使是相差最小的公式F4也相差了6倍左右。這使得GP算法必須運行多次才能得到較優(yōu)解，解決問題的效率較低。而MCTS-SR算法是一種較穩(wěn)定的算法，只要深度策略網(wǎng)絡(luò)訓(xùn)練完畢，則蒙特卡洛樹搜索過程中每次選擇或拓展的節(jié)點依據(jù)式(7)也就確定了，所以MCTS-SR不會像GP算法一樣上下限差距很大，可以穩(wěn)定得到一個較優(yōu)解。

表3 GP算法與MCTS-SR算法對比

MCTS-SR算法相比GP算法不易陷入局部最優(yōu)解。由圖8可以發(fā)現(xiàn)MCTS-SR算法在搜索時適應(yīng)度函數(shù)會不斷下降，而GP算法在快速下降之后就趨于穩(wěn)定。這是因為GP算法并不會記錄已搜索過的種群，所以有可能會在同一空間內(nèi)進行重復(fù)探索，導(dǎo)致陷入局部最優(yōu)解。而MCTS-SR算法中有剪枝操作，不會重復(fù)搜索相同的公式模型，這使得MCTS-SR可以一直探索新的子空間，發(fā)掘新的較優(yōu)公式，不易陷入局部最優(yōu)。

5 結(jié)束語

針對GP算法存在無法充分利用數(shù)據(jù)特征、收斂效率低、易陷入局部最優(yōu)解等問題。本文把符號空間分為模型空間和系數(shù)空間。模型空間使用模型空間樹表示，可以記錄每次搜索的公式模型，不會重復(fù)搜索同一子空間，避免陷入局部最優(yōu)解。并且MCTS-SR算法使用深度策略網(wǎng)絡(luò)輔助進行公式模型生成，可以充分利用數(shù)據(jù)特征生成公式模型。由實驗可知，相較GP算法而言，使用MCTS-SR算法獲得的公式適應(yīng)度值更優(yōu)、穩(wěn)定性更優(yōu)、不易陷入局部最優(yōu)。