Intelligenza artificiale/Algoritmi genetici

L'algoritmo genetico appartiene ad 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 algoritmi è 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.

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 ottima 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 cosi 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 restituisce 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".

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.

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 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.