Algoritmi genetici e programmazione genetica · programmazione genetica, descrivendo gli aspetti...

Scuola Politecnica e delle Scienze di Base Corso di Studi in Ingegneria Informatica

tesi di laurea in Intelligenza artificiale

Algoritmi genetici e programmazione genetica

Anno Accademico 2015/2016 relatore Ch.mo prof. Carlo Sansone candidato Pierluigi Filosa matr. N46/1180

Alla mia famiglia, per aver creduto in me ed essere stati guida e stimolo per la mia crescita personale e professionale.

Indice

Introduzione 1

1 Algoritmi genetici 21.1 L’algoritmo genetico di J. H. Holland . . . . . . . . . . . . . . . . . . . . . . . 21.2 Operazioni genetiche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.3 Come funzionano gli AG? Il teorema degli schemi . . . . . . . . . . . . . . . . . 6

2 Programmazione genetica 92.1 Terminal set e Function set . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.2 Inizializzazione della popolazione . . . . . . . . . . . . . . . . . . . . . . . . . 112.3 Operazioni genetiche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

3 Un esempio di programmazione genetica 143.1 Fasi preparatorie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143.2 Esecuzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

4 TinyGP 194.1 Caratteristiche . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194.2 Input data files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204.3 Compilazione ed esecuzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

Conclusioni 23

Bibliografia 24

I

Introduzione

Gran parte dei problemi trattati dall’intelligenza artificiale consistono nella ricerca di un massimo

o minimo globale in uno spazio ricerca limitato. Spesso le tecniche esatte di risoluzione non sono

in grado di espletare soluzioni in tempi ragionevoli; per tale motivo, per questo particolare tipo

di problemi, risultano più efficienti algoritmi di tipo euristico [8]. Gli algoritmi genetici e la pro-

grammazione genetica rientrano nella famiglia degli algoritmi evolutivi: un insieme di tecniche

euristiche in grado di risolvere problemi di ricerca globale imitando i processi di selezione ed evo-

luzione naturale. Questi algoritmi si basano sul principio darwiniano secondo cui gli individui più

“adatti” all’ambiente hanno più probabilità di sopravvivere e di trasmettere i propri caratteri alle

generazioni successive.

Introdurremo, inizialmente, gli aspetti fondamentali di un algoritmo genetico, per poi tratta-

re nel dettaglio il modello di algoritmo genetico proposto da J. H. Holland. Seguirà una breve

panoramica sulle operazioni genetiche, un insieme di tecniche che permettono l’imitazione del

processo evolutivo, per poi concludere con una piccola trattazione matematica sul funzionamen-

to degli algoritmi genetici. Successivamente ci concentreremo in maniera più approfondita sulla

programmazione genetica, descrivendo gli aspetti chiave e le caratteristiche principali di questa

tecnica. Negli ultimi due capitoli tratteremo due esempi di programmazione genetica. Il primo

sarà un semplice esempio illustrativo di regressione simbolica, nel quale verranno evidanziate le

fasi preparatorie atte a specificare gli ingredienti che il processo evolutivo utilizzerà per la gene-

razione di soluzioni, nonché il processo di evoluzione stesso. Infine nell’ultimo capitolo descri-

veremo in maniera sintetica un sistema di programmazione genetica reale, TinyGP, sviluppato e

implementato da Riccardo Poli.

1

Capitolo 1

Algoritmi genetici

Gli algoritmi genetici (AG) sono algoritmi di ricerca euristici ispirati al principio della selezione

naturale ed evoluzione biologica teorizzato da Charles Darwin nel 1895. L’obiettivo degli AG

è quello di trovare una soluzione ottimale di un determinato problema di ricerca, simulando le

meccaniche che governano l’evoluzione biologica e la riproduzione sessuale presenti in natura.

La ricerca parte da una popolazione iniziale di individui, detti cromosomi, che rappresentano

ipotetiche soluzioni al problema dato. Ogni individuo della popolazione è codificato in una stringa

composta da simboli di un alfabeto finito, detti geni, dove ogni gene rappresenta un’istanza di un

particolare simbolo del suddetto alfabeto, detto allele. Alla pari del processo evolutivo biologico,

nel contesto degli AG, la popolazione iniziale di individui evolve dando origine ad una nuova

generazione caratterizzata da individui tendenzialmente “migliori” della precedente in termini di

adattabilità all’ambiente, ovvero che risolvono più efficacemente il problema di ricerca dato. Tale

processo si protrae fino al raggiungimento di un criterio di terminazione prestabilito.

1.1 L’algoritmo genetico di J. H. Holland

Il primo prototipo di algoritmo genetico fu proposto da J.H. Holland nei primi anni ’60 al fine di

