遗传算法中对符号表达树进行变异的最佳方法

Question

我正在为python中的时间序列预测创建GA。假设我有一个大型的符号表达树，如下所示：

[''avg'，['diff'，'x'，['avg'，'pi'，24.90887042555513]]，['sqrt'，['max'，['mul'，['diff'，53.79502493321837 ，'e']，['mul'，0.5144978394070354，46.36225530228578]]，44.34745373778043]，['sqrt'，['diff'，['avg'，20.424103573006006004，67.68047383230076]，['div'，35.70761733351755，76.63350676737794]]] ，6.6143363501814605]]]

什么是随机变异的好方法？

1）我应该仅仅突变一个随机节点吗？或使用概率来决定发生突变的次数，次数和时间？

2）我应该通过添加分支或只是单个值（叶节点）来进行变异

3）我应该如何实施这种机制？通过递归机制？或以某种方式建立树形的索引并随机选择要变异的巢？

提前感谢

Answer 1

在进化算法中，重要的是，通过重复的突变，您可以将每个表达树转换为任何其他表达树。

在您需要做以下四件事的情况下：

1. 将所有数字随机改变。
2. 单独查看每个数字，并以较小的机会更改它以x或用新的随机表达式替换（最好仅深度为1，以防止表达式变大）。
3. 查看所有变量，并以很小的机会将其更改为随机数或新的随机表达式（最好再次选择深度1）。
4. 随机删除一些表达式。

1、2和3仅更改叶子，不需要构建树，但是可以通过线性遍历字符串来实现。

有一些简化4.也可以在不创建树的情况下实现：

代替删除随机表达式，仅删除仅包含数字的表达式就足够了（例如['mul', 4, 5]），因为与处理1,2,3一起，表达式树仍然可以转换为其他所有可能的树。删除仅包含数字的表达式非常容易，因为您可以只计算表达式：['mul', 4, 5] =4*5= 20。

此修改版本的另一个优点是，您无需更改输出，而只需更改树的结构。

但是请注意，不要替换所有仅包含数字的表达式。对将来的突变具有更深的结构可能很有用。