05. 随机常数

这是对《Gene Expression Programming: Mathematical Modeling by an Artificial Intelligence》的笔记，本页对应第5章： Chapter 5： Numerical Constants and the GEP-RNC Algorithm 本书可以在斯普林格购买纸质版或者电子版：https://link.springer.com/book/10.1007/3-540-32849-1

在GP中引入常数是一种增大信息密度的方式：因为使用非常数的function来拼凑出一个常数（尤其是非整数）非常困难，且在结构上非常长，按照交叉的偏向性，常数节点很容易代替他们，从而减少个体的大小。
在GP中最早引入常数的方法是在端点集中加入固定常数，随后Koza提出了Ephemeral Random Constant，这种常数会在每个个体第一次调用它时在某个范围内随机生成一个常数，然后保持不变。
GEP的做法是将随机常数视为是一种特殊的单节点ADF：随机常数在基因型中以“？”表示，不进行实例化。同时基因引入一个新的域：DC domain，其中存储了随机常数的映射符号。当个体被评估时，ORF按照顺序将DC domain中的映射符号填入“？”中，编译时这些映射符号会被替换为一个随机生成的常数序列中的常数。这个引入的新的DC域也同样支持遗传操作。
接下来，这一章举了两个例子来说明GEP在有常数和没有常数时的性能表现。
在第一个例子中，GEP需要拟合多项式\(y=\frac{a^2}{2}+3a\)，这个多项式中的系数都是不大的正整数，在这个任务中，没有常数的GEP的表现要好于terminal set中有常数的GEP。可能的原因有两点：

• GEP在没有常数的情况下也可以通过简单拼凑制造出常数，相比于常数节点，这些表示常数的符号子树拥有更多的被进化调整的可能性。
  
• 引入常数增加了搜索（表示）空间的维度。

在第二个例子中，GEP需要拟合多项式\(y=2.718x^2+3.141636x\)，这个多项式的系数都是小数。在这种情况下，随机在端点集中加入几个小数常数的GEP的性能明显高于没有常数的GEP。
真实的问题更接近于第二个例子。但是在真实的问题中，人类无法事先得知常数是否是小数和常数的范围。这两个参数对GEP的常数设置而言很重要，因此需要设计出一种自动尝试常数的方法。

Dc域的结构

GEP中处理常数的方法是在每个基因的尾部后面加入一个新的域：Dc domain用于进化寻找常数。这样每个基因就有头部、尾部、Dc domain三个域。每个Dc域同时对应了一个固定长度的随机数列表，列表中的元素是随机生成的，但是生成后被确定下来。Dc域中的元素是随机数在列表中的编号。在编译的时候，当编译器会将“？”的部分按照从上到下从左到右，广度优先的方式将Dc域中的元素填入，再根据这些元素代表的随机数在随机数列表中的位置将对应随机数列表的数填入。
在多基因GEP中，有多少个基因就有多少个Dc域以及和它对应的随机数列表。
Dc域和随机数序列会跟着基因一同传播和扩散。

Dc域的进化

GEP中，Dc域通过一组特殊的遗传操作进行进化。Dc域也可以有none-coding part来维持合法性。这些遗传操作可以在尝试旧的常数组合的同时激活新的none-coding常数。

突变

虽然突变的操作和之前相同，但是为了调整DC域使用的突变率，这里作者将其设定为一个单独的operator。
Dc域中的突变有两种：

• Dc-specific Mutation
  这种突变会随机选择DC域上的一个随机数编号，将这个随机数编号改为其他随机数编号。

• Direct RNC Mutation
  并不改变随机数编号，而是将随机数序列中的其中一个随机数用另一个随机数替代。这是唯一一种向种群中引入新的随机数的方式。
  实验中发现这种突变方式对个体的提升优先，甚至关闭之后还可以得到更好的结果。

发生在Dc域上的突变不会改变语法树的拓扑。

倒位

Dc domain的倒位和普通的倒位相似，差别是Dc域的倒位被限制在了Dc域当中。

易位

Dc域对IS Transpose和RIS Transpose依然适用，限制保持不变。但是增加一个只在Dc域发生的Transpose：这种Transpose类似于IS Transpose，但是目标位置被限定在Dc域中。

常数的生成方式

接着，本章节对比了没有常数的GEP，将固定常数加入端点集的GEP，随机常数的GEP（GEP-B，GEP-NC,GEP-RNC）在四个问题上的表现，有如下观察和结论：

• GEP-RNC的表现总是要比GEP-NC的表现更好，证明了提出的自适应寻找随机常数的方式是有效的。
  
• GEP在添加常数之后的表现取决于问题本身：如果问题本身就不倾向于使用常数（比如特征组合问题），那么GEP-B的性能要好于加入常数的GEP；反之如果问题本身的最终解倾向于带常数，那么情况则完全相反。

因此，在使用常数之前应当先用经验知识判断是否需要常数，如果目标解不需要，那么用简单的GEP即可，否则则使用RNC-GEP。