Teorema di Holland

In questo paragrafo si riporta l'enunciato e la dimostrazione del teorema dello schema, enunciato da Holland nel 1975. Si può ritenere sia il risultato fondamentale nella teoria sugli algoritmi genetici, anche se non può ritenersi confrontabile con i risultati presentati per i problemi di ottimizzazione deterministica, tuttavia chiarisce i principi di funzionamento impliciti degli algoritmi genetici.

Riferendoci al generico algoritmo genetico dotato di funzione di fitness $f$ si introducono le seguenti notazioni:

• Il numero di individui appartenenti all'insieme delle possibili soluzioni $\mathcal{B}$ che alla generica iterazione $t$ dell'algoritmo sono contenuti nello schema $H$ sono denotati con

  $$r_{H,t}=\vert\mathcal{B}_t \cap H\vert$$ (5.1.4)

  
  

• L'espressione $\bar f (t)$ si riferisce alla media del fitness al passo t-esimo

  $$\bar f(t)=\frac{1}{m} \sum_{i=1} ^m f(b_{i,t})$$ (5.1.5)

  
  

• Il termine $\bar f(H,t)$ si riferisce al fitness medio osservato per lo schema $H$ al passo $t$,

  $$\bar f(H,t)=\frac{1}{r_{H,t}} \sum_{i\in \left\lbrace j \vert b_{j,t} \in H \right\rbrace } f(b_{i,t})$$ (5.1.6)

  
  

Teorema 5.1.1   Assumendo di considerare un algoritmo genetico, in forma semplice, la seguente disugualianza è valida per ogni schema $H$

