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

Question

Estoy jugando con cerca de un Algoritmo Genético en la que quiero evolucionar gráficos. ¿Sabe usted una forma de aplicar cruce y mutación, cuando los cromosomas son gráficos?

O me estoy perdiendo una codificación para los gráficos que me permiten aplicar cruzado "regular" y la mutación sobre cadenas de bits?

gracias mucho! Cualquier ayuda, incluso si no está directamente relacionado con mi problema, es apreciado!

Manuel

Answer 1

de Sandor sugerencia de la utilización de Ken Stanley NEAT algoritmo .

NEAT fue diseñado para evolucionar redes neuronales con topologías arbitrarias, pero esos son sólo gráficos básicamente dirigidos. Había muchas maneras de evolucionar redes neuronales antes de NEAT, pero una de las contribuciones más importantes NEAT era que proporcionaba una forma de realizar cruzado significativa entre dos redes que tienen diferentes toplogies .

Para lograr esto, los usos NEAT marcas históricos unido a cada gen a "line up" los genes de dos genomas durante cruzado (un proceso biólogos llaman sinapsis ). Por ejemplo:

_{(fuente: natekohl.net )}

(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 . La alineación de los genes sobre la base de las marcas históricas es una forma de principios para realizar cruce entre dos redes sin un análisis topológico caro

Answer 2

Es lo mismo que tratar genética Programación . Un gráfico sería lo más parecido a un árbol y GP utiliza árboles ... si aún desea utilizar gas en lugar de los médicos luego tomar un vistazo a la forma de cruce se realiza en un GP y que le puede dar una idea de cómo llevarla a cabo en los gráficos de su GA:

_{(fuente: geneticprogramming.com )}

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

1. selecciona 2 muestras para el apareamiento.
2. Usted escoge un nodo de azar de uno de los padres e intercambiarlo con un nodo de azar en el otro padre.
3. Los árboles resultantes son la descendencia.

Answer 3

Como otros han mencionado, una forma común de gráficos transversales (o árboles) en una GA es subgraphs de intercambio (subárboles). Por mutación, simplemente al azar cambiar algunos de los nodos (w / pequeña probabilidad).

Alternativamente, si se está representando en una gráfica como una matriz de adyacencia, entonces es posible intercambiar / elementos mutar de las matrices (tipo de como el uso de una cadena de bits de dos dimensiones).

Answer 4

No estoy seguro de si se utiliza una cadena de bits es la mejor idea, prefiero representan al menos los pesos con valores reales. Sin embargo cadenas de bits puede también trabajo.

Si tiene una topología fija, entonces ambos cruce y mutación son bastante fáciles (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 usted representa los pesos como una matriz o lista. Para más detalles o alternativas ver http://en.wikipedia.org/wiki/Crossover_% 28genetic_algorithm% 29 .

Mutación:. Sólo tiene que seleccionar algunos de los pesos y ajustar ligeramente

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

Si usted también quiere evolucionar la topología entonces las cosas se vuelven mucho más interesante. Hay bastantes algunas posibilidades de mutación adicionales, como la adición de un nodo (lo más probable conectado a dos nodos ya existentes), la división de una conexión (en lugar de A-> B tienen A-> C-> B), la adición de una conexión, o los opuestos de estos.

Pero cruce no será demasiado fácil (al menos si el número de nodos no es fijo), ya que probablemente tendrá que encontrar nodos de "igualación" (donde juego puede ser cualquier cosa, pero es probable que estar relacionado con un semejante papel" ", o un lugar similar en la red). Si también quieres hacerlo lo recomiendo mucho el estudio de las técnicas ya existentes. Uno que conozco y como se llama NEAT. Usted puede encontrar algo de información al respecto 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

Answer 5

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 mutación podría cambiar al azar un nodo dentro de la gráfica, con la pequeña probabilidad.