数据挖掘技术是当前计算机技术的研究热点之一。当前的数据挖掘研究主要在命题逻辑的框架内，存在描述能力弱和不便于利用背景知识的局限性。而且，这些方法多采用了单表假设，算法寻找单表数据中的模式。但数据通常保存在关系数据库的多张表中，若想利用现有的数据挖掘算法，存在将数据转换到单表中的难题。 基于一阶逻辑的一阶规则挖掘技术常被称作归纳逻辑程序设计(ILP)。一阶逻辑为ILP提供了一致的和非常有表达力的表示手段：背景知识、例子以及挖掘到的知识都可表示为子句语言的公式，所以在挖掘过程中可非常自然地利用背景知识。另外得到的知识表示为相关谓词构成的一阶规则，比命题规则具有更强的表达能力，使知识的内涵更加丰富并易于人们理解。因此，ILP可克服传统命题规则挖掘方法的两个主要限制：描述能力的限制与背景知识利用的限制。此外，由于关系数据库的形式描述—“关系代数”与ILP的子句逻辑有着内在的关联性，ILP技术可被直接用于涉及关系数据库中多个关系(表)的数据挖掘任务。 一阶规则挖掘可看作是对一阶规则空间的搜索。由于一阶规则空间的庞大和复杂性，为了实现有效的搜索，绝大多数一阶规则挖掘系统采用了贪婪的搜索策略，并需要对具体问题给出极其严格的语言偏向(即挖掘过程中待测规则构成的特征描述)来缩小搜索的范围或作为启发知识来指导搜索过程。贪婪的搜索策略可能使算法陷于局部优解，语言偏向的添加也只对与其相适的目标规则的搜索有良好的效果，不适于数据挖掘这种目标规则构成先验知识少的任务环境。 遗传算法是模拟生物进化机制而发展起来的随机化搜索算法。算法根据概率的变迁规则来指导搜索方向，利用演化过程中获得和积累的有关搜索空间的信息自行组织搜索，并自适应地控制搜索过程，基本上不用搜索空间的知识或其它的辅助信息，对问题本身没有过多的要求，适于数据挖掘的任务环境。遗传算法采用群体搜索策略，具有较好的全局搜索性能，减少了陷于局部优解的风险。因此，采用遗传算法作为ILP的搜索策略，可从整体上提高一阶规则挖掘方法的鲁棒性和适应性，解决一阶规则获取的性能瓶颈问题。 本论文主要开展了遗传归纳逻辑程序设计技术的初步研究。用遗传算法挖掘一阶规则依赖于两个因素：遗传空间的“地貌”和在遗传空间中的“航行”。两者分别反映了算法的静态和动态特性。遗传空间的“地貌”体现了算法的静态特性，它与以下三者相关：(1)把一阶规则表示成遗传算子可操作形式的编码。依据给定的编码，所有待搜索的一阶规则被映射为遗传空间相应的点。(2)评判一阶规则优劣的适应度函数，一阶规则适应度的相应变化形成了遗传空间高低起伏的地貌特征；(3)由交叉和变异算子决定的规则间的邻接关系，描述了遗传空间地貌的沟壑或桥梁。在遗传空间的“航行”则体现了算法的动态特性，是种群在选择，交叉以及变异算子的作用下逐渐逼近最优解的过程。本论文重点研究了遗传归纳逻辑程序设计技术中的一阶规则编码，遗传算子的设计，选择策略及算法结构 北京工业大学工学博士学位论文一等关键技术。此外，我们还对自己提出的GILP算法运行中的个体编码生长现象进行了研究，并在对一阶规则挖掘中的等价类问题的研究基础上，提出了基于信息赢取的适应度函数。最后，基于研究成果，开发了GILP系统并进行了挖掘工作。主要研究成果和创新点如下： 门）在认识到一阶规则挖掘实质上是目标谓词和背景知识谓词构成的各种原子的组合优化问题基础上，我们依据occam’s razor原理，提出了符合最小字符集编码原则的一阶规则位串编码。该编码仅需用户在付出的计算代价和获取知识复杂度（规则中可能出现的相异变量的序号上界）之间作权衡，不需给出描述了待测规则构成特征的语言偏向，适于数据挖掘这种目标规则构成先验知识少的任务环境。为我们提出的位串编码设计了符合一阶规则语法约束的遗传算子。提出了基于覆盖删除策略的遗传归纳逻辑程序设计算法GILP。 门）通过对变长位串编码作模式分析，初步解释了GILP运行过程中的个体编码生长现象。并发现，若简单地从初始种群开始，在适应度中添加长度惩罚项解决生长问题时，种群会出现退化现象。为此，提出了基于演化周期的惩罚策略，既避兔了种群退化，又有效抑止了个体编码的生长。 （3）用遗传算法有效地搜索一阶规则的关键在于如何准确地评价一阶规则，即规则的适应度能有效地量化规则的优劣，指导算法逼近最忧解。在ILP技术通常采用的基于规则覆盖正负例数目的评价标准中，存在一阶规则的等价类问题。等价类问题使GILP的遗传搜索过程盲目地倾向于长规则，将严重地降低算法的搜索效率和规则的可读性。我们在绑定概念的基础上，依据信息理论，提出了基于信息赢取的适应度函数。分析和对比实验表明，新的适应度函数可区分一阶等价规则的优劣，更好地指导算法的搜索方向。 （4）我们实验了选择策略对GILP收敛性能的影响，提出了采用竞赛规模动态改变的锦标赛选择策略，来解决遗传?