Parallelismo implicito

É noto che gli algoritmi genetici operano su stringhe, tuttavia finora si è discusso di schemi. Ora chiariremo come si possa affermare che tali algoritmi operano su stringhe ma anche su schemi. Abbiamo detto che gli algoritmi genetici valutano implicitamente un numero enorme di schemi, valutando la bontà della soluzione parziale che essi contengono, ed estrapolando informazione riguardo possibili schemi più performanti; in questo consiste il paralleleismo implicito.

Ad ogni generazione l'algortimo genetico valuta il fitness di tutti gli $m$ individui, codificati in stringhe di lunghezza $n$, che appartengono alla popolazione; tuttavia il numero di schemi che implicitamente vengono valutati sono molti di più.

Infatti si possono ottenere al più $3^n$ schemi di lunghezza n da una popolazione codificata con $n$ bit. Tuttavia una stringa binaria completamente specificata appartiene a $n$ schemi di ordine uno, $\binom {n}{2}$ schemi di ordine due , in generale $\binom {n}{k}$ schemi di ordine $k$.

Quindi una stringa di lunghezza $n$ appartiene a

$$\sum_{k=1} ^n \binom {n}{k}=2^n$$

schemi; pertanto per ogni generazione che contiene $m$ individui, saranno in numero compreso tra $2^n$ e $m \cdot 2^n$ gli schemi che hanno almeno un rappresentante.

Holland ha fornito una stima degli schemi che sopravvivono a una generazione, fornendo anche una stima della quantità di schemi che vengono implicitamente valutati anche considerando una popolazione numericamente modesta.

Teorema 5.1.3   Si consideri una popolazione iniziale scelta casualmente nel dominio delle soluzioni possibili di un algoritmo genetico semplice, fissato un indice $\varepsilon$ di errore nell'intervallo $(0,1)$, lo schema di lunghezza

$$l_s< \varepsilon \cdot (n-1) +1$$ (5.1.15)

ha probabilità almeno 1- $\varepsilon$ di sopravvivere a un'operazione di cross over semplice. Se la popolazione iniziale viene scelta in numero $m=2^\frac{l_s}{2}$, il numero di schemi che sopravvivono, e quindi appartengono alla generazione successiva è dell'ordine di $\mathcal{O}(m^3)$.