Algoritmi evolutivi: ripartizioni ottimali della ripopolazione

Question

È davvero tutto nel titolo, ma ecco una ripartizione per chiunque sia interessato agli algoritmi evolutivi:

In un EA, la premessa di base è che si genera casualmente un certo numero di organismi (che in realtà sono solo insiemi di parametri), li si esegue contro un problema e si lascia sopravvivere i migliori.

Quindi ripopoli con una combinazione di incroci dei sopravvissuti, mutazioni dei sopravvissuti e anche un certo numero di nuovi organismi casuali.

Fallo diverse migliaia di volte e sorgono organismi efficienti.

Alcune persone fanno anche cose come introdurre più " isole " di organismi, che sono popolazioni separate che possono incrociarsi una volta ogni tanto.

Quindi, la mia domanda è: quali sono le percentuali ottimali di ripopolamento?

Ho mantenuto i primi 10% di performer e ripopolato con il 30% di incroci e il 30% di mutazioni. Il restante 30% è destinato a nuovi organismi.

Ho anche provato la teoria delle isole multiple e mi interessano anche i tuoi risultati.

Non mi perdo che questo è esattamente il tipo di problema che un EA potrebbe risolvere. Sei a conoscenza di qualcuno che lo sta provando?

Grazie in anticipo!

Answer 1

Inizialmente ho provato a modellare ciò che pensavo fossero i sistemi organici. Alla fine decise che non andava bene e diventò più aggressivo, con il 10% mantenuto, il 20% mutato, il 60% incrociato e il 10% casuale.

Poi ho notato che il mio 10% superiore era praticamente identico. Quindi ho aumentato il casuale al 30%. Ciò ha aiutato alcuni, ma non molto.

Ho provato l'isola multipla e il salto di generazione e il reseeding, che hanno dato risultati migliori, ma ancora molto insoddisfacenti, una variazione molto piccola nel 10% superiore, un numero folle di generazioni per ottenere risultati. Principalmente il codice ha imparato come incidere la mia valutazione di idoneità.

È davvero facile ottenere i migliori, quindi non preoccuparti di tenerne troppi in giro. Gli incroci aiutano a ridurre i tratti positivi e negativi, quindi sono utili, ma davvero quello che vuoi ottenere è un sacco di buoni casuali generati. Concentrati sulle mutazioni e sui nuovi random per portare funzionalità, e lascia che gli incroci e le migliori prestazioni basta tenere traccia dei migliori e perfezionarli più lentamente. IE: roba basata sull'ultima generazione è solo trovare un massimo locale migliore, i randoms trovano un massimo globale migliore.

Credo ancora che si possano trovare risposte ottimali alla tua domanda osservando fenomeni naturali, come in un recente articolo riguardante la casualità delle rotte di volo della mosca della frutta, in modo che ciò possa sfuggire.

Probabilmente la risposta migliore è semplicemente eseguirla e modificarla, non aver paura di modificarla abbastanza pesantemente, le popolazioni sono robuste. Assicurati di implementare un modo per salvare e continuare.

Answer 2

Le migliori risorse che ho trovato per GA ed EA sono stati i libri di John Koza su Programmazione genetica . Tratta in profondità l'argomento: tecniche per codificare il genoma, mutazione casuale, riproduzione, messa a punto della funzione fitness.

Personalmente ho scritto solo una manciata di simulatori per scopi pedagogici. Quello che ho scoperto è che il modo in cui ho sintonizzato quelle percentuali era correlato ai dettagli della funzione di fitness che stavo usando, quanta mutazione casuale avevo introdotto e quanto "intelligente" avevo cercato di effettuare la mutazione e l'allevamento - ho scoperto che meno 'intelligente' ho provato a rendere il mutatore e la logica del crossover, più velocemente la popolazione ha migliorato il suo punteggio di fitness - ho anche scoperto di essere stata troppo conservatrice nella probabilità di mutazione - le mie corse iniziali hanno raggiunto i massimi locali e avevano un è difficile uscirne.

Niente di tutto ciò ti dà risposte concrete, ma non credo che ci siano risposte concrete, GA è imprevedibile per sua natura e la messa a punto di questi tipi di parametri potrebbe essere ancora un po 'un'arte. Ovviamente potresti sempre provare un meta-GA, usando quei parametri come cromosoma, cercando impostazioni che producano un fitness più rapido nella GA di base che stai correndo.

Dipende da come 'meta' vuoi ottenere.

Answer 3

Questo è un argomento molto dibattuto (in letteratura e Melanie, et al books ) argomento che sembra essere molto specifico per il dominio. Ciò che funziona per un problema di un tipo con n parametri non funzionerà quasi mai per un altro problema, un altro dominio o un altro set di parametri.

