2014，TEVC(11) _语义

( a , k , o ) (a, k, o) (a,k,o)：通过程序树a a a 的根节点运算符，以及期望语义o o o, 和参数个数k k k，进行反转计算
CHILD ( a , n ) (a, n) (a,n)：返回从当前子树a a a 的根节点到节点n n n 路径的下一个新子树。
通过图 1 对算法 1 中的原理进行介绍：
首先执行算法将第一个t i t_i ti? 赋值给D i D_i Di?, 即D 1 = { ? 2 , 0 , 0 } D_1 = \{-2, 0, 0\} D1?={?2,0,0}，并将程序树p p p 赋值给a a a, 通过 while 循环，计算从程序树a a a 的根节点到节点n n n 路径上所有节点的期望语义，首先通过 Pos ( a , n ) (a, n) (a,n) 返回a a a 的根节点运算符对应的参数个数给k k k，并初始化D ′ D^{'} D′ 为空，用于存储待计算节点的期望语义，for 循环通过遍历D i D_i Di? 中的目标语义，从而反转计算目标节点的期望语义。比如：开始时D 1 D_1 D1? 中提取期望语义的第一个元素 -2, 此时根节点为 ‘-’，即按照二叉树的 GP，为左右两颗子树的语义进行相减从而计算出当前根节点沿路径下一个节点的期望语义，计算完成后，将语义存储到D ′ D^{'} D′ 中，并赋值给D i D_i Di?, 使得计算出的期望语义对应的节点成为一个新的根节点，通过 CHILD ( a , n ) (a, n) (a,n)，更新子树a a a, 再以当前根节点计算下一个节点的期望语义，如图 1 中的 “第二个根节点” 运算符为 ‘×’，左子树乘以右子树等于根节点的期望语义，同理已知左子树语义，根节点语义，可以反求出右子树语义。
我们用一个例子来说明反演这个过程，其中 ION 用于目标t = [ ? 2 , 0 , 0 ] t=[ - 2, 0, 0] t=[?2,0,0]，程序p p p 如图 1 所示，n n n 是用蓝色标记的节点。p p p 中子树的语义用黑框表示。首先考虑t t t 中的第一个元素 (即case 的第一个位置元素)，期望输出为? 2 -2 ?2 . 算法从根节点开始。由于待计算的目标节点n n n 在根的右子树中，因此算法将为根指令 (‘-’) 的右参数确定集合D 1 D_1 D1? 。利用计算根节点右子树第一个节点的期望值，图 1 所示，( c 1 ? c 2 , 2 , o ) ( c_1-c_2 , 2 , o) (c1??c2?,2,o)，其中c 1 c_1 c1? 表示当前根节点左子树目标语义的第一个元素值，c 2 c_2 c2? 表示当前根节点右子树目标语义的第一个元素值，目标是为了求出c 2 c_2 c2?, 而存在关系c 1 ? c 2 = o c_1 - c_2 = o c1??c2?=o, 在图 1 中c 1 = 1 c_1 = 1 c1?=1 和o = ? 2 o = - 2 o=?2 上运行。
根据表 I 的第二行返回( 1 ? c 2 , 2 , ? 2 ) ( 1-c_2 , 2 , -2) (1?c2?,2,?2)，即c 2 = c 1 ? o = 1 ? ( ? 2 ) = 3 c_2 = c_1 - o = 1- ( - 2 ) = 3 c2?=c1??o=1?(?2)=3 。该算法试图找出正确参数 (x) 的值应该是多少才能使结果满足目标? 2 -2 ?2，即1 ? x = ? 2 1 - x = - 2 1?x=?2 。这可以通过反演计算得到，因此算法以x = 1 ? ( ? 2 ) = 3 x = 1- ( -2 ) = 3 x=1?(?2)=3 结束。该值成为向根节点(蓝色虚线框)的右子节点传播的期望语义的第一个元素，与其余两个适应度情况独立计算的值一起。产生的期望语义( 3 , 2 , 3 ) ( 3,2,3) (3,2,3) 成为后续步骤反向传播 (指令× × ×) 的起点。
，RDO
在父程序p p p 中首先选择一个随机节点n n n 。接下来，ION 确定与所选节点相关的期望语义D D D 。D D D 存储一组子目标，从而定义一个编程子任务。第 4 行通过调用V-D 中描述的( L , D ) (L, D) (L,D) 来求解子任务。( L , D ) ( L,D) (L,D) 从库中返回一个与所采用的度量最接近所需语义D D D 的程序。由于库的规模有限，无法保证实际求解子问题D D D，即在L L L 中找到与D D D 完全匹配的程序。
在这种情况下，RDO 不检查D D D 是否包含空集，也会对库进行搜索。这可能看起来是徒劳的，因为没有程序(无论是否来自库)能够完美匹配这样的D D D 。但在这种情况下，将在其他case 下找到与D D D 尽可能匹配的程序p ′ p^{′} p′，RDO 将其粘贴到子代中。在非匹配的适合度情况下的行为有望通过后续几代的 RDO 突变来固定。