基于遺傳程式設計(Genetic Programming)的符号回歸(Symbolic Regression)簡介

本學期加入了數學代數系統Mathumu協會的核心開發部。

Mathmu這個項目，簡單地說，就是開發清華人（中國人）自己的Mathematica。

以Mathematica為目标可能顯得有些不自量力。達到甚至超越Mathematica不可能是我們這幾十個學生在段時間内就能夠做到的，但誰知道呢？Linus Torvalds當初(1991)寫Linux的時候難道也預計到如今Linux得到如此廣泛的應用嗎？

我加入協會的第一項工作，結合了我自己的興趣和項目的願景，是為Mathmu開發一個基于遺傳程式設計(Genetic Programming)的符号回歸(Symbolic Regression)子產品。

這裡有兩個各位可能覺得陌生的術語：遺傳程式設計和符号回歸。

遺傳程式設計，簡而言之，就是讓計算機程式，像生物一樣，變異、交配、繁殖，最終演化成符合特定的需求的程式。

Wikiepedia是這樣介紹的：“In artificial intelligence, genetic programming (GP) is an evolutionary algorithm-based methodology inspired by biological evolution to find computer programs that perform a user-defined task. It is a specialization of genetic algorithms (GA) where each individual is a computer program. It is a machine learning technique used to optimize a population of computer programs according to a fitness landscape determined by a program's ability to perform a given computational task.”

符号回歸，是相對于“數值”回歸(Numerical Regression)而言的，即統計中的回歸分析，比如我們熟悉的線性回歸。回歸分析通常要首先假設問題所服從的函數的形式及其參數，然後根據資料求得最符合的一組參數，進而最終确定函數。可以看到，應用回歸分析的人員需要對問題領域有比較深入的了解，這樣才能給出一個“合理”的函數形式。而當問題很複雜或者研究人員對其認識程度有限時這往往是難以做到的。

這時符号回歸就可以派上用處了。符号回歸是遺傳程式設計最早的一類應用之一。符号回歸的終結符集合(terminal set)主要由運算符（比如+, -, *, /, sin, cos, log等等），随機數和變量（x0, x1, .., xn）組成。這裡，演化的程式就是一串終結符（代表函數y=f(x0, x1, x2, ..., xn)）。我們希望最終得到的程式，即y=f(x0, x1, ..., xn)，能夠盡量符合給定的資料集。注意，與回歸分析不同的是符号回歸完全沒有假定函數的形式，實際上，符号回歸（包括遺傳程式設計，甚至整個計算智能（Computational Intelligence）和演化計算（Evolutionary computing）領域）的目标就是全自動地發現知識、模式和規律。

參考文獻：

• A field guide to genetic programming：一本入門的書，09年新出，基本介紹之後總結了該領域20多年的主要進展、方向和應用。
• Genetic Programming系列：John Koza寫的，他是這個領域的鼻祖級人物，目前已經出版4本。

網絡資源：

• Symbolic Regression：A Overview：對符号回歸的一個簡短的介紹
• Example Run of Genetic Programming：John Koza書上的一個很好的例子，給你對遺傳程式設計的直覺感覺