Efficient Exhaustive Generation of Functional Programs Using Monte-Carlo Search with Iterative Deepening
Efficient Exhaustive Generation of Functional Programs Using Monte-Carlo Search with Iterative Deepening
复制标题
使用蒙特卡罗搜索和迭代深化高效详尽地生成函数程序
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Susumu Katayama
中科院分区：
文献类型：
--
作者：
Susumu Katayama
函数程序的遗传编程和归纳综合是归纳函数编程的两种主要方法。最近，除了它们之外，一些研究人员追求高效的穷举程序生成算法，部分是为了提供比较器并了解这些主要方法所采用的启发式等思想的重要性，部分是期望穷举生成给定类型的程序并选择满足给定规范的程序的方法可以很好地完成任务。在穷举程序生成中，由于程序数量随着程序大小的增加而呈指数级增长，因此成功的关键是如何通过抑制语义等效但语法不同的程序来抑制指数膨胀。在本文中，我们提出了一种对迭代深化的搜索结果应用程序等价性随机测试（或蒙特卡洛搜索功能差异）的算法，通过该算法可以完全消除语义等价程序引起的冗余。我们的实验结果表明，在程序生成过程中将我们的算法应用于子表达式可以显着降低应用于丰富的基元集时的计算成本。
Genetic programming and inductive synthesis of functional programs are two major approaches to inductive functional programming. Recently, in addition to them, some researchers pursue efficient exhaustive program generation algorithms, partly for the purpose of providing a comparator and knowing how essential the ideas such as heuristics adopted by those major approaches are, partly expecting that approaches that exhaustively generate programs with the given type and pick up those which satisfy the given specification may do the task well. In exhaustive program generation, since the number of programs exponentially increases as the program size increases, the key to success is how to restrain the exponential bloat by suppressing semantically equivalent but syntactically different programs. In this paper we propose an algorithm applying random testing of program equivalences (or Monte-Carlo search for functional differences) to the search results of iterative deepening, by which we can totally remove redundancies caused by semantically equivalent programs. Our experimental results show that applying our algorithm to subexpressions during program generation remarkably reduces the computational costs when applied to rich primitive sets.