程序演化是根据某些法则从一个程序生成另一个新的程序,这两个程序在语义上是等价的,通过一系列保证正确性的对源程序的演化,进行算法和数据结构的求精,最终将源程序演化成一个面向过程的、高效的程序文本。程序演化思想的出现,使得程序优化工作耳目一新,可有效的提高程序执行的效率。对决策树算法的优化问题,一直是一个倍受关注的领域。当今,国内外不少研究人员致力于对决策树的优化工作,针对决策树容易过度拟合、规模过大、产生的规则过长等缺点,研究人员提出了不少优化方法,并取得了比较好的效果。本文在总结已有成果的基础上,在决策树的优化问题中,引入程序演化的思想,以期得到具有更高效率的决策树。围绕该问题展开以下工作:(1)用Homomorphisms递归结构描述ID3算法。为演化出新的高效程序奠定基础。(2)在对程序的规范化描述进行认真分析的基础上,研究选择合理的演化规则和演化策略。(3)运用tupling策略定义新的数据结构,基于这种数据结构进行演化,运用接点提升算法,最终演化得到新的决策树构造算法,该算法构造决策树只需要扫描一次数据集合。(4)对本文演化所得的新决策树算法的时间有效性进行分析,并用Haskell函数式语言编程实现相关算法,对算法的正确性和有效性进行验证。