Analisi sperimentale comparativa dell’evolvibilità nei sistemi di evoluzione grammaticale

UNIVERSITÀ DEGLI STUDI DI TRIESTE
Tesi Magistrale in Ingegneria Informatica
Analisi sperimentale comparativa
dell’evolvibilità nei sistemi di evoluzione
grammaticale
LAUREANDO RELATORE
Tagliapietra Danny Chiar.mo Prof. Eric Medvet
Università degli Studi di Trieste
CORRELATORE
Dott. Fabio Daolio
University of Stirling, Stirling
Anno Accademico 2015/2016

Indice
Elenco delle figure iii
Elenco delle tabelle iv
1 Introduzione 1
1.1 Stato dell’arte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2 Evoluzione Grammaticale 4
2.1 Grammatica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Funzioni di Mappatura . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2.1 Standard e Breadth First GE . . . . . . . . . . . . . . . . . . 6
2.2.2 PiGE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2.3 Structured GE . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.3 Inizializzazione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.4 Operatori . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.4.1 One e Two Point(s) Crossover . . . . . . . . . . . . . . . . . . 9
2.4.2 Probabilistic Mutation . . . . . . . . . . . . . . . . . . . . . . 10
2.4.3 Crossover e Mutazione per SGE . . . . . . . . . . . . . . . . . 10
2.5 Selezione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.5.1 Roulette Wheel e Tournament Selection . . . . . . . . . . . . 10
2.6 Rimpiazzamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3 Evolvibilità 12
3.1 Problemi esaminati . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.2 Analisi statica dell’evolvibilità . . . . . . . . . . . . . . . . . . . . . . 14
3.2.1 Procedura sperimentale . . . . . . . . . . . . . . . . . . . . . . 14
3.2.2 Fitness-Probability cloud e AEP . . . . . . . . . . . . . . . . . 15
3.2.3 Risultati e osservazioni: AEP . . . . . . . . . . . . . . . . . . 15
3.2.4 Risultati e osservazioni: Fitness-Probability Cloud . . . . . . . 16
3.3 Analisi dinamica dell’evolvibilità . . . . . . . . . . . . . . . . . . . . . 18
3.3.1 Procedura sperimentale . . . . . . . . . . . . . . . . . . . . . . 19
i

3.3.2 Risultati e osservazioni . . . . . . . . . . . . . . . . . . . . . . 19
4 Ulteriori esperimenti 22
4.1 Ridondanza e località . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4.2 Proposta di mapper con bassa ridondanza . . . . . . . . . . . . . . . 23
4.3 Rappresentazione visiva dei genotipi durante l’evoluzione . . . . . . . 26
5 Considerazioni finali e conclusioni 28
Bibliografia 30
ii

Elenco delle figure
2.1 Esempio di grammatica. . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Esempio della grammatica in 2.1 nella forma BNF. . . . . . . . . . . 5
2.3 Applicazione del mapper GE e BGE. . . . . . . . . . . . . . . . . . . 7
2.4 Esempio di applicazione di One Point Crossover. . . . . . . . . . . . . 9
3.1 Le grammatiche dei problemi considerati. . . . . . . . . . . . . . . . . 13
3.2 AEP vs. dimensione genotipo |g|. . . . . . . . . . . . . . . . . . . . . 18
3.3 Fitness-Probability Cloud per dimensione di genotipo |g| = 1024 (o
quella predefinita per SGE). . . . . . . . . . . . . . . . . . . . . . . . 19
3.4 AEP durante l’evoluzione. . . . . . . . . . . . . . . . . . . . . . . . . 20
3.5 Miglior fitness durante l’evoluzione. . . . . . . . . . . . . . . . . . . . 21
4.1 AEP vs. ridondanza. . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.2 AEP vs. località. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.3 Grammatica del problema SantaFe resa non ricorsiva. . . . . . . . . . 24
4.4 LrGE confrontato con GE, BGE e πGE in termini di ridondanza per
ogni problema con dimensione del genotipo |g| = 1024 . . . . . . . . . 25
4.5 Miglior fitness durante l’evoluzione; confronto col mapper proposto. . 25
4.6 confronto AEP durante l’evoluzione con dimensione del genotipo |g| =
1024. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.7 Rappresentazione dei migliori individui durante l’evoluzione per i
problemi Harmonic, Polynomial, SantaFe e Text . . . . . . . . . . . . 27
iii

Elenco delle tabelle
3.1 Parametri usati per l’analisi statica . . . . . . . . . . . . . . . . . . . 14
3.2 Valori AEP per gli operatori mutazione e crossover. . . . . . . . . . 17
3.3 Parametri usati per l’analisi dinamica. . . . . . . . . . . . . . . . . . 20
iv

Capitolo 1
Introduzione
La necessità di trovare la soluzione a problemi molto complessi nel minor tem-
po possibile ha portato negli scorsi decenni a studiare metodi alternativi a quelli
puramente matematici per risolverli, accettando un compromesso tra tempo di ese-
cuzione ed esattezza della soluzione. Fra questi metodi la computazione evolutiva
(EC) permette l’utilizzo di un sistema evolutivo come un processo computazionale
per la risoluzione di problemi di varia natura, che possono spaziare dalla rilevazione
di frodi al riconoscimento facciale, fino ad arrivare alla risoluzione di problemi di
ottimizzazione. Il sistema evolutivo considerato in EC è basato sul processo naturale
che regola l’esistenza degli esseri viventi e in particolare sulla teoria evoluzionistica
Darwiniana [1], i quali elementi chiave, utili a comprendere i concetti base sul suo
funzionamento, sono i seguenti:
• Uno o più popolazioni di individui in competizione per delle risorse limitate.
• Il cambiamento della popolazione causato dalla morte e nascita di individui.
• Il concetto di fitness che rispecchia l’abilità di un individuo di sopravvivere.
• Il concetto di ereditarietà variabile: i figli non sono identici ai genitori seppur
ci sia una notevole somiglianza.
Similmente a come avviene in natura, l’evoluzione consiste nel variare la popo-
lazione ricombinandone gli individui, ottenendo di volta in volta una nuova popo-
lazione formata da discendenti sempre migliori in termini di fitness, sfruttando il
fatto che, seppur i figli differiscano dai genitori, mantengono comunque una parte
del patrimonio genetico. Questo processo viene iterato più volte con lo scopo di
avvicinarsi il più possibile all’individuo perfetto, ovvero alla soluzione del proble-
ma che ci si era imposti di risolvere. Data l’estrema somiglianza con l’evoluzione
naturale molti termini e concetti usati in EC sono stati assimilati dalla biologia.
1

