中文題目：基于符號圖遺傳編程的符號回歸方法

論文題目：Symbol Graph Genetic Programming for Symbolic Regression

錄用期刊/會議：Parallel Problem Solving From Nature PPSN 2024 (CCF B)

作者列表：

1）宋晶璐 中國石油大學（北京）人工智能學院 計算機科學與技術 碩22

2）魯   強 中國石油大學（北京）人工智能學院 智能科學與技術系 教師

3）田博舟 中國石油大學（北京）人工智能學院 計算機技術 碩22

4）張經文 中國石油大學（北京）人工智能學院 計算機科學與技術 碩22

5）Jake Luo University of Wisconsin Milwaukee Department of Health Informatics and Administration Associate Professor

6）王智廣 中國石油大學（北京）人工智能學院 計算機系 教師

摘要:

符號回歸的數學表達式空間是巨大的，所以解決該問題的主要難點在于如何精準地識別更可能包含正確表達式的子空間。本文深入探討這一難點，提出名為符號圖遺傳編程（SGGP）的創新方法。SGGP首先構建一個符號圖來有效地表示表達式空間。然后，它采用基于語義相似度的廣義帕累托分布來評估該圖中每條邊（子空間）產生優秀個體的概率。根據這些概率，SGGP策略性采樣新個體來發現準確的表達式。在109個數據集上的對比實驗表明，SGGP顯著優于21種現有的符號回歸方法，其生成的表達式不僅準確性更高，而且更簡潔。

背景與動機:

符號回歸（SR）指從表達式空間中發現與給定數據集擬合的表達式。由于SR是NP難問題，演化計算特別是遺傳編程方法，通常用于尋找SR的近似解。這些方法雖然有效，但它們在搜索表達式的過程中往往忽略數據集的特征。而機器學習/深度學習算法往往受到預定義的回歸模型和所使用的訓練數據集的影響。在大規模的基準實驗中發現，最優的三種SR方法仍是基于遺傳編程的，所以我們提出一種結合數據集特征的遺傳編程方法來解決SR問題。

設計與實現:

符號圖遺傳編程(SGGP)方法總體框架如圖1所示。首先，SGGP構建一個符號圖，并在該圖中初始化種群（如圖1a所示）。然后，它利用語義算子生成新種群，具體操作如下：（1）計算極值分布：語義算子通過估計個體的語義相似度（如圖1b所示）來計算每條邊上的極值分布（如圖1c所示）；（2）采樣新個體：根據計算出的極值分布，語義算子對新個體采樣（如圖1d所示）。

圖1 符號圖遺傳編程(SGGP)

實驗結果及分析:

在FSRB、Strogatz和PMLB數據集上的對比實驗表明，SGGP在、恢復率和模型大小方面都明顯優于其他算法。

圖2 FSRB和Strogatz的實驗結果

（a） Test （b）Model Size

圖3 PMLB的實驗結果

（a）FSRB和Strogatz （b）PMLB

圖4 和模型大小的帕累托前沿圖

SGGP的突出性能主要歸功于語義算子。該算子能夠利用個體語義相似度和極值分布來指導SGGP搜索。這種方法能夠提高搜索效率，使SGGP能夠更快地找到最優解。

圖5 數據集“”收斂性比較。虛線表示每種算法運行10次的平均適應度。藍色實線是SGGP運行的結果之一。?；鶊Da、b和c表示符號圖中邊的概率。

結論:

本文設計了一種新的符號圖，用來描述符號回歸的表達式空間。在符號圖的基礎上，我們提出了一種新的遺傳編程方法——符號圖遺傳編程（SGGP）。SGGP采用極值分布以及語義相似度來計算符號圖中每條邊的概率。然后，它基于這些概率對新個體進行采樣來有效搜索正確的表達式。實驗表明，SGGP優于21種符號回歸方法，其中包括最新的機器學習/深度學習方法和演化計算方法。

通訊作者簡介:

魯強，副教授，博士生導師。目前主要從事演化計算和符號回歸、知識圖譜與智能問答、以及軌跡分析與挖掘等方面的研究工作。

聯系方式：luqiang@cup.edu.cn