魯 強，張 洋

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

0 引 言

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

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

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

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

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

1 背景知識

1.1 特征提取

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

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

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

(1)

1.2 強化學習

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

a=π(s)

(2)

2 問題和相關概念定義

將用于生成公式的基本函數(shù)稱為基本符號。例如，二元函數(shù)+，-、一元函數(shù)sin、自變量x等。這些基本符號組成的公式稱為公式模型。一個公式由公式模型和對應的系數(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ù)空間中對應的系數(shù)。

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

圖1 模型空間樹

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

圖2 公式模型生成

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

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

(3)

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

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

3 算 法

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

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

圖3 MCTS-SR算法流程

3.1 深度策略網絡模塊

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

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

(4)

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

p(a|s)=softmax(v)

(5)

v=Network(s)

(6)

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

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

圖4 深度策略網絡結構

3.2 模型空間探索模塊

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

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

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

(7)

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

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

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

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

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

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

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

在每添加一個節(jié)點后，需要對此節(jié)點表示的公式模型進行系數(shù)搜索。系數(shù)空間搜索使用PSO算法進行實現(xiàn)。首先，PSO算法隨機初始化種群中粒子位置。本文將PSO算法的粒子表示指定公式模型的系數(shù)，其編碼方式為Coe=， 其中coei為公式模型中的第i個基本符號(除去二元基本符號)對應的系數(shù)。例如，公式模型為 “x+sin(x)”， 因為其有x、sin和x這3個基本符號，則與之對應的系數(shù)可以是Coe=<0.5,0.1,0.8>。 將系數(shù)與對應的基本符號相乘，公式模型和對應系數(shù)結合而成的公式則為 “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是學習因子，Coepbesti是第i個粒子保存的自身的歷史最優(yōu)系數(shù)，Coegbest是整個種群中保存的歷史最優(yōu)系數(shù)。使用式(8)可以得到系數(shù)的變化值，再使用式(9)更新粒子的位置，得到新的一組系數(shù)值

Coei=Coei+vi

(9)

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

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

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

3.4 算法分析

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

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

(10)

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

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

4 實驗結果

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

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

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

深度策略網絡使用Keras深度學習開發(fā)平臺，其訓練參數(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é)點的全連接網絡相連。本實驗采用基于mini-batch的Adam優(yōu)化方式訓練參數(shù)，學習率設為0.001。損失函數(shù)為多類的對數(shù)損失(categorical crossentropy)。

4.2 實驗結果分析

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

圖7 深度策略網絡準確率

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

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

表1 測試公式

表2 GP算法參數(shù)

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

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

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

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

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

5 結束語

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