在遗传算法中我应该使用什么交叉方法来交叉Postfix表达式？

Question

我正在构建一个项目，其主要目标是使用6个给定数字和主要操作符（+， - ，*，/）来查找给定数字（如果可能，否则最接近可能）。想法是用反向波兰语（后缀）表示法随机生成表达式，使用给定的数字和操作符，因为我发现它是最容易生成和计算的。这些表达式是我的遗传算法的种群中的个体。这些表达式具有Java中Strings的ArrayList形式，其中Strings既是运算符也是操作数（给出的数字）。

这里的主要问题是，什么是交叉这些个体（实际上是后缀表达式）的最佳方法？现在我正在考虑由所给出的所有六个操作数构成的交叉表达式（以及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