遺傳編程（GP）屬於進化計算（Evolutionary Computation，EC）模型的一種。EC是一種借鑑自然界進化機制而產生的並行隨機搜尋算法。進化算法的基本原理是選擇和改變，它區別於其他搜尋方法有兩個顯著特徵：首先這些算法都是基於種群（population）的；其次在種群中個體（indvidual）之間存在競爭。 為搜尋特定的（感興趣的）查詢需要一種工具，這種工具可智慧型生成一組查詢並以它們是否能導出與用戶給定的同樣的對象集來進行評價。GP算法對這一類問題是很實用的。
基本介紹
- 中文名：GP算法
- 外文名：Evolutionary Computation
- 基於：種群
- 屬性：競爭
與端點集,初始種群,選擇屬性值,新一代種群,評價,
與端點集
一般GP中可生成的程式集是使用者定義的函式集和端點集。表1給出了相應的函式集和端點集，其中函式集由1.3中定義的查詢運算元、邏輯運算運算元以及比較運算元所組成。
函式集 {SEL，REL，G-REL，RES}，{UNI，INT，DIF}，{AND，OR，NOT}， {>，>=，=，<，<=} 端點集類集，屬性集，值集
表1 函式集和端點集
在我們的套用中還有一些具有不同句法的查詢運算元。每個運算元具有不同的句法且假定的資料庫是面向對象的。因此，它具有為創建個體而使用的特別的函式集（或運算元集）和端點集。從而，構成種群的所有個體的創建必然受到每個運算元的約束[3]。約束可以是運算元的句法和查詢的類型，或者是為創建查詢選擇適當屬性值的領域知識。比較運算元和邏輯運算元只使用於查詢的謂詞。當比較符號運算元時，僅使用'='。
端點集由CLASS-SET、SLOT-SET和VALUE-SET組成。CLASS-SET由1.2中定義的類名組成，SLOT-SET由每個類的所有屬性構成，VALUE-SET由數值和符號值所構成（它們均為屬性值）。數值由整型或實型數構成，其數值範圍由所用資料庫模式定義。符號值由字元串表示的符號屬性值構成。
初始種群
為了創建一個個體（查詢），首先必須確定特定查詢所返回的對象類型。結果類型被選擇後，從所選類型返回例子的運算元集中隨機地選擇一個運算元，這個過程對查詢的每個參數遞歸地進行。最初，那些句法正確的預定義數量的查詢被隨機地產生，形成初始種群。
選擇屬性值
由於可選擇範圍大，要從某個查詢的值集中選擇一個屬性值（數值或符號常數）是相當困難的。對於一個範圍為[1，10000]的整數集，隨機選到一個特定整數的機率僅為1/10000。而對於符號常數，則需要很強的背景知識。因此，我們僅就發生在資料庫里的範圍選擇屬性值。
新一代種群
每個個體用預定義的適應函式來進行評價。較適應的查詢有較高的機率被選來繁殖新種群，這個過程用三個遺傳運算元：選擇、雜交和變異來完成。為了產生下一代，選擇運算元根據個體的適應值來選擇個體。我們用一個樹來表示一個查詢，雜交運算元用交換兩個父輩的子樹來創建兩個後代。變異運算元用一個新的子樹來代替一個父輩的子樹，從而產生一個新的後代。選擇-雜交-變異循環反覆地進行直到終止標準被滿足。
評價
我們使用如下的適應函式f來評價種群中的個體查詢i ：
f ( ni , hi ) = T - ( hi * hi ) / ni ,
其中：ni > 0 ， T ≥ hi ， 且 i = 1 ，2 ，… ，種群的大小（T是被確定的對象集的勢，hi是一個個體查詢i 被選中的次數，ni是查詢 i 結果集的勢）。
上述適應函式依賴於hi和ni ，如果一個查詢沒有被選中（hi=0），則函式的值為T，這是最差的一個適應值。另一方面，如果查詢結果能夠很好地匹配提交給系統的對象集，那么它的適應值為0（在這種情況下hi = ni = T ）。如果種群中出現個體適應值遠遠超過種群平均適應值，該個體很快就會在群體中占有絕對的比例，從而出現過早收斂的現象。另一方面，在搜尋過程的後期，群體的平均適應值可能會接近群體的最優適應值，從而導致搜尋目標難以得到改善，出現停滯現象[4]。為了防止上述情況的發生，我們將對一個個體查詢的例子個數 ni 作為分母。
