Algoritmo evolutivo cellulare - Cellular evolutionary algorithm
Un algoritmo evolutivo cellulare ( cEA ) è una sorta di algoritmo evolutivo (EA) in cui gli individui non possono accoppiarsi arbitrariamente, ma ognuno interagisce con i suoi vicini più stretti su cui viene applicato un EA di base (selezione, variazione, sostituzione).
Il modello cellulare simula l'evoluzione naturale dal punto di vista dell'individuo, che codifica per un tentativo di soluzione del problema (ottimizzazione, apprendimento, ricerca). L'idea essenziale di questo modello è fornire alla popolazione EA una struttura speciale definita come un grafo connesso, in cui ogni vertice è un individuo che comunica con i suoi vicini più prossimi. In particolare, gli individui sono concettualmente inseriti in una rete toroidale e possono ricombinarsi solo con individui vicini. Questo ci porta a una sorta di località nota come isolamento dalla distanza . L'insieme dei potenziali compagni di un individuo è chiamato il suo vicinato . È noto che, in questo tipo di algoritmo, individui simili tendono a raggrupparsi creando nicchie, e questi gruppi operano come se fossero sotto-popolazioni separate (isole). In ogni caso, non esiste una chiara linea di confine tra gruppi adiacenti e le nicchie vicine potrebbero essere facilmente colonizzate da nicchie competitive e forse unire i contenuti della soluzione durante il processo. Allo stesso tempo, le nicchie più lontane possono essere interessate più lentamente.
introduzione
Un algoritmo evolutivo cellulare (cEA) solitamente evolve una griglia bidimensionale strutturata di individui, sebbene siano possibili anche altre topologie. In questa griglia, gruppi di individui simili vengono creati naturalmente durante l'evoluzione, promuovendo l'esplorazione nei loro confini, mentre lo sfruttamento viene eseguito principalmente dalla concorrenza diretta e dalla fusione al loro interno.
La griglia è solitamente una struttura toroidale 2D, sebbene il numero di dimensioni possa essere facilmente esteso (a 3D) o ridotto (a 1D, ad esempio un anello). Il quartiere di un punto particolare della griglia (dove è posizionato un individuo) è definito in termini di distanza di Manhattan da esso ad altri nella popolazione. Ogni punto della griglia ha un quartiere che si sovrappone ai quartieri delle persone vicine. Nell'algoritmo di base, tutti i dintorni hanno la stessa dimensione e forme identiche. I due quartieri più comunemente usati sono L5, chiamato anche Von Neumann o NEWS (Nord, Est, Ovest e Sud), e C9, noto anche come quartiere di Moore . Qui, L sta per Linear mentre C sta per Compact .
Nelle cEA, gli individui possono interagire solo con i loro vicini nel ciclo riproduttivo in cui vengono applicati gli operatori di variazione. Questo ciclo riproduttivo viene eseguito all'interno del vicinato di ogni individuo e, generalmente, consiste nel selezionare due genitori tra i suoi vicini secondo un certo criterio, applicando loro gli operatori di variazione (ricombinazione e mutazione ad esempio), e sostituendo l'individuo considerato con il prole di recente creazione seguendo un determinato criterio, ad esempio, sostituire se la prole rappresenta una soluzione migliore dell'individuo considerato.
Sincrono contro asincrono
In una cEA sincrona regolare , l'algoritmo procede dal primo individuo in alto a sinistra verso destra e poi verso le diverse righe utilizzando le informazioni nella popolazione per creare una nuova popolazione temporanea. Dopo aver terminato con l'ultimo individuo in basso a destra, la popolazione temporanea è piena degli individui appena calcolati e inizia la fase di sostituzione. In esso, la vecchia popolazione viene sostituita completamente e in modo sincrono con quella appena calcolata secondo qualche criterio. Di solito, il sostituto mantiene l'individuo migliore nella stessa posizione di entrambe le popolazioni, cioè si usa l'elitarismo.
Dobbiamo notare che secondo la politica di aggiornamento della popolazione utilizzata, potremmo anche definire un cEA asincrono . Questo è anche un problema ben noto negli automi cellulari . Nelle cEA asincrone l'ordine in cui gli individui nella griglia vengono aggiornati cambia a seconda del criterio utilizzato: sweep di linea, sweep casuale fisso, nuovo sweep casuale e scelta uniforme. Questi sono i quattro modi più comuni per aggiornare la popolazione. Tutti continuano a usare immediatamente l'individuo appena calcolato (o l'originale se migliore) per i calcoli dei suoi vicini. Questo fa sì che la popolazione si mantenga in ogni momento individuo in diversi stati di evoluzione, definendo una nuova linea di ricerca molto interessante.
La sovrapposizione dei quartieri fornisce un meccanismo implicito di migrazione della soluzione al cEA. Poiché le migliori soluzioni si diffondono senza problemi in tutta la popolazione, la diversità genetica nella popolazione viene preservata più a lungo rispetto agli EA non strutturati. Questa morbida dispersione delle migliori soluzioni attraverso la popolazione è uno dei problemi principali del buon compromesso tra esplorazione e sfruttamento che i cEA eseguono durante la ricerca. È quindi facile vedere che potremmo regolare questo compromesso (e quindi sintonizzare il livello di diversità genetica lungo l'evoluzione) modificando (ad esempio) la dimensione del vicinato utilizzato, poiché il grado di sovrapposizione tra i quartieri cresce in base alla dimensione del quartiere.
Un cEA può essere visto come un automa cellulare (CA) con regole probabilistiche riscrivibili, dove l'alfabeto della CA è equivalente al numero potenziale di soluzioni del problema. Quindi, se vediamo le cEA come una sorta di CA, è possibile importare la conoscenza dal campo delle CA alle cEA, e in effetti questa è un'interessante linea di ricerca aperta.
Parallelismo
Gli EA cellulari sono molto suscettibili al parallelismo, quindi di solito si trova nella letteratura della metaeuristica parallela . In particolare, il parallelismo a grana fine può essere utilizzato per assegnare thread di esecuzione indipendenti a ogni individuo, consentendo così all'intero cEA di funzionare su una piattaforma hardware concorrente o effettivamente parallela. In questo modo, è possibile ottenere notevoli riduzioni di tempo durante l'esecuzione di cEA su FPGA o GPU .
Tuttavia, è importante sottolineare che i cEA sono un modello di ricerca, in molti sensi diverso dagli EA tradizionali. Inoltre, possono essere eseguiti su piattaforme sequenziali e parallele, rafforzando il fatto che il modello e l'implementazione sono due concetti diversi.
Vedere qui per una descrizione completa dei fondamenti per la comprensione, la progettazione e l'applicazione dei cEA.
Guarda anche
- Automa cellulare
- Evoluzione in doppia fase
- Enrique Alba
- Algoritmo evolutivo
- Metaeuristico
- Metaeuristica parallela
Riferimenti
- E. Alba, B. Dorronsoro, Algoritmi genetici cellulari , Springer-Verlag, ISBN 978-0-387-77609-5 , 2008
- AJ Neighbor, JJ Durillo, F. Luna, B. Dorronsoro, E. Alba, MOCell: A New Cellular Genetic Algorithm for Multiobjective Optimization, International Journal of Intelligent Systems, 24: 726-746, 2009
- E. Alba, B. Dorronsoro, F. Luna, AJ Neighbor, P. Bouvry, L. Hogie, A Cellular Multi-Objective Genetic Algorithm for Optimal Broadcasting Strategy in Metropolitan MANETs , Computer Communications, 30 (4): 685-697, 2007
- E. Alba, B. Dorronsoro, Computing Nine New Best-So-Far Solutions for Capacitated VRP with a Cellular GA , Information Processing Letters, Elsevier, 98 (6): 225-230, 30 giugno 2006
- M. Giacobini, M. Tomassini, A. Tettamanzi, E. Alba, The Selection Intensity in Cellular Evolutionary Algorithms for Regular Lattices , IEEE Transactions on Evolutionary Computation, IEEE Press, 9 (5): 489-505, 2005
- E. Alba, B. Dorronsoro, The Exploration / Exploitation Tradeoff in Dynamic Cellular Genetic Algorithms , IEEE Transactions on Evolutionary Computation, IEEE Press, 9 (2) 126-142, 2005
