2014，TEVC( 八 ) _语义

乍看之下，目前提出的推理并不适用于此类任务。事实上，RDO ( t , p , L ) ( t , p , L) (t,p,L) 不能被调用，因为t t t 不为搜索算法所知，因此不能通过p p p 传播回来。然而，无论算法是否知道圆锥顶点的位置，基于距离的适应度函数( 公式 2 )都会诱导出一个二次曲线的适应度景观。这样的景观，单峰和没有，通常很容易搜索。
特别地，几何交叉算子 [24] 已被证明在这类问题上表现特别好。一个重组算子是在度量d d d 下的几何交叉，如果它的子代在其父代之间的 d-度量段。在语义GP中可以很容易地采用几何交叉，因为程序语义表示为一个输出向量，语义空间自然是一个向量空间。对于某些度量，几何交叉提供了吸引人的收敛性质。例如，对于欧氏度量，线段上的子代不能比父代最差的差(更详细的解释见[25]) 。
我们最初在文献 [6] 中提出的近似几何语义交叉 (，AGX) 是一种将语义反向传播与几何交叉相结合的算子。如算法 3 所示，AGX在连接父代语义的线段上选择一个点 m，通过对每个父代应用 RDO，尝试产生与 m 相匹配的程序，目标设置为 m 。也就是说，在对真实目标不知情的情况下，AGX使用父代语义之间的一段上的点作为替代目标。

文章插图
寻找跨越父程序p 1 p_1 p1? 和p 2 p_2 p2? 语义的段的中点 m 是域依赖的。对于数值语义和欧氏度量，( s ( p 1 )，s ( p 2 ) ) (s(p_1)，s(p_2)) (s(p1?)，s(p2?)) 返回m = ( s ( p 1 ) + s ( p 2 ) ) / 2 m = ( s(p_1)+ s(p_2)) / 2 m=(s(p1?)+s(p2?))/2 。对于二进制向量和汉明度量，返回一个任意选择的点m m m，即 (i) 位于段 (即d ( s ( p 1 )，m ) + d ( m , s ( p 2 ) ) = d ( s ( p 1 )，s ( p 2 ) ) ) d(s(p_1)，m) + d(m , s(p_2)) = d(s(p_1)，s(p_2))) d(s(p1?)，m)+d(m,s(p2?))=d(s(p1?)，s(p2?))) 和 (ii) 可能等距于段 (即∣ d ( s ( p 1 )，m ) ? d ( m , s ( p 2 ) ) ∣ ≤ 1 ) |d(s(p_1)，m) - d(m , s(p_2))|≤1 ) ∣d(s(p1?)，m)?d(m,s(p2?))∣≤1) 的端点。
D.by
RDO和AGX使用父代个体从原始编程任务中派生出子任务。在IV-A 节中，我们提供了子任务解决方案可以比原始任务解决方案更短的证据。因此，为了解决一个子任务，而不是像GP那样使用复杂的启发式方法，我们使用更简单的方法，在一组具有预计算语义的程序中执行穷举搜索，我们称之为库。这个过程隐藏在算法 2 的调用之下。给定一个库L L L 和一个期望的语义D D D，( L , D ) ( L,D) (L,D) 计算D D D 的组件与库中每个程序的语义之间的最佳匹配，即在L L L 中找到一个最小化的程序p p p：
当最小化该表达式时，我们从笛卡尔积中舍去所有满足D i = ? D_i =\empty Di?=? 或? ? ∈ D i *?∈D_i ??∈Di? 的集合D i D_i Di? 。因此，距离d ( y , s ( p ) ) d(y , s(p)) d(y,s(p)) 仅在语义s ( p ) s(p) s(p) 的剩余(定义良好)成分上计算。
注意，以这种方式构造一个编程子任务不同于原始编程任务 (定义 3 )，其中搜索过程的目标是单个向量(期望输出值的组合) 。在这里，寻求一个最小化到D D D 中任意一个子目标的距离的方案。
在找到L L L 中最小化公式 4 的程序后，我们验证一个常数语义是否会给出更好的匹配。通过这样做，我们不仅期望有时能找到一个常数来减少匹配距离d d d，而且还能为种群提供额外的潜在有用常数( ERCs )，减少膨胀。我们通过求解公式 4 的以下特例来计算在所有适应度情况下最小化与期望值的总体散度的常数：
其中 [c] 表示一个由l l l 个分量组成的向量，所有的集合为c c c 。与公式 4 一样，笛卡尔积只涉及恰当低定义的D i D_i Di? 分量，该表达式在问题(R表示符号回归, {0,1} 表示布尔问题)的定义域特征c c c 变化时被最小化。如果 (5) 的值小于 (4) 的值，返回c c c，否则返回库中找到的程序。