15

I'm playing arround with a Genetic Algorithm in which I want to evolve graphs. Do you know a way to apply crossover and mutation when the chromosomes are graphs?

Or am I missing a coding for the graphs that let me apply "regular" crossover and mutation over bit strings?

thanks a lot! Any help, even if it is not directly related to my problem, is appreciated!

Manuel

4

5 回答 5

16

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

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

为了实现这一点，NEAT 使用附加到每个基因的历史标记来“排列”交叉期间两个基因组的基因（生物学家称之为突触）。例如：

NEAT 中不同拓扑的交叉
（来源：natekohl.net）

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

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

于 2010-07-11T19:27:14.460 回答
4

You might as well try Genetic Programming. A graph would be the closest thing to a tree and GP uses trees... if you still want to use GAs instead of GPs then take a look at how crossover is performed on a GP and that might give you an idea how to perform it on the graphs of your GA:

Crossover
(source: geneticprogramming.com)

Here is how crossover for trees (and graphs) works:

  1. You select 2 specimens for mating.
  2. You pick a random node from one parent and swap it with a random node in the other parent.
  3. The resulting trees are the offspring.
于 2010-07-01T18:34:36.270 回答
1

As others have mentioned, one common way to cross graphs (or trees) in a GA is to swap subgraphs (subtrees). For mutation, just randomly change some of the nodes (w/ small probability).

Alternatively, if you are representing a graph as an adjacency matrix, then you might swap/mutate elements in the matrices (kind of like using a two-dimensional bit string).

于 2010-07-01T18:40:40.213 回答
1

我不确定使用位串是否是最好的主意，我宁愿至少用真实值表示权重。尽管如此，位串也可以工作。

如果你有一个固定的拓扑，那么交叉和变异都很容易（假设你只进化网络的权重）：

交叉：如果将权重表示为数组或列表，则可以很容易地从一个父级获取一些权重，其余的从另一个父级获取。有关更多详细信息或替代方案，请参阅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找到有关它的一些信息/整洁的.html

于 2010-07-02T09:35:44.287 回答
0

Well, I have never played with such an implementation, but eventually for crossover you could pick a branch of one of the graphs and swap it with a branch from another graph.
For mutation you could randomly change a node inside the graph, with small probability.

于 2010-07-01T18:33:21.697 回答