遗传编程（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 作为分母。
