2014，TEVC( 十 ) _语义

在本文中，我们考虑到程序反转 () 的模糊性和一对多的性质是一个挑战，因为它可能导致从原始目标(甚至对于 sin 这样的周期函数有无穷多个子目标)衍生出指数级的许多子目标。然而，这个问题存在着另一面。子任务的理想解是从期望的语义返回任意期望输出组合的程序11 ,一般来说，找到这样的程序比找到一个产生特定输出组合的程序要容易，这在解决具有单一原始目标的原始问题时是如此。这是语义反向传播的一个有趣的方面，值得未来的研究。
更一般地说，语义反向传播使用种群中程序的后缀生成一个不同的任务，该任务预期比原始编程任务更容易解决。为了解决派生的子任务，我们在这里使用了一个库中的穷举搜索，主要是因为它在概念上是简单和合理的快速，特别是对于小型库。其他搜索算法，如GP，也可用于此目的。考虑到GP的搜索空间远大于所考虑库的规模，GP有可能找到比更好的程序。
然而，将大量的计算精力投入到求解任一子任务上都存在一定的风险。一个子任务可以但不能保证比原始任务更容易解决。在最坏的情况下，它可能在所考虑的搜索空间中没有解。因此，本文提出的算法不是指定单个子任务(或其小样本)并投入大量的搜索精力进行求解，而是尝试在有限的库中通过穷举搜索的方式求解大量子任务(每个由 RDO/AGX 应用于父代个体产生 (s) ) 。考虑的子任务数量和致力于解决它们的计算工作量之间的权衡类似于著名的多臂强盗范式 (multi-armed)，是一个有趣的未来研究课题。
当应用于程序时，RDO临时冻结其后缀并操作其前缀，使修改后的前缀尽可能接近后缀的"期望" (期望的语义) 。一个假想的替代搜索算子可以交换前缀和后缀的角色，并在操作后缀的同时冻结前缀。然而，这至少有一个实际的缺点：必须执行整个修改后的程序来计算其适应度。在RDO中，库中的程序可以被预先计算，因为它们的行为只依赖于由适应度案例提供的程序输入，而适应度案例随编程任务而来并保持不变。
RDO和AGX的总体计算成本高于常规GP算子。主要原因是库的搜索，这可能需要大量的时间，特别是当应用于大型库。在我们之前的研究中 [18]，我们使用 kd-tree [35] 来加速搜索。然而，这种索引结构只能在所寻求的对象是单个数字向量(一个点)的情况下使用，而我们想要的语义一般代表一组点。为了满足这一要求，需要对传统的索引技术进行扩展，使这些搜索算子更加高效。其次，影响RDO和AGX计算成本的次要因素是树的大小。与标准GP类似，由RDO和AGX构建的程序往往随着进化时间的推移而增长，我们在第VI-E 节中报告了这一点。我们假设这个问题可以通过使用通用的膨胀预防技术来解决，例如那些采用空间种群结构 () [36]
VIII.
我们证明了程序执行的反转 () 可以从原始的编程任务中生成子任务，并且这些子任务可以在受约束的程序集(库)中使用穷举搜索来解决。尽管由于指令的多对一操作，程序反转本质上是不完美的，但使用这种方法的两个GP搜索算子优于标准GP和其他语义感知算子。从概念上讲，这种工作原理可以应用在其他领域和编程语言中。因此，程序反演是使包括GP算法在内的自动编程算法具备问题分解能力的可行途径
T P,B,K.forin[J]. IEEEon, 2014, 19(3): 326-340.
算法原理梳理语义反向传播，SB
算法 1 中函数和参数说明：
ION ( t , p , n ) (t, p, n) (t,p,n)：用于计算从程序树p p p 到节点n n n 的期望语义
Pos ( a , n ) (a, n) (a,n)：返回子程序树a a a 从根节点到节点n n n 路径中，a a a 根节点所对应的参数的个数k k k