Algoritmi genetici

Question

Sto cercando di implementare un algoritmo genetico che calcolerà il minimo del Rastrigin functon e sto riscontrando alcuni problemi.
Ho bisogno di rappresentare il cromosoma come una stringa binaria e come la funzione di Rastrigin prende un elenco di numeri come parametro, come può decodificare il cromosoma in una lista di numeri?
Anche il Rastrigin vuole che gli elementi nell'elenco siano -5.12 < = x (i) < = 5.12 cosa succede se quando genero il cromosoma produrrà il numero non in quell'intervallo?

Answer 1

Stai cercando di implementare un algoritmo genetico. La tua implementazione dovrebbe essere tale che funzioni per qualsiasi problema di minimizzazione (o massimizzazione) generica e non solo la funzione Rastrigin. Potresti decidere di implementare un GA codificato in binario o un GA con codice reale. Entrambi hanno i propri usi e applicazioni di nicchia. Ma per te, vorrei suggerire di implementare un GA con codice reale. In base alla tua domanda su cosa fare, se i valori delle variabili generate sono al di fuori di [-5.12: 5.12], un GA con codice reale e codice binario in codice binario li gestiranno in modo diverso.

Avere un codice di riferimento è sempre buono prima di iniziare a implementare la propria versione. Se stai cercando un'implementazione C, il laboratorio source section ha un'implementazione Real Coded GA, che è ampiamente utilizzata da noi e da altri per il nostro lavoro di ricerca. Ti suggerirei di giocarci e provare alcuni dei semplici problemi di ottimizzazione dati lì.

Pyevolve è una libreria Python per Algoritmi Genetici e Programmazione Genetica.

Ora che abbiamo parlato delle implementazioni, è chiara la tua comprensione dell'AG? In caso contrario, fare riferimento a questo tutorial, che introduce GA dal punto di vista dell'ottimizzazione. Si noti che la spiegazione del crossover e della mutazione per un GA codificato in codice binario non viene trasferita automaticamente ad un GA codificato reale. La vera codifica GA ha le sue complessità, che ti serviranno tempo per leggere alcuni documenti e capirli.Nessun affronto, ma con uno sforzo a tempo pieno dovresti essere in grado di andare avanti facilmente.

Answer 2

Suppongo che tu stia programmando in C. Interi (int per il linguaggio C) può essere impacchettato come una matrice di 4 byte/carattere (32 bit). quindi se il vostro array è

char* chrom_as_bytes=(...) 

tuo possibile ottenere il valore i-esimo lanciando a int *

int ith=3; 
value=((int*)chrom_as_bytes)[ith]; 

se un valore non è nel range -5,12 < x < 5.12 rispetto, la vostra la funzione di idoneità dovrebbe restituire un valore molto negativo e questo passo nell'evoluzione dovrebbe essere scartato alla prossima generazione.

Vedere anche l'articolo in Wikipedia.

Answer 3

Perché è necessario rappresentare il cromosoma come stringa binaria? Puoi scrivere algoritmi evolutivi che usano altri tipi. Potresti usare una lista di numeri.

Per quanto riguarda la limitazione dei valori, quando si generano i membri iniziali della popolazione assicurarsi che i numeri casuali rientrino nell'intervallo di cui si ha bisogno. Limita il tuo operatore di mutazione per evitare di produrre valori al di fuori di questo intervallo (potresti solo troncare valori che sono al di fuori di questo intervallo, oppure potresti averli avvolti).

Se davvero si deve usare una stringa binaria, dare un'occhiata a Gray Code, che è un modo di codificare valori numerici in binario rendendoli più suscettibili alle mutazioni.

Answer 4

Se sei interessato, ho eseguito un'implementazione utilizzando Pyevolve: http://pyevolve.sourceforge.net/examples.html#example-7-the-rastringin-function Ci scusiamo per il refuso nel nome.

Answer 5

La codifica di soluzioni di problemi con valori reali come una stringa di bit non è davvero la strada da percorrere. Quando hai numeri come stringhe di bit, stai usando numeri a virgola fissa per rappresentare i numeri. Una volta che l'algoritmo sarà vicino all'ottimale, fino alla precisione della codifica a punto fisso, non farà ulteriori progressi. Puoi usare più bit, ma poi avrai una convergenza più lenta. In pratica, in caso di problemi gravi, tale approccio è più lento di molti ordini rispetto a un algoritmo competente che lavora su valori in virgola mobile.

L'utilizzo di numeri in virgola mobile consente di avvicinarsi molto all'ottimale, ad esempio 1e-10, mentre si utilizzano i tipici numeri a 64 bit. Inoltre, l'algoritmo evolutivo moderno utilizza uno schema adattivo per regolare la fase di mutazione durante l'ottimizzazione. Tale meccanismo consente una maggiore velocità di convergenza, rispetto a una fase di mutazione fissa. Controlla questo per vedere quali tipici ottimizzatori evolutivi ottengono sulla funzione Rastrigin: http://coco.gforge.inria.fr/doku.php?id=bbob-2010