![]() |
|
![]() |
||||
![]() |
DOCUMENTS
elab.immagini
galileo
realtà virtuale
vrml
biomeccanica
esapodi
formula1
intelligenza
Papers
meccanica
sistemi
robotica
MODELLI EVOLUTIVI
Si consideri di voler ottimizzare una serie di grandezze dalle quali
dipende la determinazione di un’azione che da luogo ad un risultato
in modo da ottenere la miglior prestazione: analizzeremo a tal proposito
la possibilità di selezionare le soluzioni più adatte in analogia con
i processi evolutivi che hanno condotto le specie viventi ad
elaborare strategie raffinatissime volte al conseguimento dell’obiettivo
sopravvivenza.
L’ALGORITMO GENETICO
L’ idea di ricorrere a modelli evolutivi nello studio dell’intelligenza
e della conoscenza, per quanto innovativa e frutto di un percorso autonomo
ha conosciuto un notevole sviluppo oltreoceano in particolare nell’
opera del del prof. J.Holland. Abbiamo pertanto ritenuto opportuno
avvalerci del notevole patrimonio maturato in due decenni dal medesimo,
innestando idee e tecniche inedite su una comune matrice computazionale.
Se si pensa all'ottimizzazione come ad una attività di ricerca del massimo
valore per un insieme dato di argomenti (le possibili soluzioni) essa
non presenta, in linea di principio, grandi difficoltà qualora sia nota
la funzione che vincola invariabilmente le grandezze; ma poniamo il
caso in cui esista una legge deterministica ma non sia nota la funzione
che la esprime: come sappiamo quale argomento darà luogo al massimo
valore ?
Di primo acchito, di fronte ad un campo oscuro di possibili soluzioni
si sarebbe spinti a procedere per tentativi e verifiche, privilegiando
mano a mano le soluzioni che danno luogo a valori più elevati; come
è immaginabile questo metodo si rivelerebbe ben presto dispendioso e
dispersivo, a meno che non si reperisse un sistema per ricavare da ogni
soluzione tendenzialmente positiva, un'indicazione utile ad orientare
la ricerca.
Lo stratagemma cui si può ricorrere è quello di concepire ciascun singolo
argomento come una combinazione di più elementi anche laddove ciò non
risulti di per sè evidente.
In ciascuna soluzione è stata trasformata nel corrispettivo numero binario
che va a costituire una stringa di parametri, ossia, all'interno della
nostra metafora genetica, un cromosoma.
Ogni buona soluzione si può considerare come una buona organizzazione
in cui è possibile isolare e promuovere i fattori che ne sono responsabili.
Tecnicamente ciò avviene ricombinando porzioni di stringhe cui corrispondono
i valori adattativi più elevati; è proprio grazie allo scambio di materiale
genetico che avviene durante il crossover che le specie viventi si sono
adattate in tempi relativamente brevi preservandosi dal rischio di degenerare
in stirpi mostruose corrispondenti alle più svariate combinazioni di
caratteri e destinate all'estinzione.
Ci soffermiamo ora sui dettagli per la realizzazione dell’algoritmo
in questione.
CICLO ESECUTIVO
- Generazione random di n stringhe binarie di lunghezza l (possibili
soluzioni)
- Codifica: La porzione di intervallo binario (BIN / maxBin) rappresentata
da ciascuna stringa generata viene rapportata all’intervallo di ottimizzazione
(Max x - Min x) dando luogo ad una serie di input ( x1,..,xn )
- Valutazione: Assegnazione di un valore adattativo a ciascuna stringa
sulla base di una funzione y = f (x)
- Selezione delle stringe: Probabilità di sorteggio proporzionale
al tasso di mortalità
Descrizione del procedimento per la realizzazione dell'algoritmo di
selezione:
- Si dispongono i membri della popolazione iniziale in sequenza
- Si sommano tutti i valori adattativi della popolazione iniziale
- Si genera z, un numero casuale compreso tra 0 e il totale ottenuto
in precedenza
- Risulta estratto il primo membro della popolazione il cui valore adattativo,
sommato al valore adattativo complessivo dei membri precedenti, è maggiore
o uguale ad z.
- Crossover: La ricombinazione è la fase cruciale di funzionamento dell'Algoritmo
Genetico, durante la quale avviene lo scambio di elementi tra le configurazioni
che la precedente selezione ha decretato migliori. Tra le stringhe binarie
superstiti prese casualmente due a due viene effettuato un vero e proprio
cross-over, ovverosia i bit fino ad un certo punto (estratto a sorte)
della prima stringa, vengono sostituiti con i bit in analoga posizione
nella seconda stringa e viceversa. L'operazione può essere facilmente
schematizzata:
AAAAA|AAA + BBBBB|BBB = AAAAA|BBB + BBBBB|AAA -
Nuova selezione (v. sopra) e rimpiazzamento.
Sostituendo in blocco la nuova popolazione originata dagli operatori
genetici (cross-over e mutazione) con quella iniziale si corre il rischio
di eliminare prematuramente ottime porzioni di stringa che trovandosi
male assortite non hanno occasione di manifestare il proprio valore.
Per evitare ciò si cerca il più possibile di rispettare il criterio
generale della "moderazione".
Nelle mie sperimentazioni tale criterio mi ha indotto ad attuare un
rimpiazzamento tale per cui la migliore delle stringhe discendenti va
a sostituire man mano la peggiore delle stringhe genitrici sino a che
non incontriamo un discendente con valore minore o uguale al genitore.
- Ritorno al primo passo. Reiterazione da eseguire sino all’evento
di stagnazione della popolazione, ovverosia quando il valore adattativo
medio è uguale al valore adattativo massimo.
CONSIDERAZIONI TEORICHE:
IL PARALLELLISMO IMPLICITO
Una delle caratteristiche che rendono l'Algoritmo Genetico preferibile
rispetto ad altre procedure ottimizzatrici, è la sua "robustezza", vale
a dire la sua versatilità applicativa riguardo ad una grande varietà
di problemi (Goldberg, 1989); tuttavia, proprio il proliferare degli
ambiti in cui l'A.G. ha trovato impiego, ha messo in luce la possibilità
di migliorare le doti esplorative della procedura, soprattutto in rapporto
a dominii specifici (Davis, 1991). Ciò non significa che non sia possibile
apportare migliorie di portata generale all'algoritmo, ma solamente
che è difficile astrarle rispetto ai problemi in cui si manifestano,
i quali sono necessariamente particolari.
Se per un verso sono riconoscibili in linea teorica i fattori che possono
alterare la qualità delle prestazioni, molto più impegnativa è l'analisi
di come ciò possa avvenire; infatti, ironia della sorte, modifiche che
combinate in una certa maniera producono esiti soddisfacenti, combinate
diversamente o prese singolarmente, si rivelano insignificanti se non
addirittura dannose (Davis, 1991).
Come in molti casi, anche in questo la natura organica del tutto differisce
qualitativamente dalla somma delle parti, e proprio su questo punto
sembrano concentrarsi i maggiori sforzi volti al perfezionamento dell'algoritmo
(Shaffer, 1989).
Da parte mia, ritengo giustificato il ricorso ad una meta-procedura
adattativa che reimposti e verifichi le sequenze dell'algoritmo oggetto
i cui caratteri siano stati parametrizzati in maniera tale da poter
essere ottimizzati (v. anche Grefenstette 1986).
Altra caratteristica che rende spesso vantaggioso l'utilizzo di G.A.,
è il suo "parallelismo intrinseco", ovvero la sua capacità di esplorare
sterminate porzioni dello spazio delle soluzioni manipolando un numero
relativamente contenuto di stringhe.
Come ho già accennato sopra, grazie all'intervento del crossing-over,
ciascuna buona soluzione può essere considerata come una buona organizzazione
di elementi che si va a ricombinare con un'altra buona organizzazione;
quando promuovo una stringa binaria in quanto rappresentante di una
buona configurazione di fattori, è come se avessi circoscritto un'ampia
area di interesse costituita da tutte quelle soluzioni strutturalmente
affini, ovvero aventi in comune gli stessi fattori - di fatto ciascuna
stringa appartiene a tutte quelle regioni dello spazio delle soluzioni
in cui compare almeno uno dei suoi bit - (v. il concetto di "Schema"
in Holland, 1975).
Deducendo buone soluzioni da buone combinazioni e buone combinazioni
da buone soluzioni precedentemente testate, l'algoritmo, da un lato
evita un'esplorazione troppo concentrata su particolari regioni dello
spazio delle soluzioni (la ricombinazione infatti genera stringhe differenti
dalle genitrici) dall'altro impedisce la dispersione dei caratteri distintivi
di una soluzione valida (la ricombinazione conserva il materiale delle
stringhe genitrici).
In termini tecnici si dice che il parallelismo implicito garantisce
un buon rapporto esplorazione - sfruttamento (Holland, 1975) vale a
dire un buon rapporto innovazione - conservazione.
E' evidente allora che incrementare l'efficienza di A.G., significa,
in linea di principio, perfezionare l'equilibrio tra le componenti esplorazione
e sfruttamento che la procedura si trova a dover gestire.
LA DIFFUSIONE DEGLI SCHEMI
Per esplicitare i fattori che conferiscono all'Algoritmo Genetico le
proprietà che lo rendono una efficiente procedura di ottimizzazione,
è opportuno indagare gli effetti dei suoi operatori sulla popolazione
di stringhe e sugli elementi che la compongono.
In particolare ci occuperemo delle sorti di quei blocchi di informazioni
(sequenze di bit) che, come si è notato, ricorrono nelle soluzioni migliori
e le contraddistinguono; riproduzione, crossover e mutazione, determinano
in maniera caratteristica l'evoluzione di questi blocchi (Schemi) all'interno
della popolazione.
Definiamo in via preliminare P(t) - popolazione nell'istante t - costituita
da Aj, j = 1,...,n stringhe di tipo A = a1...an definite a loro volta
sull'alfabeto V = {0,1}.
Sia H = b1...bn uno Schema definito sull'alfabeto V+ = {0,1,*}.
Diremo "ordine" di uno Schema H - ç(H) - il numero delle posizioni nelle
quali compare uno 0 o un 1 (es: ç(H) (1**01*) = 3); diremo "taglia"
di uno Schema H - §(H) - la distanza tra la prima e l'ultima posizione
in cui compaiono valori definiti (cioè Ï *) (es: §(H) (1**01*) = 5-1
= 4).
Per prima cosa determiniamo gli effetti della riproduzione su un insieme
di Schemi presenti in una popolazione di n individui.
Si considerino nell'istante t, m esempi dello schema H contenuti nella
popolazione P(t): m = m(H,t)
Durante la riproduzione, le probabilità che una stringa venga duplicata,
sono proporzionali al suo valore adattativo; più precisamente una
stringa Ai avrà probabilità pi = fi/Sfj di essere selezionata (essendo
f=valore adattativo ed "S" simbolo di sommatoria).
Analogamente, lo schema H avrà ph = f(H)/Sfj probabilità di comparire
in una popolazione, essendo f(H) il valore adattativo medio delle
stringhe rappresentanti lo Schema H nell'istante t; pertanto il numero
m(H,t+1) di rappresentanti dello Schema H nella popolazione P(t+1) (popolazione
risultante dalla riproduzione) è dato dall'equazione
m(H,t+1) = m(H,t)*n*f(H)/Sfj.
Si osservi che:
m(H,t+1) = m(H,t)*n*f(H)/Sfj = m(H,t)*f(H)*n/Sfj = m(H,t)*f(H)/(Sfj/n)
e si noti che Sfj/n altro non è che il valore adattativo medio dell'intera
popolazione;
ponendo Sfj/n = f otteniamo quindi m(H,t+1) = m(H,t)*f(H)/f.
La formula appena ottenuta lascia intendere che uno Schema si propaga
in misura proporzionale al rapporto tra il valore adattativo medio dello
schema stesso ed il valore adattativo medio dell'intera popolazione;
Schemi con valore adattativo superiore alla media della popolazione,
compariranno, per le generazioni a venire, in un numero crescente di
stringhe, mentre gli Schemi con valore adattativo inferiore alla media
sono destinati ad estinguersi. La crescita esponenziale, all'interno
della popolazione, degli elementi responsabili di un buon risultato,
conduce la popolazione stessa a convergere fulmineamente verso un unico
risultato, limitando fortemente le capacità esplorative dell'algoritmo.
Per questa ragione l'Algoritmo Genetico integra la riproduzione selettiva
con la ricombinazione degli elementi migliori; tale ricombinazione è,
come sappiamo, il risultato del crossover.
Si dà il caso tuttavia che la scissione delle stringhe operata dal crossover
incorra nel pericolo di distruggere le combinazioni più promettenti
contenute negli Schemi; ci interessa pertanto effettuare una stima delle
alterazioni apportate dal crossover alla propagazione degli Schemi.
Osservando che uno schema è tanto più esposto all'eventualità di una
separazione dei suoi elementi, quanto più questi sono distanti (è molto
più facile che il punto di crossover cada tra due valori in uno schema
del tipo 1****1 piuttosto che in uno schema del tipo *11***) siamo in
grado di affermare che uno Schema ha probabilità pd = §(H)/(l-1) di
venire distrutto, ossia probabilità 1-pd = ps = 1 - §(H)/l-1 di sopravvivere.
Ulteriore fattore che interviene a condizionare la propagazione degli
Schemi nella popolazione, è la mutazione; essa consiste nell'alterazione
casuale, ricorrente con probabilità pm, del valore di un singolo gene.
La sopravvivenza di uno Schema H presuppone la conservazione dei valori
associati ad ogni singola posizione; pertanto dato che un singolo allele
rimane immutato con probabilità (1-pm), e dato che ciascuna mutazione
è statisticamente indipendente, uno Schema sopravvive fino a che ciascuno
dei ç(H) valori definiti dello Schema sopravvive.
Moltiplicando la probabilità (1-pm) (probabilità di conservazione relativa
a ciascun valore in ciascuna posizione) per sè stessa ç(H) volte, otteniamo
la probabilità (1-pm)ç(H) con la quale un intero schema sopravvive alla
mutazione.
Alla luce di quanto emerso, siamo in grado di concludere che gli Schemi
compatti, maggiormente indeterminati, e col valore adattativo superiore
alla media della popolazione, incrementano esponenzialmente i propri
rappresentanti mano a mano che le generazioni si susseguono.
Esistono schemi, ad es. lo schema 1***1, che certamente verranno distrutti,
ma dato il tipo di popolazione, con grandi probabilità di ricostituirsi
a seguito dello scambio di materiale; tuttavia il calcolo illustrato
dal prof. Goldberg relativo alle probabilità di conservazione di uno
schema (si veda alle pp. 28-32 dell'opera "Genetic Algorithms in search,
optimization and machine learning"), non mi pare dedichi le dovute considerazioni
all'eventualità di ricostituzione di uno schema, la quale, avendo noi
a che fare con stringhe binarie, avviene nel 50% dei casi; il che significa
che la probabilità di distruzione di uno schema si dimezza.
APPROFONDIMENTI TEORICI
Si confronti a tal proposito J.Holland et al. - Induction - pp. 118-121:
"How is a cognitive system to rate the components from which its rules
are constructed ?
The strenght assigned to a rule provides an estimate of it’s usefulness
to the system, but this does not give any direct estimate of the value
of it’s components.
There is, however, a simple way, and one quite effective for systems
based on competition, to use this information to rate components: the
rating of any component is taken to be the average of the strengths
of the rules employing it. That is a good building block is one that
occurs in good rules."
v. D.E. Goldberg - Genetic Algorithm in search, optimization and machine
learning - p. 30:
"During reproduction , a string is copied according to its fitness,
or more precisely, a string Ai gets selected fi / fi times. After picking a nonoverlapping population
of size n with replacement from the population A(t), we expect to have
m (H, t+1) representatives of the schema H in the population at time
t+1 as given by the equation:
m(H, t+1) = m(H, t) * n * f(H) / fj,
where f (H)
is the average fitness of the strings representing schema H at time
t. If we recognize that the average fitness of the entire population
may be written as f° = f j
/ n then we may rewrite the reproductive schema growth equation
as follows: m (H, t+1) = m(H, t) * (f(H) / f°).
In words, a particular schema grows as the ratio of the average fitness
of the schema to the average fitness of the population."