La computazione evolutiva comprende, oltre al concetto base di evoluzione, vari
algoritmi evoluzionistici che la implementano. Uno tra questi è l’evoluzione gramma-
ticale (GE), particolare algoritmo genetico dove l’elemento fondamentale che costi-
tuisce le caratteristiche di un individuo è il genotipo, espresso come stringa binaria,
allo stesso modo in cui il cromosoma costituisce il fenotipo di un essere vivente.
Sui genotipi viene poi applicata una funzione, detta di mappatura o mapper, che
determina la costruzione di un albero, le quali foglie consistono in una soluzione
di un determinato problema formalizzato con una grammatica; per questo motivo
nella comunità scientifica GE è considerato come un particolare caso della program-
mazione genetica (GP) [2], dato che molti concetti, descritti nel prossimo capitolo,
sono comuni mentre differiscono principalmente per la presenza del genotipo e del
mapper.
Essendo GE, come tutti gli algoritmi genetici, di tipo euristico, non è detto
che una evoluzione porti sicuramente ad una soluzione ottima, nè tanto meno ad
una soluzione che più le si avvicina. Per questo solitamente si è portati a dover
scegliere, non facilmente, la giusta configurazione di rappresentazione, operatori e
parametri (per esempio la dimensione del genotipo [3]) che consenta di risolvere al
meglio il problema considerato, solitamente poco conosciuto. Un modo per ovviare a
questa difficoltà è l’analisi della Fitness Landscape, ovvero lo studio dello spazio delle
soluzioni atto a identificare le caratteristiche di un problema, in modo da aiutare
nella scelta della miglior metaeuristica1
da applicare [4].
In questo studio son state analizzate le misure della Fitness Landscape legate
al concetto di evolvibilità. L’evolvibilità, ovvero la capacità di generare una prole
di individui con miglior fitness ad ogni generazione per tutta la durata dell’evolu-
zione, è solitamente usata per quantificare la difficoltà di un problema, ma qui è
stata esaminata per confrontare diverse varianti di GE (cioè funzioni di mappatura)
usando gli stessi problemi. In particolare è stata analizzata e valutata sperimental-
mente l’evolvibilità di alcuni mapper, variando operatore genetico e dimensione del
genotipo, per quattro differenti problemi comunemente utilizzati come benchmark.
Successivamente un confronto con altre due metriche relative ai mapper (ridondanza
e località) ha mostrato come una bassa ridondanza porti ad un’alta evolvibilità.
1.1 Stato dell’arte
Ad oggi sono stati effettuati numerosi studi per caratterizzare i comportamenti
di GE e l’interazione tra le funzioni di mappatura e operatori genetici, specialmente
1
Metodo euristico per la soluzione di un insieme di problemi combinando diverse procedure a
loro volta euristiche
2

in termini di località e ridondanza2
[5; 6; 7]. In particolare si è scoperto come
la ridondanza sia non uniforme, ovvero presenta una non uniformità nel numero
di genotipi che mappano lo stesso genotipo, e come, durante l’evoluzione, ci sia
un’interazione tra località/ridondanza e altre misure relative all’evoluzione, cioè
dimensione del genotipo e diversità degli individui a livello di genotipo, fenotipo
e valore di fitness. Altri studi sono stati effettuati sulla programmazione genetica
riguardo l’evolvibilità, in particolare sulle metriche adottate [4]. Tra queste ci si è
basati sul concetto di “Fitness Cloud” introdotto in [8] che esprime l’evolvibilità in
termini di correlazione tra il valore di fitness di un individuo genitore e quello dei
suoi figli. In questa tesi ci si è concentrati su due strumenti piuttosto recenti per
la misura dell’evolvibilità: la “Fitness Probability Cloud”, che in essenza mostra la
correlazione tra il valore di fitness del genitore con il tasso che i suoi figli possano
essere migliori, e una misura numerica basata su di essa, chiamata “Average Escape
Probability”, per quantificare la difficoltà di un problema [9].
2
caratteristiche che indicano rispettivamente la correlazione della modifica sul genotipo con la
modifica sul fenotipo che ne deriva e il tasso di fenotipi uguali mappati da diversi genotipi
3

Capitolo 2
Evoluzione Grammaticale
Come anticipato nell’introduzione, l’evoluzione grammaticale è un particolare
algoritmo genetico che ha come aspetto saliente la funziona di mappatura genotipo-
fenotipo. A seguire è riportato un breve elenco delle componenti che, compreso il
mapper, caratterizzano GE:
Grammatica insieme di regole attraverso le quali è possibile rappresentare qual-
siasi stringa della lingua atta a descrivere un problema.
Funzione di mappatura funzione che permette la creazione di un legame tra ge-
notipo, rappresentato come stringa binaria, e fenotipo, rappresentato come
albero.
Operatore genetico funzione che ha il compito di variare la popolazione ricombi-
nandone gli individui.
Inizializzazione processo durante il quale la popolazione iniziale è generata, il
quale può influire sull’intera evoluzione.
Funzione di fitness funzione che quantifica la performance di un individuo una
volta considerato come soluzione di un problema.
Selezione processo per cui tra tutti gli individui della popolazione sono scelti i
migliori secondo un criterio, solitamente il valore di fitness, da far riprodurre.
rimpiazzamento operazione attraverso la quale tra tutti i genitori e i figli generati
vengono scelti gli individui per generare la nuova popolazione, ovvero della
successiva generazione.
A seguire son descritti gli aspetti sopra elencati, comprese le principali varianti,
e alcune delle quali sono state prese in esame per gli esperimenti effettuati.
4

E → EOE
E → V
O → +
O → -
V → x
V → y
Figura 2.1: Esempio di grammatica.
<e> ::= <e> <o> <e> | <v>
<o> ::= + | -
<v> ::= x | y
Figura 2.2: Esempio della grammatica in 2.1 nella forma BNF.
2.1 Grammatica
Una grammatica, qui intesa come generativa, può essere definita come un insieme
di regole grazie alle quali è possibile generare qualsiasi stringa di un determinato
linguaggio, a partire da un simbolo iniziale definito. Di conseguenza formalizza
un algoritmo che genera stringhe linguistiche [10]. Formalmente, dato un insieme
N di simboli non terminali, s0 ∈ N simbolo iniziale, un insieme R di regole di
produzione e un insieme Σ di simboli terminali disgiunto da N, una grammatica
consiste in una quadrupla G = N, s0, Σ, R . Un linguaggio L(G) è definito quindi
come l’insieme di tutte le stringhe composte da simboli non terminali generate a
partire dal simbolo iniziale s0 ed applicando le regole di produzione fintantoché
vi siano solamente simboli terminali. Le grammatiche per descrivere alcuni dei
problemi standard per l’analisi degli algoritmi evolutivi sono libere dal contesto,
ovvero le regole di produzione presentano a sinistra un unico simbolo non terminale.
Un modo canonico per rappresentare le regole di produzione è mostrato in Figura
2.1 dove → rappresenta la produzione, ovvero a partire dai simboli a sinistra, si
“producono” quelli indicati a destra. La forma BNF (Backus-Naur Form [11]) è un
formalismo che dà la possibilità di descrivere la sintassi di un linguaggio in modo
preciso e non ambiguo. Per questi motivi è molto utilizzato, soprattutto in ambito
informatico e in generale per descrivere grammatiche libere dal contesto. Il modo in
cui le regole di produzione sono rappresentate è il seguente, dove espressione può
essere una serie di una o più sequenze composte a loro volta da uno o più simboli
(terminali o non):
<simbolo>::= espressione
5

