2014，TEVC( 五 ) _语义

我们认为，即使从非最优的程序中也可以得到有用的子任务候选。考虑一个进化过程的种群(或任何其他增量搜索算法) 。在这样的种群中很可能有些程序包含了发生在所寻求的最优程序中的指令子序列。特别地，一些这样的 “正确” 子序列可能构成程序的后缀。这里值得注意的是，早期关于语义GP的研究，特别是 Mc Phee 等[9]强调了识别正确程序后缀的重要性。
设p p p 是一个具有正确后缀的程序，即一个后缀是最优程序p ? p^* p? 的一部分，即p = [ p ( 1 ) p ( 2 ) ? ] p = [p_{(1)}p^*_{(2)}] p=[p(1)?p(2)??] .假设我们可以反演p ( 2 ) ? p^*_{(2)} p(2)?? 的执行，即直接计算任意子目标5t ′′ t^{′′} t′′ 使得s ( [ t ′′ p ( 2 ) ? ] ) = t s([t^{′′}p^*_{(2)}] ) = t s([t′′p(2)??])=t .然后，t ′′ t^{′′} t′′ 将定义一个子任务，由于上面给出的原因，该子任务更容易求解。
在下一节中提出的语义反向传播是寻找此类子任务的有效启发式。
B.
语义反向传播算法找到给定目标的子目标和所表示一个树形程序的后缀，为了达到这个目的，它将后缀的执行反转为目标指定的期望输出。
由于一般情况下可能存在无穷多个子目标t ′′ t^{′′} t′′，使得s ( [ t ′′ p ( 2 ) ? ] ) = t s([t^{′′}p^*_{(2)}] ) = t s([t′′p(2)??])=t，因此算法并不能保证确定所有子目标，而只能确定其中的一个子集。为了有效地表示这样的子集，我们使用期望的语义 ( )
定义 4 规划任务t t t 和后缀p ( 2 ) p_{(2)} p(2)? 的期望语义是对应于t t t 的特定成分的集合D i D_i Di? 的元组D = ( D i ) D = ( D_i ) D=(Di?)，其中每个D i D_i Di? 包含由后缀p ( 2 ) p_{(2)} p(2)? 定义的第i i i 个适应度情形的期望值，即：
换句话说，D i D_i Di? 包含一组值x x x，使得后缀在第i i i 个适应度案例 ( case)上到达目标。这些值构成了由p ( 2 ) p_{(2)} p(2)? 定义的子目标对t t t 的第i i i 个case 的期望输出。D i D_i Di? 可以包含满足等式 3 的任意一组这样的输出, 不一定全部。
算法 1 给出了 ION 过程，该过程启发式地计算由给定后缀确定的期望语义。虽然求逆过程只需要程序后缀，但为了方便起见，我们假设程序的参数为程序树p p p 和该树中的节点n n n 。节点n n n 明确标识后缀(见图 1) 。
对于给定的目标t，ION ( t , p , n ) t，\text{ION}( t , p , n) t，ION(t,p,n) 计算与由p p p 和n n n 决定的后缀相关的期望语义。对于每个caset i t_i ti? 独立地对路径上的节点进行从p p p 到n n n 的遍历。它首先通过位于根节点的指令传播原始目标的第i i i 个分量t i t_i ti? 。路径上连续指令的反转由线路 5-11 中的循环进行。对于工作集 ( set) 中的每一个o o o 的期望值D i D_i Di?，调用函数确定当前节点a a a 的第k k k 个子节点的期望值，其中该子节点为路径上的下一个节点。
我们用一个例子来说明这个过程，其中 ION 用于目标t = [ ? 2 , 0 , 0 ] t=[ - 2, 0, 0] t=[?2,0,0]，程序p p p 如图 1 所示，n n n 是用蓝色标记的节点。p p p 中子树的语义用黑框表示。考虑第一种适应度情形，期望输出为? 2 -2 ?2 .算法从根节点开始。由于n n n 在根的右子树中，因此算法将为根指令 (‘-’) 的右参数确定集合D 1 D_1 D1? 。目前，该节点计算1 ? ( ? 1 ) = 2 1 - ( -1 ) = 2 1?(?1)=2 。该算法试图找出正确参数 (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) 成为后续步骤反向传播 (指令× × ×) 的起点。