java - 我应该使用什么交叉方法来交叉遗传算法中的后缀表达式？

Question

我正在构建一个项目，其主要目标是使用 6 个给定数字和主要运算符(+、-、*、/)查找给定数字(如果可能，否则尽可能接近)。想法是使用给定的数字和运算符随机生成表达式，采用反向抛光(后缀)表示法，因为我发现它最容易生成和稍后计算。这些表达式是我的遗传算法中的个体。这些表达式在 Java 中具有字符串数组列表的形式，其中字符串既是运算符又是操作数(给定的数字)。

这里的主要问题是，交叉这些个体(实际上是后缀表达式)的最佳方法是什么？现在我正在考虑由给定的所有六个操作数(以及 5 个运算符)组成的交叉表达式。稍后我可能还会交叉由更少的操作数(5、4、3、2 和也只有 1)组成的表达式，但我想我应该首先解决这个问题，因为这是最复杂的情​​况(如果你认为以不同的方式开始可能是一个更好的主意，我愿意接受任何建议)。所以，问题是每个表达式都是由所有给定的操作数组成的，而且子表达式也应该包含所有操作数。我知道这需要某种有序的交叉(通常用于 TSP 等问题)，并且我阅读了很多相关内容(例如 here 描述了多种方法)，但我不太清楚哪一个会最适合我的情况(我也知道在遗传算法中有很多“试错”过程，但我在这里谈论的是其他事情)。

我所说的困扰我的是运营商。如果我只有一个操作数列表，那么跨越 2 个这样的列表就不会有问题，例如，从 1 个父元素中取出一个随机的半元素子数组，然后用父 2 中的剩余元素填充其余元素，保持顺序它是。但是在这里，如果我从第一个父表达式中取出表达式的前半部分，我肯定必须用剩余的操作数填充子表达式，但是我应该如何处理运算符？像剩下的操作数一样从父 2 中取出它们(但我必须小心，因为为了在后缀表达式中使用运算符，我需要至少有 1 个操作数，并且检查所有时间可能很耗时，或者不是？)，或者也许我可以为子表达式的其余部分生成随机运算符(但这不会是一个纯粹的交叉，不是吗)？

当谈到交叉时，也有变异，但我想我已经解决了。我可以采用一个表达式并执行一个突变，我将只切换 2 个操作数，或者采用一个表达式并随机更改 1 个或多个运算符。为此，我有一些想法，但真正困扰我的是交叉。

所以，这几乎总结了我的问题。就像我说的，主要问题是如何交叉，但是如果您对程序有任何其他建议或问题(可能更容易表示表达式 - 除了字符串列表 - 这可能更容易/更快地交叉，也许我没有在这里提，没关系，甚至可能是一种全新的解决问题的方法？)，我很想听听他们的意见。我没有在这里给出任何代码，因为我认为不需要回答这个问题，但如果你认为它有帮助，我一定会编辑以解决这个问题。还有一次，主要问题是回答如何交叉，问题的这一特定部分(预期的想法或伪代码，尽管代码本身也很棒 :D)，但如果您认为我需要更改更多内容，或者你知道我的整个问题的其他一些解决方案，请随意说。

提前致谢!

Answer 1

我想到了两种方法:

方法#1

将每个基因组编码为固定长度的表达式，其中奇数索引是数字，偶数索引是运算符。对于突变，您可以稍微更改数字和/或更改运算符。

优点:

• 编码非常简单

缺点:

• 必须创建一个中缀解析器
• 固定长度的表达式

方法#2

将每个基因组编码为语法树。例如，4 + 3/2 - 1 等价于 Add(4, Subtract(Divide(3, 2), 1)) 看起来像:

   _____+_____
   |         |
   4     ____-____
         |       |
       __/__     1
       |   |
       3   2

然后在交叉的时候，从每棵树中随机挑选一个节点进行交换。对于突变，您可以添加、删除和/或修改随机节点。

优点:

• 可能会找到更好的结果
• 可变长度表达式

缺点:

• 增加时间复杂度
• 增加了编程的复杂性

这是第二种方法的例子:

Source