l'applicazione di crossover e la mutazione di un grafico (algoritmo genetico)

Question

Sto giocando arround con un algoritmo genetico in cui voglio evolvere i grafici. Sapete un modo per applicare di crossover e la mutazione quando i cromosomi sono grafici?

O mi manca una codifica per i grafici che mi permetta di applicare incrociato "regolare" e la mutazione su stringhe di bit?

grazie mille! Qualsiasi aiuto, anche se non è direttamente collegato al mio problema, è apprezzato!

Manuel

Answer 1

Mi piace di Sandor suggerimento di usare di Ken Stanley NEAT algoritmo .

NEAT è stato progettato per evolvere reti neurali con topologie arbitrarie, ma questi sono solo grafi sostanzialmente orientati. C'erano molti modi per evolvere le reti neurali prima della NFTA, ma uno dei contributi della NEAT più importante era che ha fornito un modo per eseguire incrocio significativo tra due reti che hanno diversi toplogies .

Per fare questo, usi NEAT marcature storiche allegato a ogni gene a "line up" i geni di due genomi nel corso di crossover (a biologi chiamano processo sinapsi ). Ad esempio:

_{(fonte: natekohl.net )}

(In questo esempio, ciascun gene è una scatola e rappresenta una connessione tra due nodi. Il numero nella parte superiore di ciascun gene è lo storico marcatura per quel gene.)

In sintesi :. Allineando geni sulla base di segni storici è un modo di principio per eseguire crossover tra due reti senza costose analisi topologica

Answer 2

Si potrebbe anche provare a genetica programmazione . Un grafico sarebbe la cosa più vicina a un albero e GP usa alberi ... se si vuole ancora utilizzare gas al posto dei medici poi dare un'occhiata a come incrocio viene eseguita su un GP e che potrebbe dare un'idea di come eseguirla sui grafici di GA:

_{(fonte: geneticprogramming.com )}

Ecco come crossover per alberi (e grafici) funziona:

1. si seleziona 2 esemplari per l'accoppiamento.
2. si sceglie un nodo a caso da un genitore e scambiarlo con un nodo casuale l'altro genitore.
3. Gli alberi risultanti sono la prole.

Answer 3

Come altri hanno già detto, un modo comune per grafici trasversali (o alberi) in un GA è sottografi swap (sottostrutture). Per mutazione, basta cambiare in modo casuale alcuni dei nodi (w / piccola probabilità).

In alternativa, se si rappresenta un grafico come una matrice di adiacenza, allora si potrebbe scambiare / elementi mutate nelle matrici (tipo di come utilizzare una stringa di bit bidimensionale).

Answer 4

Non sono sicuro se si utilizza un bitstring è l'idea migliore, preferirei rappresentano almeno i pesi con valori reali. Tuttavia stringhe di bit può anche lavoro.

Se si dispone di una topologia fissa, sia di crossover e la mutazione sono abbastanza facili (supponendo che si evolvono solo i pesi della rete):

Crossover: prendere alcuni pesi da un genitore, il resto dalle altre, può essere facilmente fatto se voi rappresentate i pesi come un array o lista. Per maggiori dettagli o alternative vedere http://en.wikipedia.org/wiki/Crossover_% 28genetic_algorithm% 29 .

Mutazione:. È sufficiente selezionare alcuni dei pesi e regolarle leggermente

Evoluzione altre cose (per esempio funzione di attivazione) è piuttosto simile a questi.

Se si vuole anche far evolvere la topologia allora le cose diventano molto più interessanti. Ci sono piuttosto alcune possibilità di mutazione aggiuntivi, come l'aggiunta di un nodo (molto probabilmente collegato a due nodi già esistenti), la divisione di una connessione (invece di A-> B hanno A-> C> B), l'aggiunta di una connessione o gli opposti di questi.

Ma attraversamento non sarà troppo facile (almeno se il numero di nodi non è fisso), perché probabilmente vuole trovare nodi "matching" (dove di corrispondenza può essere qualsiasi cosa, ma probabilmente correlate a un simile "ruolo ", o un luogo simile nella rete). Se anche voi volete farlo mi raccomando lo studio di tecniche già esistenti. Uno che conosco e come si chiama NEAT. Potete trovare alcune informazioni su di esso a
http://en.wikipedia.org/wiki/Neuroevolution_of_augmenting_topologies
http://nn.cs.utexas.edu/?neat
e http://www.cs.ucf.edu/~kstanley/neat.html

Answer 5

Beh, non ho mai giocato con una tale implementazione, ma alla fine il cross-over si potrebbe scegliere un ramo di uno dei grafici e scambiarlo con un ramo da un altro grafico.
Per mutazione si potrebbe cambiare in modo casuale un nodo all'interno del grafico, con piccola probabilità.