2.2 Funzioni di Mappatura
Il processo di mappatura è la conversione di un genotipo in fenotipo, ovvero
dato un genotipo e una grammatica context-free di un determinato problema si
costruisce univocamente l’albero di derivazione, dove la radice è il simbolo iniziale, i
nodi i simboli non terminali e le foglie i simboli terminali. Da quest’albero è possibile
leggere la soluzione del problema, in particolare leggendo direttamente le foglie, da
sinistra a destra. Il vantaggio del mapping (e di conseguenza di GE) consiste nel fatto
che può essere applicato per qualsiasi problema che abbia una grammatica che ne
descriva formalmente le soluzioni, senza dover ridefinire gli operatori genetici o altri
componenti dell’algoritmo evolutivo, dato che essi operano sul genotipo (quindi ad
un livello inferiore) che poi viene mappato in una soluzione specifica del problema
scelto. Il mapper originario (standard) utilizzato per la grammatical evolution si
basa sull’operazione di modulo (indicata col simbolo %), ovvero la scelta del nodo
successivo si basa sul resto di una divisione per il numero di regole di produzione che
ha il nodo corrente. Questa operazione viene effettuata fintantoché non si arriva ad
aver solamente simboli terminali e quindi non si ha più la possibilità di espandere
l’albero di derivazione.
Regola selezionata = valore del codone % numero di regole (2.1)
2.2.1 Standard e Breadth First GE
Nello standard GE il genotipo, espresso in binario, viene suddiviso in parti lunghe
n, dette codoni, poi convertite in un numero intero. La procedura di mapping di un
genotipo g in un fenotipo p inizia con p = s0 (simbolo iniziale), un indice i = 0 e un
contatore w = 0. Successivamente i seguenti passi sono iterati:
1. il simbolo non terminale s di p più a sinistra è espanso usando la j−th opzione
della regola rs ∈ R per s, con j = gi mod |rs|, ovvero la divisione in modulo
dell’i−esimo codone per il numero di opzioni della regola rs.
2. l’indice i viene incrementato. Se i ≥ |g|
n
, ovvero se maggiore o uguale del
numero di codoni viene settato a 0 e w incrementato. Se w supera un limite
prefissato nw, il processo di mappatura è terminato e il fenotipo risultante è
nullo.
3. se p contiene almeno un simbolo non terminale si ricomincia al passo 1, altri-
menti il processo è terminato e il fenotipo è esattamente p.
Questa procedura, poiché riutilizza il genotipo fino ad avere un fenotipo composto
da soli simboli terminali, potrebbe non terminare mai (se la grammatica usata è
6

Genotipo:
11000010100000110101001010011110011000111000101001111100
Grammatica:
<e> ::= <e> <o> <e> | <v>
<o> ::= + | -
<v> ::= X | Y
Lunghezza codone: 4
1100 0010 1000 0011 0101 0010 1001 1110 0110 0011 1000 1
010 0111 1100
Genotipo riscritto come sequenza di numeri decimali:
12 2 8 3 5 2 9 14 6 3 8 10 7 12
Soluzione ottenuta applicando GE:
Y+X+X+X
Soluzione ottenuta applicando BGE:
X+Y+X
Figura 2.3: Applicazione del mapper GE e BGE.
ricorsiva), per questo motivo si usa il contatore w, formalmente chiamato “wrapping”
che evita questo spiacevole caso [12]. Agli individui mappati su fenotipo nullo viene
assegnato il peggior valore nel dominio della fitness.
Il mapper BGE (Breadth First GE) è una variante del mapper standard di GE,
dove l’unica differenza consiste nell’ordine di espansione dei nodi non terminali.
Infatti l’espansione è eseguita in ampiezza da sinistra a destra, al contrario del
mapper standard dove avviene per profondità prendendo sempre l’elemento più a
sinistra.
2.2.2 PiGE
Un’altra variante del mapper standard è una sua estensione, la quale ha il van-
taggio di essere indipendente dalla posizione (Position Indipendent GE) [13; 14].
Essenzialmente invece di espandere il simbolo non terminale più a sinistra del fe-
notipo, viene espanso uno scelto utilizzando il genotipo. In dettaglio in πGE ogni
codone consiste in un paio di interi identificati come sequenze di bit entrambe di
lunghezza n. Il primo intero della coppia serve per decidere quale nodo tra i non
terminali espandere, mentre il secondo per la scelta della regola di produzione, come
avviene per il mapper standard. In questo modo la struttura del fenotipo è codificata
nel genotipo e varia anch’essa durante l’evoluzione.
Nodo da espandere = valore del codone % numero di nodi non terminali (2.2)
7

Come per lo standard mapper, anche qui nel caso in cui si termini la lettura del
genotipo prima di arrivare ad una soluzione valida, si opta per il wrapping, con i
dovuti limiti.
2.2.3 Structured GE
SGE è uno dei più recenti mapper, il quale si differenzia da tutti i precedenti
[15]. Questa variante si avvantaggia di una struttura tale che durante la mappatura
ogni codone è utilizzato al massimo una volta per scegliere l’espansione di un nodo
non terminale. Infatti è presente una corrispondenza 1 : 1 tra ogni gene (parte di
un genotipo) e simbolo non terminale, assicurando che la modifica di quel gene non
influisca sulle opzioni di derivazioni degli altri simboli non terminali presenti nel
fenotipo. Di conseguenza questo mapper è strettamente dipendente dalla gramma-
tica in uso e necessita di operatori costruiti su questa sua particolare struttura (per
esempio la mutazione modifica direttamente l’intero codone, andando a sostituirlo
con un altro casuale appartenente allo stesso dominio). Poiché non c’è la possibilità
diretta di riutilizzare il genotipo, una grammatica ricorsiva deve essere convertita
in una non ricorsiva impostando un parametro di massima profondità dell’albero.
I vantaggi di SGE consistono nell’avere, come riportato dagli autori, una maggiore
località e una minore ridondanza. Inoltre ha la peculiarità di mappare un genotipo
sempre in un fenotipo valido, al contrario delle altre varianti.
2.3 Inizializzazione
Per quanto riguarda l’inizializzazione, essa può influire sul risultato dell’evolu-
zione, e perciò è molto importante scegliere una buona dimensione e distribuzione
degli individui [16]. Un metodo alternativo alla generazione puramente casuale de-
gli individui è il cosiddetto Ramped Half and Half, che consiste nella generazione
di individui con diversa lunghezza e cardinalità (caratteristiche che invece nella ge-
nerazione casuale rimarrebbero mediamente costanti). Per lo studio effettuato in
questa tesi è stata usata la generazione puramente casuale.
2.4 Operatori
Negli algoritmi evoluzionistici gli operatori sono i protagonisti nell’esplorazione
nello spazio delle soluzioni del problema. Mentre l’inizializzazione gioca un ruolo
importante sulla varietà iniziale di individui, gli operatori di variazione hanno il
compito di variare la popolazione durante l’evoluzione, diminuendo la probabilità di
ritrovarsi immediatamente in una soluzione ottima locale (chiaramente l’obiettivo è
trovare quella ottima globale).
8

01001000110100010001000
Individuo 1
11010111011101011011101
Individuo 2
0100100 0110100010001000 11011101 110101110111010
0100100 11011101 0110100010001000 110101110111010
010010011011101
Figlio 1
0110100010001000110101110111010
Figlio 2
Figura 2.4: Esempio di applicazione di One Point Crossover.
2.4.1 One e Two Point(s) Crossover
L’operazione di crossover (ovvero ricombinazione) è un processo di scambio in-
formativo tra i membri della popolazione con lo scopo di creare individui con una
miglior fitness. Esso ha la particolarità di variare anche la dimensione degli indi-
vidui, generandone di più grandi o di più piccoli [17]. Mentre in GP l’operazione
di scambio avviene direttamente sugli alberi scambiando due sotto-alberi a partire
da nodi scelti casualmente, in GE lo scambio riguarda porzioni di genotipo, ovve-
ro sotto-stringhe numeriche. In GE sono presenti vari tipi di crossover; qui sono
descritti solo i più comuni, ovvero one e two point crossover e le loro varianti che
mantengono costante la dimensione dei figli (denominate come length preserving
crossover). Nello studio effettuato in questa tesi è stato considerato solamente la
versione di one point crossover che mantiene fissa la lunghezza, dato che durante
l’evoluzione la lunghezza degli individui tende a crescere di molto rallentando l’ese-
cuzione, di fatto andando contro lo scopo della computazione evolutiva di rendere
più veloce la risoluzione dei problemi.
Come visibile in figura 2.4 in one point crossover viene selezionata una posizione
casuale in entrambi i genotipi genitori e le parti a seguire da quelle posizioni sono
scambiate in modo da generare due nuovi membri. Two points crossover opera in
modo similare, selezionando due posizioni e scambiando la parte compresa da esse.
Le due varianti di one e two point(s) crossover che hanno la particolarità di
mantenere la stessa dimensione del genotipo operano spezzando entrambi i genitori
9

