Calcolo Evoluzionistico
Evoluzione
In ogni popolazione si verificano delle mutazioni.
Le mutazioni possono generare individui che meglio si
adattano all’ambiente.
Questi sopravviveranno più a lungo (selezione naturale)
generando più figli (riproduzione).
I figli preservano in parte i caratteri genetici dei genitori
(cromosomi, composti da geni) e, in parte, mescolandoli
(crossover), creano nuovi tipi.
Evoluzione
Si ha una maggiore probabilità che le generazioni
successive presentino i caratteri degli individui più
“adatti” (cioè con fitness più elevata) all’ambiente in cui
vivono (evoluzione).
Il codice genetico di un individuo è detto genotipo. La
manifestazione dei caratteri codificati in tale codice è
detta fenotipo.
Calcolo Evoluzionistico
Nelle scienze:
• Verifica tramite simulazioni di ipotesi in biologia, sociologia,
religione ecc.
Per l'ingegneria:
• Ottimizzazione di funzioni
• Ottimizzazione combinatoria
• Apprendimento automatico
• Soluzione di problemi
Corrispondenze natura-calcolo
Individuo
Soluzione di un problema
Popolazione
Insieme di soluzioni
Fitness
Qualità di una soluzione
Cromosoma *
Rappresentazione di una
soluzione
Gene *
Componente di una
rappresentazione
Crossover Mutazione
Operatori per la ricerca di
soluzioni
Selezione Naturale
Riutilizzo di buone soluzioni
Evoluzione
Ricerca di buone soluzioni
*solo per gli algoritmi genetici
Componenti di un algoritmo evoluzionistico
1. Rappresentazione (codifica)
2. Funzione di valutazione (fitness function)
3. Popolazione
4. Meccanismo di selezione (dei genitori)
5. Operatori di modifica/ricombinazione
6. Meccanismo di selezione dei sopravviventi (sostituzione)
7. Strategia di inizializzazione
8. Condizione di arresto
Generico algoritmo evoluzionistico
1. Inizializza una popolazione
2. Valuta la fitness della popolazione
3. Ripeti:
a. seleziona un sottoinsieme della
popolazione in base alla fitness
b. a partire dagli individui selezionati, genera
una nuova popolazione mediante gli operatori
di modifica/ricombinazione
c. Valuta la fitness della nuova popolazione
fino al soddisfacimento di un criterio di arresto
Algoritmi genetici
Negli algoritmi genetici si ottengono nuove soluzioni
operando su una loro codifica: in termini genetici, si opera
(come del resto accade anche in natura) sul solo genotipo.
E’ quindi necessaria una decodifica da genotipo a fenotipo.
I cromosomi sono stringhe di simboli (es. 0 o 1).
Gli individui possono essere qualunque cosa possa essere
rappresentata con una stringa di simboli.
I fenotipi possono essere, ad esempio, vettori di parametri,
liste di possibili scelte, connessioni fra neuroni in una rete
neurale ecc.
Semplice algoritmo genetico
1.
Genera una popolazione random di cromosomi.
2.
Decodifica ogni cromosoma per ottenere un
individuo.
3.
Valuta la fitness di ciascun individuo.
4.
Genera una nuova popolazione, in parte clonando
(copiando), in parte ricombinando e in parte mutando i
cromosomi degli individui con fitness più elevata.
5.
Ripeti 2,3,4 fino ad una condizione di stop.
Rappresentazione
Numeri
Interi (da 0 a 2n-1, da K a K+N,
da 0 a M con M2n-1)
Reali
Elementi appartenenti ad insiemi limitati
Vettori di parametri o numeri
Rappresentazione
Rappresentazioni simili devono rappresentare cose simili
Codifica di Gray
Rappresentazioni di Interi consecutivi differiscono per un bit
Gray Bin
Gray Bin
0
1
2
3
000
001
011
010
000
001
010
011
4
5
6
7
110
111
101
100
100
101
110
111
L’inversione di un bit produce piccoli cambiamenti
Se però il cambiamento è grande è maggiore che con una
normale codifica binaria
Fitness Function
Ipotesi fondamentale
1.
Esiste una misura Q della bontà di una soluzione.
2.
E’ sempre positiva
3.
Va massimizzata
4.
La Q di un individuo è la sua fitness
Popolazione
Una popolazione è un multiset (insieme in cui è accettabile la
presenza di più copie di uno stesso elemento) di soluzioni
E’ caratterizzata o dalla sola dimensione (numero di individui)
o, eventualmente, anche da una struttura di tipo spaziale in
cui ogni individuo ha un insieme di vicini in un suo intorno.
Quasi sempre la dimensione resta costante nelle diverse
generazioni.
La diversità di una popolazione è il numero di individui diversi
presente al suo interno.
Selezione
E’ la strategia che determina come gli individui (in realtà il loro
genotipo, rappresentato dai cromosomi) devono essere
selezionati per la riproduzione.
Per simulare la selezione naturale, agli individui con fitness
più elevata viene attribuita una più alta probabilità di essere
selezionati.
Vi sono diverse strategie per la selezione (alcune non
plausibili biologicamente).
Di solito in un algoritmo genetico:
a.
b.
Un gruppo di soluzioni è selezionato per
l’accoppiamento (mating pool)
Coppie di individui sono estratti a caso dal mating
pool e vengono accoppiati (riproduzione sessuata)
Selezione
Selezione proporzionale alla fitness
(fitness-proportionate selection)
E’ il metodo di selezione più comune.
Ad ogni individuo è assegnata una probabilità di essere
selezionato
pi = fi/Sjfj
Selezione
Implementazione (selezione proporzionale alla fitness)
Supponiamo di avere 4 individui con fitness
f1=f2=10
f3=15
f4=25
Allora si avrà (probabilità di selezione):
p1=p2=1/6
p3=1/4
p4=5/12
Selezione
Implementazione (selezione proporzionale alla fitness)
1. Metodo della roulette
Ogni posizione della freccia corrisponde ad un certo numero.
Si estrae un numero casuale e si seleziona l'individuo puntato
dalla freccia.
Selezione
Implementazione (selezione proporzionale alla fitness)
2. Vettore di dimensione N
112233344444
0
N-1
Si estrae un numero a caso (da 0 a N-1) e si seleziona
l’individuo corrispondente al valore nella posizione estratta.
3. Numero reale compreso fra 0 e Sjfj
Si estrae un numero a caso r compreso in tale intervallo e si
seleziona l’individuo i tale che
Sj=1,i-1 fj  r < Sj=1,i fj
Selezione
Problemi
Convergenza prematura
Se un individuo i ha fitness molto maggiore della media della
popolazione ma molto minore della massima fitness
possibile, tenderà a essere sempre selezionato e quindi a
generare una popolazione “mediocre”.
Stagnazione
Dopo un certo numero di generazioni, tutti gli individui hanno
una buona fitness e quindi tendono ad avere la stessa
probabilità di essere selezionati.
Selezione
Selezione per rango (rank selection)
Individui ordinati per fitness (decrescente).
Si impone una distribuzione di probabilità decrescente con la
posizione occupata, indipendentemente dai valori di fitness.
Vantaggi
•Non si ha convergenza prematura: nessun individuo ha
probabilità molto maggiore degli altri di essere selezionato
•Non c’è stagnazione: la distribuzione probabilità non varia.
Svantaggi
Computazionalmente pesante.
Nota: non è biologicamente plausibile.
Selezione
Selezione tramite torneo
(tournament selection)
Per ogni individuo da selezionare, si seleziona un gruppo di
individui e si clona il migliore (torneo).
Vantaggi
Come selezione per rango, ma non c’è necessità di
ordinamento.
Selezione
Selezione elitista
Almeno una copia dell’individuo migliore viene mantenuta
nella generazione successiva.
Vantaggi
Non si perdono soluzioni buone nei processi “casuali” di
selezione.
Svantaggi
Si possono raggiungere massimi locali se i caratteri di tale
individuo diventano “dominanti”.
Selezione dei ‘sopravviventi’ (sostituzione)
Se m è la dimensione della popolazione e l il numero di figli che abbiamo
generato, da m genitori e l figli bisogna selezionare gli m individui che
costituiranno la popolazione nella generazione successiva.
Se l = m si parla di algoritmo generazionale, se l < m si parla di
algoritmo steady state.
Si possono utilizzare strategie di selezione basate sulla fitness o
indipendenti da essa.
Strategie basate sull’età
Indipendentemente dalla fitness, ogni individuo sopravvive per un numero
prefissato di generazioni.
Di implementazione banale se l = m (la generazione t+1 è integralmente
composta dai figli della generazione t).
Se l < m è bene tenere conto della fitness (con una sostituzione random la
probabilita di perdere l’individuo migliore è molto elevata).
Selezione dei ‘sopravviventi’ (sostituzione)
Strategie basate sulla fitness
Si possono
utilizzare le stesse strategie viste per la
definizione del mating pool (proporzionale alla fitness, basata
sull’ordine, basata su torneo).
E’ possibile anche introdurre il fattore età, imponendo ad
esempio (se l < m ) che tutti i figli passino alla generazione
successiva, per poi usare la fitness per selezionare i restanti
m -l genitori.
La strategia replace worst sostituisce i peggiori l individui.
Le strategie elitiste impongono di mantenere l’individuo con
la fitness più elevata nella popolazione.
Operatori genetici: Crossover
I figli vengono generati ricombinando il materiale genetico
degli individui che costituiscono il mating pool. Si parla di
crossover (incrocio) o di ricombinazione.
Il crossover consente, come nel caso della riproduzione
sessuata in natura, di ottenere nuovi individui il cui codice
genetico è mutuato in parte dall’uno e in parte dall’altro
genitore.
Operatori genetici: Crossover
CROSSOVER SINGOLO-PUNTO
1110001101001010
1000100111001010
GENITORI
1110000111001010
1000101101001010
FIGLI
Si seleziona un punto a caso all’interno del genoma e si scambiano le due
sezioni destre o sinistre.
CROSSOVER DOPPIO-PUNTO
1110001101001010
1000100111001010
GENITORI
1110100111001010
1000001101001010
FIGLI
La stringa è considerata circolare. Si fanno 2 ‘tagli’ e si scambiano le 2 parti
interne o le due parti esterne ad essi.
Operatori genetici: Crossover
CROSSOVER UNIFORME
1110001101001010
1000100111001010
GENITORI
1010000101001010
1010000101001010
FIGLI
Ogni bit è selezionato a caso da uno dei due genitori.
Gli stessi operatori possono essere utilizzati nel caso in cui si
usi una rappresentazione basata su stringhe di interi.
Operatori genetici: Crossover
Nel caso di una rappresentazione basata su vettori di numeri floating point
si usano operatori concettualmente simili. Tuttavia, anziché selezionare i
diversi elementi copiandoli da uno dei genitori x e y, combinano i loro
valori facendone una somma pesata.
Ricombinazione semplice: si sceglie un punto k nella stringa e a < 1
Figlio 1: < x1, x2, … , xk , a yk+1 + (1-a) xk+1, …. , a yN + (1-a) xN >
Figlio 2 come Figlio 1 con x e y scambiati
Ricombinazione singola: si sceglie un punto k nella stringa e a < 1
Figlio 1: < x1, x2, … , a yk + (1-a) xk, xk+1 …. , xN >
Figlio 2 come Figlio 1 con x e y scambiati
Ricombinazione completa
Figlio 1: a y + (1-a) x
Figlio 2: a x + (1-a) y
Crossover fra permutazioni
Partially-mapped crossover (PMX):
1. Si scelgono 2 punti nella stringa e si copiano in F1 i valori fra essi
compresi in G1
G1 : 123456789
G2: 937826514
F1:
...4567..
2. Dal primo punto si guarda quali elementi di G2 compresi fra i due punti
selezionati non sono stati ancora copiati
3. Per ciascuno di questi (i) si guarda in F1 quale elemento (j) compare
nella posizione corrispondente
4. Si pone i nella posizione occupata da j in G2
F1: ...4567.8
5. Se il posto occupato da j in G2 è già stato occupato in F1 da un
elemento k, poni i nella posizione occupata da k in G2
F1: ..24567.8
6. Gli altri elementi di F1 vengono copiati direttamente da G2
F1: 932456718 . Il figlio F2 è creato in modo analogo invertendo i G.
Operatori genetici: Mutazione
Operatore che mira a mantenere diversità genetica per
cercare di esplorare anche zone dello spazio di ricerca non
presenti nella popolazione attuale.
Mutazione per rappresentazioni binarie
Si sceglie un bit a caso e lo si inverte.
1001010010101
1000010010101
Per le rappresentazioni intere è possibile sostituire un gene
con un valore random ammissibile oppure aggiungere al
valore stesso una quantità positiva o negativa, con probabilità
più elevata intorno allo zero
Operatori genetici: Mutazione
Mutazione per rappresentazioni floating point
Da un vettore <x1,x2,. . ., xn>, xi[Li,Ui] si passa a <x’1,x’2,. . ., x’n>, x’i[Li,Ui]
attraverso un processo di sostituzione dei valori con una componente
random
Mutazione Uniforme
Si sostituiscono tutti gli elementi della rappresentazione con un valore
random appartenente allo stesso intervallo di definizione.
Mutazione non uniforme con distribuzione fissa
Si ottiene il nuovo vettore aggiungendo ad ogni elemento un numero
random appartenente ad una distribuzione centrata sullo zero e
decrescente col valori assoluto (es. Gaussiana G(0,s)).
Operatori genetici: Mutazione
Mutazione per permutazioni
Si scelgono due punti nella stringa e…
Per scambio
123456789
153426789
Per inserzione
123456789
125346789
Per rimescolamento
123456789
153246789
Per inversione
123456789
154326789
Parametri di un algoritmo genetico
• Dimensione della popolazione
• Criterio di arresto
• numero max di iterazioni
• soglia di fitness
• Distribuzione operatori per la nuova generazione:
• probabilità di clonazione
• probabilità (e tipo) di crossover
• probabilità di mutazione
Programmazione genetica
Variante degli algoritmi genetici
Si evolvono funzioni rappresentate come alberi sintattici
Funzioni
Simboli terminali
Programmazione genetica
I nodi rappresentano funzioni; le foglie i simboli terminali
(costanti, puntatori o dati)
Gli operatori devono soddisfare la proprietà di chiusura, cioè il
tipo di dato deve essere lo stesso sia per gli ingressi che per le
uscite di tutti gli operatori (esistono comunque anche varianti
in cui sono ammessi tipi diversi)
La procedura di valutazione della funzione avviene mediante
un attraversamento dell’albero sintattico
Da un attraversamento in preordine si ottiene codice LISP-like
(notazione prefissa), da un attraversamento simmetrico si
ottiene la rappresentazione della funzione in notazione
algebrica (notazione infissa)
Programmazione genetica
Bisogna adattare gli operatori alla rappresentazione
Programmazione genetica
Osservazioni
• Il risultato di una mutazione può essere un albero di
profondità maggiore rispetto all’albero originale
• Il risultato di un crossover fra due alberi può essere un
albero di profondità maggiore rispetto ad entrambi i genitori
• La programmazione genetica è un algoritmo genetico, quindi
si utilizzano gli stessi parametri visti per gli algoritmi genetici
Programmazione genetica
La programmazione genetica opera ad un livello di astrazione
maggiore rispetto agli algoritmi genetici:
• negli algoritmi genetici la rappresentazione ha sempre bit
come elementi atomici ed è solo necessario definire la
semantica della rappresentazione
• nella programmazione genetica bisogna definire a priori
anche gli elementi atomici, cioè l’insieme dei simboli
terminali e delle funzioni che devono essere utilizzate per
la costruzione degli alberi
Programmazione genetica
E’ necessario definire:
• Un insieme di funzioni F (nodi dell’albero) per ciascuna
delle quali è specificata la cardinalità (numero di argomenti)
• Un insieme di simboli terminali T (foglie dell’albero)
che rispettino le seguenti condizioni:
• Tutti gli elementi di T sono espressioni corrette
• Se f  F è una funzione con cardinalità n e (e1,…., en) sono
espressioni corrette, allora anche f(e1,….,en) è corretta
• Non ci sono altre forme di espressioni corrette
Le tre condizioni equivalgono alla proprietà di chiusura
Programmazione genetica
• Resta il problema di definire le costanti
• Una soluzione (Ephemeral Random Constant) consiste
nell’utilizzare un simbolo terminale costante definito entro un
certo intervallo;
• al momento della generazione di un nuovo albero
(inizializzazione), e quindi in corrispondenza del primo
uso di ogni ERC, ad essa viene assegnato un valore
casuale entro il dominio di definizione
• per ogni successivo uso, l’ERC si comporta di fatto come
una costante, mantenendo il valore cui è stata
inizializzata
Programmazione genetica
Selezione
Si usano gli stessi schemi utilizzati negli algoritmi genetici.
Tuttavia, poiché si usano spesso popolazioni molto grandi, si
usa un meccanismo detto di over-selection:
• La popolazione viene ordinata in base alla fitness e divisa
in due gruppi: il primo contiene il migliore x% della
popolazione, l’altro il restante (100-x)%
• L’80% degli individui viene selezionato dal primo gruppo, il
20% dal secondo.
Programmazione genetica
Inizializzazione
Si usa di solito la cosiddetta inizializzazione ramped half-andhalf
Si stabilisce una profondità massima Pmax per gli alberi e poi si
creano gli elementi appartenenti alla prima generazione
utilizzando uno dei due metodi seguenti con uguale
probabilità:
• Metodo Full: ogni ramo ha profondità Pmax; ogni elemento è
estratto da F se P < Pmax, da T altrimenti.
• Metodo Grow: gli alberi possono essere sbilanciati e quindi si
sceglie ogni elemento da F U T, se P < Pmax, da T altrimenti.
Programmazione genetica
Bloat
Il fatto di avere una rappresentazione a lunghezza variabile fa
sì che la dimensione degli alberi tenda a crescere nel tempo
Il fenomeno è detto bloat o, scherzosamente, “survival of the
fattest” (contrapposto a “survival of the fittest”).
Rimedi possibili:
• Si impediscono operazioni che producano individui di
profondità P > Pmax
• Si aggiunge nella fitness un termine che penalizza gli alberi
più grandi (Es. F = Err% + 0.0001 * Size) (parsimony
pressure)
Apprendimento Automatico
Calcolo Evoluzionistico
Parte III: teoria
Stefano Cagnoni
Analisi dell’evoluzione
Gli algoritmi evoluzionistici sono processi stocastici di
ottimizzazione.
Il loro studio si può quindi basare soltanto su teorie
probabilistiche.
Le speranze di ottenere risultati ‘definitivi’ e globali non sono
tuttavia elevate: se da un lato il calcolo evoluzionistico è una
disciplina giovane, dall’altro la genetica delle popolazioni
studia il problema da oltre un secolo e molti sono tuttora i
problemi aperti.
Due risultati importanti ai fini della discussione del problema
sono il teorema degli schemi (Holland) e il cosiddetto ‘No Free
Lunch Theorem’
Teorema degli schemi
Propone un risultato che consente, in certe condizioni, di fare
previsioni sulla distribuzione statistica della popolazione al
tempo t+1, una volta che sia nota quella al tempo t.
Se lo spazio di ricerca è [0,1]N (lo spazio delle stringhe binarie
di lunghezza N), si definisce schema un iperpiano contenuto
in tale spazio e si rappresenta con una stringa contenente i
simboli {0, 1, #} dove # indica il simbolo ‘don’t care’.
Es. su 5 bit lo schema 11### rappresenta l’iperpiano
definito dalla presenza di due 1 nelle prime due posizioni.
Tutte le stringhe che soddisfano tale criterio sono istanze o
esempi di tale schema (in questo caso sono 23).
Teorema degli schemi
La fitness dello schema è la media della fitness di tutte le
istanze di quello schema. Se il numero di istanze di uno
schema all’interno di una popolazione è sufficientemente
elevato la loro media può essere considerata una stima della
fitness dello schema.
Un problema di ottimizzazione globale può essere visto come
una ricerca dello schema privo di simboli ‘#’ avente la
massima fitness.
Lo studio del comportamento di un algoritmo genetico è più
semplice se fatto in termini di schemi anziché in termini di
singole istanze (aggregazione).
Una stringa di l bit è istanza di 2l schemi.
Teorema degli schemi
Una popolazione di m individui individua al più m·2l schemi.
In realtà saranno molti di meno: Holland ha stimato che una
popolazione di m individui sfrutti utilmente O(m3) schemi.
Questo risultato, detto anche parallelismo implicito, viene
citato come uno dei principali motivi che determinano
l’efficacia degli algoritmi genetici.
Ogni schema ha un ordine, definito come il numero di
elementi dello schema che differiscono da ‘#‘, e una
lunghezza di definizione (defining length) che è la distanza fra
i due elementi diversi da ‘#’ più esterni.
Es. H = 1##0#1#0 ha ordine o(H) = 4
e defining length d(H) = 7
Teorema degli schemi
Il numero di istanze di uno schema in una popolazione
dipende principalmente dagli effetti degli operatori genetici che
vengono ad essa applicati.
Gli operatori di selezione possono solo modificare la
distribuzione statistica delle istanze preesistenti, gli operatori
di ricombinazione e di mutazione possono creare nuove
istanze e farne estinguere altre.
Si indica con Pd(H,x) la probabilità che l’applicazione
dell’operatore x abbia un effetto distruttivo sullo schema H, e
Ps(H) la probabilità che un’istanza dello schema H venga
selezionata.
Teorema degli schemi
Holland applicò la sua analisi all’algoritmo genetico standard
(SGA) che fa uso della selezione proporzionale alla fitness,
del crossover singolo-punto (1X) e della mutazione sul singolo
bit, con uno schema generazionale di sopravvivenza.
Lo schema H relativo ad un genotipo di lunghezza l è distrutto
da 1X se il punto di crossover cade fra gli estremi dello
schema, quindi
Pd(H,1X) = d(H)/(l-1)
La Pd(H,mut) relativa alla mutazione è invece proporzionale
all’ordine dello schema
Pd(H,mut) = 1 - (1-Pm) o(H)
approssimabile con Pd(H,mut) = Pm · o(H)
(eliminando i termini di
ordine superiore in Pm)
Teorema degli schemi
La probabilità che uno schema sia selezionato dipende dalla
fitness relativa (rispetto alla fitness totale della popolazione)
degli individui in cui compare e dal numero di istanze presenti
n(H,t).
Ps(H,t) = (n(H,t) · f(H))/(m · <f>)
dove f(H) è la fitness dello schema (stimata sulle istanze) e
<f> è la fitness media della popolazione
Poiché per creare la generazione successiva si estraggono m
campioni (individui) indipendenti, il numero atteso di istanze di
H selezionate sarà
n’(H,t) = m · Ps(H,t) = n(H,t) · f(H) / <f>
Teorema degli schemi
Normalizzando per rendere il risultato indipendente dalla
popolazione,
considerando gli effetti distruttivi degli operatori e
utilizzando un segno di disuguaglianza per tenere conto della
creazione di nuovi istanze di H da parte degli operatori stessi,
la percentuale m(H) di istanze dello schema H in istanti
successivi soddisfa la seguente relazione:
m(H,t+1) ≥ m(H,t) · (f(H)/<f>) · (1 - pc · d(H)/(l-1)) · (1 – pm · o(H))
dove
pc = probabilità di crossover
pm = probabilità di mutazione
Teorema degli schemi: limiti
Interpretazione immediata del teorema: gli schemi con fitness più elevata
aumentano il numero di istanze di generazione in generazione.
Il teorema degli schemi tuttavia è stato criticato con le seguenti
motivazioni:
• E’ basato sulla selezione proporzionale alla fitness, che non è detto che
‘allochi risorse’ ai diversi schemi in modo ideale ai fini della convergenza.
• Esistono fenomeni di saturazione dovuti al fatto che, all’aumentare della
prevalenza di uno schema H sugli altri, il rapporto f(H)/<f> decresce in
quanto <f> aumenta
• E’ basato su una stima della fitness dello schema che è in grado di
prevedere la frequenza dello schema nella prossima generazione, ma non
sulla frequenza nelle generazioni successive, in quanto la frequenza degli
altri schemi cambia, modificando anche la composizione delle stringhe di H
e quindi la stima di f(H).
• Considera solo gli effetti distruttivi degli operatori e non quelli costruttivi.
Teorema ‘No Free Lunch’
Teorema di controversa interpretazione (Wolpert & McReady)
In sintesi afferma che “mediando sullo spazio di tutti i possibili
problemi, tutti gli algoritmi di ottimizzazione ‘black box’ (che
non sfruttano cioè conoscenze a priori sul problema) e che
valutano ogni punto dello spazio di ricerca al più una sola
volta (non-revisiting) forniscono le STESSE prestazioni”.

Relativamente agli algoritmi evolutivi, ci si è tuttavia chiesti se
i problemi che tendiamo a risolvere con essi sono un
campione di TUTTO lo spazio dei problemi o se
rappresentano una particolare regione
Teorema ‘No Free Lunch’
In ogni caso dal teorema si può ricavare che:
 se inventiamo un nuovo algoritmo che pare essere il
migliore per una certa classe di problemi, il prezzo da pagare
è l’esistenza di altre classi di problemi per cui esso è inadatto.
 per uno specifico problema è possibile aggirare il teorema
NFL incorporando conoscenza specifica sul dominio nella
soluzione.
GAucsd
Funzione di
valutazione senza
decodifica
double f1(x)
register double *x;
{
register int i;
register double sum;
/*
wrapper
Funzione di
valutazione con
decodifica
double _eval(genome, length)
char genome[];
int length;
{
register int i;
char buff[30];
char outbuf[10];
double sum = 0.0;
for (i = 0; i < 3; i++)
{
/* convert next 10 bits to an integer */
Degray(&buff[i*10], outbuf, 10);
x[i] = Ctoi(outbuf, 10);
/* scale x to the range [-5.12, 5.11] */
x[i] = (x[i] - 512.0) / 100.0;
accumulate sum of squares of x's
*/
for (sum = 0.0, i = 0; i < 3; i++)
sum += x[i]*x[i];
return (sum);
}
/* GAeval f1 10:5.12d3 */
/* phenotype description, must be static */
static double x[3];
/* accumulate sum of squares of x's */
sum += x[i]*x[i];
/* return previous phenotype on request */
if (length < 0)
sprintf(genome, ""n%lf %lf %lf", x[0], x[1], x[2]);
else
{
/* GAlength 30 */
if (length != 30) Error("length error in eval");
/* unpack the genotype */
Unpack(genome, buff);
}
}
return(sum);
}
Sintassi ‘commento’
/* GAeval f1 10:5.12d3 */
Nome funzione
valutazione
Lunghezza
gene
Range
(opz.)
Tipo
Numero
geni
Altre opzioni (da inserire tra tipo e numero geni):
u se il tipo è unsigned
b o g a seconda che si voglia usare la codifica di Gray oppure binaria
Parametri (1)
Evaluation File Name
Name of Experiment
Genome Length
Population Size
Trials per Run
Number of Runs
Crossing Rate (probabilità di crossover per individuo)
Mutation Rate (probabilità di mutazione di ogni bit della popolazione)
Generation Gap (percentuale della popolazione che viene sostituita in ogni generazione)
Parametri(2)
Windowsize (dimensione della finestra di riscalatura; Zero indica dimensione infinita, un
valore negativo l’uso del sigma scaling. La fitness viene riscalata per mantenere la ‘pressione
evolutiva’ entro margini utili. Per fare ciò si massimizza F-f(x) dove F è una costante. F è
uguale alla max fitness delle ultime Windowsize generazioni. )
Sigma Scaling Factor
(in questo caso F=avg(f(x))+SSF*std(f(x)))
DPE Time Constant (costante di tempo dell’algoritmo DPE [Dynamic Parameter
Encoding] utilizzata per interpolare le statistiche sulla convergenza ed evitare la convergenza
prematura. L’algoritmo DPE riscala l’intervallo di definizione dei parametri dimezzandolo ogni
volta che si raggiunge una certa soglia di convergenza; un valore nullo disattiva il DPE)
Convergence Threshold (percentuale di alleli che devono essere uguali perché vi sia
convergenza su un particolare allele)
Max Alleles to Converge
Maximum Bias (percentuale di alleli che hanno raggiunto la convergenza)
Max Gens w/o Evaluation (numero di generazioni senza comparsa di nuovi individui)
Parametri(3)
Report Interval (frequenza di generazione delle statistiche)
Structures Saved (numero di individui con la fitness più alta che vengono salvate)
Dump Interval (numero di generazioni fra due salvataggi della popolazione)
Dumps Saved (numero di popolazioni salvate; zero annulla il dump)
Options (le principali…)
A
rende stocastica Ctoi() usata nella conversione
c
genera le statistiche sulla convergenza
e
usa la strategia elitista
i
inizializza la popolazione da file
l
genera un file di log delle attività
L
salva l’ultima generazione
r
fa ripartire una sessione sospesa inizializzando la popolazione dall’ultimo dump
u
crea una popolazione iniziale superuniforme in cui tutti gli schemi fino ad una certa
lunghezza sono ugualmente rappresentati
Random Seed (seme del generatore di numeri casuali)