implementare i meccanismi di adattamento naturale nei sistemi informatici. L’algoritmo genetico

di Holland prevede una popolazione di N cromosomi di lunghezza prefissata L codificati in codice

binario. L’insieme di tutti i possibili cromosomi rappresenta lo spazio di ricerca, ovvero lo spa-

zio che l’algoritmo esplora durante il processo di ricerca, formato al massimo da 2L cromosomi.

Supponiamo di avere un problema codificato con L = 3 bit: lo spazio di ricerca del problema sarà

2

Scuola Politecnica e delle Scienze di Base – Corso di Studi in Ingegneria Informatica Algoritmi genetici e programmazione genetica

Figura 1.1: Esempio di spazio di ricerca con L = 3.

composto al massimo da 8 cromosomi, rappresentabile geometricamente come un cubo (Figura

1.1).

L’algoritmo genetico formulato da Holland funziona come descritto a seguire. Inizialmente

viene generata, in maniera casuale, una popolazione iniziale di N individui di lunghezza L. Ogni

singolo individuo della popolazione Ci (i = 1, ...,N) viene valutato mediante una funzione di fit-

ness f , la quale restituisce un valore fi, per l’appunto la fitness, proporzionale alla capacità del

cromosoma di risolvere il problema dato. L’algoritmo genera iterativamente una nuova popolazio-

ne di N individui (rimpiazzando completamente quella precedente) applicando alla generazione

corrente le operazioni genetiche fino al soddisfacimento di un criterio di terminazione prestabilito:

questo può essere un numero massimo di generazioni (iterazioni massime dell’algoritmo) Gmax,

oppure il raggiungimento di un valore di fitness accettabile per il problema dato. In figura 1.2 è

riportato un diagramma di flusso che sintetizza il ciclo di vita di un tipico algoritmo genetico.

1.2 Operazioni genetiche

Darwin, osservando le differenze fra specie affini viventi nelle diverse isole dell’Arcipelago delle

Galápagos, si convinse che la lenta modificazione delle specie - la loro evoluzione - era dovuta

principalmente alla selezione naturale: sopravvivono e si riproducono, cioè, gli individui dotati di

caratteristiche più vantaggiose nella lotta per l’esistenza (in sostanza, meglio adattati all’ambiente)

[7]. Analogamente, un algoritmo genetico seleziona i candidati che contribuiranno alla creazione

della nuova generazione in base ai loro valori di fitness, premiando tendenzialmente quelli dotati

3


Figura 1.2: Diagramma di flusso di un tipico algoritmo genetico. Le quantità pr, pc, e pm indicano, rispettivamente, leprobabilità di riproduzione, crossover e mutazione. [4].

di fitness più alta. La probabilità di selezione del generico cromosoma Ci è data da

pi =fi

n

∑k=1

fk

Tale logica di selezione è denominata selezione proporzionale alla fitness oppure selezione a

roulette. Supponiamo di avere una popolazione composta da N = 5 individui con rispettive fitness

f1 = 6.82, f2 = 1.11, f3 = 8.48, f4 = 2.57, f5 = 3.08. Ogni individuo occupa uno spicchio

della roulette proporzionale al suo valore di fitness e, dunque, alla sua probabilità di selezione.

L’algoritmo genera un numero casuale compreso nell’intervallo [0,1) , il quale individua uno

4


Figura 1.3: Selezione a roulette [2].

spicchio di roulette corrispondente all’individuo che verrà selezionato. La roulette per questo

esempio assumerà la forma in figura 1.3.

Un’ulteriore logica di selezione, particolarmente diffusa nella programmazione genetica, è la

selezione a torneo. Si scelgono casualmente due individui dalla popolazione e si genera un nu-

mero casuale r ∈ [0,1] . Se r < k, dove k ∈ [0,1] è un parametro prefissato, si seleziona l’individuo

con fitness più alta, altrimenti quello con fitness più bassa. Infine, i due individui vengono reinse-

riti nella popolazione iniziale, pronti per essere eventualmente scelti per un altro torneo [3].

L’operazione di riproduzione consiste semplicemente nel copiare cromosomi dell’attuale popo-

lazione, precedentemente selezionati, nella generazione successiva.

L’operazione di crossover (Figura 1.4, v. pag. 6), nella sua variante più semplice, detta

crossover a un punto, coinvolge due cromosomi genitori C1 e C2 e, dopo la scelta casuale di una

posizione (o locus), detta punto di crossover, consiste in uno scambio di geni che dà origine a

due nuovi cromosomi figli a partire dai due cromosomi genitori. In tale accezione il primo figlio,

