2014，TEVC( 二 ) _语义

II.WORK
本文关注程序行为，反映了对语义GP的兴趣不断增长。语义GP不是专注于程序，而是专注于研究程序执行的影响，并利用这些影响的知识来设计更有效的GP搜索算法。除了[8] 的基础分析研究外，Mc Phee 等人首次研究了交叉对程序语义和语义构建块的影响 [9] 。据我们所知，最早研究了交叉对程序语义和语义构建块的影响 [9] 。他们定义了在树交换交叉中形成后代的组件的语义属性，即子树和上下文(有悬挂枝的部分树木)，并观察它们如何随着布尔问题 ( ) 的演化而变化。在早期的另一项研究中，和[10] 针对布尔问题提出了一种语义驱动的交叉算子，保证子代在语义上与父代和子代都不同。在 [11] 中分析了初始群体的语义多样性。最近，-Lopez 等人提出了一种抑制语义重复的锦标赛选择 [12] 。
等 [13] 考虑了两种用于符号回归的语义交叉算子，一种仅当父代中待交换的子树在语义上比给定的下限(方法的一个参数)更远时才允许交叉，另一种对距离有额外的上限。后来，等[14] 提出了一个算子，从父代中待交换的有效子树对集合中，选择最小但超过下限距离的子树对，从而降低上限参数。这里采用的语义表示，即程序为所有训练样本(适应度案例)返回的一个数字向量，是目前语义GP中应用最广泛的一种，本文也采用了这种表示。在类似意图的驱动下，Day 和 Nandi 虽然没有明确提到程序语义，但使用二进制字符串来表征种群中的个体如何应对特定的适应度情况，并设计了利用这些信息的交配策略 [15] 。
等 [16]，[17] 最近的工作采用了一种定性不同的方法。支撑他们方法的关键观察是，GP中的适应度函数通常被定义为程序语义和预定义目标语义之间的距离。这将语义集合转化为具有一定几何性质的度量空间，可以利用这些几何性质使搜索过程更加高效。作者提出了两个依赖于该原理的搜索算子，包括一个精确的几何交叉，保证产生相对于其父代语义中间的子代(即,结合他们的行为) 。这是通过使用一个额外的句法结构将父程序合并成子程序来实现的。类似地，和[18] 提出了一种近似几何的交叉算子。其中一些几何算子作为控制方法在第 VI 部分介绍.在这些研究的背景下，本文提出的方法在尝试语义层面的问题分解时保持了原创性。在第四节中，语义反向传播使用了类似于可逆计算的概念 [19]，该范式假设计算的效果总是可以逆转的。在该框架中，每条指令都必须实现一个转换函数，以一对一的方式，即单射的方式将执行环境(例如,寄存器,内存)的当前状态转换到另一个状态，即内射性 () 。难怪它成为量子计算中许多研究者感兴趣的领域，并且在遗传编程中也被研究。文献 [2 ] 中的分析了可逆程序的适应度分布，发现它是正常的。在文献 [21] 中，多表达式编程(Multi)[22]和gate 被用来解决偶宇称问题(even- ) 。
不幸的是，可逆计算主要是一个理论领域，因为它假定了一个强大的、内射的可逆性概念，而传统的编程语言中充斥着不可逆的指令。为此，我们在这里提出了一个更宽松的程序反转的概念，它允许指令实现多对一映射(投射) 。
III.? A.
正如引言中提到的，在解决一个编程任务时，我们主要对程序行为感兴趣 (程序做了什么) 。在正式定义编程任务之前，必须首先明确什么是程序行为。为此，我们引入程序语义的概念。
设p ∈ P p∈P p∈P 是一个程序，即来自给定编程语言 P 的符号序列(或其他结构) 。当应用于一个输入i n ∈ I in∈I in∈I 时，程序p p p 产生确定的输出p ( i n ) p(in) p(in) 。这样，程序就实现了从输入集合I I I 到输出集合O O O 的某种映射，记为p ： I → O p：I→O p：I→O