Quindi, come suggerito da TraumaPony, modificalo tu stesso per ogni problema che stai risolvendo o scrivi qualcosa per ottimizzarlo. La cosa migliore che puoi fare è tenere traccia di tutto il tuo " manopola-twiddling " e perfezionare gli esperimenti in modo da poter mappare il terreno della soluzione e avere un'idea di come ottimizzare rapidamente all'interno di quello spazio. Prova anche tecniche alternative come l'arrampicata in collina in modo da poter avere una base da battere.

@Kyle Burton: i tassi di crossover vs. mutazione sono anche costantemente dibattuti in ogni classe di problemi consegnati a GA e medici generici.

Answer 4

Supponendo che tu abbia un metodo per quantificare i migliori X% percento di performer, suggerirei che invece di usare una soglia hard coded analizzi la distribuzione delle prestazioni e porti il ??cutoff da qualche parte nell'intervallo del primo grande calo delle performance, e quindi sintonizzare i crossbread, le mutazioni e i nuovi organismi per colmare le lacune. In questo modo se hai un valore molto "produttivo" In una serie di variazioni che hanno avuto successo, non lanci un numero significativo di alte prestazioni. Inoltre, se hai un "improduttivo" In questo modo è possibile eliminare più organismi esistenti a favore di altri organismi più nuovi che dovrebbero prendere il loro posto.

Answer 5

Ho avuto un certo successo nell'aumentare la diversità della popolazione impostando mutazioni e crossover da un paio di geni dei cromosomi genitori.

Funziona fino a quando il tasso di mutazione non scende a zero; poiché è probabile che ci sarà una pressione evolutiva periodica per farlo, dovresti cercare di assicurarti che questi geni abbiano un tasso minimo.

In pratica, ho optato per un genotipo multi-cromosoma. Un cromosoma codificato per la funzione riproduttiva dell'altro. Il "cromosoma di riproduzione" più piccolo aveva un tasso fisso sensibile per mutazione e crossover.

Ho scoperto che questo avrebbe fermato l'altopiano classico e la convergenza della popolazione.

Per inciso, tendo a fare sia il crossover che la mutazione per ogni bambino.

Per le GA generazionali, provo a evitare del tutto l'elitarismo, ma dove popolando da più isole, mantengo l'élite superiore di ogni isola. Quando le isole si uniscono, allora le élite possono riprodursi tutte insieme.

Answer 6

Sembrano esserci alcune risposte che suggeriscono di usare un 2o GA per determinare i parametri ottimali per il 1o GA, senza menzione di come determinare i parametri ottimali per il 2o. Non posso fare a meno di chiedermi quali siano le credenze religiose di coloro che suggeriscono questo approccio ...

Answer 7

Come altri hanno già detto, il mix ottimale dipenderà dal tuo problema specifico e da altri fattori specifici del problema come la dimensione dello spazio della soluzione.

Prima di discutere la ripartizione dell'evoluzione da una generazione all'altra, è importante considerare le dimensioni di ogni generazione. Generalmente il mio approccio è quello di iniziare con una popolazione abbastanza grande (~ 100k-500k individui) di individui abbastanza diversi, cosa che Koza suggerisce in alcuni dei suoi lavori. Per ottenere questa diversità dall'inizio, è possibile dividere lo spazio della soluzione in bucket e quindi assicurarsi che almeno un determinato numero di individui cada in ciascun bucket. (Ad esempio, se hai una rappresentazione ad albero per ogni individuo, assicurati che vengano create quantità uguali di profondità 2, 3, ..., max_depth)

Per quanto riguarda la tua vera domanda, non esiste un modo chiaro per affrontarla, ma a seconda del tuo problema, potresti voler enfatizzare la casualità o de-enfatizzarla. Quando vuoi enfatizzarlo, dovresti mantenere intatti meno individui e introdurre un numero maggiore di nuovi individui casuali. In genere, ti piacerebbe farlo se ci sono molti massimi locali nel tuo spazio della soluzione e vuoi avere una ricerca più ampia.

Quando ottieni una suddivisione ci sono alcune cose da considerare ... per una, la duplicazione (un sacco di individui identici o appena identici nella consanguineità superiore). Per ridurlo, potresti voler spazzare la tua popolazione tra generazioni e sostituire i duplicati con nuovi individui casuali o incrociati.

Detto questo, il mio approccio attuale è quello di mantenere il 1% superiore, incrocio il 20% superiore in un nuovo 20%, incrocio il 40% superiore nel 20% successivo, incrocio il 90% superiore per generare il 20% successivo e genera casualmente il resto (39%). Se ci sono duplicati, li rimuovo e li sostituisco con nuovi individui casuali.

Non uso le mutazioni perché l'alto numero di individui casuali dovrebbe occuparsi di aggiungere "mutazioni" durante l'incrocio successivo.

Answer 8

Sai cosa potresti fare ... Potresti scrivere un algoritmo genetico per determinare quella distribuzione ottimale.

Ma di solito mantengo il 12% in alto e il 28% in incroci; con il 30% ciascuno per gli altri.