$$E[r_{H,t+1}] \geqslant r_{H,t} \cdot \dfrac{\bar f(H,t)}{\bar f(t... ... \left( 1-p_C \cdot \frac{\delta(H)}{n-1}\right) \cdot (1-p_M)^{\mathcal{O}(H)}$$ (5.1.7)

Dimostrazione La probabilità di selezionare un individuo che appartiene allo schema $H$ è

$$\dfrac{\sum_{i\in \left\lbrace j \vert b_{j,t} \in H \right\rbrace } f(b_{i,t})}{\sum_{i=1} ^m f(b_{i,t})} .$$ (5.1.8)

Questa probabilità non cambia all'interno del ciclo di selezione, infatti ognuno degli $m$ individui può venire selezionato indipendentemente dagli altri. Quindi il numero di individui selezionati che appartengono a un certo schema $H$ è una distribuzione binomiale su $m$ campioni.

Si ottiene pertanto che il numero atteso di individui che appartengono ad $H$ è

$$m \cdot \frac{\sum_{i\in \left\lbrace j \vert b_{j,t} \in H \right\rbrace } f(b_{i,t})}{\sum_{i=1} ^m f(b_{i,t})} = m \cdot \frac{r_{H,t}}{r_{H,t}} \cdot \frac{\sum_{i\in \left\lbrace j \vert b_{j,t} \in H \right\rbrace } f(b_{i,t})}{\sum_{i=1} ^m f(b_{i,t})}$$ (5.1.9)

$$= r_{H,t} \cdot \frac{ \frac{\sum_{i\in \left\lbrace j \vert b_{j,t... ...rac{\sum_{i=1} ^m f(b_{i,t})}{m}}= r_{H,t} \cdot \dfrac{\bar f(H,t)}{\bar f(t)}$$ (5.1.10)

Se due individui appartenenti ad $H$ vengono incrociati, i loro figli apparterranno ancora ad $H$. L'unico modo per far diminuire il numero di individui di $H$ è quello di incrociare un'individuo che non appartiene ad $H$ con uno che vi appartiene, con cesura della stringhe scelta arbitrariamente tra i bit assegnati di $H$.

La probabilità che il punto di incrocio sia scelto all'interno della lunghezza di definizione di $H$ è

$$\dfrac{\delta(H)}{n-1} \; .$$

Quindi la probabilità di sopravvivenza dello schema $H$, cioè la probabilità che una stringa che appartiene ad $H$, produca figli ancora appartenti ad $H$ può essere stimata nel modo seguente, dove con $p_{\textbf{C}}$ si indica la probabilità di cross over:

$$p_{\textbf{S}} \geq 1-p_{\textbf{C}} \cdot \dfrac{\delta(H)}{n-1} .$$ (5.1.11)

Sfruttando la relazione precedente si può scrivere pertanto il numero atteso di stringhe che appartengono allo schema $H$ dopo l'operazione di cross over nella forma

$$\dfrac{\bar f(H,t)}{\bar f(t)} \cdot r_{H,t}\cdot p_{\textbf{S}} ... ... \cdot r_{H,t}\cdot \left( 1-p_{\textbf{C}} \cdot \dfrac{\delta(H)}{n-1}\right)$$ (5.1.12)

Dopo l'operazione di cross over tuttavia interviene l'operatore di mutazione che può alterare l'individuo nei bit assegnati di $H$, e far si che non possa più appartenere allo schema.

La probabilità che tutte gli individui che appartengono ad $H$ rimangano inalterati dopo una operazione di mutazione è

$$(1-p_{\mathbf{M}})^{\mathcal{O^{}}(H)}$$ (5.1.13)

Introducendo la precente espressione nella 5.1.12 si ottiene la 5.1.7. $\Box$

Il teorema di Holland viene sviluppato rispetto alla semplice operazione di cross over uniforme, tuttavia può essere analogamente esteso a implementazioni che utilizzano altri operatori di mutazione e cross over.

Corollario 5.1.2   Per un algoritmo genetico nella forma semplice, con regola di selezione 'roulette wheel', la disugualianza 5.1.7 assume la forma

$$E[r_{H,t+1}] \geqslant r_{H,t} \cdot \dfrac{\bar f(H,t)}{\bar f(t)} \cdot P_\mathbf{C} (H) \cdot P_\mathbf{M} (H)$$ (5.1.14)

per ogni schema $H$, dove con $P_\mathbf{C}$ una costante che dipende dallp schema e dal metodo di cross over utilizzato, mentre $P_\mathbf{M}$ dipende solamente da $H$ e dal metodo di mutazione scelto. In tabella 5.1 sono evidenziate le espressioni da utilizzare per ogni metodo di mutazione o cross over utilizzato.

Tabella 5.1: Espressioni da utilizzare per il corollario 5.2.2 in presenza di diversi metodi di mutazione o cross over.

$P_\mathbf{C}(H)=1-p_\mathbf{C} \cdot \frac{\delta (H)} {n-1}$	Cross over su singolo bit
$P_\mathbf{C} (H)=1-p_\mathbf{C} \cdot (1-\frac{1}{2}^{\mathcal{O}(H)})$	Cross over uniforme
$P_\mathbf{C} (H)=1-p_\mathbf{C}$	Ogni altro tipo di cross over
$P_\mathbf{M} (H) = (1-p_\mathbf{M})^ {\mathcal{O}(H)}$	Mutazione bit a bit
$P_\mathbf{M} (H) = 1-p_\mathbf{M} \cdot \frac{\mathcal{O}(H)} {n}$	Inversione di un singolo bit
$P_\mathbf{M} (H) = 1-p_\mathbf{M}$	Inversione bit a bit
$P_\mathbf{M} (H) = 1-p_\mathbf{M} \cdot \frac{\vert H\vert}{2^n}$	Selezione casuale

Il teorema di Holland, a una prima interpretazione appare sicuramente poco esplicativo, apre inoltre numerose questioni che sembrano rendere ancora più nebulosa la questione della convergenza verso le soluzioni ottime.

Dapprima è necessario notare che in base alla 5.1.7, gli schemi con fitness superiore alla media e distanza minima tendono a produrre più figli che gli altri. Gli schemi con questa proprietà vengono chiamati building blocks. Se assumiamo che il rapporto

$$\dfrac{\bar f(H,t)}{\bar f(t)}$$

sia stazionario o quasi stazionario, cioè indipendente dal tempo e dalla generazione che si considera, si intuisce immediatamente che il numero di stringhe che appartengono a schemi con fitness sopra la media e distanza breve, cresce esponenzialmente con le generazioni.

Questo ci impone di capire se sia una strategia saggia quella di far crescere esponenzialmente il numero di soggetti appartenenti a uno schema con fitness superiore alla media e distanza breve.

Tenuto conto che l'algoritmo genetico lavora su stringhe e non su schemi, il teorema di Holland fornisce informazioni in parallelo su come tutti gli schemi possano crescere in popolazione se il loro fitness è superiore alla media, ridursi altrimenti.

Nei prossimi paragrafi si affronteranno queste due questioni; prima l'ottimizzazione della popolazione e poi il parallelismo implicito degli algoritmi genetici.