The automatic generation of computer programs is one of the main applications with practical relevance in the field of evolutionary computation. With program synthesis techniques not only software developers could be supported in their everyday work but even users without any programming knowledge could be empowered to automate repetitive tasks and implement their own new functionality. In recent years, many novel program synthesis approaches based on evolutionary algorithms have been proposed and evaluated on common benchmark problems. Therefore, we identify in this work the relevant evolutionary program synthesis approaches and provide an in-depth analysis of their performance. The most influential approaches we identify are stack-based, grammar-guided, as well as linear genetic programming. Further, we find that these approaches perform well on benchmark problems if there is a simple mapping from the given input to the correct output. On problems where this mapping is complex, e.g., if the problem consists of several sub-problems or requires iteration/recursion for a correct solution, results tend to be worse. Consequently, for future work, we encourage researchers not only to use a program's output for assessing the quality of a solution but also the way towards a solution (e.g., correctly solved sub-problems).
翻译:自动生成计算机程序是进化计算领域具有实际相关性的主要应用之一。由于程序合成技术不仅可以在日常工作中得到软件开发者的支持,而且即使没有编程知识的用户也可以被授权将重复性任务自动化并实施自己的新功能。近年来,提出了许多基于进化算法的新的程序合成方法,并对共同的基准问题进行了评估。因此,我们在此工作中确定了相关的进化方案合成方法,并深入分析了这些方法的绩效。我们发现,最有影响力的方法是堆叠式的、语法制的以及线性基因编程。此外,我们发现,如果从给定的输入到正确的输出,有了简单的绘图,这些方法在基准问题上效果良好。关于这种绘图的复杂性,例如,如果问题包括几个子问题,或者需要反复/反复解决,结果往往更差。因此,我们鼓励研究人员不仅使用程序的产出来评估解决方案的质量,而且还要找到解决办法(例如,正确解决子问题)。