appliquer croisement et de mutation à un graphique (algorithme génétique)

Question

Je joue arround avec un algorithme génétique dans lequel je veux évoluer graphiques. Est-ce que vous connaissez un moyen d'appliquer croisement et la mutation lorsque les chromosomes sont graphiques?

Ou suis-je manque un codage pour les graphiques qui me permettent d'appliquer un crossover de « régulier » et de mutation sur les chaînes de bits?

Merci beaucoup! Toute aide, même si elle est pas directement lié à mon problème, est apprécié!

Manuel

Answer 1

Je aime la suggestion de Sandor d'utiliser algorithme NEAT de Ken Stanley.

NEAT a été conçu pour évoluer avec les réseaux de neurones topologies arbitraires, mais ce ne sont que des graphiques essentiellement dirigés. Il y avait plusieurs façons d'évoluer les réseaux de neurones avant NEAT, mais l'un des Neat contributions les plus importantes est qu'il a fourni un moyen de effectuer croisement significatif entre deux réseaux différents qui ont toplogies .

Pour ce faire, les utilisations NLFA marquages ??historiques attaché à chaque gène de « ligne » les gènes des deux génomes lors croisement (appeler un biologistes de processus synapse ). Par exemple:

_{(source: natekohl.net )}

(Dans cet exemple, chaque gène est une boîte et représente une connexion entre deux noeuds. Le nombre au-dessus de chaque gène est le marquage de l'historique de ce gène.)

En résumé :. Doublure des gènes à base de marques historiques est une façon ordonnée effectuer croisée entre les deux réseaux sans analyse topologique coûteux

Answer 2

Vous pourriez aussi bien essayer de programmation génétique. Un graphique serait le plus proche d'un arbre et GP utilise des arbres ... si vous voulez continuer à utiliser à la place des médecins généralistes AGs alors jetez un oeil à la façon dont croisement est effectué sur un GP et qui pourrait vous donner une idée de l'exécuter sur les graphiques de votre GA:

_{(source: geneticprogramming.com )}

Voici comment croisement pour les arbres (et graphiques) fonctionne:

1. Vous sélectionnez 2 spécimens pour l'accouplement.
2. Vous choisissez un nœud aléatoire d'un parent et l'échanger avec un nœud aléatoire dans l'autre parent.
3. Les arbres qui en résultent sont les descendants.

Answer 3

Comme d'autres l'ont dit, d'une manière commune aux graphes croisés (ou des arbres) dans un GA est de sous-graphes d'échange (de) sous-arbres. Pour mutation, il suffit de changer au hasard quelques-uns des nœuds (w / faible probabilité).

Par ailleurs, si vous représentez un graphique comme une matrice de contiguïté, alors vous pourriez échanger / éléments muter dans les matrices (un peu comme l'aide d'une chaîne de bits à deux dimensions).

Answer 4

Je ne sais pas si vous utilisez un bitstring est la meilleure idée, je préfère représenter au moins les poids avec des valeurs réelles. Néanmoins bitstrings peut également.

Si vous avez une topologie fixe, alors à la fois croisement et la mutation sont assez faciles (en supposant que les évoluez poids du réseau):

Crossover: prendre quelques poids d'un parent, le reste de l'autre, peut être très facilement fait si vous représentez les poids comme un tableau ou d'une liste. Pour plus de détails ou voir des alternatives http://en.wikipedia.org/wiki/Crossover_% 28genetic_algorithm% 29 .

Mutation:. Il suffit de sélectionner quelques-uns des poids et les ajuster légèrement

Évoluer d'autres choses (par exemple la fonction d'activation) est assez similaire à ceux-ci.

Si vous souhaitez également faire évoluer la topologie, les choses deviennent beaucoup plus intéressant. Il y a pas mal de possibilités de mutation supplémentaires, comme l'ajout d'un noeud (très probablement relié à deux noeuds déjà existants), le fractionnement d'une connexion (au lieu de A> B ont A-> C-> B), l'ajout d'une connexion ou les contraires de ceux-ci.

Mais croisement ne sera pas trop facile (au moins si le nombre de noeuds est pas fixe), parce que vous voudrez probablement trouver des noeuds « correspondants » (où l'appariement peut être quelque chose, mais être probablement liée à un même « rôle », ou un lieu similaire dans le réseau). Si vous voulez aussi le faire, je vous recommande vivement d'étudier les techniques déjà existantes. Que je connais et comme est appelé NEAT. Vous pouvez trouver quelques informations à ce sujet sur
http://en.wikipedia.org/wiki/Neuroevolution_of_augmenting_topologies
http://nn.cs.utexas.edu/?neat
et http://www.cs.ucf.edu/~kstanley/neat.html

Answer 5

Eh bien, je n'ai jamais joué avec une telle mise en œuvre, mais éventuellement pour multisegment vous pouvez choisir une branche de l'un des graphiques et échanger avec une branche d'un autre graphique.
Pour mutation, vous pouvez changer au hasard un nœud à l'intérieur du graphique, avec faible probabilité.