C3, eredita i primi k geni del genitore C1 e gli ultimi L− k geni del genitore C2. Viceversa, il

secondo figlio, C4, eredita i primi k geni del genitore C2 e gli ultimi L− k geni del genitore C1.

L’operazione di crossover appena descritta avviene alla stregua della ricombinazione biologica tra

due organismi aploidi1.

L’operazione di mutazione (Figura 1.5, v. pag. 7) consiste nell’invertire il valore di un singolo

gene, scelto casualmente, di un cromosoma selezionato. Secondo Holland [1], lo scopo dell’opera-

zione di mutazione è quello di garantire la diversità di un dato gene all’interno della popolazione.

1Organismi caratterizzati da un corredo cromosomico costituito da un singolo cromosoma.

5


Figura 1.4: Esempio di crossover.

Per esempio, senza mutazione, ogni cromosoma della popolazione potrebbe avere come primo

gene un “1” , e potrebbe non esserci alcun modo di ottenere un cromosoma con uno “0” nel primo

gene.

1.3 Come funzionano gli AG? Il teorema degli schemi

Holland affermava che gli AG operano esplorando, enfatizzando e ricombinando buoni blocchi

costituenti (combinazioni di bit che conferiscono alti valori di fitness alle stringhe in cui essi sono

presenti) di soluzioni in maniera altamente parallela. L’idea di base è che buone soluzioni sono

tendenzialmente formate da buoni blocchi costituenti. Holland introdusse la nozione di schema

per formalizzare la nozione informale di blocchi costruttori [3]. Un esempio di schema è il piano

frontale del cubo in figura 1.1 (v. pag. 3), ovvero tutte le stringhe di lunghezza L = 3 che hanno

come secondo gene il valore “1”, ovvero: 111,110,011,010. È possibile descrivere tale sottoinsie-

me dello spazio di ricerca mediante la notazione compatta H = ∗1∗2 . Possiamo allora definire

uno schema come l’insieme di tutte le stringhe ottenibili sostituendo al posto del simbolo * gli

altri elementi dell’alfabeto di codifica, lasciando invariati i bit definiti.

Si definisce ordine di uno schema H, indicato con o(H), il numero di bit definiti all’interno

dello schema stesso.

Si definisce lunghezza di uno schema H, indicato con d(H), la distanza tra il primo e l’ultimo

bit definito. Per esempio lo schema H = 1∗∗∗∗1 è di ordine 2 ed ha lunghezza 5.

Ogni stringa di bit di lunghezza L è un’istanza di 2L schemi differenti. Per esempio, la stringa

“11” è un’istanza degli schemi H1 = ∗∗, H2 = 1∗, H3 = ∗1 e H4 = 11. Quindi, una popolazione

2H sta per “hyperplane” (iperpiano), in quanto gli schemi definiscono iperpiani nello spazio L-dimensionale dellestringhe di L bit [3].

6


Figura 1.5: Esempio di mutazione.

di N individui, con1 ≤ N ≤ 2L, è caratterizzata da istanze di un numero di schemi compreso tra

2L e N2L. Di conseguenza, l’algoritmo genetico, pur valutando esplicitamente la fitness di soli

N individui, in realtà elabora implicitamente la fitness media3 di un numero molto maggiore di

schemi. Tale caratteristica degli AG è chiamata parallelismo implicito.

Consideriamo ora gli effetti che apportano le operazioni genetiche alle istanze degli schemi,

trattando in primis l’operazione di selezione. Sia m(H, t) il numero di istanze dello schema H

al tempo t e U (H, t)la fitness media dello schema H al tempo t. Indichiamo, infine, con f (t)la

fitness media dell’intera popolazione. Il numero atteso di istanze di H al tempo t +1 è dato dalla

seguente equazione

E (m(H, t +1)) = m(H, t)U (H, t)

f (t)

La precedente equazione afferma che, se la fitness media di uno schema è maggiore della fit-

ness media dell’intera popolazione, allora il numero di istanze dello schema H al tempo t + 1 è

aumentato.

Consideriamo ora gli effetti del crossover e della mutazione. Sia pc la probabilità di crossover

a singolo punto su un cromosoma, supponiamo inoltre che un’istanza dello schema H sia selezio-

nata come cromosoma genitore. Si dice che lo schema H “sopravvive” al crossover se uno dei

discendenti è anch’esso un’istanza di H. Possiamo definire la probabilità di sopravvivenza di uno

schema H al crossover a singolo punto mediante la seguente formula

Sc (H)≥ 1− pcd (H)

L−1

Dunque gli schemi più piccoli (in termini di lunghezza) hanno più probabilità di sopravvivenza.

