Scarsa randomizzazione nel Genetic Algorithm Framework

Qualcuno ha visto risultati convincenti dal .Net Genetic Algorithm Framework?Scarsa randomizzazione nel Genetic Algorithm Framework

Sto riscontrando una scarsa randomizzazione nella demo del Problema del venditore ambulante fornita con il Genetic Algorithm Framework. La seguente chiamata genera lo stesso gene order casuale in tutto il x 100 seme popolazione cromosoma:

chromosome.Genes.ShuffleFast();

Se solo passo attraverso il codice dell'ordine gene sembra casuale, quindi, ho il sospetto c'è un tempo/Rdn() bug in ShuffleFast() oppure sto trascurando un passaggio di installazione.

Ho cercato di aggirare il problema rimescolando le sequenze di geni del cromosoma e questo ha prodotto un piccolo cambiamento nei risultati del TSP. Tuttavia, il log della console della corsa mostra ancora il GAF che scopre solo 4 potenziali soluzioni su 400 generazioni di popolazione. Ciò è in disaccordo con i video di YouTube di GA che mostrano implementazioni di algoritmi genetici in arrivo su una soluzione suggerita con un sacco di jitter. Cito questo come un'ulteriore indicazione che il GAF ha un problema interno sistemico con generazione di numeri casuali.

L'Algorithm Framework genetico è molto ben documentato tramite il blog degli autori, quindi sto cercando di mantenere una mente aperta come motivo.

Passaggi per la riproduzione = Scarica GAF da nuget, compilare & eseguire il debug del progetto predefinito con un punto di interruzione dopo aver creato i loop per il ciclo, ispezionare la popolazione.Soluzioni. Windows 7, VS2015, .Net 4.5 & 4.61. Debug o Release.

fonte

2015-12-30 camelCase

Puoi pubblicare altro codice per mostrare il contesto di questa chiamata. Ci possono essere problemi con i generatori di numeri casuali se non sono inizializzati correttamente. – ChrisF

@ChrisF I meccanismi interni della routine ShuffleFast() si trovano all'interno della libreria GAF, che a mio avviso è closed source. L'autore della biblioteca dovrebbe rispondere, è attivo su SO. Fino ad allora cercherò un'altra libreria GA. La chiamata di ShuffleFast() viene eseguita 100 volte in un ciclo stretto su un elenco di 16 numeri interi, se si interrompe manualmente e F10 all'interno di quel ciclo i risultati di Shuffle appaiono casuali. – camelCase

"La chiamata ShuffleFast() viene eseguita 100 volte in un ciclo stretto su un elenco di 16 numeri interi," - Probabilmente è la causa del problema.Sembra che il generatore di numeri casuali sia inizializzato ogni iterazione del ciclo. Entrare nel debugger lo rallenta abbastanza da darti risultati casuali. È necessario inizializzare il generatore una volta fuori dal ciclo. – ChrisF

Guardando il codice in un disassembler, ci sono due versioni di ShuffleFast definiti come metodi di estensione: si prende un oggetto Random come parametro e l'altro crea uno nuovo utilizzando il default constructor e utilizza tale. Sono altrimenti identici, facendo un rimescolamento standard di Fisher-Yates.

quindi è necessario costruire il proprio Random e poi passarlo in:

Random r = new Random(); 
... 
chromosome.Genes.ShuffleFast(r); 
otherChromosome.Genes.ShuffleFast(r); 
...

In questo modo hai solo un flusso di numeri casuali, e tale flusso è seminato basa sull'ora corrente ogni volta che si esegui il tuo programma.

fonte

2015-12-30 15:00:41

Ho seguito il tuo consiglio usando il sovraccarico ShuffleFast (Random r) con r dichiarato al di fuori del loop della popolazione del cromosoma. Ora la popolazione seme ha sequenze di geni casuali. L'output del test appare ancora strano, con solo poche modifiche alla distanza del tour in città per 400 generazioni. Il mio prossimo passo sarà quello di trasferire i dati del test GAF in un framework GA .Net alternativo per verificare se l'algoritmo si trova progressivamente in una migliore risposta. Contrassegnerò la tua risposta come risposta accettata se l'autore del GAF non offre una descrizione più approfondita dei risultati dei test di runtime. – camelCase

Ci scusiamo per la risposta tardiva alla domanda. Il problema è davvero con il GAF. Il metodo Shuffle utilizza un generatore di numeri System.Random e ne crea uno nuovo ogni volta che viene chiamato il metodo. Ciò causa problemi dovuti alla semina. Ho risolto questo (stasera) nel GAF e questo sarà nella prossima versione. Suggerisco che il seguente codice viene utilizzato come soluzione alternativa.

var rnd = GAF.Threading.RandomProvider.GetThreadRandom(); 
myList.ShuffleFast (rnd);

Ogni generatore di numeri casuali creato utilizzando il codice precedente crea un generatore di numeri casuali con un seme singe per thread. Questo può quindi essere passato al metodo Shuffle() come descritto da Matteo.

fonte

2016-01-08 23:05:08

Scarsa randomizzazione nel Genetic Algorithm Framework

risposta

Problemi correlati