2014，TEVC( 七 ) _语义

当 ION 沿着从树根到所选节点n n n ( 算法 1)的路径前进时，适应度景观的反向误差传播网络将继续。给定如图 2 (b) 所示的热图，我们可以对指令s i n sin sin 进行类似的计算，考虑这样的程序后缀 [sin cos] 。该后缀定义的子任务的适应度图如图 2 (c ) 所示。然而，这一次子目标没有从图 2 (b) 传播到图 2 (c )：全局最优解消失，因为? ? y ″ : c o s ( s i n ( y ″ ) ) = 0 \neg\ y^{″}:cos (sin(y^{″})) = 0 ??y″:cos(sin(y″))=0 。因此，没有一个形式为 [p p p sin cos] 的程序，其中p p p 是一个任意的子程序，可以作为这个编程任务的解决方案。
通过实例说明，子目标的数量可以随着后缀长度(图 2 (a) 中一个目标,图 2 (b) 中多个子目标)的增加而增加。这种增长可以是适应度案例 ( cases) 数量和后缀长度的指数函数。然而，期望语义通过独立存储每个case 的期望输出，可以以存储高效的方式捕获子目标；图 2 (b) 中的 16 个子目标只需要期望语义中的 8 个值： D = ( { ? 3 π 2 , ? π 2 , π 2 , 3 π 2 } , { ? 3 π 2 , ? π 2 , π 2 , 3 π 2 } ) D = ( \{\frac{-3π}{2} ,\frac{-π}{2} , \frac{π}{2} , \frac{3π}{2} \} , \{ \frac{-3π}{2} , \frac{-π}{2} , \frac{π}{2} , \frac{3π}{2} \}) D=({2?3π?,2?π?,2π?,23π?},{2?3π?,2?π?,2π?,23π?}) 。
从上面的例子中观察到的关键观察是语义反向传播改变了整个景观。给定一个语义位于图 2 (b) 中某处的程序p p p，通过修改该程序使其语义更接近于任一子目标，我们使得完整程序 [ p p p cos] 的语义接近于图 2 (a) 中的原始目标t t t 。这是设计使用语义反向传播的搜索算子的主要动机。
V.IN? A.
我们提出了两种采用语义反向传播的遗传搜索算子：一种可视为变异形式的一元随机期望算子 (RDO) 和近似几何语义交叉算子 (AGX) 。两者都是从父程序p p p 中选择一个随机节点n n n 开始的，将p p p 分为前缀和后缀。然后，他们调用 ION 来确定一个子任务。接下来，操作符试图通过对V-D 中描述的程序库的穷举搜索来解决子任务。通过这种方式找到的最佳程序替换p p p 中相应的前缀，产生子代。
RDO 和 AGX 的主要区别在于它们在反向误差传播网络过程中所设定的起始语义，即 ION ( t , p , n ) (t , p , n) (t,p,n) 调用中的参数t t t 。RDO 使用任务提供的原始目标。AGX 使用 “合成” 目标，因此可以应用于原始目标不明确的任务。
B.
随机期望算子 (RDO)，在 Alg.2 是我们在文献 [7] 中首次提出的，它遵循上述工作原理。在父程序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 突变来固定。
C.
RDO 以搜索过程的原始目标为期望目标，t t t 。这在那些期望的程序结果作为任务制定(我们对本文的这一点进行了假设,特别是在公式 2 中。)的一部分明确给出的领域中特别有用。符号回归和布尔函数合成的典型表述都属于这一类。
然而，存在目标不被搜索算法显式知道的任务，且适应度函数是只能针对特定程序进行查询的黑箱。例如，可能是目标包含机密信息而无法向实验者透露。