Giuseppe Bruno » 9.Gli Algoritmi Genetici

Argomenti della lezione

• Introduzione
• Caratteristiche della procedura
• I passi della procedura
• Considerazioni generali

Introduzione

In termini generali un problema di ottimizzazione può essere formulato come

z = f (x)    Max!

x∈X

con

• X di insieme di soluzioni ammissibili
• z=f(x) funzione obiettivo z=f(x) da massimizzare

Una soluzione x*∈X è un massimo locale se f(x*)≥f(x) per ogni x ∈Iε(x);

Una soluzione x*∈X è un massimo globale se f(x*)≥f(x) per ogni x ∈X.

Introduzione (segue)

Problema e metodo di risoluzione

Una volta formalizzato un problema di ottimizzazione si pone il problema di individuarne le soluzioni (ottimi globali o locali).

Un metodo di risoluzione è una tecnica che consente di trovare soluzioni del problema.

Un metodo di risoluzione può essere:

• esatto se individua un ottimo globale ammissibile
• euristico se è orientato alla ricerca di una buona soluzione (ma non necessariamente ottima).

Introduzione (segue)

In presenza di problemi complessi dal punto di vista computazionale (NP-hard) nelle applicazioni è necessario ricorrere a tecniche euristiche di risoluzione.

Le tecniche costruttive sono orientate alla individuazione (costruzione) di una soluzione ammissibile.

Le tecniche migliorative o di ricerca locale partono da una soluzione ammissibile e puntano a migliorarla attraverso la applicazione iterativa di una mossa. Esse convergono in un ottimo locale.

Per migliorare la qualità delle soluzioni individuabili con queste tecniche è possibile ricorrere a tecniche cosiddette metaeuristiche.

Introduzione (segue)

Introduzione (segue)

Introduzione (segue)

La qualità della soluzione ottenibile da una tecnica di ricerca locale dipende dalla soluzione di innesto e dalla tipologia di mossa.

Per superare la “trappola” della convergenza in un minimo locale, in corrispondenza di esso, bisognerebbe individuare una procedura che consenta di accettare soluzioni peggiorative.

Caratteristiche della procedura

Gli Algoritmi Genetici sono una una tecnica metaeuristica naturale che si basa sull’analogia con i meccanismi di selezione naturale in campo genetico.

Il metodo è stato sviluppato a partire da una ricerca il cui obiettivo era quello di astrarre e spiegare i processi di adattamento dei sistemi naturali alle diverse condizioni ambientali e di progettare, quindi, sistemi software che ricalcassero i meccanismi di evoluzione di questi sistemi.

L’idea di base è quella di considerare una “popolazione” di soluzioni che evolve in accordo con un meccanismo di selezione in modo da produrre soluzioni con buoni valori della funzione obiettivo.

Caratteristiche della procedura (segue)

L’evoluzione di una popolazione è legata al processo di riproduzione. Durante la loro vita gli individui (genitori) si accoppiano producendo nuovi individui (figli) il cui patrimonio genetico è una combinazione di quello dei genitori. I figli subiscono mutazioni rispetto al patrimonio genetico ereditato dai genitori per effetto della vita di relazione e delle influenze dell’ambiente.

La legge di selezione naturale si basa sul principio che, tra gli individui generati, hanno maggiori probabilità di sopravvivere quelli che possiedono una migliore capacità di adattamento all’ambiente.

Caratteristiche della procedura (segue)

Le caratteristiche di un organismo sono determinate dai geni presenti nei suoi cromosomi. Ciascun gene può assumere alleli diversi che producono differenze delle caratteristiche associate a quel gene. (es: i piselli hanno un singolo gene che determina, in funzione dell’allele, il colore del fiore (bianco o rosa)).

L’insieme dei geni è detto genotipo. Con il termine fitness (letteralmente “forma fisica”), si intende la capacità di adattarsi ad un determinato ambiente.

L’evoluzione è un processo che altera, di generazione in generazione, le caratteristiche genetiche degli organismi in modo che possano adattarsi meglio al proprio ambiente. In altri termini, il processo di evoluzione è la progressiva selezione di individui con elevata fitness.

Caratteristiche della procedura (segue)

Gli Algoritmi Genetici simulano il processo di evoluzione partendo da una popolazione iniziale ed applicando ad essa i cosiddetti operatori genetici.

Considerando i problemi di ottimizzazione, ad un gene corrisponde una variabile decisionale e ad un allele il valore ad essa associato.

Ad un cromosoma corrisponde un insieme di variabili decisionali mentre il genotipo, ossia l’insieme dei valori assunti dai geni, è una possibile soluzione del problema.

La fitness associata ad ogni genotipo è il valore di funzione obiettivo.

Caratteristiche della procedura (segue)

Due soluzioni (genitori) si accoppiano attraverso l’applicazione di un operatore (crossover) che consente di produrre nuove soluzioni (figli) con valori delle variabili dedotti da quelli dei genitori.

Alle soluzioni così generate si applicano altri operatori genetici (mutazione, inversione,..) in modo da produrre modifiche che simulino gli effetti delle variazioni indotte dall’ambiente.

Caratteristiche della procedura (segue)

I passi della procedura