nella stessa posizione scelta casualmente. In questo modo la lunghezza degli indi-
vidui di una popolazione è controllata, evitando che vengano generati individui di
dimensione tale da rallentare drasticamente l’evoluzione.
2.4.2 Probabilistic Mutation
La mutazione opera andando a modificare piccole e mirate parti genotipo, nel
caso in cui esso sia binario sono modificati i singoli bit effettuandone un’operazione
detta “flip”, ovvero di inversione. Questo specifico operatore modifica ogni singolo
bit, effettuandone il flip con una probabilità precedentemente impostata.
2.4.3 Crossover e Mutazione per SGE
Poichè il mapper SGE necessita di una particolare struttura del genotipo diversa
dalla stringa binaria, gli operatori sopra descritti non si possono applicare. Gli
autori di questa variante hanno ideato quindi due operatori di crossover e mutazione
adattati per questo caso. In particolare la mutazione si basa su integer flip mutation,
qui inteso come sostituzione dell’intero con un altro casuale all’interno del dominio,
mentre il crossover è simulato da un’operazione di ricombinazione, che, attraverso
una maschera binaria, indica quali parti dei genotipi scambiare [15].
2.5 Selezione
La selezione è il meccanismo usato dalla computazione evolutiva per scegliere
quali genitori far riprodurre. È un processo al quale porre una particolare attenzione,
poiché, come avviene in natura, se si scegliesse soltanto gli individui migliori (e quindi
potenzialmente simili) si rischierebbe di creare una omogeneità tra gli individui
che potrebbe causare una convergenza prematura ad una soluzione ottima locale.
L’operazione di crossover, per sua natura, genera individui con valori di fitness
migliore o peggiore indipendentemente dal fatto che i genitori abbiamo una buona
fitness o meno. Questo fatto, comunemente causato dalla presenza di più soluzioni
ottime locali nello spazio, porta a dover selezionare individui con valori di fitness
non sempre ottimali, in modo da mantenere una certa diversità tra la popolazione
[18].
2.5.1 Roulette Wheel e Tournament Selection
Due metodi per effettuare una selezione volutamente “imperfetta” degli individui
sono i seguenti:
10

Roulette Wheel Detta anche “selezione proporzionale alla fitness”, consiste nel-
l’associare ad ogni individuo una probabilità di essere scelto proporzionale al
suo valore di fitness. In particolare un individuo i ∈ C ha una probabilità
di essere scelto Pi = fi
j∈C fj
. In questo modo si da la possibilità anche ad
individui con bassa fitness di essere selezionati.
Tournament Si applica—ogni volta che si deve scegliere un individuo—prelevando
un sottoinsieme casuale di individui dall’intera popolazione e scegliendone
quello con miglior fitness. Ha inoltre l’abilità di poter variare, cambiando
la dimensione del sottoinsieme da prelevare, la “pressione” della selezione; in-
fatti se la dimensione del sottoinsieme è pari a quella della popolazione, sarà
assicurata la scelta del miglior individuo, se invece la dimensione è pari a 1, si
può considerare la scelta come puramente casuale.
2.6 Rimpiazzamento
Generalmente, avanzando con l’evoluzione, la numerosità della popolazione tende
a crescere, mentre nella computazione evolutiva generalmente è di una dimensione
fissa. Per questo motivo è necessario effettuare un’operazione di rimpiazzamento,
per poter costruire la nuova popolazione combinando nuovi e vecchi individui [18].
I due più comuni metodi utilizzati in GE sono i seguenti:
Steady State consiste nel valutare ogni individuo generato al momento della sua
creazione; se il suo valore di fitness è migliore di quello del peggior individuo
della attuale popolazione, allora viene inserito nella nuova popolazione e il
peggiore eliminato. Poiché questo metodo tende a mantenere solamente gli
individui con miglior fitness, c’è il rischio di una convergenza prematura ad
una soluzione locale.
Generational in questo metodo la popolazione ad ogni generazione è formata da
nuovi individui, con i figli che sostituiscono i genitori. In questo modo l’esplo-
razione dello spazio è più ampio e si evita una immediata convergenza dato che
non sempre le operazioni di crossover e mutazione generano migliori individui.
Per evitare che il valore di fitness migliore della popolazione cali con l’avan-
zare dell’evoluzione, si procede solitamente con l’integrazione di una sorta di
elitismo, mantenendo i migliori individui incontrati durante l’evoluzione.
11

Capitolo 3
Evolvibilità
L’evolvibilità è una caratteristica importante dei sistemi evoluzionistici, può esse-
re definita come l’abilità di apportare dei miglioramenti in termini di fitness variando
casualmente la popolazione degli individui. Dato che in GE avvengono due trasfor-
mazioni, una data dalla funzione di mappatura e una dalla funzione di fitness, lo
studio dell’evolvibilità risulta ancora più interessante dato che le variabili in gioco
sono maggiori rispetto ad altri algoritmi evoluzionistici. L’aggiunta di una trasfor-
mazione attuata dal mapper introduce, come già anticipato, altre due caratteristiche,
ovvero ridondanza degli individui mappati e località delle modifiche. È probabile
di conseguenza che ci sia una relazione tra ridondanza/località e evolvibilità, e di
conseguenza tra quest’ultima e mapper.
Lo scopo di questa tesi è quindi analizzare da quali aspetti dipenda l’evolviblità
e cosa può influire sul suo miglioramento o peggioramento. In particolare si valuterà
l’influenza del tipo di operatore (mutazione e crossover), del mapper utilizzato (GE,
BGE, πGE e SGE) e della dimensione del genotipo. Ad oggi questo è il primo
studio effettuato su questa possibile relazione tra evolvibilità e alcune tra le altre
caratteristiche di GE.
L’analisi è stata suddivisa in due fasi, “statica” e “dinamica”. La prima consiste
nell’analisi dell’evolvibilità applicando più volte gli operatori ad una popolazione
statica di individui. La seconda consiste invece nel valutare l’evolvibilità durante
l’evoluzione, calcolandola ad ogni generazione. Questa scelta di effettuare entrambe
le analisi è derivata dal fatto che l’evolvability possa cambiare drasticamente da un
caso all’altro oppure variare soltanto ad un certo punto dell’evoluzione.
3.1 Problemi esaminati
Per non limitare l’analisi dell’evolvability ad uno specifico caso, si son considerati
quattro problemi di diversa natura: Harmonic, Polynomial, Santa-Fe e Text. Mentre
12

<expr> ::= (<expr><op><expr>) |
(<pre-op><expr>) |
<var>
<op> ::= + | *
<pre-op> ::= uminus | 1/ | sqrt
<var> ::= x
(a) Harmonic
<expr> ::= (<expr><op><expr>) |
(<pre-op><expr>) |
<var>
<op> ::= + | - | * | /
<pre-op> ::= sin | cos | exp | log
<var> ::= x | 1.0
(b) Polynomial
<code> ::= <line> | <code> <line>
<line> ::= <if> | <op>
<if> ::= if(food ahead())<line>
else<line>
<op> ::= left(); | right(); |
move();
(c) Santa-Fe
<text> ::= <sentence> <text> |
<sentence>
<sentence> ::= <Word> <sentence> |
<word> <sentence> |
<word> <punct>
<word> ::= <letter> <word> |
<letter>
<Word> ::= <Letter> <word>
<letter> ::= <vowel> | <consonant>
<vowel> ::= a | o | u | e | i
<consonant> ::= b | c | d | f | g |
h | j | k | l | m |
n | p | q | r | s |
t | v | w | x | y | z
<Letter> ::= <Vowel> | <Consonant>
<Vowel> ::= A | O | U | E | I
<Consonant> ::= B | C | D | F | G |
H | J | K | L | M |
N | P | Q | R | S |
T | V | W | X | Y | Z
<punct> ::= ! | ? | .
(d) Text
Figura 3.1: Le grammatiche dei problemi considerati.
i primi 3 sono dei classici problemi benchmark spesso usati in GE e GP [19], l’ultimo
è stato introdotto in [7] appositamente per lo studio di località e ridondanza. Son
stati scelti questi 4 problemi poiché, date le loro grammatiche e funzioni di fitness
differenti, si crede possano rappresentare al meglio i problemi del mondo reale.
Harmonic In questo problema di regressione lo scopo è quello di approssimare
la funzione f(x) = x
i=1
1
i
e la fitness è l’errore assoluto calcolato nei punti
x ∈ {1, . . . , 50}.
Polynomial Anche qui lo scopo è approssimare la funzione f(x) = x4
+x3
+x2
+x
e la fitness è calcolata nei punti x ∈ {−1, −0.9, . . . , 0.9, 1}.
Santa-Fe Lo scopo è trovare un programma che guidi una formica artificiale per
raccogliere 89 oggetti staticamente distribuiti in una griglia 32 × 32 entro un
massimo numero di passi. La fitness è il numero di oggetti non raccolti.
Text Lo scopo è creare una stringa che combaci con una definita a priori (Hello
world! in questo caso) e la fitness è la distanza di Edit tra le due stringhe.
13

