将交叉和变异应用于图形（遗传算法）

Question

我正在尝试使用遗传算法来进化图形。当染色体是图形时，您知道如何应用交叉和突变吗？

还是说我需要编写图形的代码，以便可以对位串应用“常规”的交叉和突变？

非常感谢！任何帮助，即使与我的问题无关，也将不胜感激！

曼努埃尔

- Manuel Araoz

Answer 1

我喜欢Sandor的建议使用Ken Stanley的NEAT算法。

NEAT旨在演化具有任意拓扑结构的神经网络，但这些基本上只是有向图。在NEAT之前，有许多方法可以演化神经网络，但NEAT最重要的贡献之一是它提供了一种方法来在具有不同拓扑结构的两个网络之间执行有意义的交叉。

为了实现这一点，NEAT使用附加到每个基因的历史标记来“排列”两个基因组的基因进行交叉（生物学家称此过程为联会）。例如：

_{（来源：natekohl.net）}

在这个例子中，每个基因都是一个框，代表两个节点之间的连接。每个基因顶部的数字是该基因的历史标记。

总之，根据历史标记排列基因是一种原则性的方法，在不进行昂贵的拓扑分析的情况下在两个网络之间执行交叉。

- Nate Kohl

---

NEAT允许具有循环/递归的网络。在评估过程中如何处理？ - Ilia Choly

@iliacholy，这通常取决于您要解决的问题。对于控制任务（如平衡杆机器人），循环连接可能很有用，因为它们可以提供一种计算随时间变化的值的导数的方法。在评估网络时，您可以每个时间步执行一次值传播，或者您可以继续传播值直到输出稳定...我不确定是否有任何单一的“正确”答案。 :) - Nate Kohl

Answer 2

你可以尝试使用遗传编程。图表是最接近树的东西，而遗传编程使用树形结构...如果你仍然想使用遗传算法而不是遗传编程，那么看一下遗传编程如何执行交叉可能会给你一个关于如何在你的遗传算法图表上执行它的想法:

_{（来源：geneticprogramming.com）}

以下是树（和图表）交叉的工作原理：

1. 选择两个个体进行配对。
2. 从一个父代中选择一个随机节点，并将其与另一个父代中的随机节点交换。
3. 得到的树就是后代。

- Kiril

Answer 3

正如其他人所提到的，GA 中交叉图表（或树）的一种常见方式是交换子图表（子树）。对于变异，只需随机更改一些节点（带有小概率）。

或者，如果您将图形表示为邻接矩阵，则可能会交换/变异矩阵中的元素（有点像使用二维位串）。

- unignorant

---

我正在尝试理解：从技术上讲，如何使用邻接矩阵交换子图？ - Lucien S.

Answer 4

我不确定使用位串是否是最好的想法，我更愿意用真实值来表示至少权重。尽管位串也可以使用。

如果您有固定的拓扑结构，那么交叉和变异都很容易（假设您只演化网络的权重）：

交叉：从一个父代中取出一些权重，从另一个父代中取出其余的权重，如果您将权重表示为数组或列表，则可以非常轻松地完成。有关更多详细信息或替代方法，请参见http://en.wikipedia.org/wiki/Crossover_%28genetic_algorithm%29。

突变：只需选择一些权重并略微调整它们即可。

演化其他东西（例如激活函数）与这些非常相似。

如果您还想演化拓扑结构，那么事情就变得更加有趣了。还有许多额外的突变可能性，例如添加节点（最有可能连接到已经存在的两个节点），分裂连接（而不是 A-> B 有 A-> C-> B），添加连接或这些反面。

但如果节点数量不固定，交叉可能并不容易（至少不会太容易），因为您可能希望找到“匹配”的节点（其中匹配可以是任何东西，但可能与相似的“角色”或在网络中相似的位置有关）。如果您也想这样做，我强烈建议您研究已经存在的技术。我知道并喜欢的技术之一称为NEAT。您可以在以下链接中找到有关它的一些信息：
http://en.wikipedia.org/wiki/Neuroevolution_of_augmenting_topologies
http://nn.cs.utexas.edu/?neat
和http://www.cs.ucf.edu/~kstanley/neat.html

- Sandor Murakozi

Answer 5

嗯，我从未使用过这样的实现方法，但是最终对于交叉操作，您可以选择其中一个图形的分支并将其与另一个图形的分支进行交换。
对于变异操作，您可以在图形内随机更改一个节点，概率很小。

- Luis Miguel Serrano