Teorema degli schemi

Il teorema degli schemi, conosciuto anche come teorema di Holland o teorema fondamentale degli algoritmi genetici, fu formalizzato nel 1970 da John Henry Holland ed è oggi considerato uno dei teoremi più importanti per mostrare la potenzialità degli algoritmi genetici.

Ipotesi

Dato un algoritmo genetico, le informazioni contenute all'interno dei suoi cromosomi possono essere categorizzate ed identificate con particolari stringhe dette schemi. Gli schemi consistono di un insieme di metacaratteri riconosciuti come validi e da un insieme di simboli prelevati dall'alfabeto di codifica utilizzato. Per una maggiore comprensione di quanto affermato è opportuno procedere con un esempio. A tale scopo consideriamo:

• Una codifica binaria ed i suoi simboli di codifica 0 e 1.
• Il metacarattere * che identifica un valore qualsiasi tra quelli ammessi dalla codifica.
• Tre generiche soluzioni codificate in forma di cromosoma binario A=1001101, B=1000100 e C=0000010.
• Uno schema S=100*.

In questo esempio, lo schema identifica tutte le sottostringhe di A, B e C che cominciano con 100 e che sono lunghe quattro caratteri ossia: la sottostringa 1001 appartenente ad A e la sottostringa 1000 appartenente a B. C, a differenza di A e di B, non possiede sottostringhe identificate dallo schema.

Tesi

All'interno dei cromosomi sono codificati dei passi elementari che permettono la risoluzione parziale del problema (se non dovessero essere presenti, prima o poi verrebbero comunque introdotti e codificati grazie alle mutazioni). Questi passi, se sopravvivono e vengono sufficientemente ricombinati, si ampliano e permettono di giungere ad una soluzione completa e definitiva. Delle simili informazioni, rappresentabili con degli schemi, potrebbero essere definite come "blocchi costruttori".

Dimostrazione

Basandosi sul fatto che durante l'esecuzione di un algoritmo genetico, valutando le stringhe relative alla codifica vettoriale delle soluzioni del problema considerato, si valuta implicitamente il valore di fitness di diversi schemi, con qualche calcolo matematico si può dedurre la formula che permette di approssimare il numero atteso del valore di fitness dello schema successivo.

La formula che si ricava da questa affermazione è la seguente:

$M(H_{i},t+1)\geq M(H_{i},t)\cdot \left[{f(H_{i}) \over {\bar {f}}}\right]\cdot \left[1-p_{c}\cdot {\delta (H_{i}) \over {l-1}}\right]\cdot \left[(1-p_{m})^{o(H_{i})}\right]$

dove:

• $f(H_{i})$: è la media dei parametri associati dalla funzione di fitness alle stringhe identificate dall'i-esimo schema.
• ${\bar {f}}$: è la media dei parametri associati dalla funzione di fitness alle soluzioni della popolazione considerata.
• $\delta (H_{i})$: è la lunghezza dell'i-esimo schema considerato.
• $l$: è la lunghezza delle stringhe nello spazio di ricerca.
• $o(H_{i})$: è il numero di bit conosciuti nello schema considerato.
• $p_{m}$ e $p_{c}$: sono le probabilità di mutazione e di crossover.

La formula mostrata afferma che quando esistono stringhe caratterizzate da schemi corti, alto parametro di fitness e basso ordine ci sono maggiori probabilità di sopravvivenza. Queste caratteristiche permetterebbero la ricombinazione di stringhe simili che andrebbero a generare altre stringhe linearmente più lunghe ma con parametro di fitness esponenzialmente più alto sulle quali la formula potrebbe essere nuovamente applicata.

Conclusioni

Quanto mostrato dalla dimostrazione sancisce l'esistenza e la forma dei blocchi costruttori inizialmente teorizzati che rappresenta poi l'essenza e la natura degli algoritmi genetici ossia la possibilità di ricombinare soluzioni parziali (esistenti o generate per mutazione) per poi giungere ad una soluzione completa.

Voci correlate

• Algoritmi genetici
• Soft computing
• Intelligenza artificiale