グラフにクロスオーバーと突然変異を適用する（遺伝的アルゴリズム）

Question

私はグラフを進化させたい遺伝的アルゴリズムで前進しています。染色体がグラフであるときにクロスオーバーと突然変異を適用する方法を知っていますか？

それとも、グラフのコーディングがありませんか？

どうもありがとう！それが私の問題に直接関係していなくても、どんな助けも感謝しています！

マヌエル

Answer 1

好き サンドールの提案 Ken Stanley'sを使用すること きちんとしたアルゴリズム.

Neatは、任意のトポロジを使用してニューラルネットワークを進化させるように設計されていますが、それらは基本的に指示されたグラフです。 Neatの前にニューラルネットワークを進化させる方法はたくさんありましたが、Neatの最も重要な貢献の1つは、 異なるトップルーギーを持つ2つのネットワーク間で意味のあるクロスオーバーを実行する.

これを達成するために、きちんとした使用 歴史的なマーキング 各遺伝子に取り付けて、クロスオーバー中に2つのゲノムの遺伝子を「並べる」（プロセス生物学者が呼び出す シナプス）。例えば：

_{（ソース： natekohl.net)}

（この例では、各遺伝子はボックスであり、2つのノード間の接続を表します。各遺伝子の上部にある数は、その遺伝子の履歴マーキングです。）

要約すれば: ：履歴マーキングに基づいて遺伝子を並べることは、高価なトポロジ分析なしで2つのネットワーク間でクロスオーバーを実行する原則的な方法です。

Answer 2

あなたも試してみるかもしれません 遺伝的プログラミング. 。グラフは木に最も近いものであり、GPは木を使用します... GPの代わりにガスを使用したい場合は、GPでクロスオーバーがどのように実行されるかを見てください。 GAのグラフで：

_{（ソース： GeneticProgramming.com)}

木（およびグラフ）のクロスオーバーがどのように機能するかは次のとおりです。

1. 交尾用の2つの標本を選択します。
2. 一方の親からランダムノードを選択し、他の親のランダムノードと交換します。
3. 結果として生じる木は子孫です。

Answer 3

他の人が言及したように、GAでグラフ（または木）を交差させる一般的な方法の1つは、サブグラフ（サブツリー）を交換することです。突然変異の場合、ノードの一部をランダムに変更するだけです（確率が少ない）。

または、グラフを隣接マトリックスとして表現している場合、マトリックスの要素を交換/変異させることができます（2次元ビット文字列を使用するようなもの）。

Answer 4

ビットストリングを使用することが最良のアイデアであるかどうかはわかりません。少なくとも実際の価値のあるウェイトを表現したいと思います。それにもかかわらず、ビットストリングも機能する可能性があります。

固定トポロジがある場合、クロスオーバーと突然変異の両方が非常に簡単です（ネットワークの重みを進化させるだけであると仮定します）：

クロスオーバー：一方の親から、残りは他方からの残りからいくつかのウェイトを取ります。アレイまたはリストとして重みを表す場合、非常に簡単に実行できます。詳細または代替案については、参照してください http://en.wikipedia.org/wiki/crossover_%28genetic_algorithm%29.

突然変異：重みの一部を選択して、わずかに調整するだけです。

他のいくつかのもの（アクティベーション関数など）を進化させることは、これらにかなり似ています。

トポロジーも進化したい場合は、物事がはるかに興味深いものになります。ノードを追加する（おそらく2つの既存のノードに接続されている可能性が高い）、接続の分割（> 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

まあ、私はそのような実装で遊んだことはありませんが、最終的にはクロスオーバーのために、グラフの1つのブランチを選択して、別のグラフからブランチと交換できます。
突然変異の場合、グラフ内のノードをランダムに変更して、確率がわずかになります。