GP演算法
❶ GP演算法的與端點集
一般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由數值和符號值所構成（它們均為屬性值）。數值由整型或實型數構成，其數值范圍由所用資料庫模式定義。符號值由字元串表示的符號屬性值構成。
❷ 什麼是G-p演算法
遺傳編程（GP）屬於進化計算（Evolutionary Computation，EC）模型的一種。EC是一種借鑒自然界進化機制而產生的並行隨機搜索演算法。進化演算法的基本原理是選擇和改變，它區別於其他搜索方法有兩個顯著特徵：首先這些演算法都是基於種群（population）的；其次在種群中個體（indvial）之間存在競爭。 為搜索特定的（感興趣的）查詢需要一種工具，這種工具可智能生成一組查詢並以它們是否能導出與用戶給定的同樣的對象集來進行評價。GP演算法對這一類問題是很實用的。
1 函數集與端點集
一般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由數值和符號值所構成（它們均為屬性值）。數值由整型或實型數構成，其數值范圍由所用資料庫模式定義。符號值由字元串表示的符號屬性值構成。
[編輯本段]
2 創建初始種群
為了創建一個個體（查詢），首先必須確定特定查詢所返回的對象類型。結果類型被選擇後，從所選類型返回例子的運算元集中隨機地選擇一個運算元，這個過程對查詢的每個參數遞歸地進行。最初，那些句法正確的預定義數量的查詢被隨機地產生，形成初始種群。
[編輯本段]
3 選擇屬性值
由於可選擇范圍大，要從某個查詢的值集中選擇一個屬性值（數值或符號常數）是相當困難的。對於一個范圍為[1，10000]的整數集，隨機選到一個特定整數的概率僅為1/10000。而對於符號常數，則需要很強的背景知識。因此，我們僅就發生在資料庫里的范圍選擇屬性值。
[編輯本段]
4 繁殖新一代種群
每個個體用預定義的適應函數來進行評價。較適應的查詢有較高的概率被選來繁殖新種群，這個過程用三個遺傳運算元：選擇、雜交和變異來完成。為了產生下一代，選擇運算元根據個體的適應值來選擇個體。我們用一個樹來表示一個查詢，雜交運算元用交換兩個父輩的子樹來創建兩個後代。變異運算元用一個新的子樹來代替一個父輩的子樹，從而產生一個新的後代。選擇-雜交-變異循環反復地進行直到終止標准被滿足。
[編輯本段]
5 評價（適應函數測量）
我們使用如下的適應函數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 作為分母。