Algoritmo genetico

Article on other languages:

del.icio.us del.icio.us
Digg Digg
Furl Furl
Reddit Reddit
Rojo Rojo
Add to OnlyWire

L'algoritmo genetico è un algoritmo di analisi dei dati e appartiene a una particolare classe di algoritmi utilizzati in diversi campi, tra cui l'intelligenza artificiale. È un metodo euristico di ricerca ed ottimizzazione, ispirato al principio della selezione naturale di Charles Darwin che regola l'evoluzione biologica.

Questo tipo di algoritmo è detto genetico perché mutua terminologia dalla genetica, branca della biologia.

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.

Indice

Principi di funzionamento

Un tipico algoritmo genetico parte da un certo numero di possibili soluzioni (individui) chiamate popolazione e provvede a farle evolvere nel corso dell'esecuzione: a ciascuna iterazione, esso opera una selezione 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 ottimale del problema assegnato.

La loro evoluzione viene ottenuta attraverso una parziale ricombinazione delle soluzioni, ogni individuo trasmette parte del suo patrimonio genetico ai propri discendenti, e l'introduzione di mutazioni casuali nella popolazione di partenza, sporadicamente quindi nascono individui con caratteristiche non comprese tra quelle presenti nel corredo genetico della specie originaria.

Finita la fase di evoluzione la popolazione delle soluzioni viene analizzata e vengono tenute solo le soluzioni che meglio risolvono il problema: gli individui con le qualità più adatte all'ambiente in cui si trovano hanno quindi maggiori possibilità di sopravvivere e riprodursi. Queste soluzioni subiranno una nuova fase di evoluzione e così via.

Alla fine ci si aspetta di trovare una popolazione di soluzioni che riescano a risolvere adeguatamente il problema posto. Non vi è modo di decidere a priori se l'algoritmo sarà effettivamente in grado di trovare una soluzione accettabile. Di norma gli algoritmi genetici vengono utilizzati per problemi di ottimizzazione per i quali non si conoscono algoritmi di complessità lineare o polinomiale.

Un caso particolare di applicazione di algoritmi genetici è Acovea, un software studiato per trovare il profilo migliore delle opzioni di ottimizzazione del compilatore gcc: un problema di elevata complessità.

Dettaglio del funzionamento

La soluzione del problema viene codificata in una struttura, di solito una stringa, detta gene.

Inizialmente viene creato un certo numero di geni in maniera casuale e si definisce una funzione che restituisca la "bontà" di un gene come soluzione del problema, detta funzione di fitness.

L'algoritmo consiste nell'applicazione di operazioni, che tendono a modificare la popolazione dei geni, nel tentativo di migliorarli in modo da ottenere una soluzione sempre migliore.

L'evoluzione procede quindi in passi, per ognuno di questi viene per prima cosa eseguito un ordinamento dei geni sulla base del risultato della funzione di fitness. Vengono poi eseguite le operazioni su un numero di geni stabilito dai parametri dell'algoritmo, che in generale determinano quanti geni devono subire crossover e mutazioni, e in quale misura.

L'algoritmo evolve quindi attraverso i seguenti punti:

  • generazione, in maniera casuale, una popolazione iniziale;
  • creazione di 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.

Crossover

In base a un coefficiente stabilito inizialmente, alcune parti dei geni risultati migliori vengono scambiate, nell'ipotesi che questo possa migliorare il risultato della funzione di fitness nel successivo "passo evolutivo".

Single point crossover

Single point crossover
Single point crossover

Ci sono varie tecniche di crossover. Una delle più semplice è la "single point crossover" che consiste nel prendere due individui e tagliare le loro stringhe di codifica in un punto a caso. Si creano così due teste e due code. A questo punto si scambiano le teste e le code, ottenendo due nuovi geni. Il crossover non è applicato sempre, ma con una probabilità pc. Nel caso in cui non viene applicato i figli sono semplicemente le copie dei genitori.

Sperimentalmente si può vedere che il miglioramento diventa apprezzabile solo dopo un certo numero di passi. Questo a meno di casi fortunati, ovviamente.

Mutazione

La mutazione consiste nella modifica casuale di alcune parti dei geni con valore di fitness più basso, in base a coefficienti definiti inizialmente. Queste modifiche puntano a migliorare il valore della funzione per il gene in questione.

In realtà non è corretto pensare di mutare solo i cromosomi con fitness più bassa; al fine di garantire una maggiore capacità esplorativa dell'algoritmo (e non finire in "buche" di ottimo locale) sono ritenute utili anche le mutazioni di cromosomi con valore di fitness alto. In definitiva le mutazioni servono soprattutto a esplorare lo spazio di ricerca, non hanno quindi scopo migliorativo.

Basi teoriche e storia

La traduzione e l'estensione dei principi esposti, validi per i sistemi biologici e per i sistemi artificiali, si deve storicamente a John Henry 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.

Un teorema, dovuto 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.

Programmazione Evolutiva

In questi casi, la cosiddetta programmazione evolutiva, sviluppata principalmente da David B. Fogel, anch'essa ispirata all'evoluzione naturale ma non alla genetica, può essere impiegata 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, è 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 princìpi 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.

Voci correlate

Bibliografia

  • D.B. Fogel, Evolutionary computation: toward a new philosophy of machine intelligence, IEEE Press, NewYork, 1995 ISBN 078035379X
  • J.R Koza, Genetic programming: on the programming of computers by means of natural selection, MIT Press, Cambridge, MA, 1992 ISBN 0262111705
  • Poli, R., Langdon, W. B., McPhee, N. F. (2008), A Field Guide to Genetic Programming, Lulu.com, disponibile gratuitamente via internet ISBN 978-1-4092-0073-4
  • Alden H. Wright, Genetic Algorithms for Real Parameter Optimization, 1991 [1]

Collegamenti esterni



Estratto da "http://it.wikipedia.org/wiki/Algoritmo_genetico"

This article is from Wikipedia. All text is available under the terms of the GNU Free Documentation License.

Giant Panda

Mercedes Car
James Bond Guide
This site monitored by SitePinger.net