1. Codifica delle soluzioni
Si rappresenta una soluzione in termini di stringa di variabili.
2. Inizializzazione e valutazione della fitness
Si genera un insieme di possibili soluzioni che forma la popolazione iniziale e si associa a ciascuna soluzione un valore di fitness.
3. Selezione
Si selezionano coppie di soluzioni della popolazione alle quali applicare gli operatori genetici (crossover, mutazione…).
4. Generazione di nuove soluzioni
Si applicano gli operatori genetici alla coppia di soluzioni selezionate al fine di produrre nuove soluzioni.
5. Sostituzione di elementi della popolazione
Si sostituiscono le soluzioni prodotte a soluzioni presenti nella popolazione.
6. Criterio di arresto
Si applicano iterativamente i passi 3, 4 e 5 fin quando non si verifichi una condizione di arresto.

I passi della procedura (segue)

I passi della procedura (segue)

I passi della procedura (segue)

I passi della procedura (segue)

I passi della procedura (segue)

Selezione

Consiste nella scelta di due elementi della popolazione. Si può utilizzare il metodo della roulette per selezionare elementi con probabilità proporzionale alla loro fitness, in ossequio alla legge di evoluzione naturale.

Se f_i/Σf_i è il valore di fitness normalizzato associato all’elemento i, il metodo della roulette viene realizzato nel seguente modo:

• Si calcola per ciascun elemento i il valore cumulato di fitness normalizzato (vedi figura);
• Si generano due numeri casuali a e b tra 0 e 1 (0≤a≤1; 0≤b≤1);
• Si selezionano gli elementi s e t della popolazione tali che
  • F_s-1 ≤ a < F_s
  • F_t-1 ≤ b < F_t

I passi della procedura (segue)

I passi della procedura (segue)

Generazione nuove soluzioni

Alla coppia selezionata si applicano gli operatori genetici allo scopo di generare nuove soluzioni del problema.

Gli operatori più frequentemente utilizzati sono il crossover e la mutazione.

L’operatore di crossover accoppia due soluzioni (genitori) generandone altre due (figli) che presentano un patrimonio genetico e, quindi, valori delle variabili dedotti da quelli dei genitori.

La forma di implementazione del crossover dipende dalla codifica adottata per rappresentare le soluzioni.

I passi della procedura (segue)

I passi della procedura (segue)

I passi della procedura (segue)

I passi della procedura (segue)

Generazione nuove soluzioni

L’applicazione degli operatori genetici può produrre soluzioni non ammissibili. In tal caso, si può procedere in diversi modi.

Si possono modificare gli operatori genetici al fine di evitare la produzione di soluzioni non ammissibili.

Le soluzioni non ammissibili possono essere sottoposte a meccanismi di “mutazione forzata” in modo da rientrare nell’ammissibilità.

Si assegnano alle soluzioni non ammissibili delle penalità nella fitness in modo che, introdotte comunque nella popolazione, presentino bassa probabilità di selezione ed alta probabilità di essere sostituite.

I passi della procedura (segue)

Sostituzione di elementi della popolazione

La popolazione evolve attraverso il progressivo rinnovo dei suoi elementi, ovvero introducendo gli individui generati in sostituzione di individui già presenti (in generale si tende a mantenere inalterata la dimensione della popolazione).

Una popolazione di n elementi può essere aggiornata in modo totale o parziale. Nel primo caso tutti gli n elementi sono sostituiti da nuovi elementi. L’aggiornamento parziale consiste, invece, nella sostituzione di n‘<n elementi.

L’aggiornamento può essere effettuato in diversi modi. Ad esempio, si può confermare la presenza di elementi con i migliori valori di fitness e provvedere alla sostituzione degli altri.
In alternativa si possono sostituire individui già presenti, introducendo i figli al posto dei genitori o al posto degli elementi con i peggiori valori di fitness.

I passi della procedura (segue)

Criterio di arresto

Un algoritmo genetico converge quando gli individui della popolazione divengono più o meno simili. Al verificarsi di questa condizione l’operatore di crossover in pratica non è in grado di produrre nuove soluzuoni e l’algoritmo esplora un sottoinsieme limitato dello spazio delle soluzioni.

Un criterio di arresto può essere dato da una qualche misura della varietà della popolazione presente (es: varianza della fitness). In alternativa, si può fissare un numero prestabilito di iterazioni o un certo numero di iterazioni nel corso delle quali la soluzione migliore della popolazione è rimasta la stessa.

La soluzione all’interno della popolazione finale che presenta il miglior valore di funzione obiettivo è assunta come soluzione finale dell’algoritmo.

I passi della procedura (segue)

Criterio di arresto

Nel corso dello sviluppo dell’algoritmo si può verificare un fenomeno di “convergenza prematura“. In pratica, dopo un certo numero di iterazioni, la popolazione potrebbe risultare formata da individui molto simili con scarsa variabilità del patrimonio genetico. In questo caso l’algoritmo non riesce più ad individuare soluzioni migliori effettuando, così, iterazioni improduttive.

Per evitare questo fenomeno si possono introdurre forzatamente meccanismi che assicurino un certo grado di varietà nella popolazione alterando, ad esempio, il patrimonio genetico relativo ad un sottoinsieme della popolazione o modificando l’espressione della fitness in modo da accentuare diversità esistenti tra elementi della popolazione.

Considerazioni generali

Considerazioni generali (segue)

Caratteristiche generali della procedura

In alcune applicazioni produce soluzioni molto buone.

Presenta una elevata flessibilità intesa come capacità di adattamento per la risoluzione di problemi diversi.

L’implementazione è molto semplice.

Non risulta molto sensibile alla scelta dei parametri di calibrazione.

I tempi di calcolo dipendono dal criterio di arresto.

La convergenza prematura avviene molto frequentemente.

Risultano più efficaci nella soluzione di problemi poco vincolati.