Introduzione
ii
funzioni di riparazione e di penalty. Tuttavia, la loro applicazione
è successiva al problema specifico. Nell' approccio modulare, i
problemi che coinvolgono i vincoli sono risolti dal modulo del
decodificatore, che libera l'algoritmo genetico della gestione dei
vincoli. L’ algoritmo sviluppa in primo luogo un metodo veloce,
elastico e modulare per la soluzione dei problemi di set covering
e, secondo, sviluppa un metodo per soddisfare i vincoli. In questa
sede si usa un metodo modulare tri-fase. In primo luogo, la
procedura genetica trova la permutazione 'migliore' delle righe e
buoni parametri per la fase due. La procedura del decodificatore,
un semplice euristico, assegna buone colonne alle righe trovate
dall' algoritmo genetico. Infine un post-hill-climber ottimizza
tutte le soluzioni. Prima di analizzare nel dettaglio l’ algoritmo
nei primi capitoli verrà presentata un breve excursus sull’ origine
degli algoritmi genetici, la terminologia usata in questo ambito la
loro rappresentazione classica e i problemi che si posso incontrare
affrontando l’ argomento. Negli ultimi capitoli verranno invece
presentati ,innanzitutto ,il problema del set covering e
successivamente l’ algoritmo da me implementato con le relative
spiegazioni di ogni funzione usata e tabelle che illustrano i
risultati da me ottenuti.
Capitolo 1 Introduzione agli algoritmi genetici
Capitolo 1
INTRODUZIONE AGLI ALGORITMI GENETICI
1.1 Variazione genetica e selezione naturale
Gli Algoritmi Genetici (GA), proposti nel 1975 da J.H. Holland, sono un
modello computazionale idealizzato dall’evoluzione naturale darwinista.
Ogni individuo ha sue caratteristiche e proprietà specifiche, manifestate
esternamente e “visibili”, che ne costituiscono il fenotipo. È il fenotipo a
dettare le possibilità e i limiti delle interazioni dell’individuo con
l’ambiente in cui vive. Ma il fenotipo è determinato sostanzialmente
dall’invisibile patrimonio genetico o genotipo, costituito dai geni, che sono
le unità fondamentali dei cromosomi. Ad ogni gene corrisponde, in
generale, un caratteristico fenotipo. Pertanto, la sopravvivenza degli
individui con le caratteristiche più adattabili all’ambiente, significa in realtà
la sopravvivenza dei geni più adatti. I due principi fondamentali
dell’evoluzione sono la variazione genetica e la selezione naturale.
Affinché la popolazione possa evolvere, gli individui che la costituiscono
devono anzitutto avere una ricca varietà di fenotipi e quindi di genotipi. A
questo punto, scatta la selezione, che premia la sopravvivenza, la longevità
e la riproduzione degli individui meglio adattabili. I meccanismi generatori
della varietà del genotipo sono sostanzialmente due: un processo
combinatorio di geni, grazie ai diversi apporti dei genitori nell’ambito della
riproduzione sessuale, e le mutazioni genetiche casuali. Le mutazioni
producono nuovi geni, alcuni dei quali si tramandano alle generazioni
successive, mentre altre scompaiono: è il cosiddetto pool di gen (mating
pool), nel quale “pesca” la selezione naturale, che cambia continuamente. I
cambiamenti che si verificano da una generazione all’altra sono
praticamente invisibili, ma quelli positivi vanno ad accumularsi (selezione
cumulativa) e, nell’arco di migliaia di anni, danno origine a cambiamenti
macroscopici. Secondo la moderna versione degli equilibri punteggiati,
1
Capitolo 1 Introduzione agli algoritmi genetici
l’evoluzione sarebbe fortemente influenzata da eventi eccezionali ma
soprattutto avverrebbe per salti. Ciò significa che a periodi di ristagno, che
possono essere anche lunghissimi, seguono periodi di accelerazione
evolutiva relativamente brevi. Come già aveva notato Darwin, in alcuni
casi bastano periodi limitati di tempo affinché si verifichino cambiamenti
notevoli. Un esempio è costituito dalla selezione di animali domestici,
guidata dall’uomo anziché dall’ambiente, che ha prodotto nel giro di poche
migliaia di anni razze canine così diverse come ad esempio il pastore
tedesco o il bassotto. Un esempio di rapidità evolutiva ancora maggiore è
quello verificatosi in Inghilterra in piena era industriale. Prima dell’avvento
della macchina a vapore, esisteva una specie di farfalla dalle ali bianche .
Con lo sviluppo industriale ed il conseguente utilizzo del carbone per il
funzionamento delle macchine, queste farfalle risaltavano sui tronchi
d’albero, anneriti dal pulviscolo, e diventavano facile preda degli uccelli.
Se nonché esistevano poche ma decisive farfalle di colore alquanto scuro
(variazione genetica, caso) che poterono sopravvivere e moltiplicarsi
(selezione naturale, necessità), originando così in poche decine di anni una
specie diversa di farfalle aventi colore completamente diversoda quello
della specie originale.
1.2 Algoritmi Genetici (GA)
I GA considerano una popolazione di cromosomi (individui) che
rappresentano soluzioni possibili per un certo problema. La qualità di un
individuo (cioè quanto è buona la soluzione per il problema) è misurata
mediante una funzione di fitness. In un certo senso, la funzione di fitness
indica l’adattabilità all’ambiente: gli individui che meglio si adattano
(‘fit’), hanno più probabilità di riprodursi e di trasmettere i propri geni alle
generazioni future. Un GA è una procedura di ricerca iterativa, il cui scopo
è l’ottimizzazione della funzione di fitness. Partendo da una popolazione
iniziale, un GA produce nuove generazioni che contengono di solito
2
Capitolo 1 Introduzione agli algoritmi genetici
individui migliori delle precedenti: l’algoritmo evolve verso l’ottimo
globale della funzione di fitness. In realtà, non è garantito che un GA trovi
una soluzione ottima globale: un GA è in grado di trovare soluzioni buone
in tempi ragionevoli. Nel modello tradizionale, i cromosomi sono stringhe
di bit di lunghezza fissa e tutte le generazioni hanno la stessa dimensione
(numero di individui). Ogni cromosoma rappresenta un punto nello spazio
di ricerca. I più importanti operatori di ricerca sono la ricombinazione (o
crossover) e la mutazione. Il crossover combina i geni tipici di due
individui per produrre individui figli che ereditano caratteristiche da
entrambi i genitori. La mutazione reintroduce nella popolazione materiale
genetico perduto. La ricerca genetica realizza un compromesso tra
‘exploitation’ della soluzione disponibile migliore ed ‘exploration’ dello
spazio di ricerca. Exploitation ed exploration corrispondono,
rispettivamente, a ricerca locale e ricerca globale: un’exploitation
eccessiva, può portare l’algoritmo a convergere ad una soluzione non
accettabile (la ricerca resta intrappolata in un ottimo locale), mentre
un’exploration eccessiva può non sfruttare appropriatamente la conoscenza
già disponibile rendendo il processo di ricerca molto lento (un esempio è la
ricerca casuale).
1.3 Elementi di base di un GA
Vediamo ora di quali passi è composto di un GA. La nuova generazione
indicata con P(t+1) è ottenuta dalla popolazione P(t) per mezzo dei seguenti
passi:
· Valutazione: si valuta la qualità di ogni individuo (tramite la
funzione di fitness).
· Selezione per riproduzione: gli individui migliori sono selezionati per la
riproduzione. Sono inseriti in una popolazione intermedia P1. Gli individui
3
Capitolo 1 Introduzione agli algoritmi genetici
in P1 entreranno nel mating pool con una certa probabilità (probabilità di
crossover).
· Crossover: si applica l’operatore di crossover agli individui nel
mating pool. Si ottiene una nuova popolazione intermedia P2.
· Mutazione: l’operatore di mutazione è applicato con una certa
probabilità (probabilità di mutazione) agli individui di P2. Viene
prodotta una popolazione P3.
· Selezione per rimpiazzamento e sopravvivenza: la nuova generazione
P(t+1) contiene gli individui della popolazione P3 ma può includere anche
altri individui. Sono possibili più algoritmi di selezione. Ad esempio, un
sottoinsieme di individui di P(t) che non sono stati selezionati per la
riproduzione, oppure gli individui migliore di P(t).
In un GA canonico , cioè quello introdotto da Holland, i cromosomi sono
stringhe binarie di lunghezza fissa. Il valore di ogni gene è standardizzato
in 0 o 1. Il numero di cromosomi in ogni generazione è costante. Il modello
GA canonico parte con una arbitraria popolazione iniziale. La nuova
generazione P(t+1), ottenuta applicando crossover e mutazione, rimpiazza
completamente la generazione precedente. In seguito è riportata la
semplificazione di un programma che schematizza il GA canonico:
BEGIN Genera la popolazione iniziale
Calcola il fitness di ogni individuo
While Not finito DO
Begin /* ciclo riproduttivo */
Seleziona due individui dalla vecchia generazione per
l'accoppiamento
/* influenzato in favore dei migliori */
4
Capitolo 1 Introduzione agli algoritmi genetici
ricombina i due individui per avere due discendenti
calcola il fitness dei due discendenti
inserisci i discendenti nella nuova generazione
End
IF la popolazione converge Then
Finito := TRUE
END
END
I punti fondamentali sono quindi : la funzione fitness ed il ciclo
riproduttivo.
Funzione Fitness
Per ogni problema da risolvere deve essere costruita una specifica funzione
fitness. Dato un particolare cromosoma, la funzione fitness restituisce un
singolo valore numerico "fitness" o una "figura di merito", che si suppone
sia proporzionale alla utilità o abilità dell'individuo che il cromosoma
rappresenta. Per molti problemi, in particolari funzioni di ottimizzazione, è
ovvio che la funzione fitness deve misurare il valore stesso della funzione.
Ma non è sempre questo il caso (ad esempio per ottimizzazioni
combinatorie).
Riproduzione
Durante la fase di riproduzione di un GA, gli individui sono selezionati tra
la popolazione e, ricombinati, produrranno la discendenza che sarà
compresa nella generazione successiva. I genitori sono selezionati a caso
usando uno schema che favorisce gli individui migliori. Gli individui buoni
saranno probabilmente selezionati più volte per la riproduzione, mentre
quelli peggiori potrebbero non essere mai scelti. Avendo selezionato due
5
Capitolo 1 Introduzione agli algoritmi genetici
individui, i loro cromosomi sono ricombinati, usando il meccanismo del
crossover e la mutazione.
Il crossover prende due individui, taglia le stringhe dei loro due
cromosomi in una posizione scelta a caso, per produrre così due segmenti
"testa" (head)} e due segmenti "coda" (tail). I segmenti coda sono poi
scambiati per produrre due nuovi cromosomi di lunghezza completa.
Ciascuno dei figli eredità alcuni geni da ogni genitore. Questo è conosciuto
come single point crossover. Il crossover non è abitualmente applicato a
tutte le coppie di individui selezionati per l'accoppiamento. Si fa una scelta
a caso, dove la probabilità di crossover applicata è usualmente tra 0.6 e 1.0.
Se il crossover non è applicato, i figli sono generati semplicemente
duplicando i genitori. Questo dà la possibilità a ogni individuo di propagare
i propri geni nella generazione successiva senza la scissione operata dal
crossover.
La mutazione è applicata singolarmente a ogni figlio dopo il crossover.
Viene alterato a caso ogni gene con una probabilità bassa (solitamente
6
Capitolo 1 Introduzione agli algoritmi genetici
0.001). La teoria tradizionale ritiene che il crossover sia più importane della
mutazione per quanto riguarda la rapidità nell'esplorare lo spazio di ricerca.
La mutazione porta un po' di "casualità" nella ricerca e aiuta ad assicurarci
che nessun punto nello spazio non abbia nessuna probabilità di essere
esaminato (un punto di vista alternativo verrà discusso in seguito). Un
esempio di due individui che si riproducono per generare due figli è
mostrato in figura nella pagina successiva. La funzione di fitness è un
esponenziale ad una variabile, con un massimo per x = 0.2 ed è codificata
con un numero di 10 bit. Nella tabella 1 sono mostrati due genitori e i figli
che hanno prodotto quando sono incrociati sul secondo bit (senza
mutazione) questa frase non è chiara. Ciò mostra come sia possibile che il
crossover ricombini parti dei cromosomi dei due individui e produca figli
con fitness più elevato potrebbe anche produrre individui con fitness
minore, ma essi avrebbero poche possibilità di riprodursi nella generazione
successiva).
7
Capitolo 1 Introduzione agli algoritmi genetici
8
Se il GA è correttamente implementato, la popolazione evolverà in molte
generazioni in modo che il fitness del miglior individuo e la media in ogni
generazione cresca verso l'ottimo globale. La convergenza è la
progressione verso la crescente uniformità . Un gene converge quando il
95% della popolazione condivide lo stesso valore. La popolazione
converge quando tutti i geni convergono.
Capitolo 2 I GA funzionano : perché ?
Capitolo 2
I GA FUNZIONANO : PERCHE’ ?
Molta della ricerca sui GA si è concentrata sul trovare regole empiriche per
farli funzionare bene. Non c'è una teoria generalmente accettata che spieghi
esattamente perché un GA ha certe proprietà, ma sono state fatte alcune
ipotesi che possono parzialmente spiegarne il successo ed essere tenute in
considerazione per implementare un buon algoritmo.
2.1 Gli Schemata e il Teorema dello Schema
Il teorema dello schema di Holland è la prima rigorosa spiegazione del
perché gli algoritmi genetici funzionano. Uno schema (al plurale spesso
schemata) è un modello di valori del gene che possono essere rappresentati
- nella codifica binaria - da una stringa di caratteri dell'alfabeto {0,1,#}. Un
cromosoma contiene gli schemi ottenuti sostituendo col simbolo "#" uno o
più dei suoi bit. Per esempio, il cromosoma"1010", contiene tra gli altri gli
schemi 10##, #0#0, ##10 e ##1#. L'ordine di uno schema è il numero di
simboli diversi da "#\" che contiene mentre la lunghezza definita è la
distanza tra i simboli diversi da "#\" più esterni (nell'esempio 2,3,1,3,
rispettivamente).
Il Teorema dello Schema spiega la potenza di un GA in termini di quanti
schemi sono processati. Agli individui della popolazione viene data la
possibilità di riprodursi, questa spesso viene chiamata prova di
riproduzione (reproduce trials), e generano figli. Il numero di opportunità
che ogni individuo riceve è in proporzione al suo fitness, quindi i migliori
individui contribuiscono maggiormente ai geni della generazione
successiva. Si presuppone che un alto valore di fitness sia dovuto al fatto
che l'individuo possiede buoni schemi. Passando i migliori schemi alla
generazione successiva, aumenta la probabilità di trovare soluzioni
9
Capitolo 2 I GA funzionano : perché ?
migliori. Holland ha dimostrato che la cosa migliore è assegnare prove di
riproduzione in numero sempre maggiore agli individui che hanno il fitness
più elevato rispetto al resto della popolazione, in modo che gli schemi
migliori abbiano un numero di prove crescente in modo esponenziale nelle
generazioni successive (teorema dello schema). Holland ha mostrato inoltre
che, poiché ogni individuo contiene un gran numero di schemi diversi, il
numero degli schemi che devono essere effettivamente processati è
dell'ordine di n elevato 3, dove n è il numero di individui. Questa proprietà
è detta parallelismo implicito ed è una delle motivazioni del buon
funzionamento dei GA.
2.2 Building Block Hypothesis
La potenza dei GA sta nella loro capacità di trovare buoni blocchi di
costruzione. Questi sono schemi di lunghezza definita “corta”, formata da
bit che lavorano bene insieme e tendono a portare miglioramenti quando
sono incorporati nello stesso individuo. Uno schema di codifica ben riuscita
è uno schema che incoraggia la formazione di building block, assicurandosi
che:
1. i geni correlati siano vicini all'interno del cromosoma
2. ci sia poca interazione tra i geni
L' interazione tra geni, spesso chiamata epistasis, significa che il contributo
di un gene al fitness dipende dal valore degli altri geni nel cromosoma.
Infatti c'è sempre una certa interazione in una funzione multimodale, e
questo risulta essere importante, perché le multimodali sono l'unico tipo di
funzioni che vengono processate con i GA, in quanto problemi più semplici
possono essere risolti più facilmente con altri metodi. Se queste regole sono
rispettate, il GA sarà efficiente come specificato dal teorema dello schema.
10
Ricevi informazioni sui nostri servizi, sulle offerte e non perdere news e consigli su università e lavoro.