Sia pmla probabilità di mutazione di un bit di un cromosoma. Uno schema H “sopravvive” al-

l’operazione di mutazione se tutti i o(H) bit fissi restano invariati. Possiamo definire la probabilità

di sopravvivenza di uno schema H all’operazione di mutazione come

3Con fitness media di uno schema H indichiamo la media delle fitness di tutte le possibili istanze del dato schema.

7


Sm(H) = (1− pm)o(H)

Dunque gli schemi con ordine più basso hanno più probabilità di sopravvivenza.

Unendo i contributi di tutti gli operatori genetici ricaviamo la seguente relazione, nota come

teorema degli schemi :

E (m(H, t +1))≥ m(H, t)U (H, t)

f (t)

(1− pc

d (H)

L−1

)(1− pm)

o(H)

Essa descrive la crescita di uno schema di generazione in generazione: schemi di piccola lunghez-

za, di basso ordine e con fitness media al di sopra della media riceveranno un aumento esponenziale

di istanze nel tempo [3].

8

Capitolo 2

Programmazione genetica

La programmazione genetica (PG), elaborata principalmente ad opera di John R. Koza, è un

metodo per la generazione automatica di programmi in grado di risolvere un determinato pro-

blema a partire da una descrizione di alto livello di quest’ultimo. Analogamente a quanto visto

con gli algoritmi genetici, si tratta di un processo casuale che non garantisce un risultato perfetto,

bensì un risultato ottimale che rispetti determinati criteri prefissati dall’utente. La PG è di fatto

un’estensione degli algoritmi genetici, dove gli individui della popolazione sono programmi, tipi-

camente espressi come alberi sintattici. Per esempio in figura 2.1 è mostrata la struttura ad albero

del programma max(x+ x, x+3∗ y).

2.1 Terminal set e Function set

Le unità basilari per il processo di creazione dei programmi sono i terminali e le funzioni. L’in-

sieme dei terminali, il quale comprende gli input, le costanti e le funzioni senza argomento dei

programmi da generare, è detto terminal set. Il programma in figura 2.1 è composto da due input

(x e y), una costante (5) e da nessuna funzione senza argomento. In analogia alla struttura ad albe-

ro dei programmi, gli elementi appartenenti al terminal set rappresentano i nodi foglia dell’albero

stesso.

L’insieme delle funzioni è detto function set. La scelta del function set per un problema di PG

è strettamente correlato al dominio del problema da risolvere. La gamma delle funzioni disponibili

è molto ampia, trattandosi a tutti gli effetti di un problema di programmazione, e può comprendere:

funzioni booleane, operazioni aritmetiche, strutture di controllo iterative, subroutine generiche etc.

9


Figura 2.1: Esempio di struttura ad albero del programma max(x+ x, x+3∗ y) [5]

[5]. In analogia alla struttura ad albero dei programmi, gli elementi appartenenti al function set

rappresentano i nodi intermedi dell’albero stesso. L’unione di terminal set e function set è detto

primitive set.

Il terminal set ed il function set dovrebbero essere scelti in maniera tale da soddisfare i requisiti

di chiusura e sufficienza [4]. La proprietà di chiusura richiede che ogni funzione del function set

sia in grado di accettare ed elaborare ogni valore e tipo di dato appartente al terminal set, nonché

ogni valore e tipo di dato elaborato dalle funzioni del function set. Tale proprietà è indispensa-

bile poiché le funzioni appartenenti al terminal set potrebbero fallire a tempo di esecuzione[5].

L’esempio classico di funzione che non soddisfa la proprietà di chiusura è la divisione, la qua-

le non può accettare come secondo input lo 0. Per ovviare a tale problema è possibile ricorrere

ad una versione modificata della classica divisione, detta divisione protetta, la quale restituisce,

per esempio, all’evenienza della situazione precedentemente descritta, il valore 1. La proprietà

di sufficienza è soddisfatta quando il primitive set è, per l’appunto, sufficiente per la generazione

di una soluzione al problema da risolvere. Purtroppo tale proprietà è assicurata solo quando l’u-

tente è consapevole che una soluzione al problema dato è ottenibile combinando gli elementi del

primitive set. Supponendo di voler rappresentare una funzione trascendente, per esempio ln(x),

l’insieme P = {x,+,−,∗,%,0,1,2} sarebbe insufficiente per tale problema, poiché non esiste una

combinazione finita degli elementi di P in grado di rappresentare perfettamente la funzione ln(x).

Quando la proprietà di sufficienza non è soddisfatta, la PG può produrre solo risultati approssimati

rispetto a quello desiderato [5].

10


