基于蒙特卡洛樹搜索的符號(hào)回歸算法

魯 強(qiáng)，張 洋

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

0 引 言

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

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

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

然后，根據(jù)數(shù)據(jù)集特征，將在模型空間中搜索(生成)公式模型的過程看作一個(gè)強(qiáng)化學(xué)習(xí)過程。將數(shù)據(jù)集和模型空間樹中的節(jié)點(diǎn)作為生成公式模型的當(dāng)前環(huán)境，利用強(qiáng)化學(xué)習(xí)中的策略函數(shù)π來選擇合適的基本符號(hào)(+、-和*等)以生成下一個(gè)公式模型。為生成此策略函數(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來獲取公式模型的序列特征；使用全連接層將上述兩類特征進(jìn)行融合，并與基本符號(hào)建立映射。通過使用該網(wǎng)絡(luò)來指導(dǎo)并生成下一個(gè)公式模型。

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

1 背景知識(shí)

1.1 特征提取

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

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

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

(1)

1.2 強(qiáng)化學(xué)習(xí)

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

a=π(s)

(2)

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

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

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

圖1 模型空間樹

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

圖2 公式模型生成

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

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

(3)

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

根據(jù)上面的描述，本文將符號(hào)回歸問題轉(zhuǎn)換為模型空間樹的搜索過程。首先，利用數(shù)據(jù)集特征和已搜索空間信息，使用MCTS算法完成模型空間的搜索。再使用PSO算法完成系數(shù)空間的搜索。在搜索過程中，當(dāng)找到適應(yīng)度低于設(shè)定閾值的公式或者到達(dá)指定搜索路徑次數(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òng)作選擇概率)，以指導(dǎo)MCTS算法；②模型空間探索模塊：其通過MCTS算法來選擇或生成樹節(jié)點(diǎn)(即公式模型)，在搜索過程中，使用UCB1整合以下兩個(gè)方面的信息：深度策略網(wǎng)絡(luò)模塊提供的公式生成信息和蒙特卡洛樹自身包含的模型空間探索信息，指導(dǎo)樹節(jié)點(diǎn)的選擇或生成；并設(shè)計(jì)相關(guān)的剪枝規(guī)則，提高搜索效率；③系數(shù)空間探索模塊：其為對(duì)上一步獲得的每一個(gè)公式模型運(yùn)行指定代數(shù)的PSO算法，以得到適合此公式模型的系數(shù)。

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

圖3 MCTS-SR算法流程

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

如第2節(jié)問題描述所示，每次蒙特卡洛樹搜索過程是強(qiáng)化學(xué)習(xí)中的一個(gè)“狀態(tài)-動(dòng)作”序列生成過程，所以可通過強(qiáng)化學(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代表可選擇的動(dòng)作。由于式(4)中s與a之間的關(guān)系很難進(jìn)行量化建模，因此設(shè)計(jì)了一種基于CNN與RNN的深度策略網(wǎng)絡(luò)，通過訓(xùn)練大量“狀態(tài)-動(dòng)作”序列，來得到最佳的策略函數(shù)。式(4)中的p(a|s) 使用式(5)、式(6)來計(jì)算

p(a|s)=softmax(v)

(5)

v=Network(s)

(6)

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

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

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

3.2 模型空間探索模塊

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

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

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

(7)

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

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

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

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

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

(4)更新整條路徑上的搜索信息。新添加的節(jié)點(diǎn)搜索次數(shù)置為1，其余節(jié)點(diǎn)的搜索次數(shù)加1。此步驟對(duì)應(yīng)圖5中(9)行。MCTS-SR算法循環(huán)運(yùn)行上述步驟，直到達(dá)到最大搜索路徑次數(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é)點(diǎn)已經(jīng)被搜索過，則把此節(jié)點(diǎn)標(biāo)記為不可搜索節(jié)點(diǎn)；②如果某節(jié)點(diǎn)的所有子節(jié)點(diǎn)全部被標(biāo)記為不可搜索節(jié)點(diǎn)，則此節(jié)點(diǎn)同樣會(huì)被標(biāo)記為不可搜索節(jié)點(diǎn)。在MCTS算法中加入剪枝操作可以避免蒙特卡洛樹多次搜索同一條路徑，提高搜索效率。

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

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

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

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

(8)

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

Coei=Coei+vi

(9)

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

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

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

3.4 算法分析

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

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

(10)

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

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

4 實(shí)驗(yàn)結(jié)果

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

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

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

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

4.2 實(shí)驗(yàn)結(jié)果分析

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

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

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

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

表1 測(cè)試公式

表2 GP算法參數(shù)

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

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

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

表3 GP算法與MCTS-SR算法對(duì)比

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

5 結(jié)束語

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