aplicar cruce y mutación a un gráfico (algoritmo genético)

Question

Estoy jugando arround con un algoritmo genético en el que quiero desarrollar gráficos. ¿Conoces una forma de aplicar el cruce y la mutación cuando los cromosomas son gráficos?

¿O me falta una codificación para los gráficos que me permiten aplicar "crossover" y mutación "normal" sobre cadenas de bits?

muchas gracias! ¡Se agradece cualquier ayuda, incluso si no está directamente relacionada con mi problema!

Manuel

Answer 1

me gusta Sandor's suggestion de utilizar Ken Stanley NEAT algorithm.

NEAT fue diseñado para evolucionar redes neuronales con topologías arbitrarias, pero esas son básicamente gráficos dirigidos. Hubo muchas formas de evolucionar las redes neuronales antes de NEAT, pero una de las contribuciones más importantes de NEAT fue que proporcionó una forma de de realizar un cruce significativo entre dos redes que tienen diferentes topologías.

Para lograr esto, NEAT usa historical markings adjunto a cada gen para "alinear" los genes de dos genomas durante el cruce (un proceso que los biólogos llaman synapsis). Por ejemplo:

crossover with different topologies in NEAT http://natekohl.net/media/neat-crossover.png

(En este ejemplo, cada gen es una caja y representa una conexión entre dos nodos El número en la parte superior de cada gen es el histórico de marcado para ese gen..)

En resumen: alinear los genes basados ​​en marcas históricas es una forma de principio para realizar el cruce entre dos redes sin costoso análisis topológico.

Answer 2

Bueno, nunca he jugado con tal implementación, pero con el tiempo de cruce usted podría escoger una rama de uno de los gráficos e intercambiarlo con un ramal de otro gráfico.
Para la mutación, podría cambiar aleatoriamente un nodo dentro del gráfico, con poca probabilidad.

Answer 3

Es mejor que intente Genetic Programming. Un gráfico sería lo más parecido a un árbol y GP usa árboles ... si aún desea usar GA en lugar de GP, observe cómo se realiza el cruce en un GP y eso podría darle una idea de cómo llevarlo a cabo en los gráficos de su GA:

Crossover http://www.geneticprogramming.com/Tutorial/cross1.gif

Así es como cruce de árboles (y gráficos) funciona:

1. selecciona 2 muestras para el apareamiento.
2. Escoge un nodo aleatorio de uno de los padres y lo intercambia con un nodo aleatorio en el otro padre.
3. Los árboles resultantes son la descendencia.

Answer 4

Como han mencionado otros, una forma común de cruzar gráficos (o árboles) en un GA es intercambiar subgrafos (subárboles). Para la mutación, simplemente cambie aleatoriamente algunos de los nodos (con una probabilidad pequeña).

Alternativamente, si representa un gráfico como una matriz de adyacencia, entonces puede intercambiar/mutar elementos en las matrices (algo así como usar una cadena de bits bidimensional).

Answer 5

No estoy seguro si usar una cadena de bits es la mejor idea, prefiero representar al menos los pesos con valores reales. Sin embargo, las cadenas de bits también pueden funcionar.

Si tiene una topología fija, entonces ambos cruce y mutación son bastante fácil (suponiendo que sólo se evolucionan los pesos de la red):

Crossover: tomar unas pesas de uno de los padres, el resto de la otra, se puede hacer muy fácilmente si representa los pesos como una matriz o lista. Para más detalles o alternativas, vea http://en.wikipedia.org/wiki/Crossover_%28genetic_algorithm%29.

Mutación: simplemente seleccione algunos de los pesos y ajústelos ligeramente.

Evolución de algunas otras cosas (por ejemplo, la función de activación) es bastante similar a estos.

Si también desea evolucionar la topología, las cosas se vuelven mucho más interesantes. Hay algunas posibilidades de mutación adicionales, como agregar un nodo (muy probablemente conectado a dos nodos ya existentes), dividir una conexión (en lugar de A-> B tener A-> C-> B), agregar una conexión, o los opuestos de estos.

Pero el cruce no será demasiado fácil (al menos si el número de nodos no es fijo), porque es probable que desee encontrar nodos "coincidentes" (donde la coincidencia puede ser cualquier cosa, pero probablemente relacionada con una similar " rol ", o un lugar similar en la red). Si también quieres hacerlo, te recomendaría estudiar técnicas ya existentes. Uno que conozco y me gusta se llama NEAT. Usted puede encontrar algo de información acerca de ello en
http://en.wikipedia.org/wiki/Neuroevolution_of_augmenting_topologies
http://nn.cs.utexas.edu/?neat
y http://www.cs.ucf.edu/~kstanley/neat.html