2014，TEVC( 九 ) _语义

我们通过在公式 4 的每个维度上分别最小化来解决这两个问题，由于距离的性质，可以在多项式时间内完成。具体内容见附录 6 。
我们考虑库的两个程序来源。一个静态库L L L 由达到一定高度7限制的所有程序树填充，在进化搜索过程中不发生变化。一个动态库包含了从当前种群中所有个体收集的所有子树，因此在搜索过程中会发生变化。
一个库，无论是静态的还是动态的，都只存储语义唯一的程序。如果两个候选程序具有相同的语义，则库中只包含较短的程序。需要注意的是，语义唯一性的验证是在没有任何阈值8 的情况下完成的，其目的是保持库的大小，减少程序膨胀。尽管如此，这是库生成的主要计算成本。因此，维护一个动态库通常比较耗时。
VII.
实验表明，RDO操作符合预期的 ( Sec.VI~F)，在所考虑的两个域 () 中都优于所有其他算子，而 AGX 只在回归域 ( ) (Sec.VI-B) 中证明有用。造成这些差异的原因是什么?
RDO的表现源于明确使用了问题描述中最具信息含量的部分：目标。通过使用目标作为语义反向传播的目标，RDO旨在直接解决问题，即没有逐渐接近目标的"意图" 。幸运的是，它可以从初始种群中已有的程序中选择合适的后缀，并在库中找到一个完美匹配的程序，从而在第一代中解决问题。对于 AGX 来说，要发生类似的事情，确定的替代目标必须与真实目标重合，这是不可能的，特别是在连续语义空间。因此，AGX在设计上无法比RDO更快地收敛。
那么，AGX在符号回归域中的表现如何?第二节中提到的语义空间的几何性质。这里 V-C 起关键作用。对于连续的语义空间和欧氏度量 d，适应度景观 ( ) 形成一个欧氏锥体悬停在语义空间 (其实例如图 2a 所示)上。语义空间中一个点的适应度可以通过将其投影到圆锥上并测量到该投影(图 2a 中用颜色描绘的 “高度”) 的距离得到。对于一对父代语义s ( p 1 ) s(p_1) s(p1?) 和s ( p 2 ) s(p_2) s(p2?)，程序指定AGX的代理目标为s ( p 1 ) s(p_1) s(p1?) 和s ( p 2 ) s(p_2) s(p2?) 之间的分段中点 m (算法 3 ) 。根据圆锥的定义，m 投影在圆锥上的像不能高于s ( p 1 ) s(p_1) s(p1?) 和s ( p 2 ) s(p_2) s(p2?) 投影的高度。因此，如果 AGX 能够产生一个与 m 匹配的程序 (由于程序反演和库检索的不完善性,这是不保证的)，那么该程序不能比父代程序差。尤其是，当s ( p 1 ) s(p_1) s(p1?) 和s ( p 2 ) s(p_2) s(p2?) 恰好位于原目标 t 的对边时(因而它们在圆锥体的对面斜面上的像)，子代可以比父代更适合(其图像在锥体上较低) 。
这种几何性质导致符号回归基准中 AGX 比 GPX 和 LGX 收敛得更快。然而，在布尔域 ( ) 中AGX的表现更差 (图4 ) 。可能的原因是这里的语义空间和适应度景观的结构与连续符号回归域的结构有本质的不同。虽然分段在汉明空间 ( space) 中定义良好，但分段的中点一般不唯一：对于两个相差n n n 位的布尔语义 ( )，大约有( n / 2 ? n ) (n/2 - n) (n/2?n) 个这样的中点。与欧几里得空间相反，这样的中点可以比双亲更少的拟合 (fit) 。，AGX 可以指定一个替代目标m m m，使搜索远离原始目标t t t 。
考虑到这一点，AGX是否有任何其他优点，使其具有潜在的有用性，因为RDO的性能要好得多?我们声称是这样的，因为正如第五节所示，RDO和AGX的应用领域在一定程度上是互补的。RDO的优点在于它不要求语义距离d d d 是一个范数： d d d 是一个度量就足够了。AGX则相反，要求语义空间是赋范向量空间，因为它需要在父代语义之间构造一个中点。然而，AGX提供了对搜索目标不了解的优势；它不需要明确知道什么是期望的程序输出。得益于此，它能够以适应度值作为唯一信息(除了编程语言之外)对所要解决的问题进行搜索。这使得当目标不能明确地显示给搜索算法时，例如由于机密性问题，或者当目标完全不知道时，这是一种方便的选择方法，这在控制问题(如人造蚂蚁或极点平衡)中就是如此。我们假设AGX在后一种情况下也能表现良好，尽管这类任务一般不是单峰的(即可能有不止一个目标) 。在更广泛的视角下，值得注意的是，这里引入的期望语义概念可以作为多模态任务的目标泛化。这里介绍的算法将目标等同于向量，主要是由于GP中广泛存在的约定；在给定任务所需语义作为输入的情况下，其中许多(特别是 ION 和 RDO )也能正常工作。