Post on 12-Oct-2015
description
transcript
UNIVERSIT DEL SALENTO
Facolt di Scienze Matematiche Fisiche e Naturali Corso di Laurea in Fisica
_______________________________________________________________
TESI DI LAUREA TRIENNALE
LEVOLUZIONE SIMULATA:
BASI E APPLICAZIONI
DEGLI ALGORITMI GENETICI
Relatore: Chiar.mo Dott. Giorgio De Nunzio Correlatore: Chiar.ma Dott.ssa Marina Donativi
Laureanda:
Francesca Itta _____________________________________________________
ANNO ACCADEMICO 2012 - 2013
1
Alla mia famiglia che ha creduto in me anche quando io non ho creduto in me stessa.
2
SOMMARIO
Introduzione ............................................................................... 3 Capitolo 1 ...................................................................................... 1.1 Introduzione agli algoritmi genetici (GA) ................................ 5 1.2 Quando occorre utilizzare un GA? .......................................... 6 1.3 Terminologia ............................................................................ 8 1.4 Funzionamento di un GA ..................................................... 10 1.5 Elementi di base degli algoritmi genetici .............................. 11 1.5.1 Codifica .............................................................................. 12 1.5.2 Funzione di fitness ............................................................. 13 1.5.3 Operatori ........................................................................... 14 1.6 Perch i GA funzionano ? ..................................................... 19 1.7 Teorema degli Schemi .......................................................... 20 1.7.1 Dimostrazione .................................................................... 21 1.8 Applicazioni di GA ................................................................ 26 1.8.1 Utilizzo della programmazione genetica in elettronica .... 27 Capitolo 2 ....................................................................................... 2.1 Casi di studio ......................................................................... 31 2.2 Ricerca del massimo di una funzione ad una variabile ........ 31 2.3 Analisi di immagini digitali ................................................... 38 Conclusioni ............................................................................... 45 Appendice A .............................................................................. 47 Appendice B .............................................................................. 51 Bibliografia .............................................................................. 53
3
Introduzione
Questa Tesi di Laurea propone una panoramica su una tecnica di
ottimizzazione che offre una valida metodologia di risoluzione per svariati
problemi. Tale metodo adotta particolari algoritmi, detti genetici (GA1) in
quanto emulano metodi di ottimizzazione biologici e in particolare genetici.
In pratica con questo metodo si imita quel meccanismo di ottimizzazione
messo in atto dalla natura la cui validit ormai consolidata da millenni :
levoluzione. Essa un processo creativo molto fecondo: dalla complicata
biochimica delle singole cellule all'elaborata struttura del cervello umano, ha
prodotto meraviglie di incredibile complessit. Questi risultati sono ottenuti
iterando per molte generazioni pochi processi molto semplici: mutazione,
ricombinazione e selezione naturale.
In questo campo di studio vengono mescolati argomenti appartenenti a
discipline diverse (biologia, fisica e informatica) con un approccio
computazionale. necessario quindi introdurre dei concetti generali relativi a
queste materie, come le nozioni di selezione naturale e codice genetico, che
sono alla base delle iterazioni degli GA e sono indispensabili per lo sviluppo
logico del procedimento. La maggior parte dei termini utilizzati sono adottati
dalle scienze naturali. Le applicazioni possibili sono innumerevoli ed in questo
lavoro di Tesi ci si soffermer in particolare sullapplicazione di GA per la
risoluzione di problemi fisici e matematici. Uno degli scopi meno espliciti ma
che ritengo di grande importanza in questo lavoro quello di illustrare al lettore
linterazione che esiste tra rami solo apparentemente diversi e indipendenti della
scienza, mostrando quanto sia invece presente una stretta cooperazione tra i
diversi scibili.
1 Dora in avanti nel testo ci riferiremo agli algoritmi genetici con la sigla GA dallinglese genetic
algorithm.
4
La Tesi strutturata in due capitoli:
Capitolo 1: espone le basi degli algoritmi genetici, descrivendo come essi siano
mutuati dal processo di selezione naturale caratteristico dell'evoluzione delle
specie viventi; enuncia e riporta una dimostrazione del teorema degli schemi;
riporta una applicazione degli algoritmi per la progettazione di circuiti
elettronici .
Capitolo 2: la parte applicativa della Tesi, e descrive due casi di studio ai quali
mi sono dedicata al fine di comprendere meglio il funzionamento degli GA e
come essi dipendano dalla numerosit della popolazione, dal numero di
iterazioni, e dagli altri parametri in gioco; si tratta di un semplice problema di
individuazione del punto di massimo di una funzione algebrica, e di
un'applicazione all'analisi di immagini.
Chiudono la Tesi le Conclusioni e una Bibliografia essenziale.
Il lavoro da me effettuato per la realizzazione della Tesi consistito
nell'individuazione e la sintesi dei testi da consultare, la scelta e la comprensione
degli esempi applicativi da Letteratura, e la partecipazione al consolidamento e
completamento del software adoperato per i casi di studio dettagliatamente
descritti nel Capitolo 2.
5
e da un inizio cos semplice, innumerevoli forme bellissime e meravigliose si sono evolute, e tuttora si evolvono .
Charles Darwin
5
Capitolo 1
1.1 Introduzione agli algoritmi genetici (GA)
Gli algoritmi genetici (GA) sono strategie di ottimizzazione nella ricerca di
soluzioni ispirati al principio della selezione naturale e dellevoluzione
teorizzata nel 1859 da Charles Darwin nellopera On the Origin of
species[1]. Lidea centrale della teoria evoluzionistica che in certe
popolazioni, gli individui che sono pi adatti a vivere in determinate
circostanze hanno una maggiore probabilit di sopravvivenza e di conseguenza
una migliore probabilit di trasmettere specifici tratti alla loro discendenza.
Lidea cardine della teoria evoluzionistica Darwiniana pu essere riassunta
nella seguente frase:
"Non la specie pi forte a sopravvivere, e nemmeno quella pi intelligente ma la specie che
risponde meglio al cambiamento"2
Col trascorrere delle generazioni, le caratteristiche vantaggiose diverranno
dominanti nella popolazione. Questa la selezione naturale. L'aggettivo
"genetico" per gli algoritmi deriva dal fatto che il modello evolutivo darwiniano
trova spiegazioni nella branca della biologia detta genetica e nel fatto che gli
algoritmi genetici attuano dei meccanismi concettualmente simili a quelli dei
processi biochimici scoperti da questa scienza. Si pu dire che gli algoritmi
genetici sono algoritmi che permettono di valutare delle soluzioni di partenza e
che, ricombinandole ed introducendo elementi di disordine, sono in grado di
crearne di nuove nel tentativo di convergere ad una soluzione ottimale.Oltre a
risolvere quei problemi di ottimizzazione per i quali un approccio procedurale
2Citazione tratta da On the Origin of Species[1]
6
impossibile o troppo complesso, i GA possono produrre risultati competitivi
anche per compiti normalmente affrontati nel modo classico. La vera prima
creazione di un algoritmo genetico storicamente attribuita a John Henry
Holland che, nel 1975, nel libro Adaptation in Natural and Artificial
Systems[2] pubblic una serie di teorie e di tecniche di fondamentale
importanza per lo sviluppo della materia.
Computer programs that evolve in ways that resemble natural selection can solve complex problems even their creators do not fully understand
J.Holland
1.2 Quando occorre utilizzare un GA ?
Generalmente, rispetto alle altre tecniche di ricerca, gli algoritmi genetici
trovano soluzioni migliori per il problema posto e riescono a farlo in tempi pi
brevi. I problemi che normalmente si affrontano e si risolvono con i computer
e con il software sono problemi la cui complessit computazionale
polinomiale, ossia il tempo di esecuzione dipende in maniera polinomiale
dalla dimensione dei dati. Tutti quei problemi per i quali il tempo impiegato
anche dal miglior algoritmo cresce troppo velocemente rispetto al numero delle
variabili in gioco, o al loro quadrato, al loro cubo, ecc., risultano impossibili da
risolvere in un tempo ragionevole; tali problemi sono chiamati di tipo N-P, e il
tempo necessario per la soluzione, non polinomiale rispetto alla dimensione
dei dati, usualmente esponenziale.
7
Come esempio, ammettiamo che ci venga assegnato un lavoro che prevede la
stesura dellorario scolastico di una grande scuola composta da molte classi, e
decine di professori. Ci viene raccomandato, inoltre ,che lorario debba tenere
conto del sovraccarico delle lezioni sugli alunni: in altre parole, bene evitare
di sistemare ore di lezioni troppo impegnative o troppo simili una di seguito
allaltra. Naturalmente il tutto deve funzionare in modo tale che i professori
non abbiano ore di lezione nello stesso momento e pause non adeguate tra una
lezione e laltra.
Formalizzando il lavoro, ci ritroviamo con i seguenti dati: le ore fornite da
ciascun professore, il numero di classi e i vincoli suddetti.
Anche solo a livello concettuale difficile trovare un sistema risolutivo:
avremmo la tentazione di scrivere uno schema a blocchi formato da un solo
blocco che chiameremo risolutore, che fornisca in output la tabella degli orari.
In realt, contemplando una ricerca iterativa del problema, creeremmo
probabilmente dei cicli prima sui professori, poi sulle classi, poi verificheremmo
i vincoli, il tutto intriso di asserzioni che verifichino che non vengano
commesse assurdit come la sovrapposizione di ore di lezione nello stesso
momento. Se a livello concettuale tutto questo pu avere un senso, a livello
applicativo, comporterebbe un enorme impiego di tempo ed energia data la
complessit delle interazioni fra variabili.
Quella che abbiamo definito una ricerca dellorario in modo iterativo,
controllando i casi uno ad uno. Ogni caso corrisponde ad una combinazione
differente delle variabili in input.
Per risolvere questo tipo di problemi di ottimizzazione combinatoria pi
conveniente utilizzare algoritmi non lineari: di norma si usano metodi di
approssimazione della migliore soluzione che si basano sul concetto di
8
probabilit. Sembra paradossale, ma in questi casi la miglior soluzione sembra
sia estrarre casualmente una combinazione degli input dallinsieme di tutte le
combinazioni possibili e provarla, se non soddisfacente scartarla e proseguire,
cos fino alla scoperta di una soluzione accettabile.
La seleziona naturale questo, ed cos che i GA lavorano, operando
sullinsieme di tutte le combinazioni o soluzioni e scegliendo un insieme di
elementi con successo pi probabile rispetto le altre.
1.3 Terminologia
Prima dell'effettiva spiegazione del funzionamento degli algoritmi
genetici, necessario premettere che questi ereditano e riadattano dalla
biologia alcuni termini che vengono di seguito preventivamente
presentati per una successiva maggiore chiarezza espositiva:
. Cromosoma : una delle soluzioni a un problema considerato.
Generalmente codificata con un vettore di bit o di caratteri detto
materiale genetico o DNA dellindividuo (soluzione) considerato.3
3 Gli individui sono detti cromosomi, fatto che potrebbe risultare fuorviante, dato che ogni cellula di un organismo appartenente ad una data specie possiede un certo numero anche elevato di cromosomi. Nella maggior parte delle applicazioni sono comunque sufficienti individui costituiti da un solo cromosoma ovvero aploidi, ma non mancano i casi in cui individui poliploidi siano stati utilizzati con successo.
9
. Popolazione : insieme di tutte le soluzioni relative al problema considerato.
. Gene : parte di un cromosoma.
Generalmente consiste in una o pi parti
del vettore di bit o caratteri che codificano
il cromosoma.
. Fitness : grado di valutazione associato
a una soluzione.La valutazione avviene in
base ad una funzione appositamente
progettata detta funzione di fitness.
. Crossover : generazione di una nuova
soluzione mescolando delle soluzioni
esistenti.
. Mutazione: alterazione casuale di una
soluzione.
Figura 1. Rappresentazione di un cromosoma e del suo materiale genetico .
10
1.4 Funzionamento di un GA
Un tipico algoritmo genetico, nel corso della sua esecuzione, provvede a fare
evolvere delle soluzioni secondo il seguente schema di base:
1. Generazione casuale della prima popolazione di soluzioni (cromosomi) e
applicazione della funzione di fitness alle soluzioni appartenenti
all'attuale popolazione.
2. Selezione delle soluzioni considerate migliori in base al risultato della
funzione di fitness e della logica di selezione scelta.
3. Procedimento di crossover e mutazione per generare delle soluzioni
ibride a partire dalle soluzioni scelte al punto 2.
4. Creazione di una nuova popolazione a partire dalle soluzioni
identificate al punto 3.
5. Riesecuzione della procedura a partire dal punto 2 utilizzando la nuova
popolazione creata al punto 4.
1)Generazione random della popolazione
2)Selezione degli individui per la riproduzione
3)Crossover e mutazione
4)Formazione della
generazione
5)Condizione di o
11
L'iterazione dei passi presentati permette l'evoluzione verso una soluzione
ottimale del problema come garantito dal Teorema Fondamentale di Holland
(detto anche Teorema degli schemi) il quale afferma che dopo una fase iniziale
nella quale il GA esplora in modo quasi random lo spazio di ricerca o di
campionamento, esso si concentra sulla regione pi promettente, i.e. la
regione caratterizzata da individui con fitness maggiori.
1.5 Elementi di base degli algoritmi genetici
Per quanto stato esposto nei paragrafi precedenti possiamo dire che gli
algoritmi genetici operano su una popolazione di cromosomi artificiali che
vengono fatti riprodurre selettivamente. Durante il processo riproduttivo le
repliche dei cromosomi degli individui migliori vengono accoppiate
casualmente e parte del materiale genetico viene scambiato, mentre alcune
piccole mutazioni casuali alterano localmente la struttura del codice genetico.
Le nuove strutture genetiche vanno dunque a rimpiazzare quelle dei loro
genitori dando luogo ad una nuova generazione di individui. Il processo
continua fino a quando nasce un individuo che rappresenta una soluzione
accettabile per il problema in esame. Gli algoritmi genetici si basano quindi su
tre operatori principali: la riproduzione selettiva degli individui migliori, la
ricombinazione genetica (crossover) e le mutazioni casuali. Prima di analizzare
in maggior dettaglio il funzionamento di questi operatori osserviamo che ci
sono due importanti strumenti necessari allo sviluppo di un algoritmo genetico:
la codifica e la funzione di fitness.
12
1.5.1 Codifica
Per codifica genetica si intende il tipo di rappresentazione che viene utilizzata
per identificare le soluzioni del problema. Esistono diversi tipi di codifica ma la
pi diffusa la Codifica vettoriale binaria: consiste in un vettore di n
campi binari, dove i valori 1 o 0 identificano delle caratteristiche elementari
della soluzione. I vantaggi di questa tecnica risiedono nel fatto di essere
semplice da implementare e da gestire durante l'intera evoluzione. Gli
svantaggi consistono nelle difficolt intrinseche della conversione delle soluzioni
in questa codifica.
Loriginario modello di GA proposto da Holland opera su una popolazione P
di n stringhe di bit (cromosomi o genotipi) di lunghezza l fissata come mostrato
in Figura 3. :
In alternativa alla codifica binaria possono essere usate altri tipi di codifica
come le due riportate di seguito.
Figura 3. Rappresentazione in codifica binaria degli individui di una popolazione.
13
Codifica vettoriale reale: come la codifica vettoriale binaria ma vengono
utilizzati dei numeri reali. Il vantaggio quello di introdurre una maggiore
espressivit e versatilit nella codifica, a scapito di un'aumentata complessit.
Codifica vettoriale diretta: consiste in una codifica vettoriale dove ogni
campo contiene direttamente i valori relativi al problema. Il vantaggio quello
di una facile codifica, lo svantaggio risiede nella difficile gestione dell'algoritmo
e nella difficile progettazione della funzione di fitness e dei processi di crossover
e mutazione.
1.5.2 Funzione di fitness
Essa valuta la bont degli individui gi della popolazione P nel risolvere il
problema di ricerca dato:
f : P (- , +) f(gi) = fi
L'insieme delle stringhe binarie di lunghezza l ha 2l elementi; tale insieme
rappresenta lo spazio di ricerca (search space) del GA, cio lo spazio che il
GA deve esplorare per risolvere il problema di ricerca. I valori della funzione
di fitness sui punti dello spazio di ricerca detto paesaggio d'idoneit
(fitness landscape).
14
Esempio
Supponiamo che la codifica binaria delle soluzioni del nostro problema possa
avvenire tramite stringhe di 2 bit.
Lo spazio di ricerca del GA, S , costituito da 2l = 22 = 4 elementi:
S = { (0,0), (0,1), (1,0), (1,1) }
I valori di fitness sui punti di S definiscono il paesaggio didoneit del GA.
1.5.3 Operatori
Una volta che la funzione di fitness ha determinato il valore di bont di ogni
individuo della popolazione, una nuova popolazione di individui (o genotipi)
viene creata applicando alcuni operatori che si ispirano alla selezione naturale
e alla genetica.
Gli operatori proposti da Holland sono:
1)Selezione (ispirato alla selezione naturale)
La selezione naturale Darwiniana sostiene che gli individui pi adatti
abbiano maggiori probabilit di sopravvivere nellambiente in cui vivono e,
dunque, maggiore probabilit di riprodursi. Nel contesto del GA di Holland,
gli individui pi adatti sono quelli con fitness pi alta, poich risolvono meglio
di altri il problema di ricerca dato; per questo essi devono essere privilegiati
nella fase di selezione degli individui che potranno riprodursi dando luogo a
nuovi individui.
15
A causa di complessi fenomeni di interazione non dato per scontato n che
da due soluzioni promettenti ne nasca una terza pi promettente n che da due
soluzioni con valori di fitness basso ne venga generata una terza con valore di
fitness pi basso. Per ovviare a questi problemi, durante la scelta delle soluzioni
candidate all'evoluzione, oltre che sul parametro ottenuto dalla funzione di
fitness ci si basa anche su particolari tecniche di "selezione" di cui si analizzano
di seguito i principali tratti.
Selezione a roulette: la probabilit che una soluzione venga scelta per farla
evolvere direttamente proporzionale al valore restituito dalla funzione di
fitness.
Sia fi il valore di fitness del genotipo gi, la probabilit che gi sia selezionato per
la riproduzione :
ps,i = fi / fj
dove la somma calcolata sull'intera popolazione attuale di individui.
Tali probabilit sono utilizzate per costruire una sorta di roulette come di
seguito :
1. La circonferenza di un immaginario cerchio viene divisa in M segmenti con
apertura angolare:
Ai=2 / con Ai = 2 e ciascun individuo gi, associato al corrispondente segmento Ai.
16
2. si estraggono tanti numeri casuali, con distribuzione uniforme tra 0 e
2,quanti sono gli individui che si vogliono selezionare.
3. il cromosoma (i) viene scelto se il numero casuale cade nel relativo settore Ai.
Ogni volta che un individuo della popolazione selezionato ne viene creata
una copia; tale copia inserita nel cos detto mating pool (piscina
daccoppiamento).Quando il mating pool riempito con esattamente n
(numero di individui della popolazione) copie di individui della popolazione,
nuovi n discendenti sono creati applicando gli operatori genetici.
Esempio
I quattro individui A1, A2, A3 e A4, con probabilit di selezione 0.12, 0.18, 0.3 e
0.4, occupano uno spicchio di roulette di ampiezza pari alla propria
probabilit di selezione(vedi Figura 4.). Se viene generato un numero tra 0 e
0.12 verr selezionato lelemento A1,se viene estratto un numero compreso tra
0.12 e 0.3=0.12+0.18 (estremo dellintervallo ottenuto sommando al primo
estremo 0.12 la probabilit di estrazione dellelemento A2 ) verr selezionato
lelemento A2 e cos via. Nell'esempio l'operatore di selezione genera il numero
casuale c = 0.78 e l'individuo A4 viene selezionato.
Figura 4. Rappresentazione della roulette usata per il processo di selezione.
17
2)Crossover (ispirato alla genetica)
Si scelgono a caso due individui nel mating pool (genitori) e un punto di taglio
(punto di crossover) su di essi. Le porzioni di genotipo alla destra del punto di
crossover vengono scambiate generando due discendenti (vedi Figura
5.).L'operatore di crossover applicato, in accordo a una prefissata probabilit
pc, n/2 volte in modo da ottenere n discendenti; nel caso in cui il crossover non
sia applicato, i discendenti coincidono con i genitori.
La modalit di crossover appena descritta detta a un punto poich lo scambio
del materiale genetico avviene in seguito alla scelta di un punto di taglio.
Esistono ulteriori modalit di crossover come quello a due punti che consiste
nel considerare due soluzioni adatte all'evoluzione e nel tagliare i loro vettori di
codifica in due punti predefiniti o casuali al fine di ottenere una testa, una parte
centrale ed una coda dalla prima e dalla seconda soluzione. La prima nuova
soluzione sar data dalla testa e della coda della prima soluzione e dalla parte
centrale della seconda soluzione. La seconda nuova soluzione sar data dalla
parte centrale della prima soluzione e dalla testa e dalla coda della seconda
soluzione. Esiste anche il Crossover uniforme che consiste nello scambiare
casualmente dei bit tra le soluzioni candidate all'evoluzione.
Figura 5. Rappresentazione del processo di crossover
18
3)Mutazione (ispirato alla genetica)
Una volta che due discendenti sono stati generati per mezzo del crossover, in
funzione di una usualmente piccola probabilit pm, il valore di alcuni bit dei
nuovi individui sono cambiati da 0 in 1 o viceversa (vedi Figura 6.). Come il
crossover, rappresenta una metafora della riproduzione sessuale, l'operatore di
mutazione modella il fenomeno genetico della rara variazione di elementi del
genotipo negli esseri viventi durante la riproduzione. Il punto di vista
tradizionale che lincrocio sia il pi importante dei due operatori genetici
perch responsabile di una rapida esplorazione dello spazio di ricerca. Tuttavia
la presenza della mutazione ugualmente essenziale per quanto
apparentemente piccola sia la sua incidenza sulla ricerca.
Il meccanismo di selezione, ricombinazione e calcolo della fitness viene iterato.
Levoluzione termina quando viene raggiunto lottimo, se questo noto.
Altrimenti levoluzione termina quando viene raggiunto il numero massimo Ng
di generazioni oppure quando un indicatore di convergenza (uniformit della
popolazione, mancanza di progressi nellevoluzione) raggiunge un determinato
valore . Se lalgoritmo genetico correttamente implementato, la popolazione
evolver nel susseguirsi delle generazioni in modo che la fitness del miglior
individuo e la media in ogni generazione cresca verso lottimo globale.
Figura 6. Rappresentazione del processo di mutazione.
19
1.6 Perch i GA funzionano?
Il processo evolutivo della popolazione di cromosomi corrisponde ad una
ricerca nello spazio delle soluzioni potenziali. Tale ricerca richiede l'equilibrio
di due finalit apparentemente in contrasto: lo sfruttamento delle soluzioni
migliori e l'esplorazione dello spazio delle soluzioni. E' principalmente questa
capacit di bilanciamento a distinguere gli algoritmi genetici da altre
metodologie che invece sfruttano costantemente le soluzioni migliori trovate,
rinunciando all'esplorazione dello spazio delle soluzioni, o la ricerca casuale,
che, al contrario, esplora tale spazio senza dare alcun peso alle regioni
dimostratesi pi promettenti. Gli algoritmi genetici effettuano una ricerca
multi-direzionale mantenendo una popolazione di soluzioni potenziali e
incoraggiando lo scambio di informazione .
Figura 7. L'evoluzione pu essere vista come una ricerca nello spazio di tutti gli organismi possibili, rappresentato qui nel piano. L'operazione di incrocio (in rosso) agisce in modo creativo, combinando di quando in quando caratteristiche disparate e saltando verso nuove regioni dello spazio degli organismi dove risiede la maggior parte degli individui pi adatti. La mutazione (in verde), al contrario, tende quasi sempre a cercare il miglior organismo tra i primi vicini.
20
1.7 Teorema degli schemi
John H. Holland, insieme ai suoi studenti della University of Michigan, ha
perseguito lo scopo di studiare le dinamiche generali che governano
l'adattamento in natura e trasporle in analoghi informatici ovvero i GA,
piuttosto che cercare di progettare algoritmi per un problema specifico. Era
per necessario fornire una valida base teorica che garantisse la convergenza
del GA verso lottimo. Questo viene fatto attraverso il Teorema degli
schemi. La formulazione tradizionale della teoria sugli GA (1975) ipotizza che
le soluzioni migliori tendano ad essere costituite da blocchi buoni, cio da
piccole sequenze di bit (non necessariamente vicine) che aumentano il valore
della funzione di fitness del cromosoma. Nel teorema fondamentale degli algoritmi
genetici (o teorema degli schemi)[2] Holland dimostra che gli individui cos costituiti
tendono a crescere esponenzialmente nella popolazione attraverso il
meccanismo dell'incrocio, assicurando cos la convergenza dell'algoritmo
genetico verso una soluzione ottimale. L'algoritmo funziona individuando,
favorendo e ricombinando tali blocchi. Viene qui esposto il teorema cos come
presentato da Holland, relativo cio alla codifica binaria.
E necessario introdurre i seguenti concetti:
Schema: E' un cromosoma,di lunghezza predefinita, in cui siano specificati i
valori assunti da alcune particolari posizioni di bit nella stringa e siano invece
lasciati indefiniti i valori associati alle altre posizioni. Due esempi di schemi sono
i seguenti :
Ha = 1 * * * * 0 Hb = * * * * * 1 0
cio rispettivamente l'insieme di tutte le stringhe di sei bit che cominciano con
1 e finiscono con zero (100000, 100010, 100100,....) e l'insieme di tutte le
21
stringhe di lunghezza sette e che finiscono con 10.
Istanze di uno schema : Le differenti stringhe corrispondenti allo stesso
schema. Ad esempio 100000 una istanza dello schema Ha.
Ordine dello schema o(H) :il numero di bit definiti ovvero due sia per
Ha che per Hb .
Lunghezza di definizione d(H) : la distanza tra i due bit definiti pi
esterni (5 e 1 rispettivamente per Ha e Hb) .
In un algoritmo genetico, la competizione fra cromosomi pu essere
equivalentemente intesa, dal punto di vista teorico, come una competizione
fra schemi. A questo proposito si noti che:
Il GA agendo su una stringa di lunghezza l come se agisse su una istanza
per pi schemi, 2! in particolare essendo queste le permutazioni di l bit. 1.7.1 Dimostrazione
Supponendo di avere nella popolazione m istanze di un particolare schema
H, all'istante t cio al ciclo generazionale t-esimo, si pu indicare m con la
seguente notazione che ne descrive la dipendenza dallo schema e dalla
generazione considerate: m=m(H,t).Durante la riproduzione, nell'Algoritmo
Genetico,gli individui ricevono copie in proporzione alla loro idoneit o
valore di fitness .E' questo il criterio di selezione proporzionale in cui un individuo verr selezionato con una probabilit pari a:
!" !"!! (1.1)
22
Detta f(H) l'idoneit media dello schema H, all'istante generazionale t, la
probabilit media delle m istanze di H di essere selezionate sar:
!(!)!"!! (1.2) Ad un istante t+1 si pu quindi esprimere:
, + 1 = , !(!)!"!! (1.3) La (1.3) afferma semplicemente che il numero di istanze dello schema che ci
si pu aspettare nella successiva generazione, aumenta linearmente sia con
n, ove n la dimensione della popolazione, sia con f(H), idoneit media
delle stringhe appartenenti allo schema.
L'idoneit media su tutta la popolazione sia indicata con :
= /! !!"! = !!! (1.4) Sostituendo questa espressione nella (1.3) si ottiene la seguente (1.5):
, + 1 = , !(!)! (1.5) Quindi uno schema accresce o decresce il numero di sue istanze secondo il
rapporto fra idoneit media di schema e idoneit media di popolazione; gli
schemi con valore di idoneit' alto riceveranno molte repliche nelle prossime
generazioni. Quelli con valori bassi al contrario riceveranno un numero di
repliche che andr progressivamente decrementandosi.
23
Supponiamo che uno schema H abbia f(H) maggiore di di una quantit c con c fattore costante, cio : , + 1 = , !!!!! = 1 + (, ) (1.7) Ma , 1 = (1 + ) (, 0) e questo vale per ogni t, quindi , 2 = (1 + ) , 1 = 1 + ! (, 0) da cui la regola generale: , + 1 = (1 + )! (, ) (1.8) L'effetto della riproduzione, come espresso dalla (1.8) quindi quello di
allocare un numero di discendenti che cresce o decresce in progressione
geometrica per gli schemi aventi grado di idoneit rispettivamente superiore
o inferiore alla media di un fattore costante c. A questo punto bisogna
considerare lincrocio .L'incrocio distruttivo per lo schema quando una
parte delle posizioni fissate dello schema si vengono a trovare a destra del
punto di incrocio e una parte a sinistra. Quindi se la lunghezza definita
corta l'incrocio sar distruttivo con minore probabilit nei confronti dello
schema. Se l la lunghezza del cromosoma e il punto di incrocio scelto in
una posizione a caso fra 1 e l-1 la probabilit che esso divida le posizioni
definite : ! = ()/( 1) (1.9) dove con d(H) si intende la lunghezza definita dello schema H. Uno schema,
dunque, sopravvive all'incrocio se il punto di incrocio cade al di fuori della
lunghezza definita.Detta ps tale probabilit di sopravvivenza dello schema,
si ha che
24
! = 1 ! = 1 ! !!!! (1.10) e se dopo la riproduzione, poi, l'incrocio non avviene sempre ma solo con
probabilit pc allora si pu calcolare un limite inferiore alla probabilit di
sopravvivenza di uno schema H, cio :
! 1 ! ! !!!! (1.11) Nell'ipotesi di statistica indipendenza fra le operazioni di incrocio e
riproduzione, si possono moltiplicare il numero atteso nella generazione t+1
di istanze dello schema dopo la selezione proporzionale (1.5),per la
probabilit di sopravvivenza all'incrocio (1.10),ottenendo il numero di
istanze di schema atteso nella generazione t+1 dopo riproduzione e
incrocio.
Per concludere esaminiamo anche l'effetto della mutazione. La probabilit
di mutazione di un singolo bit sia pm ; se lo schema H deve sopravvivere
alla mutazione, tutti i singoli bit che esso contiene nelle posizioni fissate
devono sopravvivere. Quindi un singolo bit ha una probabilit di
sopravvivere alla mutazione pari a 1 - pm ; poich ogni singola mutazione
statisticamente indipendente dalle altre e uno schema ha ordine o(H) ossia
un altrettanto numero di bit, la probabilit di sopravvivenza di uno schema
alla mutazione ! = (1 !)!(!) (1.12)
25
In conclusione si provato che (enunciato del Teorema degli schemi ) :
Schemi brevi, di basso ordine, sopra la media ricevono un incremento esponenziale nelle
successive generazioni di un algoritmo genetico.
Il numero di istanze di uno schema H alla generazione t+1, dopo un
incrocio che avviene con probabilit pc e una mutazione che avviene con
probabilit pm , dato infatti dalla seguente espressione:
, + 1 = , ! !! 1 ! ! !!!! (1 !)!(!) (1.13) da cui si vede che le stringhe migliori sono ottenute dal confronto fra schemi
a pi alta idoneit, a pi corta lunghezza definita e minore probabilit di
mutazione.
26
1.8 Applicazioni di GA
Le innumerevoli applicazioni degli algoritmi genetici spaziano dalla
progettazione di antenne (figura 8.) [3] allo sviluppo di modelli come quello
della corona solare[4], ad applicazioni in diagnostica medica per
immagini[5].E interessante osservare, come mostrano i seguenti grafici (Figura
9 e 10), come risulti stabilmente crescente nel tempo lutilizzo di tali tecniche.Si
analizzer di seguito, a titolo di esempio, l'applicazione dei GA alla risoluzione
di un problema di elettronica.
Figura 10. Raggruppamento dei temi di ricerca di astrofisica che fanno uso di GA [6]
Figura 9. Numero ricerche in astrofisica che hanno fatto uso di GA [6]
Figura 8. Queste che sembrano graffette modellate da bambini sono le antenne progettate dalla NASA con GA per la missione ST5 2006 [3]
27
1.8.1 Utilizzo della programmazione genetica in elettronica
Nella maggior parte dei casi i problemi di elettronica hanno una natura
combinatoriale, cio per risolverli si deve sondare un enorme spazio di
possibilit al fine di trovare quella che meglio soddisfa determinate richieste. Un
circuito elettronico viene sempre schematizzato in termini di pochi elementi
fondamentali collegati tra loro: resistori, induttanze, capacit, diodi,etc.
Consideriamo a titolo di esempio [7] un problema concreto quale la
realizzazione di un filtro passa basso con frequenza di taglio fT di 1kHz. Gli
elementi primordiali sono banalmente dei circuiti in cui dei cavi conduttori
connettono un input ad un output. Dunque ciascun circuito comincia come un
embrione elementare che consiste in un singolo cavo che va dall'input
all'output.Il circuito embrionale cresce per applicazione progressiva di funzioni
di costruzione dei circuiti. Alcune di queste funzioni inseriscono particolari
componenti, altre modificano lo schema di connessioni tra questi. A nostra
disposizione ci sono resistori, induttanze e capacit che connettono via via pi
cavi tra loro.
Il primo passo quello di tradurre l'organizzazione circuitale in un genotipo
matematico, cio una stringa che identifica il tipo di componente (R per
resistenza, C per condensatore...), ed i punti di connessione nella rete.
L'algoritmo genetico consente alle componenti R,L, e C di creare collegamenti
tra i cavi, connessioni a terra, cortocircuiti. L'idoneit del circuito sar valutata
in base alla capacit dello stesso di bloccare le frequenze superiori a fT.
28
Nella figura seguente (vedi Figura 11.) si mostra un esempio di mescolamento
tra due circuiti, seguito dal mescolamento relativo modellizzato con il cross-
over tra le due stringhe. La riga in alto mostra i due individui prima del
crossover, e la seconda riga dall'alto mostra l'avvenuto scambio di materiale
genetico. Sia G la lunghezza fissata del genoma, quindi il numero massimo di
collegamenti possibili, e sia P il numero di nodi (fissato) del circuito. Ogni nodo
pu essere collegato con ciascuno degli altri P-1 nodi, con un certo numero di
componenti complessivamente minore di G (possibilit di collegamento in
parallelo).Ogni gene composto (se supponiamo che i valori dei componenti
siano fissi) da tre caratteri, due numerici (nodo di partenza e nodo di arrivo) e
uno alfabetico centrale che indica il tipo di collegamento (CC cortocircuito, R
resistenza, L induttanza, C capacit, eventualmente in maniera esplicita CA
circuito aperto).
Figura 11. Rappresentazione in termini circuitali(in alto) ed in termini di geni (in basso) del
processo di cross-over tra due circuiti(in questa rappresentazione il CA non stato
esplicitamente indicato).
29
Ogni collegamento risulta indipendente dagli altri, quindi possiamo avere
collegamenti in parallelo ma escludiamo la possibilit di avere collegamenti in
serie, poich questi comporterebbero la creazione di nuovi nodi, quindi
implicitamente la variazione della lunghezza del genoma che noi abbiam
fissato.
Cerchiamo dunque una stima del numero di possibili combinazioni: ogni nodo
di partenza pu essere scelto in P modi, ogni nodo di arrivo in P-1 modi e il
collegamento in n = 5 ulteriori modi differenti. Tutto questo va considerato per
tutti i G elementi del genoma (G = 5 in questo). Quindi il numero N di
possibili combinazioni di G geni che l'algoritmo pu simulare :
= ( 1 )!
Nel nostro caso se G=5 avremmo N=150! possibilit. Se trattiamo il circuito aperto come una delle cinque possibilit di
collegamento, tra due nodi esiste sempre almeno un collegamento. Il numero
minimo di collegamenti possibili non ridondanti : P*(P-1) /2 .
Il cromosoma deve dunque essere lungo abbastanza da consentire questo
numero, cio un circuito composto solo da collegamenti semplici e nodi
isolati. Dopo un certo tempo si sar ottenuto un gran numero di variazioni, e,
in base alla capacit del circuito di attenuare le frequenze indesiderate, noi
possiamo potremo ritenere di aver raggiunto una soluzione soddisfacente.
Il processo fornisce la topologia del circuito. Del circuito soluzione noi non
30
conosciamo i dettagli, in quanto ottenuto in base a combinazioni casuali di altri
circuiti, ma sappiamo che il suo funzionamento soddisfacente rispetto alla
condizione fT=1kHz (andando a calcolare un fattore di merito). L'algoritmo
compone automaticamente i circuiti senza utilizzare alcun know-how del
sistema.
Figura 12. Evoluzione di un filtro passa-basso a partire dallincrocio di vari
individui.Tratto da [7].
31
Capitolo 2
2.1 Casi di studio
In questo capitolo verranno presentati due esempi di applicazioni di algoritmi
genetici con lutilizzo di Matlab (The Mathworks). I codici derivano da sorgenti
liberamente disponibili in Rete, e sono riportati nelle appendici. Essi sono stati
opportunamente corretti, completati e arricchiti per quanto concerne
l'interfaccia con l'utente, dal mio Relatore con la mia attiva partecipazione.
Come variante rispetto quanto descritto nel capitolo precedente, il software
adoperato parte dalla popolazione iniziale di numerosit N, effettua N volte il
crossover (ottenendo una nuova popolazione avente un numero doppio di
individui), la mutazione, realizza la selezione degli N individui pi adatti,
verifica il raggiungimento di una condizione di stop, e reitera.
Il primo esempio che verr analizzato un problema matematico riguardante
la ricerca del massimo di una funzione di una variabile, mentre il secondo
mostra unapplicazione di GA per lelaborazione di immagini digitali.
2.2 Ricerca del massimo di una funzione ad una variabile
Ci proponiamo di osservare il funzionamento di un algoritmo genetico in una
situazione molto semplice: il problema consiste nel trovare il valore della
variabile x che massimizza la funzione f(x)=260 ( 15)! dove x pu variare tra 0 e 31 (si vedr in seguito il perch della scelta dei limiti).
32
Figura 13. Grafico della funzione da massimizzare
Il codice riportato interamente in Appendice A.
Fissiamo in partenza il numero di generazioni che vogliamo creare, e dunque
di iterazioni: essendo questo un esempio dimostrativo del funzionamento del
meccanismo alla base di un GA, ci limiteremo a sole cinque generazioni cos
da poter analizzare loutput del programma ad ogni ciclo.Il secondo passo
consiste nella scelta della rappresentazione genetica: utilizziamo un codice
binario a stringhe di lunghezza 5 che ci permettono di codificare numeri interi
da 0 (00000) a 31 (11111)4. Come si intuisce, la scelta dei limiti per la
variabile indipendente, prima effettuata, (x tra 0 e 31) non stata quindi
casuale, ma rispecchia la struttura del codice GA; scegliendo (arbitrariamente)
5 bit per la definizione dei geni, otteniamo 32 possibili valori, che coprono il
range di numeri interi tra 0 e 31. Naturalmente, ove si fosse cercata una
soluzione non intera, o fosse stata necessaria una maggior accuratezza, o si
4 Il processo di trasformazione da numero binario a numero decimale dato da
x = 2!!!!!!! dove p indica la posizione del numero intero binario a partire dall ultima cifra, N il numero di cifre e i il valore binario dellintero
corrispondente. Ad esempio 10100 =1*2! + 0*2! + 1*2! + 0*2!+ 0*2!=20
33
fosse voluto un range pi ampio, si sarebbe considerato un numero maggiore
di bit.
Creiamo dunque una piccola popolazione iniziale composta solamente da due
stringhe generate casualmente. Ciascuna stringa viene decodificata da binario
in decimale e il suo valore di fitness calcolato applicando la funzione f al
numero decimale ottenuto.
Figura 14. Output del programma Matlab. Da sinistra verso destra, le varie colonne rappresentano per i diversi individui : un indice progressivo, la codifica in binario, la decodifica in decimale ed il valore di fitness. Per ciascun individuo della popolazione attuale che indichiamo con gli
indici 1 e 2 , scelto in maniera casuale il compagno di accoppiamento e
la posizione del punto di taglio cos da poter effettuare il processo di
crossover.
In questiterazione, casualmente, il crossover ha incrociato ciascun individuo
con se stesso.
Dopo il crossover la popolazione si presenta come segue :
34
Per ciascun individuo si applicher con una probabilit (arbitraria!) pm = 50 %
loperatore di mutazione ad un bit della stringa che viene scelto casualmente.
La popolazione a questo punto si presenta come segue:
Lindividuo con il massimo valore di fitness viene registrato in una variabile, e
di esso si terr conto nel proseguo poich saranno utilizzati in combinazione,
come regole di selezione per formare la generazione successiva, sia il criterio di
selezione a roulette che il criterio elitistico, il quale garantisce il trasferimento
alla generazione successiva del miglior individuo a disposizione5.
5 Metodo elitistico [8]
Questo metodo che consiste nel conservare per ogni generazione il migliore individuo e di sostituirlo al peggiore .E infatti provato che per un algoritmo genetico classico, questo metodo rende pi efficace la ricerca del massimo globale, poich reintroduce
35
La nuova popolazione di cromosomi ottenuta stata decodificata e valutata.
Alla fine del processo di valutazione ciascuna stringa riceve una probabilit di
riproduzione proporzionale alla propria fitness; ci permette la realizzazione
dei settori circolari della roulette, ciascuno associato ad un individuo.
Il generatore di numeri casuali ci permette di estrarre dal pool dei 4 individui i
due potenziali, che andranno a formare la prima generazione. Di questi,
lesemplare con il valore di fitness pi basso viene sostituito con il migliore
individuo di cui si tenuta memoria precedentemente (metodo elitistico).
Figura 15. I cerchietti in blu rappresentano i numeri casuali generati che permettono di selezionare gli individui che potranno formare la generazione di interesse in base al settore della roulette in cui cadono. Per ciascun settore riportato il valore decimale dellindividuo che esso rappresenta.
delle istanze di schemi promettenti che possono aiutare la localizzazione del massimo quando il meccanismo di selezione proporzionale non alloca il valore atteso di discendenza ai migliori. Si corre comunque il rischio di favorire una ricerca locale a scapito di una prospettiva globale.
36
Di seguito vengono riportati gli output dei vari cicli di iterazione.
########################## ITERAZIONE N. 2 ################### ------- Popolazione attuale --------------------------------- 1 > 0 0 1 1 0 - 6.0000 --- fitness 179.000000 2 > 0 0 1 1 0 - 6.0000 --- fitness 179.000000 CROSSOVER tra individuo di indice 1 e individuo di indice 2, al bit 3 (da sinistra) CROSSOVER tra individuo di indice 2 e individuo di indice 1, al bit 3 (da sinistra) ------- Popolazione dopo crossover ------------------------- 1 > 0 0 1 1 0 - 6.0000 --- fitness 179.000000 2 > 0 0 1 1 0 - 6.0000 --- fitness 179.000000 3 > 0 0 1 1 0 - 6.0000 --- fitness 179.000000 4 > 0 0 1 1 0 - 6.0000 --- fitness 179.000000 MUTAZIONE nell'individuo di indice 2, al bit 2 (da sinistra) MUTAZIONE nell'individuo di indice 3, al bit 2 (da sinistra) ------- Popolazione dopo mutazione--------------- 1 > 0 0 1 1 0 - 6.0000 --- fitness 179.000000 2 > 0 1 1 1 0 - 14.0000 --- fitness 259.000000 3 > 0 1 1 1 0 - 14.0000 --- fitness 259.000000 4 > 0 0 1 1 0 - 6.0000 --- fitness 179.000000 Individuo con massima fitness: 1 > 0 1 1 1 0 - 14.0000 --- fitness 259.0000
########################## ITERAZIONE N. 3 ################### ------- Popolazione attuale --------------------------------- 1 > 0 1 1 1 0 - 14.0000 --- fitness 259.000000 2 > 0 0 1 1 0 - 6.0000 --- fitness 179.000000 CROSSOVER tra individuo di indice 1 e individuo di indice 2, al bit 4 (da sinistra) CROSSOVER tra individuo di indice 2 e individuo di indice 1, al bit 5 (da sinistra) ------- Popolazione dopo crossover ---------------------- 1 > 0 1 1 1 0 - 14.0000 --- fitness 259.000000 2 > 0 0 1 1 0 - 6.0000 --- fitness 179.000000 3 > 0 0 1 1 0 - 6.0000 --- fitness 179.000000 4 > 0 1 1 1 0 - 14.0000 --- fitness 259.000000 MUTAZIONE nell'individuo di indice 1, al bit 5 (da sinistra) MUTAZIONE nell'individuo di indice 2, al bit 4 (da sinistra) ------- Popolazione dopo mutazione--------------- 1 > 0 1 1 1 1 - 15.0000 --- fitness 260.000000 2 > 0 0 1 0 0 - 4.0000 --- fitness 139.000000 3 > 0 0 1 1 0 - 6.0000 --- fitness 179.000000
37
4 > 0 1 1 1 0 - 14.0000 --- fitness 259.000000 Individuo con massima fitness: 1 > 0 1 1 1 1 - 15.0000 --- fitness 260.000000 ########################## ITERAZIONE N. 4 ################### ------- Popolazione attuale --------------------------------- 1 > 0 1 1 1 1 - 15.0000 --- fitness 260.000000 2 > 0 1 1 1 0 - 14.0000 --- fitness 259.000000 CROSSOVER tra individuo di indice 1 e individuo di indice 2, al bit 2 (da sinistra) CROSSOVER tra individuo di indice 2 e individuo di indice 1, al bit 2 (da sinistra) ------- Popolazione dopo crossover ------------------------- 1 > 0 1 1 1 0 - 14.0000 --- fitness 259.000000 2 > 0 1 1 1 1 - 15.0000 --- fitness 260.000000 3 > 0 1 1 1 1 - 15.0000 --- fitness 260.000000 4 > 0 1 1 1 0 - 14.0000 --- fitness 259.000000 MUTAZIONE nell'individuo di indice 1, al bit 1 (da sinistra) MUTAZIONE nell'individuo di indice 4, al bit 3 (da sinistra) ------- Popolazione dopo mutazione--------------- 1 > 1 1 1 1 0 - 30.0000 --- fitness 35.000000 2 > 0 1 1 1 1 - 15.0000 --- fitness 260.000000 3 > 0 1 1 1 1 - 15.0000 --- fitness 260.000000 4 > 0 1 0 1 0 - 10.0000 --- fitness 235.000000 Individuo con massima fitness: 1 > 0 1 1 1 1 - 15.0000 --- fitness 260.000000 ########################## ITERAZIONE N. 5 ################### ------- Popolazione attuale --------------------------------- 1 > 0 1 1 1 1 - 15.0000 --- fitness 260.000000 2 > 0 1 0 1 0 - 10.0000 --- fitness 235.000000 CROSSOVER tra individuo di indice 1 e individuo di indice 2, al bit 4 (da sinistra) CROSSOVER tra individuo di indice 2 e individuo di indice 2, al bit 2 (da sinistra) ------- Popolazione dopo crossover ------------------------- 1 > 0 1 1 1 0 - 14.0000 --- fitness 259.000000 2 > 0 1 0 1 1 - 11.0000 --- fitness 244.000000 3 > 0 1 0 1 0 - 10.0000 --- fitness 235.000000 4 > 0 1 0 1 0 - 10.0000 --- fitness 235.000000 MUTAZIONE nell'individuo di indice 2, al bit 2 (da sinistra) ------- Popolazione dopo mutazione--------------- 1 > 0 1 1 1 0 - 14.0000 --- fitness 259.000000 2 > 0 0 0 1 1 - 3.0000 --- fitness 116.000000 3 > 0 1 0 1 0 - 10.0000 --- fitness 235.000000 4 > 0 1 0 1 0 - 10.0000 --- fitness 235.000000 Individuo con massima fitness : 1 > 0 1 1 1 1 - 15.0000 --- fitness 260.000000 SOLUZIONE : 15.0000000 (fitness 260.000000)
38
Figura 16. Andamento della fitness media della popolazione(in blu) e del valore massimo di
fitness(in rosso) in funzione del numero di iterazioni
Il grafico in figura 16 illustra landamento della fitness massima e della fitness
media della popolazione, in funzione della generazione. Tale grafico permette
di notare come, dopo un certo numero di iterazioni, si raggiunga la stabilit del
valore massimo. La soluzione trovata effettivamente quella corrispondente al
punto di massimo della funzione di fitness. Si pu notare come anche il valore
medio della fitness tenda ad aumentare verso il massimo, ma tale tendenza non
sempre stabile, potendo verificarsi oscillazioni anche molto ampie. Questa
convergenza del massimo alla soluzione ottimale dopo un certo numero di cicli
verifica la validit del teorema degli schemi.
2.3 Analisi di immagini digitali
Questo paragrafo illustra un ulteriore esempio di applicazione degli algoritmi
genetici, che sfrutta il codice riportato nellappendice B. Si tratta di un test
effettuato su un'immagine, denominata 'blobs.gif',6 reperibile a corredo di
6 In analisi d'immagine si tende a indicare con il termine inglese "blob" qualunque
oggetto di interesse di forma approssimativamente circolare, quali nel nostro caso le particelle d'oro di cui si parla nel seguito.
39
ImageJ, un software di trattamento e analisi di immagini liberamente disponibile
in rete (http://rsbweb.nih.gov/ij/).
L'immagine microscopica, mostrata in figura 17 , raffigura delle particelle di oro
su un substrato. Considereremo le particelle d'oro (grigio scuro) come gli
"oggetti" di interesse, e il substrato, grigio chiaro, sar lo sfondo. Si pu notare
come, mentre la maggior parte degli "oggetti" mostrati sia di forma rozzamente
ellittica, alcuni siano pi complessi, perch costituiti dall'accostamento di due
blob. Ci poniamo il problema di separare questi ultimi oggetti nei blob
costituenti, con il fine, ad esempio, di contare le particelle con maggior
accuratezza. Se estendiamo l'idea ad altri tipi di immagini, per esempio
immagini microscopiche rappresentanti cellule o microorganismi, lo scopo
potrebbe essere la separazione di due individui allo scopo di poterne indagare
l'interno senza essere fuorviati dagli accoppiamenti casuali tra blob.
Figura 17. L'immagine di partenza per l'applicazione del GA allo scopo di separare i "blob"
accoppiati.
Separare oggetti visualmente connessi un problema che si pone spesso, in
analisi d'immagini. Per richiamare un altro campo di applicabilit, possiamo
considerare il caso dei noduli polmonari con contatto vascolare. A differenza dei
40
noduli detti "isolati", relativamente facili da individuare con un sistema
automatico perch lontani da strutture che potrebbero in parte mascherarne la
natura (in particolare i vasi che irrorano i polmoni), i noduli vascolari crescono a
contatto con un vaso (figura 18) e con esso tendono a confondersi.
Figura 18. Particolare di un'immagine di tomografia computerizzata (TAC), che mostra un nodulo polmonare (struttura tondeggiante al centro dell'immagine) con contatto vascolare (il vaso parzialmente visibile, nel quadrante destro in basso). Tratta da [9]
L'applicazione del codice GA al problema della separazione dei blob "doppi"
nell'immagine di figura 17 , comporta naturalmente alcune scelte, in particolare:
a. quale modello di blob si pu adoperare nella segmentazione, ossia
nell'individuazione dei singoli blob costituenti quelli "doppi"?
b. di che tipo di preelaborazione necessita l'immagine, al fine di essere
inserita nell'algoritmo GA?
c. quali sono i parametri da introdurre nel modello, che poi diverranno i
parametri genetici del GA?
d. qual la funzione obiettivo da massimizzare o minimizzare?
41
Naturalmente le risposte alle varie domande sono tutte tra loro connesse.
Cominciamo dal punto (a). Siccome i blob hanno forma grossolanamente
ellittica, si pu proporre un modello semplificato che individui ciascuno dei blob
tramite un'ellisse generica (ossia di assi principali, centro, e inclinazione
arbitrari). Il software Matlab necessario per il tracciamento di un'ellisse, dati i
suddetti cinque parametri stato reperito all indirizzo riportato in nota 7.
La scelta del modello semplificato in forma di ellissi porta facilmente al punto (b),
perch una preelaborazione possibile l'individuazione dei bordi degli oggetti, in
modo tale che ciascuno sia rappresentato solo dai propri pixel di bordo. Con la
definizione del modello, resta anche definito il punto (c), perch saranno usati i
menzionati cinque parametri (variabili entro limiti ragionevoli e dipendenti dalle
dimensioni dell'immagine e dei blob) come geni, da far evolvere con le regole dei
GA. Per definire il punto (d) conviene mostrare l'immagine originale dopo la
preelaborazione, con sovrapposta un'ellisse generica (figura 19):
Figura 19. L'immagine originale dopo preprocessing (individuazione dei bordi), con un'ellisse generica sovrapposta.
Conviene ricordare che un'immagine essenzialmente una matrice le cui celle (i
pixel, picture element) hanno un valore che varia da 0 per il colore nero, ad un
valore massimo per il bianco (usualmente il valore 1, se i pixel sono rappresentati
7 http://carmelab.huji.ac.il/software/General/general.html
42
con numeri reali, o 255 se con numeri interi a 8 bit). Nel caso delll'immagine
nella figura 19 (preelaborata), la matrice contiene solo due valori: 0 per i pixel
neri, e 1 per i pixel bianchi ( una immagine binaria). Siccome lo scopo
dell'esempio sovrapporre l'ellisse (in verde nella figura 19) ai singoli elementi
costitutivi l'immagine (bordi dei blob), risulta intuitivo proporre come funzione
da massimizzare semplicemente la somma dei valori dei pixel sui quali l'ellisse si
pone, somma che tende a raggiungere un massimo quando la sovrapposizione
perfetta.
Cos facendo, i quattro punti da (a) a (d) sono tutti esplicitati, e si pu passare alla
codifica del programma.
Per semplicit, anzich scrivere un codice che individui tutti i blob, isoleremo
dapprima uno di quelli "doppi", e poi lavoreremo su quello. Chiaramente,
cercare i blob sull'intera immagine comporta semplicemente di trovare via via i
singoli blob, eliminandoli ogni volta dall'immagine prima di ripetere
l'applicazione dell'algoritmo per individuare il blob seguente.La figura n.19
mostra, quindi, un unico oggetto "doppio", previo preprocessamento.
Figura 20. L'immagine originale dopo preprocessing (individuazione dei bordi),e la scelta di un unico oggetto composito.
In base a quanto detto, stata allestita un'interfaccia software (Appendice B)con
il codice GA gi descritto in Appendice A. Tale interfaccia carica limmagine,la
43
preelabora, definisce i parametri tipici della simulazione (popsize=20;
dimension=5; stringlength=5; x_bound=[5 30; 5 30; 90 150; 90 150; 0 pi];
pm=0.5;), la funzione di fitting, e lancia il codice GA. L'immagine seguente
mostra un momento della simulazione, con la popolazione attuale di ellissi
sovrapposte all'oggetto da segmentare.
Figura 21. Una fase della simulazione, con parte della popolazione attuale di ellissi via via sovrapposte all'oggetto da segmentare.
Le prossime immagini si riferiscono invece a due risultati, ottenuti in run diversi,
sovrapposti all'immagine originale. Come si vede, il sistema ha efficacemente
individuato sia una che l'altra parte dell'oggetto composito, a seconda della
popolazione iniziale e delle scelte via via fatte dal programma riguardanti quali
individui accoppiare, come, dove effettuare le mutazioni, e cos via: tutte queste
scelte sono casuali (o meglio, pseudocasuali) e quindi determinano un risultato o
l'altro. Dopo ciascun risultato, anche mostrato l'andamento della funzione di
fitness durante la simulazione.
44
Figura 22. Sovrapposizione allimagine di partenza dellellisse ottenuta come risultato dellesecuzione del GA nel run a (a sinistra) e b (a destra) .
Figura 23. Andamento della fitness media della popolazione(in blu) e del valore massimo di fitness(in rosso) in funzione del numero di iterazioni per il run a(a sinistra) e b(a destra).
0 50 100 150 200 250 300 350 400 450 5000
10
20
30
40
50
60
Iterazione
Fitn
ess
max fitnessmean fitness
0 50 100 150 200 250 300 350 400 450 5000
10
20
30
40
50
60
Iterazione
Fitn
ess
max fitnessmean fitness
45
Conclusioni
Argomento di questa Tesi di Laurea sono gli algoritmi evolutivi, in particolare
gli algoritmi genetici (GA): si tratta di metodi matematici applicabili
allottimizzazione di funzioni di un numero arbitrario di variabili. I GA
appartengono ad una linea di pensiero, affermatasi negli ultimi decenni, che
consiste nell'emulare il migliore schema organizzativo a nostra disposizione: la
Natura. L'approccio computazionale sempre pi ispirato ai modelli biologici,
dai quali c' molto da imparare essendo essi il risultato migliore ottenuto dopo
millenni di tentativi. Inoltre le attuali capacit informatiche ci permettono di
muoverci abilmente, creando dei mondi virtuali in cui far crescere ed evolvere
soluzioni a problemi altrimenti molto complessi da risolvere.
Dopo una descrizione teorica dei GA, si verificata la gran diffusione che essi
hanno attualmente, in tanti campi della scienza, constatando la costante
crescita del numero di articoli di Ricerca in questambito. Sono state descritte
brevemente alcune applicazioni di grande interesse, tra cui la progettazione di
circuiti elettronici. Infine, volendo verificare sul campo lefficacia dei GA, si
studiato, completato, e applicato un software GA alla ricerca del massimo di
una funzione ad una variabile, e ad un problema classico della segmentazione
di immagini, ossia la separazione di oggetti.
Lesperienza cos maturata ha confermato lefficacia degli algoritmi GA.Da un
punto di vista teorico e applicativo, la Tesi ha analizzato solo l'incrocio tra due
organismi aploidi e la mutazione. Molta ricerca si spinge nella direzione di
incorporare nella sintesi dei GA anche meccanismi biologici pi complicati
quali la dominanza, la trasposizione, la differenziazione sessuale e la
regolazione genetica. Mediante quest'ultima i geni degli organismi biologici si
regolano reciprocamente in maniera indiretta. In questa maniera ad ogni
46
situazione specifica solo determinati geni sono attivi, rendendo un sistema cos
complesso estremamente specifico e adattivo.
I GA dunque promettono di divenire strumenti sempre pi potenti e utili nella
ottimizzazione della ricerca di una soluzione di problemi fisici.
47
APPENDICE A
Codice MATLAB "Punto di massimo di una funzione
Il codice inserito e descritto in quest'appendice incluso in [10].L'articolo reperibile in Rete
all'indirizzo
http://www.ccsenet.org/journal/index.php/mas/article/download/9230/6779 (accesso al sito
effettuato in settembre 2013).
Il software stato lievemente corretto in alcune parti dove figuravano errori di stampa, ed
stato integrato con sezioni di codice adoperate per la visualizzazione della funzione di fitness,
per la stampa a video della popolazione di individui, per la raffigurazione della procedura di
selezione tramite roulette. Sono stati poi inseriti ampi commenti per la comprensione
approfondita dell'algoritmo adoperato. Il programma, nell'inserimento nella Tesi, ha sofferto
della limitazione sul numero di colonne di testo disponibili, dovuto alle scelte sui margini della
pagina; pertanto, alcune delle righe di codice risultano suddivise su pi righe di testo. Di ci si
dovr tenere conto nel caso in cui si volesse effettuare un test del codice riportandolo in un file
Matlab per l'esecuzione.
function [value,x] = test03 %% Massimizzazione della funzione obiettivo (coincidente con % la funzione di fitness) entro i bound % % Lanciare con % [val x] = test03 % oppure semplicemente % test03; % iteraz = 5; % numero iterazioni % Le prossime variabili sono: % popsize: numero di individui della popolazione % dimension: numero di parametri che costituiscono un % individuo % stringlength: numero di bit di ciascun parametro % x_bound: valori limite per il o i parametri % pm: probabilita' di mutazione popsize=2; dimension=1; stringlength=5; x_bound=[0,31]; pm=0.5; % grafico la funzione di fitness (contenuta nella function funname) fplot(@(x) funname(x), x_bound) xlabel('x') ylabel('fitness') drawnow % genero la popolazione iniziale, casuale pop=encoding(popsize,stringlength,dimension); % dalla popolazione iniziale in rappresentazione binaria, % calcolo i valori della funzione obiettivo
48
pop=decoding(pop,stringlength,dimension,x_bound); % trovo l'individuo con il massimo valore della funzione % obiettivo (andra' in 'choice') % choice_number e' il valore della funzione obiettivo, % choice_k e' l'indice corrispondente in pop [choice_number,choice_k]=max(pop(:,stringlength*dimension+1)); choice=pop(choice_k,:); maxfit = [choice_number]; meanfit = [mean(pop(:,stringlength*dimension+1))]; %% Iterazioni per la convergenza for it=1:iteraz % numero iterazioni fprintf('\n########## ITERAZIONE N. %d ###################\n', it) % stampa l'attuale popolazione fprintf('\n------- Popolazione attuale --------\n') printPop(pop,stringlength,dimension,x_bound) % effettua crossover e mutazione; il crossover duplica la popolazione pop=cross_over(pop,popsize,stringlength,dimension); pop=decoding(pop,stringlength,dimension,x_bound); fprintf('\n------- Popolazione dopo crossover ------\n') printPop(pop,stringlength,dimension,x_bound) pop=mutation(pop,stringlength,dimension,pm); pop=decoding(pop,stringlength,dimension,x_bound); % stampa l'attuale popolazione duplicata fprintf('\n------- Popolazione dopo mutazione------\n') printPop(pop,stringlength,dimension,x_bound) % trovo l'individuo con il massimo valore della funzione obiettivo [number,k]=max(pop(:,stringlength*dimension+1)); % se il valore e' maggiore di quello individuato al ciclo precedente, % lo conservo con il corrispondente individuo in choice_number % e choice rispettivamente if choice_number
49
% decoding calcola il valore della funzione di fitting % Parte dalle rappresentazioni binarie, le trasforma in un numero tra 0 e % 1, scala tale numero tra x_bound(*,1) e x_bound(*,2), per poi calcolarvi % il valore della funzione di fitting, inserito nell'ultima colonna di pop function pop=decoding(pop,stringlength,dimension,x_bound) popsize=size(pop,1); temp=2.^(stringlength-1:-1:0)/(2^stringlength-1); for i=1:dimension bound(i)=x_bound(i,2)-x_bound(i,1); end for i=1:popsize for j=1:dimension m(:,j)=pop(i,stringlength*(j-1)+1:stringlength*j); end x=temp*m; x=x.*bound+x_bound(:,1)'; pop(i,stringlength*dimension+1)=funname(x); end end function new_pop=cross_over(pop,popsize,stringlength,dimension) match=round(rand(1,popsize)*(popsize-1))+1; for i=1:popsize fprintf(' CROSSOVER tra individuo di indice %d e individuo di indice %d, \n', i, match(i)) [child1,child2]=cross_running(pop(i,:),pop(match(i),:),stringlength,dimension); new_pop(2*i-1:2*i,:)=[child1;child2]; end end function [child1,child2]=cross_running(parent1,parent2,stringlength,dimension) cpoint=round((stringlength-1)*rand(1,dimension))+1; for j=1:dimension fprintf('(componente %d): bit %d (da sinistra)\n', j, cpoint(j)) child1((j-1)*stringlength+1:j*stringlength)=... [parent1((j-1)*stringlength+1:(j-1)*stringlength+cpoint(j)) parent2((j-1)*stringlength+cpoint(j)+1:j*stringlength)]; child2((j-1)*stringlength+1:j*stringlength)=... [parent2((j-1)*stringlength+1:(j-1)*stringlength+cpoint(j)) parent1((j-1)*stringlength+cpoint(j)+1:j*stringlength)]; end end function new_pop=mutation(new_pop,stringlength,dimension,pm) new_popsize=size(new_pop,1); for i=1:new_popsize if rand
50
x=binary2number(pop,stringlength,dimension,x_bound); drawRoulette(x, fitness, r, it) snapnow % accumulo la fitness fitness=cumsum(fitness); % fitness normalizzata cumulativa for i=1:popsize % devo scegliere popsize soluzioni: per ciascuna... for j=1:popsize_new % ciclo sulle popsize_new disponibili e... if r(i)
51
for i = 1 : stringlength fprintf('%d ', pop(k, (j-1)*stringlength+i)) end fprintf(' - ') end for j = 1 : dimension fprintf(' %10.4f ', x(k, j)) end fprintf(' --- fitness %12.6f\n', pop(k, stringlength*dimension+1)) end % k fprintf('\n') end
APPENDICE B
Codice MATLAB Segmentazione immagini
L'appendice riporta la sezione iniziale del codice di segmentazione dell'immagine
'blobs.gif', che illustra il caricamento dell'immagine, l'applicazione dell'operatore di
edge (individuazione dei margini degli oggetti), la selezione di uno degli oggetti
compositi (le due particelle di oro accoppiate). E' inoltre mostrato il calcolo della
funzione di fitness. Il resto del codice coincide con quello presente in appendice A,
tranne che per il mancato uso della rappresentazione grafica della funzione di fitness
(che qui non algebrica) e per la soppressione della visualizzazione della roulette:
quest'ultima, data la numerosit della popolazione, sarebbe stata scarsamente
interessante. La libreria di funzioni da cui tratto il calcolo dei punti dell'ellisse,
adoperato nella funzione di fitness, reperibile su
http://carmelab.huji.ac.il/software/General/general.html (accesso effettuato in settembre
2013) function [value,x] = test04 % % Lanciare con % [val x] = test04 % oppure semplicemente % test04; % global L3g global ecolor addpath GeneralTools %% Caricamento immagine ecolor = 'b'; I = imread('blobs.gif');
52
figure, imshow(I) BW1 = edge(I,'canny'); figure, imshow(BW1) % individuo l'oggetto doppio L = bwlabel(BW1); stats = regionprops(L,'basic'); areas = [stats.Area]; hist(areas); idx = find(areas > 110); L2 = zeros(size(L)); for j = idx L2(L == j) = j; end figure, imshow(L2, []) L3 = L2 == 29; G = fspecial('gaussian',[3 3],1); L3g = imfilter(double(L3), G, 'same'); figure, imshow(L3g) % 5 parametri: % x(1) e x(2) sono gli assi (limiti: da 100 a 150) % x(3) e x(4) sono le coordinate (x,y) del centro % (limiti da 90 a 150, e da 90 a 150) % x(5) e' l'angolo di rotazione (da 0 a pi) % Le prossime variabili sono: % popsize: numero di individui della popolazione % dimension: numero di variabili che costituiscono un individuo % stringlength: numero di bit di ciascuna variabile % x_bound: valori limite per la o le variabili % pm: probabilita' di mutazione popsize=20; dimension=5; stringlength=5; x_bound=[5 30; 5 30; 90 150; 90 150; 0 pi]; pm=0.5; %% Massimizzazione della funzione obiettivo (coincidente con la funzione di fitness) entro i bound iteraz = 500; % numero iterazioni %%%%%% DA QUI IN POI IL CODICE COINCIDE CON QUELLO DELL'APPENDICE A %%%%%% SI RIPORTA SOLO LA FORMA DELLA funname, LA FUNZIONE DI FITNESS end function y=funname(x) global L3g global ecolor ax = [x(1) x(2)]; center = [x(3) x(4)]; rot = x(5); no_points = 50; ell = ellipse(ax, center, rot, no_points); hold on plot(ell(1,:), ell(2,:), ecolor) y = sum(improfile(L3g, ell(1,:), ell(2,:))); end
53
BIBLIOGRAFIA
[1] Charles Darwin, On the origin of species by means of natural selection or the preservation of favoured races in the struggle for life , John Murray, London, 1859.
[2] John Holland, Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control and Artificial Intelligence, MIT Press Cambridge, MA, USA 1992.
[3] Gregory S Hornby , Automated Antenna Design with Evolutionary Algoritms,2006,sito visitato in Settembre 2013.
Disponibile allindirizzo: http://alglobus.net/NASAwork/papers/Space2006Antenna.pdf
[4] Gibson, S.E., Charbonneau, P . Empirical modeling of solar corona using genetic algorithms, Space Physics, Volume 103, Pags 14511-14521
[5] U. Maulik, Medical Image Segmentation Using Genetic Algorithms, IEEE Transactions on Information Technology in Biomedicine", vol 13, no. 2, March 2009
[6] Jos A. Garca Gutirrez, Carlos Cotta, and Antonio J. Fernndez-Leiva, "Evolutionary Computation in Astronomy and Astrophysics: A Review", Proceedings of CoRR ,The Computing Research Repository 2012.
[7] J.H.Koza, M.A.Kane e M.J.Streeter; Levoluzione delle invenzioni, Le Scienze, Marzo 2003.
[8] Valerio Lacagnina, Algoritmi genetici,Universit di Palermo,Ottobre 2003.
[9] Y. Song et al., Location Classification Of Lung Nodules With Optimized Graph Construction, 9th IEEE International Symposium on Biomedical Imaging (ISBI), Barcelona 2012. [10] C. Guo & X. Yang, A Programming of Genetic Algorithm in Matlab7.0, Modern Applied Science, Vol. 5, No. 1; February 2011
54
55