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."