Figura 2.2: Creazione di un albero completo di profondità massima 2 mediante tecnica full. Per ogni iterazionedell’algoritmo, corrispondente ad un dato istante temporale ti, i nodi scelti sono cerchiati in rosso.

2.2 Inizializzazione della popolazione

Alla stregua degli AG e degli altri algoritmi evolutivi, nella PG gli individui della popolazione

iniziale sono generati in maniera casuale. Di seguito verranno descritti tre algoritmi di inizializza-

zione per la popolazione iniziale degli individui: full, grow ed una combinazione delle precedenti

nota come ramped half-and-half [4, 5]. Per gli esempi illustrativi, il primitive set di riferimento

per la generazione degli alberi sarà P = {+ ,− ,∗ ,% ,x ,y ,0 ,1 ,2}.

Fissato il parametro h che decreta la profondità massima consentita per gli alberi, la tecnica

full prevede la scelta casuale di elementi dal function set fino alla profondità massimah, dopodiché

verranno scelti solo elementi dal terminal set per completare l’albero. La figura 2.2 mostra il

processo di inizializzazione di un albero di profondità massima 2 con la tecnica full. Se le funzioni

appartenenti al function set hanno tutte la stessa arità1, la popolazione risultante avrà lo stesso

numero di nodi per ogni albero (valore che definisce la dimensione dell’albero) e quindi la stessa

forma.

Nella tecnica grow i nodi vengono selezionati dall’intero primitive set fino alla profondità

massima h, dopodiché l’albero verrà completato con soli nodi appartenenti al terminal set. Questa

tecnica permette di creare alberi di varie forme e dimensioni; può succedere infatti che ad una data

altezza i nodi scelti siano tutti appartenenti al terminal set, troncando il processo di inizializzazione

dell’albero prima di giungere alla profondità massima h. La figura 2.3 mostra il processo di

1La arità di una funzione è pari al numero di argomenti della stessa. Graficamente corrisponde al numero di ramiuscenti dal nodo.

11


Figura 2.3: Creazione di un albero completo di profondità massima 2 con la tecnica di inizializzazione grow.

inizializzazione di un albero di profondità 2 con la tecnica appena descritta. Notiamo che al passo

2 viene scelto un nodo terminale, troncando il ramo sinistro dell’albero nonostante la profondità

massima non sia stata raggiunta.

Con la tecnica ramped half-and-half metà della popolazione iniziale viene creata con la tec-

nica full, l’altra metà con la tecnica grow. La profondità varia in un intervallo I = [2, hmax] in modo

incrementale, garantendo una maggiore diversità degli alberi in termini di forme e dimensioni. Per

esempio, se la massima profondità è 6, il 20% degli alberi avrà profondità 2, 20% avrà profondità

3 e così via fino alla profondità 6.

2.3 Operazioni genetiche

Analogamente a quanto visto con gli algoritmi genetici, nella PG le operazioni genetiche lavorano

su individui della popolazione selezionati in base alla loro fitness. La logica di selezione più

diffusa nella PG è la selezione a torneo, precedentemente discussa nel capitolo 1.

L’operazione di crossover, denominata subtree crossover, consiste in uno scambio di sottoal-

beri tra gli individui della popolazione selezionati. Dati due alberi genitori, si sceglie in maniera

casuale un punto di crossover (un nodo) per ogni albero. L’albero figlio risultante sarà generato

rimpiazzando il sottoalbero tagliato nel punto di crossover del primo genitore con il sottoalbero

tagliato nel punto di crossover del secondo genitore, come illustrato in figura 2.4.

La forma di mutazione più comune nella PG, la cosiddetta subtree mutation, seleziona in

maniera casuale un punto di mutazione in un albero e sostituisce il corrispondente sotto-albero

tagliato con uno generato casualmente, come illustrato in figura 2.5.

12


Figura 2.4: Esempio di subtree crossover. Da notare che gli alberi sulla sinistra sono soltanto copie dei genitoriselezionati, usate per non alterare la struttura genetica di quest’ultimi [5].

Un’altra forma comune di mutazione è la point mutation, analoga all’operazione di mutazio-

ne degli algoritmi genetici. Nella point mutation viene selezionato un nodo casuale ed in seguito

sostituito con un altro nodo scelto casualmente dal primitive set avente la stessa arità del primo

nodo. La scelta di quali operazioni applicare per la creazione della nuova generazione è proba-

bilistica. Tipicamente, il crossover viene applicato con una probababilità del 90% o superiore,

mentre la mutazione con una probabilità pari circa all’1%. Quando le probabilità di crossover e

mutazione insieme raggiungono un valore p inferiore al 100%, con probabilità 1− p si effettua

un’operazione di riproduzione, analoga all’operazione di riproduzione degli algoritmi genetici.

