科研動(dòng)態(tài)
基于符號(hào)圖遺傳編程的符號(hào)回歸方法
中文題目：基于符號(hào)圖遺傳編程的符號(hào)回歸方法
論文題目：Symbol Graph Genetic Programming for Symbolic Regression
錄用期刊/會(huì)議：Parallel Problem Solving From Nature PPSN 2024 (CCF B)
作者列表：
1）宋晶璐 中國(guó)石油大學(xué)（北京）人工智能學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù) 碩22
2）魯 強(qiáng) 中國(guó)石油大學(xué)（北京）人工智能學(xué)院 智能科學(xué)與技術(shù)系 教師
3）田博舟 中國(guó)石油大學(xué)（北京）人工智能學(xué)院 計(jì)算機(jī)技術(shù) 碩22
4）張經(jīng)文 中國(guó)石油大學(xué)（北京）人工智能學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù) 碩22
5）Jake Luo University of Wisconsin Milwaukee Department of Health Informatics and Administration Associate Professor
6）王智廣 中國(guó)石油大學(xué)（北京）人工智能學(xué)院 計(jì)算機(jī)系 教師
摘要:
符號(hào)回歸的數(shù)學(xué)表達(dá)式空間是巨大的，所以解決該問(wèn)題的主要難點(diǎn)在于如何精準(zhǔn)地識(shí)別更可能包含正確表達(dá)式的子空間。本文深入探討這一難點(diǎn)，提出名為符號(hào)圖遺傳編程（SGGP）的創(chuàng)新方法。SGGP首先構(gòu)建一個(gè)符號(hào)圖來(lái)有效地表示表達(dá)式空間。然后，它采用基于語(yǔ)義相似度的廣義帕累托分布來(lái)評(píng)估該圖中每條邊（子空間）產(chǎn)生優(yōu)秀個(gè)體的概率。根據(jù)這些概率，SGGP策略性采樣新個(gè)體來(lái)發(fā)現(xiàn)準(zhǔn)確的表達(dá)式。在109個(gè)數(shù)據(jù)集上的對(duì)比實(shí)驗(yàn)表明，SGGP顯著優(yōu)于21種現(xiàn)有的符號(hào)回歸方法，其生成的表達(dá)式不僅準(zhǔn)確性更高，而且更簡(jiǎn)潔。
背景與動(dòng)機(jī):
符號(hào)回歸（SR）指從表達(dá)式空間中發(fā)現(xiàn)與給定數(shù)據(jù)集擬合的表達(dá)式。由于SR是NP難問(wèn)題，演化計(jì)算特別是遺傳編程方法，通常用于尋找SR的近似解。這些方法雖然有效，但它們?cè)谒阉鞅磉_(dá)式的過(guò)程中往往忽略數(shù)據(jù)集的特征。而機(jī)器學(xué)習(xí)/深度學(xué)習(xí)算法往往受到預(yù)定義的回歸模型和所使用的訓(xùn)練數(shù)據(jù)集的影響。在大規(guī)模的基準(zhǔn)實(shí)驗(yàn)中發(fā)現(xiàn)，最優(yōu)的三種SR方法仍是基于遺傳編程的，所以我們提出一種結(jié)合數(shù)據(jù)集特征的遺傳編程方法來(lái)解決SR問(wèn)題。
設(shè)計(jì)與實(shí)現(xiàn):
符號(hào)圖遺傳編程(SGGP)方法總體框架如圖1所示。首先，SGGP構(gòu)建一個(gè)符號(hào)圖，并在該圖中初始化種群（如圖1a所示）。然后，它利用語(yǔ)義算子生成新種群，具體操作如下：（1）計(jì)算極值分布：語(yǔ)義算子通過(guò)估計(jì)個(gè)體的語(yǔ)義相似度（如圖1b所示）來(lái)計(jì)算每條邊上的極值分布（如圖1c所示）；（2）采樣新個(gè)體：根據(jù)計(jì)算出的極值分布，語(yǔ)義算子對(duì)新個(gè)體采樣（如圖1d所示）。
圖1 符號(hào)圖遺傳編程(SGGP)
實(shí)驗(yàn)結(jié)果及分析:
在FSRB、Strogatz和PMLB數(shù)據(jù)集上的對(duì)比實(shí)驗(yàn)表明，SGGP在
、恢復(fù)率和模型大小方面都明顯優(yōu)于其他算法。
圖2 FSRB和Strogatz的實(shí)驗(yàn)結(jié)果
（a）
Test （b）Model Size
圖3 PMLB的實(shí)驗(yàn)結(jié)果
（a）FSRB和Strogatz （b）PMLB
圖4 
和模型大小的帕累托前沿圖
SGGP的突出性能主要?dú)w功于語(yǔ)義算子。該算子能夠利用個(gè)體語(yǔ)義相似度和極值分布來(lái)指導(dǎo)SGGP搜索。這種方法能夠提高搜索效率，使SGGP能夠更快地找到最優(yōu)解。
圖5 數(shù)據(jù)集“
”收斂性比較。虛線表示每種算法運(yùn)行10次的平均適應(yīng)度。藍(lán)色實(shí)線是SGGP運(yùn)行的結(jié)果之一。桑基圖a、b和c表示符號(hào)圖中邊的概率。
結(jié)論:
本文設(shè)計(jì)了一種新的符號(hào)圖，用來(lái)描述符號(hào)回歸的表達(dá)式空間。在符號(hào)圖的基礎(chǔ)上，我們提出了一種新的遺傳編程方法——符號(hào)圖遺傳編程（SGGP）。SGGP采用極值分布以及語(yǔ)義相似度來(lái)計(jì)算符號(hào)圖中每條邊的概率。然后，它基于這些概率對(duì)新個(gè)體進(jìn)行采樣來(lái)有效搜索正確的表達(dá)式。實(shí)驗(yàn)表明，SGGP優(yōu)于21種符號(hào)回歸方法，其中包括最新的機(jī)器學(xué)習(xí)/深度學(xué)習(xí)方法和演化計(jì)算方法。
通訊作者簡(jiǎn)介:
魯強(qiáng)，副教授，博士生導(dǎo)師。目前主要從事演化計(jì)算和符號(hào)回歸、知識(shí)圖譜與智能問(wèn)答、以及軌跡分析與挖掘等方面的研究工作。
聯(lián)系方式：luqiang@cup.edu.cn