2014，TEVC _语义_甘肃龙网

在遗传规划中，搜索算法(交叉，变异)期望产生最终计算状态的程序(期望输出) 。为了达到该状态，执行程序需要遍历某些中间计算状态。一个进化搜索过程被期望能够自主发现这样的状态。这对于需要长时间程序才能解决的tasks 来说可能是困难的。本文提出的语义反向传播算法通过启发式地反转演化程序（theof）的执行来确定所需的中间计算状态。两个搜索算子，随机期望算子 (, RDO) 和近似几何语义交叉 (, AGX)，使用语义反向传播确定的中间状态定义原始编程任务的子任务，然后使用穷举搜索求解。该算子在一组符号回归和布尔基准 ( ) 上的表现优于标准遗传搜索算子和其他语义感知算子。该结果和本研究中进行的额外分析表明，语义反向传播有助于进化识别所需的中间计算状态，并使搜索过程更有效。
I.
自动编程任务中的目标是合成一个表现出某种期望行为的程序。期望行为通常通过将期望的程序输出指定为程序输入的函数来定义。这可以通过显式地枚举所有相关的输入输出对(或其样品)来实现，也可以通过隐式地定义程序响应必须优化的目标来实现。
【2014，TEVC】除了平凡的情况 ( cases) 外，通过对输入数据施加单一的指令无法实现期望的输入输出行为。根据编程范式的不同，指令的组合是必要的：序列、树或图。指令(语法)的组合以复杂的方式决定程序行为(语义) 。这种特性被称为适应度景观的鲁棒性 [1] 或低因果性 [2]，使得很难设计出与任务复杂度相匹配的自动编程算法。
解决编程任务的一个简便的方法是将它们作为搜索问题：一个搜索算法运行程序，观察它们的行为，并使用这些信息来指导搜索过程。在遗传编程(，GP )中，这个过程涉及到生物启发的变异和选择机制，以及一个适应度函数，它量化了实际程序输出与期望输出(下面的目标)的匹配程度。
在传统的GP中，适应度只取决于程序执行的最终效果；中间效应，如程序树的子树计算的值，或线性GP中寄存器的瞬态，均被忽略。这种选择性是被普遍接受的：最终，只有最终的结果决定了编程任务是否得到了解决。然而，这与程序员所行使的编程过程形成了鲜明对比。当面临非平凡任务 ( task) 时，程序员将其拆分为子任务，并试图独立或半独立地解决。这种策略往往被证明是有效的，因为程序员往往事先知道哪些中间执行状态是期望的，哪些不是。例如，对于一个编程任务 “设计一个算法来计算一个数字数组的中位数”，这样一个期望的中间值是按升序或降序排序的输入数组。
分解任务的能力使程序员能够在自动编程方法仍然难以解决的任务上出类拔萃。因此，我们非常希望GP算法具有类似的能力，我们在之前的研究 [3]，[4]，[5]中假设了这一点。
在本文中，我们提出了一种在求解给定的编程任务时确定哪些中间计算状态是可取的方法。该方法利用了程序执行可以在一定程度上反转的事实：对于任意计算状态(例如,工作记忆或其他执行环境的状态)，通过执行单个指令可以实现的其他状态的数量是有限的(虽然潜在的大) 。因此，可以还原对给定输出执行指令序列的影响(尽管在某些情况下模棱两可) 。这种语义反向传播的过程允许我们确定一个期望的中间记忆状态(子目标)，进而定义一个特定的编程子任务。求解子任务需要考虑的程序空间是原始搜索空间的一个子空间，因此可以更高效地进行搜索。
本文的主要贡献是演示了如何将这种思想(第三和第四节介绍了)用于变异和交叉算子(Sec.V) 。与我们最初提出这些算子的 [6]，[7] 相比，在这里我们给出了语义反向传播的一个广义版本，将搜索算子嵌入到一个通用的形式化框架中，并在广泛的基准上进行详细的检验 (Sec.VI) 。