将跨界和突变应用于图（遗传算法）

Question

我正在使用一种遗传算法来演奏，我想在其中进化图形。当染色体是图形时，您知道一种应用跨界和突变的方法吗？

还是我错过了让我对位字符串应用“常规”交叉和突变的图形编码？

多谢！即使与我的问题没有直接关系，任何帮助也将受到赞赏！

曼努埃尔

Answer 1

我喜欢 桑多的建议 使用肯·斯坦利的 整洁算法.

整洁旨在以任意拓扑结构发展神经网络，但基本上是指向图。在整洁之前，有很多方法可以发展神经网络，但是整洁的最重要的贡献之一就是它提供了一种方法 在有不同的库存的两个网络之间执行有意义的交叉.

为此，整洁使用 历史标记 连接到每个基因，以“对”两个基因组的基因，在交叉期间（过程生物学家称呼） 突触）。例如：

_{（来源： natekohl.net)}

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

总之: ：基于历史标记的基因排列是在没有昂贵拓扑分析的两个网络之间执行交叉的原则方法。

Answer 2

你最好尝试 基因编程. 。图将是最接近树的东西，而GP使用树...如果您仍然想使用气体而不是GP，请查看如何在GP上执行跨界车，这可能会使您有一个想法如何执行它在您的GA的图表上：

_{（来源： GeneticProgramming.com)}

这是树木（和图形）的跨界如何工作的方式：

1. 您选择2个标本进行交配。
2. 您从一个父母中选择一个随机节点，然后在另一个父母中与随机节点交换。
3. 最终的树是后代。

Answer 3

正如其他人提到的那样，在GA中横图（或树）的一种常见方法是交换子图（子树）。为了突变，只需随机更改某些节点（带有较小概率）。

另外，如果将图表示为邻接矩阵，则可以在矩阵中交换/突变元素（就像使用二维位字符串一样）。

Answer 4

我不确定使用bottring是最好的主意，我宁愿至少代表具有真实价值的权重。然而，斑点也可能起作用。

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

交叉：如果将权重表示为阵列或列表，则可以从一个父母那里获得一些权重，其余的。有关更多详细信息或替代方案 http://en.wikipedia.org/wiki/crossover_%28Genetic_algorithm%29.

突变：只需选择一些权重，然后稍微调整它们即可。

不断发展的其他一些东西（例如激活功能）与这些东西非常相似。

如果您也想发展拓扑，那么事情就会变得更加有趣。还有很多其他突变的可能性，例如添加节点（最有可能连接到两个已经存在的节点），分解连接（而不是A-> B具有A-> C-> B），添加连接或对立面这些。

但是跨界车不会太容易（至少如果节点的数量未固定），因为您可能想找到“匹配”节点（在其中匹配可以是任何东西，但可能与类似的“角色”或网络中的类似位置）。如果您也想这样做，我强烈建议您研究已经存在的技术。我知道和喜欢的一个被称为整洁。您可以在
http://en.wikipedia.org/wiki/neurovolution_of_augmenting_topologies
http://nn.cs.utexas.edu/?neat
和 http://www.cs.ucf.edu/~kstanley/neat.html

Answer 5

好吧，我从来没有玩过这样的实现，但是最终，对于跨界车，您可以选择其中一个图的分支，然后将其与另一个图的分支交换。
对于突变，您可以以较小的概率随机更改图内的节点。