Algoritmi genetici
28px|left Questo articolo sembra trattare lo stesso argomento di Algoritmo genetico. Vedi anche le altre pagine da unire.
Algoritmi genetici
| Indice |
Algoritmi genetici
Un algoritmo genetico è un metodo euristico di ricerca ed ottimizzazione, ispirato al principio della selezione naturale di Charles Darwin che regola l'evoluzione biologica. Nel corso dell'esecuzione, l'algoritmo interviene a modificare ripetutamente una popolazione costituita da un certo numero di soluzioni (individui): a ciascuna iterazione, esso opera una selezione casuale di individui della popolazione corrente, impiegandoli per generare nuovi elementi della popolazione stessa, che andranno a sostituire un pari numero d'individui già presenti, e a costituire in tal modo una nuova popolazione per l'iterazione (o generazione) seguente. Tale successione di generazioni evolve verso una soluzione ottima del problema assegnato.
Gli algoritmi genetici sono applicabili alla risoluzione di un'ampia varietà di problemi d'ottimizzazione non indicati per gli algoritmi classici, compresi quelli in cui la funzione obiettivo è discontinua, non derivabile, stocastica, o fortemente non lineare.
Secondo i principi classici dell'evoluzione naturale, ogni individuo trasmette parte del suo patrimonio genetico ai propri discendenti; inoltre, sporadicamente nascono individui con caratteristiche non comprese tra quelle presenti nel corredo genetico della specie originaria, dando origine in tal modo a variazioni genetiche. Infine, gli individui con le qualità più adatte all'ambiente in cui si trovano hanno maggiori possibilità di sopravvivere e riprodursi.
La traduzione e l'estensione di tali principi, validi per i sistemi biologici, anche ai sistemi artificiali, si deve storicamente a John Holland. Dopo un non breve periodo di tempo, in cui il rilievo di tale lavoro non fu pienamente riconosciuto, l'impiego degli algoritmi genetici si è andato consolidando in ambito informatico, ingegneristico, finanziario ed ovviamente nel campo delle scienze sociali e naturali.
L'implementazione di un algoritmo genetico rispetta l'analogia esistente coi sistemi naturali, e prevede sempre alcune fasi fondamentali, che si elencano di seguito:
- una fase di selezione, in cui sono individuati gli individui da riprodurre, detti genitori, i quali contribuiscono alla generazione successiva della popolazione di soluzioni.
- una fase d'incrocio o riproduzione degli individui selezionati, in cui due genitori sono combinati in modo da formare opportunamente dei nuovi individui per la prossima generazione.
- infine, una fase di mutazione, nel corso della quale vengono apportati dei cambiamenti casuali ai genitori prima che questi possano generare nuovi individui, che pertanto avranno un patrimonio genetico di caratteri diverso da quello dei genitori.
In dettaglio, l'algoritmo evolve attraverso i seguenti punti:
- l'algoritmo comincia generando, in maniera casuale, una popolazione iniziale;
- l'algoritmo crea in seguito una sequenza di nuove popolazioni, o generazioni. In ciascuna iterazione, gli individui della popolazione corrente sono usati per creare la generazione successiva, e a questo scopo si compiono degli ulteriori passi:
- ciascun membro della popolazione corrente è valutato calcolandone il rispettivo valore di fitness (idoneità);
- si determina un opportuno ordinamento di tali individui sulla base dei valori di fitness;
- gli individui più promettenti sono selezionati come genitori;
- a partire da tali individui si genera un pari numero di individui della generazione successiva, e ciò può avvenire secondo due modalità distinte, vale a dire effettuando cambiamenti casuali su un singolo genitore – mutazione – oppure combinando opportunamente le caratteristiche di una coppia di genitori – incrocio.
- gli individui così generati vanno a sostituire i genitori consentendo la formazione della generazione successiva.
- infine, l'algoritmo s'interrompe quando uno dei criteri d'arresto è soddisfatto.
Un noto teorema, dovuto ancora a Holland, assicura che, sotto determinate ipotesi, gli individui con alti valori di fitness tendono a crescere esponenzialmente nella popolazione attraverso il meccanismo dell'incrocio, assicurando così la convergenza dell'algoritmo genetico verso una soluzione ottimale. Nel suo teorema sugli schemi (schema theorem), detto anche "teorema fondamentale degli algoritmi genetici", egli dimostra che uno schema (ossia una particolare combinazione di geni che occupano posizioni precise all'interno di un cromosoma) prolifera più rapidamente se, oltre ad avere un alto valore di fitness, contiene un piccolo numero di geni specifici non lontani l'uno dall'altro. Ciò, infatti, riduce la probabilità di distruggere lo schema durante la fase di riproduzione.
Brevi successioni di geni, che assumono particolari valori, definiscono i cosiddetti blocchi costitutivi (building blocks): favorendo l'incrocio dei cromosomi meglio adattati, in cui si riscontra statisticamente la presenza di peculiari blocchi costitutivi, l'algoritmo aumenta la probabilità che blocchi costituenti opportuni, provenienti da cromosomi diversi, si ritrovino in uno stesso cromosoma. Assumendo che l'associazione di siffatti blocchi sia dunque vantaggiosa, dovrà anche ritenersi probabile la comparsa di un cromosoma (soluzione) eccellente per il problema in esame, in un tempo ragionevole.
La dimostrazione del teorema degli schemi è basata sull'ipotesi di codifica binaria, ma Wright (1991) l'ha estesa al caso di codifica con numeri reali; lo stesso Wright ha mostrato che una codifica reale è da preferirsi nel caso di problemi continui d'ottimizzazione. Herrera e Lozano (1998) hanno poi presentato un'ampia rassegna di operatori genetici applicabili a cromosomi codificati mediante numeri reali, compresi vari tipi di operatori di crossover (incrocio).
Pertanto, il campo dei numeri reali costituisce ormai un'appropriata e consolidata forma di rappresentazione per gli algoritmi genetici in domini continui. Tuttavia, a causa di complessi fenomeni di interazione non lineare (epistaticità) tra gruppi di valori di una stringa rappresentante un individuo, non si può affermare con certezza che la combinazione di blocchi costitutivi altamente performanti sia sempre destinata a produrre individui ancora migliori. In altri termini, non sempre l'operazione genetica di crossover produce risultati accettabili, e anzi a volte accade che, a partire da due genitori estremamente promettenti, si ottenga un discendente decisamente meno valido.
Calcolo evolutivo
In questi casi, il cosiddetto calcolo evolutivo, sviluppato principalmente da David B. Fogel [Fogel D.B., Evolutionary computation: toward a new philosophy of machine intelligence, IEEE Press, NewYork, 1995], anch'esso ispirato all'evoluzione naturale ma non alla genetica, può essere impiegato con successo nelle applicazioni. Tale metodologia differisce dagli algoritmi genetici in quanto non utilizza l'operazione genetica di crossover, che invece per essi risulta imprescindibile.
Programmazione genetica
La programmazione genetica, elaborata fondamentalmente ad opera di John R. Koza [Koza J.R., Genetic programming: on the programming of computers by means of natural selection, MIT Press, Cambridge, MA, 1992], è invece un metodo per la generazione automatica di programmi, a partire da una descrizione ad alto livello del task da svolgere, e basato sul principio darwiniano della selezione naturale allo scopo di sviluppare una popolazione di programmi migliorativi nell'arco delle successive generazioni. Essa si avvale di operazioni capaci di alterare l'architettura di detti programmi e di prendere decisioni sull'uso delle subroutine, dei loop, della ricorsione e della memoria.
Da ciò si nota che la programmazione genetica costituisce in sostanza un'estensione degli algoritmi genetici al caso di popolazioni costituite da programmi di dimensione variabile; la programmazione genetica sostituisce in altri termini alla stringa di lunghezza costante, codificata in vario modo, un programma con struttura ad albero, il cui corpo (radice, nodi intermedi) è costituito da funzioni aritmetiche o logiche, mentre i nodi terminali rappresentano variabili o costanti numeriche. Pertanto la popolazione risulta ora composta da un numero opportuno di programmi, i quali mediante le operazioni genetiche di riproduzione (non è prevista alcuna mutazione) producono, in un certo numero di generazioni, il programma che risolve al meglio un problema assegnato, in forma topologica parametrizzata.
Neuroevoluzione
Infine, si denota col termine neuroevoluzione l'uso degli algoritmi genetici, o di altri metodi e tecniche evolutive, nella messa a punto delle reti neurali artificiali, per quanto riguarda sia l'architettura della rete (cioè la sua struttura intesa come numero di nodi e numero di connessioni tra i nodi stessi), sia i parametri relativi (ossia i pesi delle connessioni tra i nodi). Un metodo neuroevolutivo degno di nota è quello proposto recentemente da K. Stanley, denominato NEAT (NeuroEvolution of Augmenting Topologies), e basato su un processo di graduale incremento della complessità strutturale delle reti che si propongono di risolvere un problema assegnato (tipicamente un problema di reinforcement learning). A partire da reti estremamente semplici, in quanto completamente prive di neuroni intermedi, la procedura in questione sembra avere maggiori possibilità di determinare soluzioni efficaci e robuste rispetto a metodi analoghi, che però partono da topologie predeterminate o comunque casuali. I tre principi fondamentali su cui si basa il NEAT sono i seguenti:
1. il primo principio è l'omologia: il NEAT codifica ciascun nodo e ciascuna connessione della rete attraverso un gene. Ogni volta che una mutazione strutturale sfocia nella creazione di un nuovo gene, quel gene riceve un contrassegno numerico che lo rende permanentemente rintracciabile. Tale marcatura storica è utilizzata in seguito per verificare la conciliabilità di geni omologhi durante l'operazione di crossover, e per definire un operatore di compatibilità;
2. il secondo principio è la protezione dell'innovazione. L'operatore di compatibilità definito in precedenza è adoperato per dividere la popolazione, composta da reti neurali, in specie differenti, allo scopo di proteggere le soluzioni innovative da un'eliminazione prematura, e di prevenire l'incrocio di materiale genetico incompatibile. Tali innovazioni strutturali presentano una significativa possibilità di raggiungere il loro pieno potenziale, in quanto protette dal resto della popolazione attraverso la suddivisione in specie, cioè la creazione di nicchie o spazi riservati;
3. da ultimo, il principio secondo cui la ricerca di una soluzione dovrebbe avvenire nel più piccolo spazio possibile (inteso come numero di dimensioni), da espandere poi in maniera graduale. Cominciando il processo evolutivo da una popolazione di elementi a struttura minima, le successive mutazioni topologiche comportano l'aggiunta di nuovi nodi e connessioni alle reti, conducendo pertanto ad una crescita incrementale della popolazione stessa. Dal momento che solo le modifiche strutturali vantaggiose tendono a sopravvivere nel lungo termine, le topologie che vengono raffinate tendono ad essere le minime necessarie alla soluzione del problema assegnato.