Teorema dello schema di Holland

Descrizione

Consideriamo stringhe binarie di lunghezza 6. Lo schema 1*10*1 descrive l'insieme di tutte le stringhe di lunghezza 6 con 1 nelle posizioni 1, 3 e 6 e uno 0 nella posizione 4. L'* è un simbolo jolly, il che significa che le posizioni 2 e 5 possono avere sia il valore di 1 che di 0. Lo schema o ( H ) è definito come uno schema che ha il valore di 1. L'* è un simbolo jolly, il che significa che le posizioni 2 e 5 possono avere un valore di 1 o 0. L'ordine di uno schema o ( H ) {displaystyle o(H)} è definito come il numero di posizioni fisse nello schema, mentre la lunghezza di definizione δ ( H ) {displaystyle \delta (H)} è la distanza tra la prima e l'ultima posizione specifica. L'ordine di 1*10*1 è 4 e la sua lunghezza determinante è 5. Il fitness di uno schema è il fitness medio di tutte le stringhe che corrispondono allo schema. Il fitness di una stringa è una misura del valore della soluzione del problema codificata, come calcolato da una funzione di valutazione specifica del problema. Usando i metodi consolidati e gli operatori genetici degli algoritmi genetici, il teorema dello schema afferma che gli schemi brevi e di basso ordine con fitness superiore alla media aumentano esponenzialmente nelle generazioni successive. Espresso come un'equazione:

E ( m ( H , t + 1 ) ) ≥ m ( H , t ) f ( H ) a t [ 1 - p ] . E ( m(H,t+1) ) ≥ m ( H,t ) f ( H ) a t [ 1 - p ] . (m(H,t+1))\geq {m(H,t)f(H) su a_{t}}[1-p]. }

Qui m ( H , t ) {displaystyle m(H,t)} è il numero di stringhe appartenenti allo schema H {displaystyle H} alla generazione t {displaystyle t} , f ( H ) {displaystyle f(H)} è la fitness media osservata dello schema H {displaystyle H} e a t {displaystyle a_{t}} è la fitness media osservata alla generazione t {displaystyle t} . La probabilità di interruzione p {displaystyle p} è la probabilità che il crossover o la mutazione distruggano lo schema H {displaystyle H} . Può essere espressa come:

p = δ ( H ) l - 1 p c + o ( H ) p m {displaystyle p={delta (H) \over l-1}p_{c}+o(H)p_{m}}

dove o ( H ) {displaystyle o(H)} è l'ordine dello schema, l {displaystyle l} è la lunghezza del codice, p m {displaystyle p_{m}} è la probabilità di mutazione e p c {displaystyle p_{c}} è la probabilità di crossover. Quindi uno schema con una lunghezza di definizione più breve δ ( H ) {\displaystyle \delta (H)} ha meno probabilità di essere interrotto.
Un punto spesso frainteso è perché il teorema dello schema è una disuguaglianza piuttosto che un'uguaglianza. La risposta è infatti semplice: il Teorema trascura la piccola, ma non nulla, probabilità che una stringa appartenente allo schema H {displaystyle H} venga creata "da zero" per mutazione di una singola stringa (o ricombinazione di due stringhe) che non apparteneva a H {displaystyle H} nella generazione precedente.

Limitazione

Il teorema dello schema vale nell'ipotesi di un algoritmo genetico che mantiene una popolazione infinitamente grande, ma non sempre si applica alla pratica (finita): a causa di un errore di campionamento nella popolazione iniziale, gli algoritmi genetici possono convergere su schemi che non hanno alcun vantaggio selettivo. Questo accade in particolare nell'ottimizzazione multimodale, dove una funzione può avere più picchi: la popolazione può andare alla deriva per preferire uno dei picchi, ignorando gli altri.

La ragione per cui il teorema dello schema non può spiegare la potenza degli algoritmi genetici è che vale per tutte le istanze del problema e non può distinguere tra i problemi in cui gli algoritmi genetici funzionano male e i problemi in cui gli algoritmi genetici funzionano bene.

Tracciato di una funzione multimodale in due variabili.