Tabella 3.1: Parametri usati per l’analisi statica
GE, BGE, πGE SGE
# di coppie di genotipi 300 300
# di applicazioni operatori 30 30
Crossover operator One-point SGE crossover
Mutation operator Prob mut, p = 0.01 SGE mut, p = 0.01
Dimensione iniziale genotipo 128, 256, 512, 1024 n.a.
Numero massimo di wraps 5 n.a.
Massima profondità albero n.a. 6
3.2 Analisi statica dell’evolvibilità
Il primo passo per l’analisi è quella identificata come “statica”, ovvero valutare
le performance in termini di evolvibilità applicando i vari operatori e funzioni di
mappatura ad un set di individui generati casualmente.
3.2.1 Procedura sperimentale
L’analisi è stata effettuata seguendo un procedimento cos`ı descritto:
• Per ogni variante di mapper, problema, operatore e dimensione di genotipo
(eccetto per SGE dato che la dimensione è determinata dalla grammatica uti-
lizzata) si son generati 300 genotipi gp (per la mutazione) o coppie di genotipi
g1
p, g2
p (per il crossover).
• Per ogni genotipo o coppia di genotipi sono stati applicati gli operatori per 30
volte, generando ogni volta un figlio gc.
• Successivamente sono state applicate le funzioni di mappatura per i genitori
e per ogni figlio generato ottenendone i fenotipi p1
p, p2
p, pc, valutandone poi i
valori di fitness f1
p , f2
p , fc.
Il processo di generazione dei 300 individui/coppie è stato pensato in modo
che per ogni combinazione di mapper, problema, operatore e dimensione ci siano
effettivamente 300 individui/coppie che assieme al figlio generato non diano dei
risultati di mappatura invalidi (ciò non avviene per SGE poiché di per sé non genera
mappature invalide).
Nella Tabella 3.1 son presenti i parametri utilizzati per le funzioni di mappatura
e gli operatori genetici, oltre ai dettagli del procedimento. I risultati ottenuti sono
espressi in termini di Escape Probability e Fitness-Probability Cloud, condensati
poi nell’indice AEP [9].
14

3.2.2 Fitness-Probability cloud e AEP
La Escape Probability è la probabilità che a partire da un valore di fitness se
ne ottenga uno migliore applicando un operatore genetico. Formalmente, come
descritto in [9], supponendo di partizionare lo spazio delle soluzioni in L + 1 set in
base ai valori di fitness, F = {f0, f1, ..., fL | f0 < f1 < ... < fL} rappresenta tutti
i possibili valori di fitness nello spazio di soluzioni. Si indica la media dei passi
richiesti, a partire da un valore di fitness fi, per trovarne uno migliore. L’Escape
Probability P(fi) è quindi definita come
P(fi) =
1
Si
(3.1)
Maggiore è il valore di Escape Probability per un particolare valore di fitness fi,
più facile è migliorare quel valore. Estendendo questo concetto ad un set di valori
di fitness, Pi indica il valore medio di Escape Probability per gli individui di fitness
maggiore o uguale a fi, definito come:
Pi =
fj∈Ci
P(fj)
|Ci|
, con Ci = {fj | j ≥ i} (3.2)
Se si considerano tutti i Pi per un dato problema si avrebbe un indice di evolvi-
bilità del problema. Ciò può essere rappresentato dalla Fitness-Probability Cloud:
fpc = {(f0, P0), ..., (fL, PL)} (3.3)
Questi valori possono essere condensati calcolandone la media. Questa media
prende il nome di Accumulated Escape Probability (AEP) ed è definita come:
AEP =
fi∈F Pi
|F|
con F = {f0, f1, ..., fL | f0 < f1 < ... < fL} (3.4)
Maggiore è il valore AEP, maggiore è l’evolvability del problema e di conseguenza
più facile da risolvere dovrebbe essere il problema considerato. Di conseguenza
questo indice può essere utilizzato per esprimere, con le dovute approssimazioni, la
difficoltà nell’ottenere soluzioni migliori durante l’evoluzione e quindi, fissati mapper,
operatore e genotipo, la difficoltà del problema.
3.2.3 Risultati e osservazioni: AEP
Per poter comparare i risultati ottenuti da SGE con quelli ottenuti dagli altri
mapper si è deciso di rappresentare la dimensione del genotipo |g| in bit assumendo
per ogni codone il minimo numero di bit necessario per rappresentare il dominio.
Nella Tabella 3.2 sono mostrati i valori di AEP (calcolati distintamente per l’o-
peratore di mutazione e quello di crossover), tra i quali sono evidenziati in grassetto
15

il migliore e gli altri che distano meno del 10% migliore. Gli stessi risultati sono
mostrati in forma grafica in Figura 3.2, dove X è la dimensione del genotipo e Y il
valore di AEP. Dai risultati ottenuti è possibile fare tre considerazioni:
1. si può notare come i più alti valori di AEP si ottengono per mutazione e
crossover a dimensioni di genotipo diverse. Infatti per l’operatore crossover
l’AEP migliore è riscontrabile per dimensioni di genotipo piccole, in particolare
per i problemi Harmonic e Polynomial col mapper SGE, mentre per Sant-Fe
e Text all’incirca con gli altri 3 mapper, per dimensioni di genotipo a 128 bit.
Al contrario, per l’operatore mutazione il miglior AEP è possibile averlo con
dimensioni di genotipo pari a 512 bit o 1024 bit e in particolare con il mapper
πGE.
2. il mapper SGE presenta dei valori AEP generalmente diversi da quelli ottenuti
con gli altri mapper. Applicando l’operatore mutazione, per esempio, con SGE
si ha dei valori di AEP molto più bassi rispetto a tutti gli altri, che in più sono
“coerenti” tra loro, ovvero che per ogni dimensione di genotipo sono simili
tra loro (questo fatto è più visibile nella Figura 3.2). Questo fatto mostra
potrebbe spiegare due aspetti, ovvero che il mapper SGE è strutturalmente
diverso dagli altri 3 (che tra loro hanno la maggior parte delle caratteristiche
in comune), e che a sua volta la decisione del parametro di massima profondità
dell’albero è significativa quanto non semplice da effettuare.
3. i valori medi di AEP in tutti e 4 i problemi rispecchiano a grosso modo la
loro natura. Harmonic e Polynomial hanno valori molto simili, in accordo
col fatto che hanno delle grammatiche simili e sono entrambi dei problemi di
regressione. D’altra parte Santa-Fe e Text hanno valori di AEP più alti il che
suggerisce che la loro difficoltà sia minore rispetto ad Harmonic e Polynomial.
Inoltre Text è il problema dove è possibile notare maggiormente le differenze
tra le varianti di mapper utilizzate.
3.2.4 Risultati e osservazioni: Fitness-Probability Cloud
Proseguendo con l’analisi, sono stati analizzati con più dettaglio i dati con |g| =
1024 (o la dimensione predefinita di SGE). Nella Figura 3.3 è mostrata la Fitness-
Probability Cloud per ogni combinazione di problema, operatore e mapper, dove
l’asse X rappresentata il valore di fitness del miglior genitore (o dell’unico genitore
nel caso di mutazione), mentre l’asse y l’Escape Probability.
Dato che per ogni combinazione sono state generate 300 differenti coppie di
genitori, per aver grafici più chiari si è deciso di scartare un quarto delle coppie
16

Tabella 3.2: Valori AEP per gli operatori mutazione e crossover.
Mutazione Crossover
Problema |g| GE BGE πGE SGE GE BGE πGE SGE
Harmonic
75 0.018 0.129
128 0.067 0.073 0.067 0.023 0.029 0.049
256 0.08 0.092 0.106 0.017 0.023 0.034
512 0.114 0.102 0.111 0.016 0.014 0.026
1024 0.113 0.11 0.12 0.01 0.01 0.016
Polynomial
121 0.019 0.097
128 0.047 0.048 0.049 0.027 0.033 0.058
256 0.067 0.06 0.074 0.019 0.02 0.036
512 0.071 0.072 0.071 0.009 0.012 0.02
1024 0.065 0.065 0.076 0.004 0.004 0.01
Santa-Fe
31 0.008 0.058
128 0.066 0.072 0.054 0.103 0.095 0.099
256 0.071 0.074 0.084 0.064 0.079 0.096
512 0.091 0.112 0.114 0.055 0.06 0.077
1024 0.123 0.141 0.148 0.044 0.058 0.077
Text
85 0.011 0.113
128 0.118 0.146 0.137 0.14 0.196 0.178
256 0.165 0.218 0.272 0.135 0.166 0.189
512 0.173 0.224 0.314 0.086 0.094 0.144
1024 0.203 0.223 0.334 0.057 0.051 0.083
17

0
0.1
0.2
0.3
Mutation
Harmonic Polynomial Santa-Fe Text
0 500 1,000
0
0.1
0.2
0.3
Crossover
0 500 1,0000 500 1,0000 500 1,000
GE BGE πGE SGE
Figura 3.2: AEP vs. dimensione genotipo |g|.
aventi la fitness peggiore (è stata considerata la miglior fitness tra i due genitori) e
raggruppare le rimanenti in 10 intervalli aventi la stessa ampiezza lungo l’asse delle
ascisse. Ad ogni intervallo è stata poi associata la media dei valori di fitness di
ogni coppia di genitori contenuta. La rimozione del quarto di coppie con peggior
fitness ha giovato soprattutto per Harmonic e Polynomial che non hanno una fitness
limitata.
Nella figura 3.3 è possibile notare come l’Escape Probability diminuisca al mi-
glioramento del valore di fitness (si ricorda che per miglioramento si intende una
diminuzione del valore), il che rispecchia il fatto che, man mano che ci si avvicina
all’ottimo con la soluzione, la difficoltà che si ha nel migliorarla aumenta. Questo
comportamento è meno visibile per il problema Harmonic, il quale per sua natura
genera delle soluzioni molto sparse, il che va a distogliere l’attenzione sulla parte più
vicina allo zero (soluzione ottima), le quali curve però hanno un andamento simile
a quelle degli altri problemi.
3.3 Analisi dinamica dell’evolvibilità
Per proseguire l’analisi dal punto di vista dell’evoluzione, si è deciso di analizzare
l’andamento della fitness ad ogni generazione, per vedere quale combinazione di
18

500 1,000
0
0.2
0.4
Mutation
Harmonic
5 10 15 20
Polynomial
60 70 80
Santa-Fe
10 15 20
Text
500 1,000
0
0.2
0.4
Crossover
5 10 15 60 70 80 8 10 12
GE BGE πGE SGE
Figura 3.3: Fitness-Probability Cloud per dimensione di genotipo |g| = 1024 (o
quella predefinita per SGE).
mapper e dimensione genotipo si avvicina maggiormente alla soluzione ottima e con
che velocità (intesa come numero di generazioni).
3.3.1 Procedura sperimentale
Son stati presi in esame i tre mapper basati su stringhe binarie, ovvero GE,
BGE e PiGE, mentre come dimensione genotipo 256 bit e 1024 bit. Gli operatori
scelti sono probabilistic mutation e length preserving one point crossover, applicati
rispettivamente con una percentuale pari a 20% e 80%. Nella Tabella 3.3 è possibile
vedere i parametri utilizzati per l’analisi dinamica. Oltre ad analizzare l’evoluzione
vera e propria, si è tenuto traccia anche dell’indice AEP per vedere se effettivamente,
come si suppone, sussiste una stretta correlazione tra evolvability e miglioramento
della fitness.
3.3.2 Risultati e osservazioni
Come si può vedere confrontando la Figura 3.4 con la Figura 3.5, in media il
miglioramento di fitness è tanto più marcato quanto è presente un alto valore di
Average Escape Probability. In particolare, sia per il valore di fitness che di AEP,
19

Tabella 3.3: Parametri usati per l’analisi dinamica.
Popolazione 500
# di generazioni 50
# di ripetizioni 10
Mapper analizzati GE, BGE, πGE
Operatore Crossover Length Preserving One-point con rate 0.8
Operatore Mutation Probabilistic mutation, p = 0.01 con rate 0.2
Numero massimo di wraps 5
Dimensione iniziale genotipo 256, 1024
Tecnica di inizializzazione puramente casuale
Tecnica di selezione Tournament con dimensione=3
Tecnica di rimpiazzamento Steady-State
20 40
0
0.2
0.4
256bit
Harmonic
20 40
Polynomial
20 40
Santa-Fe
20 40
Text
20 40
0
0.2
0.4
1024bit
20 40 20 40 20 40
GE BGE πGE
Figura 3.4: AEP durante l’evoluzione.
20

20 40
20
30
40
50
256bit
Harmonic
20 40
4
6
8
10
12
Polynomial
20 40
60
80
Santa-Fe
20 40
4
6
8
10
Text
20 40
20
30
40
50
1024bit
20 40
2
4
6
8
10
20 40
60
80
20 40
6
8
10
GE BGE πGE
Figura 3.5: Miglior fitness durante l’evoluzione.
durante l’evoluzione si susseguono due fasi: la prima dove avviene un netto miglio-
ramento degli individui, la seconda dove i miglioramenti sono sporadici e di minor
rilevanza. Questo fatto può essere riferito all’omogeneità (in termini di fitness) cre-
scente della popolazione con l’avanzare dell’evoluzione, dato che alla generazione
successiva son mantenuti gli individui migliori, diminuendo la diversità della popo-
lazione. In questo modo la probabilità di trovare soluzioni migliori cala, come è
visibile in Figura 3.4.
Un’altra considerazione è possibile farla osservando il valore AEP: nonostante il
valore massimo raggiungibile durante l’evoluzione rimanga circa lo stesso variando
la dimensione del genotipo, il numero di generazioni dove esso è diverso da zero è
maggiore per il caso con 256 bit. Ciò è in linea con gli esiti dati dall’analisi statica:
infatti durante l’evoluzione l’operatore prevalente è il crossover, e proprio per il
crossover si ha una maggiore evolvibilità avendo genotipi di piccole dimensioni.
Un altro fatto evidente è che nessuno tra i mapper utilizzati è migliore in assoluto
rispetto agli altri, il che fa propendere che la mappatura genotipo-fenotipo, conside-
rata singolarmente, non giochi un ruolo essenziale nell’apportare un miglioramento
rilevante alle prestazioni del sistema.
21

Capitolo 4
Ulteriori esperimenti
Per cercare di spiegare in modo più esaustivo i risultati ottenuti con lo studio
statico e dinamico dell’Escape Probability, sono state svolte delle analisi aggiun-
tive, con lo scopo di trovare quali caratteristiche possano influire positivamente o
negativamente sull’evolvibilità.
4.1 Ridondanza e località
Per cercare di identificare quali fattori causino l’evolvibilità in GE, si è provato
a studiare la località e la ridondanza, ovvero due proprietà che misurano quanto si
rispetti il principio generale dell’ereditarietà variabile [1].
Località misura con che grado piccole modifiche al genotipo di un individuo corri-
spondono a piccole modifiche al fenotipo. In particolare è calcolato il coefficien-
te di correlazione lineare tra la distanza minima di genotipi min(dg(g1
p, gc), dg(g2
p, gc))
e la distanza minima di fenotipi min(dp(p1
p, pc), dp(p2
p, pc)).
Ridondanza misura quanto spesso diversi genotipi sono mappati su di uno stesso
fenotipo, calcolando la percentuale dei casi in cui il figlio ha genotipo diverso
da quelli dei genitori e ha fenotipo uguale a uno tra quelli dei due genitori.
Per i genotipi è stata utilizzata la distanza di Hamming (dg) mentre per i fenotipi
la distanza di Levenshtein (edit distance, dp). Si son misurate località e ridondanza
separatamente per ogni combinazione di mapper, problema operatore e dimensione
di genotipo, mostrate poi assieme alla retta di regressione lineare e al valore di AEP
nelle figure 4.1 e 4.2. Si ricorda che tutti i parametri hanno un dominio limitato
([0,1] per AEP e ridondanza essendo delle frequenze relative, [-1,1] per la località
espressa come correlazione).
22

0.2 0.4 0.6 0.8
0.1
0.2
0.3
Ridondanza
AccumulatedEscapeProbability
Figura 4.1: AEP vs. ridondanza.
0 0.1 0.2 0.3 0.4
0.1
0.2
0.3
Località
Figura 4.2: AEP vs. località.
La figura 4.1 mostra come ci sia una chiara influenza della ridondanza sull’evolvi-
bilità; in particolare una minore ridondanza porta ad avere una miglior evolvibilità.
Ciò è possibilmente dovuto al fatto che se la mappatura genotipo-fenotipo fatica a
generare individui con genotipo differente da quello dei genitori, si ha una minor
probabilità di avere degli individui con miglior (o peggior) fitness. In questi termini
si suppone che un’adozione di una funzione di mapping incentrata a favorire una
bassa ridondanza possa influire positivamente all’evolvability e di conseguenza alle
prestazioni dell’evoluzione, al contrario di quanto affermato in [20].
Al contrario, la figura 4.2 non esprime alcun forte legame. Infatti il coefficiente di
determinazione della regressione lineare è in questo caso molto baso (R2
= 0.05, al
contrario di quello riguardante la ridondanza, ovvero R2
= 0.45). Questo è spiegabile
dal fatto che la località indica solamente una correlazione tra l’entità della modifica
apportata al genotipo e quella conseguente avvenuta al fenotipo, senza indicare
se questa modifica abbia apportato un peggioramento o una miglioria al valore di
fitness.
4.2 Proposta di mapper con bassa ridondanza
Poiché si è notato come una bassa ridondanza aumenti in media l’escape pro-
bability, si è cercato di implementare una funzione di mappatura, identificata qui
con l’acronimo “LrGE” (Low Redundancy GE), che portasse alla generazione di un
più vario set di fenotipi. Infatti è stato costruito in modo tale che la modifica di un
solo bit influisca su tutto il fenotipo. Inoltre, come SGE, La modalità con cui viene
23

<code> ::= <line> | <code> <line>
<line> ::= <if> | <op>
else<line>
<op> ::= left(); | right(); |
move();
(a) Santa-Fe
<code> ::= <line>
<line> ::= <op>
else<line>
<op> ::= left(); | right(); |
move();
(b) Santa-Fe
Figura 4.3: Grammatica del problema SantaFe resa non ricorsiva.
generato il fenotipo a partire dal genotipo è ricorsiva e simile alla costruzione di un
albero.
1. La mappatura inizia dal simbolo iniziale s0 al quale è associato l’intero genotipo
g.
2. Sia s in p un non terminale al quale è associato una parte del genotipo g
e rs la relativa regola di produzione. Per la scelta dell’opzione da usare per
espandere s si opera in questo modo:
• si divide il genotipo in parti lunghe n =8 bit.
• Posto m come il numero delle parti cos`ı ottenute e vi come la codifica in
valore intero di ogni i-esima parte, l’indice j dell’opzione da scegliere è
cos`ı calcolato: j = m
i=1 vi mod |rs|
3. Scelta l’opzione, il genotipo viene suddiviso in un numero di parti pari al
numero di simboli che contiene l’opzione scelta.
4. Per ogni simbolo viene associata la relativa parte di genotipo e se la dimensione
è maggiore o uguale a 8 bit allora la mappatura continua dal punto 2 avendo
cura di considerare come genotipo la parte associata al simbolo. Se invece
è minore di 8 bit, viene considerato per lo step successivo l’intero genotipo e
come grammatica una sua versione non ricorsiva in modo che da quel punto
in poi si arriverà di sicuro ad un simbolo terminale, come mostrato in Figura
4.3.
Dai grafici mostrati in Figura 4.4 si nota come il mapper proposto abbia una
ridondanza molto minore rispetto agli altri analizzati. Nonostante questa evidente
differenza, le prestazioni in termini di miglior fitness sono lievemente apprezzabili
solamente per la dimensione di genotipo pari a 1024 bit per i problemi Harmonic
e Santa-Fe, mentre pari a 256 bit per il problema Polynomial, come visibile nella
Figura 4.5.
Osservando la Figura 4.6 si nota invece come l’escape probability media abbia un
valore generalmente maggiore (meno evidente per il problema Santa-Fe) e che duri
24

0
0.2
0.4
0.6
0.8
1
Crossover
GE BGE πGE LrGE
0
0.2
0.4
0.6
0.8
1
Mutazione
Harmonic Polynomial SantaFe Text
Figura 4.4: LrGE confrontato con GE, BGE e πGE in termini di ridondanza per
ogni problema con dimensione del genotipo |g| = 1024 .
15
20
25
30
256bit
Harmonic
2
3
4
Polynomial
42
44
46
48
50
Santa-Fe
4
5
6
Text
10 20 30 40 50
10
15
20
25
30
1024bit
10 20 30 40 50
2
2.5
3
3.5
4
10 20 30 40 50
40
45
50
10 20 30 40 50
5
5.5
6
GE BGE πGE LrGE
Figura 4.5: Miglior ﬁtness durante l’evoluzione; confronto col mapper proposto.
25

20 40
0
0.2
0.4
Harmonic
20 40
Polynomial
20 40
Santa-Fe
20 40
Text
GE BGE πGE LrGE
Figura 4.6: confronto AEP durante l’evoluzione con dimensione del genotipo |g| =
1024.
per più generazioni, di fatto andando a confermare la relazione tra bassa ridondanza
e alta evolvibilità.
4.3 Rappresentazione visiva dei genotipi durante
l’evoluzione
L’ultima attività effettuata è stata quella di cercare un modo per avere un re-
sponso visivo dell’andamento evolutivo. Per far ciò si è pensato di effettuare una
conversione in immagine del genotipo con miglior fitness per ogni generazione. In
particolare ogni individuo è rappresentato come sequenza di bit, codificata come
vettore di pixel bianchi o neri, e per ogni generazione viene accodato il miglior in-
dividuo. In questo modo si può notare la permanenza di alcune parti del genotipo
durante l’evoluzione (ereditarietà) causate dalla combinazione di un individuo col
precedente migliore e il ritrovamento di uno con miglior fitness ma proveniente da
un altro ramo di parentela.
In Figura 4.7 è mostrata una evoluzione lunga 150 generazioni di 500 individui
di lunghezza costante pari a 512 bit. Il mapper utilizzato è lo standard GE mentre
gli operatori sono length preserving one point crossover e probabilistic mutation.
Come si può vedere, per un breve periodo prevale un unico individuo, fintantoché
sopraggiunge una combinazione con miglior fitness.
26

Figura 4.7: Rappresentazione dei migliori individui durante l’evoluzione per i
problemi Harmonic, Polynomial, SantaFe e Text
27

Capitolo 5
Considerazioni finali e conclusioni
La funzione di mappatura genotipo-fenotipo gioca un ruolo cruciale e può essere
considerata come la principale motivazione dell’utilizzo di GE come algoritmo di
evoluzione in molti campi di applicazione. D’altra parte molti studi hanno mostrato
come i mapper non aderiscano appieno con il principio di eredità, mostrando bassa
località e alta ridondanza.
In questa tesi si è studiato sperimentalmente l’evolvibilità di GE sia staticamente
(tenendo conto di una singola generazione) che dinamicamente (valutando durante
un’evoluzione lunga 50 generazioni) in differenti condizioni di problema, funzione
di mappatura, dimensione genotipo e operatore genetico. Questa proprietà è stata
analizzata utilizzando il parametro “Accumulated Escape Probabilty” e “Fitness
Probability Cloud”. Inoltre è stata confrontata con la proprietà di località e ridon-
danza per vedere se ci fosse una qualche correlazione. Le conclusioni che si possono
trarre sono le seguenti:
• Per tutti i problemi analizzati, nessuna caratteristica presa singolarmente tra
funzione di mappatura, dimensione del genotipo o operatore genetico porta un
netto miglioramento per quanto riguarda l’evolvibilità del sistema. In questo
senso le performance di un mapper piuttosto che un altro son legate stretta-
mente alla tipologia di problema che si vuole affrontare, e lo stesso vale per
operatore e dimensione del genotipo. Allo stesso modo, osservando i risultati
dinamici, tra le tre varianti di mapper analizzati nessuno predomina in termini
di miglior fitness.
• Un risultato notevole lo si è visto analizzando la relazione tra evolvability e
ridondanza, mostrando quanto possa quest’ultima avere una discreta influenza
sulla prima più di quanto la abbia la località. Infatti si è potuto vedere come
una bassa ridondanza porti ad avere una maggiore evolvibilità, il che può essere
visto come uno spunto per dei futuri studi e approfondimenti.
28

• La ridondanza di un mapper seppur influisca per l’evolvibilità di un sistema,
non è sufficiente a far si che quest’ultimo sia superiore dal punto di vista
prestazionale durante l’evoluzione. Infatti il mapper proposto, nonostante
abbia una ridondanza ben al di sotto del 30%, ha delle prestazioni in linea con
quelle degli altri mapper usati come confronto.
• Riguardo l’ultima parte dello studio, ovvero la rappresentazione dell’evoluzione
sotto forma di immagine, ha dato la possibilità di vedere come soltanto durante
le prime generazioni avvenga l’esplorazione di soluzioni distanti tra loro nello
spazio (genotipi molto differenti tra loro), mentre avviene poi un raffinamento
della migliore, che però non è detto sia la migliore in assoluto. L’immissione di
nuovi individui casuali e l’utilizzo di un operatore che non mantenga costante
la lunghezza del genotipo durante l’evoluzione potrebbe far si che l’esplorazione
dello spazio sia più vasta con la conseguente meno probabilità di imbattersi
prematuramente in soluzioni ottime locali.
Per concludere si può affermare che non esiste una combinazione di funzione
di mappatura, operatore e dimensione del genotipo migliore in assoluto per ogni
problema, piuttosto ogni problema necessita di uno studio mirato a trovare la com-
binazione che dia una maggiore prestazione. Una volta trovata la configurazione ot-
timale, sicuramente una bassa ridondanza porta ad avere una maggiore evolvibilità
e di conseguenza un tempo di esecuzione minore per trovare la soluzione.
29

Bibliografia
[1] Kenneth A De Jong. Evolutionary computation: a unified approach. MIT press,
2006.
[2] Robert I Mckay, Nguyen Xuan Hoai, Peter Alexander Whigham, Yin Shan,
and Michael O’Neill. Grammar-based genetic programming: a survey. Genetic
Programming and Evolvable Machines, 11(3-4):365–396, 2010.
[3] Alberto Bartoli, Andrea De Lorenzo, Eric Medvet, and Fabiano Tarlao. Syntac-
tical similarity learning by means of grammatical evolution. In Parallel Problem
Solving from Nature – PPSN XIV: 14th International Conference, Edinburgh,
UK, September 17-21, 2016, Proceedings, pages 260–269, Cham, 2016. Springer
International Publishing.
[4] Katherine M Malan and Andries P Engelbrecht. A survey of techniques for
characterising fitness landscapes and some possible ways forward. Information
Sciences, 241:148–163, 2013.
[5] Tom Castle and Colin G Johnson. Positional effect of crossover and mutation
in grammatical evolution. In European Conference on Genetic Programming,
pages 26–37. Springer, 2010.
[6] Ann Thorhauer. On the non-uniform redundancy in grammatical evolution.
In International Conference on Parallel Problem Solving from Nature, pages
292–302. Springer, 2016.
[7] Eric Medvet. A comparative analysis of dynamic locality and redundancy in
grammatical evolution. In Genetic Programming: 20th European Conference,
EuroGP 2017, Amsterdam, Netherlands, April 19-21, 2017, Proceedings, page
to appear, Cham, 2017. Springer International Publishing.
[8] Sébastien Verel, Philippe Collard, and Manuel Clergue. Where are bottlenecks
in nk fitness landscapes? In Evolutionary Computation, 2003. CEC’03. The
2003 Congress on, volume 1, pages 273–280. IEEE, 2003.
30

[9] Guanzhou Lu, Jinlong Li, and Xin Yao. Fitness-probability cloud and a mea-
sure of problem hardness for evolutionary algorithms. In European Conference
on Evolutionary Computation in Combinatorial Optimization, pages 108–117.
Springer, 2011.
[10] Maggie Johnson and Julie Zelenski. Formal grammars, 2012.
[11] J.W. Backus. The syntax and semantics of the proposed international algebraic
language of the zuricacm-gamm conference. 1959.
[12] Michael O’Neill and Conor Ryan. Grammatical evolution. IEEE Transactions
on Evolutionary Computation, 5(4):349–358, 2001.
[13] Michael O’Neill, Anthony Brabazon, Miguel Nicolau, Sean Mc Garraghy,
and Peter Keenan. πgrammatical evolution. In Genetic and Evolutionary
Computation Conference, pages 617–629. Springer, 2004.
[14] David Fagan, Miguel Nicolau, Michael O’Neill, Edgar Galván-López, Anthony
Brabazon, and Sean McGarraghy. Investigating mapping order in πge. In IEEE
Congress on Evolutionary Computation, pages 1–7. IEEE, 2010.
[15] Nuno Louren¸co, Francisco B Pereira, and Ernesto Costa. Sge: a structu-
red representation for grammatical evolution. In International Conference on
Artificial Evolution (Evolution Artificielle), pages 136–148. Springer, 2015.
[16] Robin Harper. Ge, explosive grammars and the lasting legacy of bad
initialisation. 2010.
[17] Michael O’Neill, Conor Ryan, Maarten Keijzer, and Mike Cattolico. Crosso-
ver in grammatical evolution. Genetic programming and evolvable machines,
4(1):67–93, 2003.
[18] David Fagan. Analysing the Genotype-Phenotype Map in Grammatical
Evolution. PhD thesis, University College Dublin, 2013.
[19] David R White, James Mcdermott, Mauro Castelli, Luca Manzoni, Brian W
Goldman, Gabriel Kronberger, Wojciech Ja´skowski, Una-May O’Reilly, and
Sean Luke. Better gp benchmarks: community survey results and proposals.
Genetic Programming and Evolvable Machines, 14(1):3–29, 2013.
[20] Marc Ebner, Patrick Langguth, Juergen Albert, Mark Shackleton, and
Rob Ship-man. On neutral networks and evolvability. 2001 Congress on
Evolutionary Computation CEC2001, pages 1—-8, 2001.
31

Analisi sperimentale comparativa dell’evolvibilità nei sistemi di evoluzione grammaticale

Recommended

Recommended

More Related Content

Viewers also liked

Viewers also liked (10)

Similar to Analisi sperimentale comparativa dell’evolvibilità nei sistemi di evoluzione grammaticale

Similar to Analisi sperimentale comparativa dell’evolvibilità nei sistemi di evoluzione grammaticale (20)

Recently uploaded

Recently uploaded (7)

Analisi sperimentale comparativa dell’evolvibilità nei sistemi di evoluzione grammaticale