APP下载

多表达式程序设计的新型评估方法*

2015-07-10郑秋生

计算机工程与科学 2015年2期

郑秋生,何 锫,2,3,李 骥

(1.长沙理工大学计算机与通信工程学院,湖南 长沙 410114;2.广州大学计算机科学与教育软件学院,广东 广州 510006;3.北京大学高可信软件技术教育部重点实验室,北京 100871)

1 引言

遗传程序设计GP(Genetic Programming)[1]是重要的自动程序设计方法,包括线性与非线性表示两类。多表达式程序设计MEP(Multi Expression Programming)、基因表达式程序设计GEP(Gene Expression Programming)、文法演化GE(Grammatical Evolution)以及Hoare语义型遗传程序设计等都是线性表达的遗传程序设计方法[2~9],它们在多目标优化、金融预测、海量数据分析、软件工程、信息安全等领域都得到了广泛的应用[6, 10]。

与传统GP相比较,MEP等线性表达的GP(某些文献也将线性表达的GP简称为线性GP)既便于个体表示、遗传操作,又易于描述复杂结构和实现,因此自提出以来一直很受关注。然而一切GP都以遗传算法[11]为基础,因而转换、评估工作十分繁复,除要将个体的树型/线性表示方式转换成相应的表现型外,还要执行、测试所得的近似解以确认它的合适程度。如此一来,评估(某些语义计算甚至一个小小的步骤就得耗费数十小时以上)等的计算耗费了大量的时空资源,成为GP研究的挑战性问题[12]。

本文拟就评估问题对MEP做深入探讨。先系统化分析它的表示、评估过程中重复计算现象的根源所在,而后给出规避这些问题的理论依据、实际解决方案。因无须重复计算相同的语义工作,新方法在演化效率上有了显著提高。

2 背景和相关工作

多表达式程序设计[3,6,9]作为线性表达的遗传程序设计方法,主要通过将搜索目标分为基因型与表现型两个层面来规范求解过程。……

登录APP查看全文