2014，TEVC( 四 ) _语义

GP中考虑的大多数编程任务在适应度案例 ( cases) 和语义距离方面定义类似。例外是没有明确指定目标的任务，如进化控制器(例如,极点平衡、人造蚂蚁、机器人学等) 。对于此类任务，适应度评估是隐式的，例如基于仿真的结果，不能直接应用涉及目标的语义方法。在本文介绍的两个算子中，一个 (RDO ,V-B) 需要目标的知识，而另一个 (AGX ,V-C) 不需要目标的知识，因此本文提出的方法可以适用于广泛的GP任务。
IV.OF? A. Thefor反演的原理
编程任务 (定义 3 ) 一般很难解决，因为从组合程序空间到语义空间的映射通常非常复杂。然而，当语义是程序针对特定的适应度情况所产生的输出向量时 (公式 1 )，语义映射s ： P → S s：P→S s：P→S 就不再是黑盒体。在这种情况下，形成语义的向量的每个组成成分都是一个序列过程的结果，其中特定的程序指令处理其前一个指令的结果，最后一个指令的执行完成语义(对于单个case)的计算。该过程的可分解性是本文方法的关键。
我们假设任何程序p p p 都可以分解为它的前缀 ()p ( 1 ) p_{(1)} p(1)? 和后缀 ()p ( 2 ) p_{(2)} p(2)?，这里采用的反向波兰记法 () 记为
对输入数据i n in in 执行这样的复合程序涉及到将后缀p ( 2 ) p_{(2)} p(2)? 应用于前缀p ( 1 ) p_{(1)} p(1)? 产生的结果，即p ( i n ) = p ( 2 ) ( p ( 1 ) ( i n ) ) p(in) = p_{(2)} ( p_{(1)}(in) ) p(in)=p(2)?(p(1)?(in)) 。在这个公式中，我们从程序表示中抽象出来。对于指令序列，前缀和后缀也采取序列的形式。对于无副作用的树形程序(这在本文中我们限制了关注点)，前缀是程序的任意子树，后缀是删除了单个子树的程序树(在 [9] 中称为上下文) 。不管表示方式如何，我们假设前缀是一个形式良好的(子)程序，可以执行。因此，每个前缀也会像定义 1 中描述的那样具有特定的语义。
如果考虑的任务t t t 是可解的，则存在一个程序p ? p^* p?，使得s ( p ? ) = t s(p^*) = t s(p?)=t 。设p ( 1 ) ? p^*_{(1)} p(1)?? 是p ? p^* p? 的前缀，p ( 2 ) ? p^*_{(2)} p(2)?? 是相应的后缀。关键的点是p ( 1 ) ? p^*_{(1)} p(1)?? 决定了 (可以作为另一个编程任务的目标的) 语义 s ( p ( 1 ) ? ) s(p^*_{(1)}) s(p(1)??) 。我们称p ( 1 ) ? p^*_{(1)} p(1)?? 决定一个子目标t ′ = s ( p ( 1 ) ? ) t^′= s(p^*_{(1)}) t′=s(p(1)??) 。任何求解由子目标t ′ t^′ t′ 定义的子任务的程序p s p_s ps? 都可以作为p ? p^* p? 中p ( 1 ) ? p^*_{(1)} p(1)?? 的替代。形式上，若s ( p s ) = t ′ s(p_s) = t^′ s(ps?)=t′，则程序[ p s p ( 2 ) ? ] [ p_sp^*_{( 2 )}] [ps?p(2)??] 求解任务t t t，即s ( [ p s p ( 2 ) ? ] ) = t s([ p_sp^*_{( 2 )}]) = t s([ps?p(2)??])=t 。

文章插图
类似地，后缀p ( 2 ) ? p^*_{(2)} p(2)?? 可以说决定了一组子任务，即一组这样的语义t ′′ t^{′′} t′′，s ( [ t ′′ p ( 2 ) ? ] ) = t s([t^{′′}p^*_{(2)}] ) = t s([t′′p(2)??])=t 。由前缀决定的子任务t ′ t^′ t′ 就是其中之一，但由于程序指令的多对一操作，可以有更多这样的子任务t ′′ t^{′′} t′′ 。我们在IV-B 中将这个概念形式化为所需的语义。
由于每个子任务的解都会形成至少一个原任务的解的前缀，并且任何(恰当的)前缀都比它所在的程序短，因此可以合理地假设一个子任务比原任务更容易求解。假设求解一个规划任务的计算成本是最短解长度的单调增函数4，求解一个子任务而不是原任务可能会带来大量的节省。
然而，上述子任务都是从给定的最优方案中派生出来的，即求解原任务的已知方案。实际问题是：我们能否定义一个任务的子任务而不首先解决后一个任务?