Figura 2.5: Esempio di subtree mutation [5].

13

Capitolo 3

Un esempio di programmazione

genetica

In questo capitolo tratteremo un esempio illustrativo di programmazione genetica, tratto da [5],

avente come obiettivo l’individuazione di una funzione matematica che fornisca gli stessi valori

della funzione target f (x) = x2 + x+ 1 nell’intervallo [−1,+1]. Il diagramma di flusso in figura

3.1 illustra i vari passaggi che caratterizzano l’esecuzione della programmazione genetica.

3.1 Fasi preparatorie

Lo scopo delle prime due fasi preparatorie è quello di specificare gli ingredienti che il processo

evolutivo utilizzerà per la generazione di potenziali soluzioni, ovvero le composizioni di terminal

e function set. Poiché il problema consiste nel trovare una funzione matematica di una variabile

indipendente, il terminal set sarà composto dalla medesima variabile indipendente, nonché da

costanti numeriche effimere selezionate casualmente in un intervallo prefissato, rappresentate dal

terminale R. Ogni volta che il terminale R viene scelto per la costruzione di un nuovo albero, un

differente numero casuale è assegnato a quel determinato terminale, il quale rimarrà immutato per

tutto il tempo di esecuzione. Dunque il terminal set, T , sarà

T = {x,R}

La scelta del function set è strettamente correlata al dominio del problema da risolvere. Data

14


Figura 3.1: Diagramma di flusso programmazione genetica [5].

la natura del nostro problema, un function set costituito solo dalle operazioni di moltiplicazione

e addizione sarebbe sufficiente, in quanto nella funzione target f (x) compaiono soltanto queste

due operazioni. Tuttavia, per completezza, scegliamo un function set caratterizzato dalle quattro

ordinarie operazioni aritmetiche: addizione, sottrazione, moltiplicazione e divisione. Dunque il

function set, F , sarà

F = {+,−,∗,%} ,

dove % rappresenta l’operazione di divisione protetta discussa nel capitolo 2.

La terza fase preparatoria consiste nel definire una misura di fitness f . Tale misura dovrà

riflettere, per ogni individuo della popolazione, la vicinanza degli gli output di un determinato

programma con la funzione target f (x). Nel nostro esempio la misura di fitness di un determi-

nato programma fp sarà calcolata come somma, in valore assoluto, delle differenze tra l’output

della funzione target f (x) e l’output del programma, calcolate in corrispondenza di n valori dati

15


Figura 3.2: Popolazione iniziale di programmi generata casualmente.

dall’intervallo I = {−1,−0.9,−0.8 . . . 0.8,0.9,1}:

fp =n

∑i=1

| pi − f (xi) |

dove pi corrisponde all’i-esimo valore di output del programma p in corrispondenza dell’i-esimo

valore dell’intervallo I e f (xi) all’i-esimo valore della funzione target f (x) in corrispondenza

dell’i-esimo valore dell’intervallo I. La bontà di una soluzione è maggiore per valori di fitness

bassi, dunque una fitness pari a 0 corrisponde alla soluzione perfetta, ovvero ad una corrispondenza

perfetta tra gli output dell’individuo e quelli della funzione target f (x). Così definita la fitness

di un individuo sarà proporzionale all’area tra la parabola x2 + x+ 1 e la curva che rappresenta

graficamente tale individuo.

Nella quarta fase preparatoria si decidono i parametri di esecuzione. Per rendere ancora

più semplice l’esempio, la dimensione della nostra popolazione sarà pari a quattro. Infine, le

probabilità di crossover, mutazione e riproduzione saranno, rispettivamente, 50%, 25% e 25%.

La quinta e ultima fase preparatoria consiste nella scelta di un criterio di terminazione. Un

criterio di terminazione ragionevole per questo problema è che il processo evolutivo continui di

generazione in generazione fintanto che un individuo risulti con fitness minore di 0,1.

3.2 Esecuzione

La popolazione iniziale sarà composta da quattro individui, mostrati in figura 3.1, generati casual-

mente mediante la tecnica di inizializzazione ramped half-and-half. Il primo individuo, x+1, ha

un valore di fitness pari a 7.7. Il secondo individuo, x2 +1, ha un valore di fitness pari a 11.0. Gli

ultimi due individui, 2 e x, hanno rispettivamente valori di fitness pari a 17.98 e 28.7. Come già

16


Figura 3.3: Comparazione dei grafici degli individui della popolazione iniziale con la funzione target f(x). La curvanera in ogni grafico rappresenta la funzione target, mentre le curve rosse tratteggiate i grafici dei rispettivi individui. Lafitness associata ad ogni individuo è approssimativamente proporzionale all’area compresa tra le due curve[5].

detto in precedenza, la fitness di un individuo sarà proporzionale all’area tra la parabola x2+x+1e

la curva che rappresenta graficamente tale individuo. Dalla figura 3.2, la quale compara i grafici

dei quattro individui generati con quello della funzione x2 + x+ 1, si nota che il primo individuo

generato, ovvero x+1, è quello che più di tutti si avvicina alla funzione target. A questo punto si

applicano le operazioni genetiche alla popolazione iniziale per dare vita alle successive generazio-

ni. Partendo dall’operazione di riproduzione, viene scelto l’individuo ritenuto migliore sulla base

della misura di fitness adottata per il problema. In questo caso, l’individuo migliore è quello con

la fitness più bassa in assoluto: dunque viene scelto per la riproduzione l’individuo x+1.

Successivamente viene eseguita l’operazione di mutazione. Ipotizziamo che venga selezio-

nato, mediante selezione a roulette, il terzo individuo della popolazione iniziale (figura 3.1c). Il

punto di mutazione sarà scelto casualmente tra uno dei tre nodi che caratterizzano l’individuo (in

questo esempio il nodo terminale 2). Infine, viene sostituito il sottoalbero troncato al punto di

mutazione scelto (in questo caso solo il terminale 2) con un albero generato casualmente a par-

tire dai terminal e function set precedentemente dichiarati. In questo esempio, l’albero generato

casualmente è x%x ; la figura 3.4b mostra il risultato finale della mutazione.

Gli ultimi due individui della nuova generazione sono creati mediante l’operazione di cros-

sover, ricombinando il materiale genetico di due individui della popolazione iniziale selezionati,

17


Figura 3.4: Popolazione evoluta in seguito alle operazioni di riproduzione, crossover e mutazione.

ancora una volta, mediante selezione a roulette. Per la prima istanza dell’operazione, supponiamo

che tali individui selezionati siano il primo ed il quarto, rappresentati rispettivamente dagli alberi

in figura 3.1a e 3.2d. I punti di crossover scelti casualmente per i due alberi saranno, rispettivamen-

te per il primo ed il quarto, il nodo “+” ed il nodo “x”. Il risultato di tale operazione corrisponde

all’albero in figura 3.4c. Per la seconda istanza dell’operazione, gli individui selezionati saranno

il primo ed il secondo, rappresentati rispettivamente dagli alberi in figura 3.1a e 3.2b. I punti di

crossover scelti casualmente per i due alberi saranno, rispettivamente per il primo ed il quarto, il

nodo “+” ed il nodo “x” in fondo a sinistra. Il risultato di tale operazione corrisponde all’albero

in figura 3.4d. A questo punto la generazione 1 è completata; poiché l’individuo in figura 3.3d

corrisponde esattamente alla funzione target del nostro problema, quest’ultimo avrà fitness pari a

0: condizione che soddisfa il criterio di terminazione prestabilito.

18

Capitolo 4

TinyGP

In questo capitolo descriveremo in maniera sintetica un sistema di PG reale, TinyGP, sviluppato e

implementato da Riccardo Poli. Il codice e la trattazione completa del sistema sono reperibili in

[5].

4.1 Caratteristiche

TinyGP è un sistema di regressione simbolica avente le seguenti caratteristiche:

1. Il terminal set include un certo numero di variabili in virgola mobile definibili dall’utente

(denominate X1 . . . XN);

2. Il function set è caratterizzato dalle operazioni di addizione, sottrazione, moltiplicazione e

divisione protetta;

3. Il training set, composta da un header e vari casi di fitness, viene letto da file;

4. La selezione avviene tramite la tecnica di selezione a torneo;

5. Implementata la subtree crossover e la point mutation;

6. Implementa variabili statiche che specificano parametri quali dimensione della popolazione,

probabilità di crossover e mutazione, numero massimo di generazioni e così via ;

19


7. La funzione di fitness è calcolata come l’opposto della somma delle differenze, in valore

assoluto, tra l’output del programma attuale e del valore desiderato, per ogni caso di fitness.

Tinygp la massimizza;

8. I programmi sono strutturati come sequenze di istruzioni e dati, secondo la rappresentazione

lineare standard per gli alberi.

4.2 Input data files

Il file di input per TinyGP ha il seguente formato:

La prima riga specifica, rispettivamente, il numero di variabili del sistema, il numero di costanti

casuali nel primitive set, il limite inferiore e superiore per la generazione delle costanti casuali ed

infine il numero di casi di fitness. Per esempio, una parte dei casi di fitness per la funzione sin(x)

per x ∈ {0.0,0.1, ...6.2} è:

il file completo è reperibile al seguente indirizzo: http://cswww.essex.ac.uk/staff/rpoli/TinyGP/sin-

data.txt

20

http://cswww.essex.ac.uk/staff/rpoli/TinyGP/sin-data.txt

http://cswww.essex.ac.uk/staff/rpoli/TinyGP/sin-data.txt


4.3 Compilazione ed esecuzione

Come training set per l’esecuzione di TinyGP scegliamo la funzione sin(x) precedentemente mo-

strata. TinyGP può essere facilmente compilato dalla shell del sistema operativo, producendo un

output simile al seguente:

Notiamo che ad ogni generazione il programma calcola e mostra in output: il numero attuale della

generazione, la fitness e la dimensione media della popolazione, la miglior fitness nonché il pro-

gramma associato a tale fitness, designato come miglior programma per la generazione attuale.

La figura 4.1 mostra nei primi due grafici l’evoluzione della fitness media, della fitness migliore

e della dimensione media dei programmi nell’arco delle generazione; l’ultimo grafico rappresenta

l’andamento del miglior programma a fine esecuzione, avente una fitness di 1.88 e corrispondente

alla seguente funzione:

21


Figura 4.1

22

Conclusioni

In questo elaborato sono stati trattati gli aspetti principali che caratterizzano gli algoritmi genetici

e la programmazione genetica. Sebbene non siano stati menzionati nel corso dell’elaborato, si ri-

tiene giusto elencare alcuni aspetti critici riguardanti le tecniche appena discusse. Trattandosi, per

l’appunto, di metodi di ricerca euristici, la convergenza ad una soluzione non è sempre garantita.

D’altro canto, per garantire la convergenza è spesso necessario ricorrere a popolazioni di individui

di grandi dimensioni. Questo aspetto, unito al fatto che calcolare la fitness di un singolo individuo

richiede la valutazione su un certo training set, porta ad uno sforzo computazionale notevole. Nel

caso particolare della programmazione genetica, l’albero di un programma può anche essere mol-

to complesso; in tal caso il problema non riguarderebbe solo la dimensione temporale, ma anche

quella spaziale che può superare la capacità di memorizzazione di una singola macchina. Da qui

la necessità di realizzare un’implementazione parallela di questo tipo di algoritmi su ambienti di

tipo distribuito, per ovviare anche al problema della memoria insufficiente [8]. Gli algoritmi ge-

netici e la programmazione genetica, sin dalla loro nascita, hanno prodotto innumerevoli risultati

in numerosi contesti applicativi. La programmazione genetica risulta particolarmente efficace, per

esempio, nei problemi di ricerca che non richiedono necessariamente una soluzione esatta; o an-

cora, si è dimostrata un ottimo strumento nei casi in cui il dominio del problema non è del tutto

noto. Per un elenco dettagliato dei risultati ottenuti dalla programmazione genetica è possibile

consultare [5] nonché la vasta bibliografia di John R. Koza.

23

Bibliografia

[1] J.H. Holland, Adaptation in Natural and Artificial Systems: An Introductory Analysis With

Applications to Biology, Control, and Artificial Intelligence, University of Michigan Press,

1975.

[2] Roulette wheel selection, http://www.edc.ncl.ac.uk/highlight/rhjanuary2007g02.php,

16/12/2015.

[3] M. Mitchell, An Introduction to Genetic Algorithms, MIT Press, 1996.

[4] J.R. Koza, Genetic Programming: On the Programming of Computers by Means of Natural

Selection, MIT Press, 1992.

[5] R. Poli, W. B. Langdon and N, F. McPhee, A Field Guide to Genetic Programming,

http://www0.cs.ucl.ac.uk/staff/ucacbbl/ftp/papers/poli08_fieldguide.pdf

[6] W. Banzhaf, F.D. Francone, R.E. Keller, P. Nordin, Genetic Programming: An Introduction

on the Automatic Evolution of Computer Programs and Its Applications, Morgan Kaufmann,

1998

[7] Selezione naturale, Enciclopedia Treccani, http://www.treccani.it/enciclopedia/selezione-

naturale, 2/12/2015

[8] Algoritmi evolutivi e programmazione genetica: strategie di progettazione e parallelizzazione,

http://biblio.cs.icar.cnr.it/tr/scaricaTR.asp?FileID=51, 20/12/2015

[9] Flowchart (Executional Steps) of Genetic Programming,

http://www.genetic-programming.com/gpflowchart.html, 19/12/2015

24

Algoritmi genetici e programmazione genetica · programmazione genetica, descrivendo gli aspetti...

Documents

Transcript of Algoritmi genetici e programmazione genetica · programmazione genetica, descrivendo gli aspetti...