Twierdzenie Hollanda o schematach

Twierdzenie Hollanda o schematach – centralne twierdzenie algorytmów genetycznych zaproponowane przez Johna Henry’ego Hollanda. Twierdzenie to orzeka, że pod pewnymi warunkami schematy z ponadprzeciętną wartością funkcji przystosowania zwiększają swoje występowanie w populacji w kolejnych krokach procesu ewolucyjnego w sposób wykładniczy.

Definicje

Schemat (ang. l.p. schema, l.mn. schemata) jest podzbiorem przestrzeni genotypów, którego elementy są łańcuchami genetycznymi z góry ustalonymi wartościami wybranych alleli. Przykładem schematu w reprezentacji binarnej jest $H=(1*0*1)$, w którym zostały ustalone pierwszy, trzeci i piąty allel na wartości odpowiednio 1, 0 oraz 1 a pozostałe dwa allele mogą przyjmować wartość dowolną. Do oznaczania nieustalonych wartości alleli przyjmuje się symbol $*$ (aczkolwiek Holland stosował symbol #). Alternatywnie, schemat można zdefiniować z użyciem teorii grup lub z wykorzystaniem pojęcia zbioru cylindrowego.

Rzędem $o$ schematu $H$ nazywa się liczbę alleli ustalonych, tzn. różnych od $*$. Długością definiującą $\delta$ schemat $H$ nazywa się odległość między pierwszym a ostatnim ustalonym allelem, tzn. odległość między pierwszym a ostatnim elementem schematu różnym od $*$. Długością $l$ schematu $H$ nazywa się łączną liczbę alleli ustalonych i zmiennych. Dla przykładu, jeśli $H=(1*0*1)$, to $o(H)=3$, $\delta (H)=4$ oraz $l(H)=5$.

Przez kruchość schematu $H$ rozumie się liczbę $\frac{\delta (H)}{l(H)-1}$, która opisuje fragment schematu, który może zostać zakłócony przez wariację.

Wartość funkcji przystosowania $f(H,t)$ obliczona dla schematu $H$ w iteracji numer $t$ jest równa średniej wartości funkcji przystosowania wszystkich genotypów próbkujących $H$ obecnych w populacji w iteracjij $t$. Wartość $\overline{f}(t)$ jest równa średniej wartości funkcji przystosowania ze wszystkich genotypów obecnych w populacji w iteracji $t$.

Blokiem budującym (ang. building block) lub cegiełką nazywa się krótki schemat niskiego rzędu o ponadprzeciętnej wartości funkcji przystosowania.

Hipoteza bloków budujących (hipoteza cegiełek)

Wersja podstawowa hipotezy:

Dobry algorytm genetyczny łączy bloki budujące w celu osiągania lepszych rozwiązań.

Wersja podstawowa hipotezy bloków budujących jest sformułowana w sposób niejednoznaczny i posiada potencjalnie prawdziwe interpretacje.

Twierdzenie Hollanda o schematach

Twierdzenie o schematach określa oczekiwaną liczbę genotypów próbkujących schemat w kolejnej iteracji algorytmu genetycznego z reprezentacją binarną wykorzystującego mechanizm selekcji proporcjonalnej, rekombinację jednopunktową oraz mutację bitową z prawdopodobieństwami odpowiednio $p_{\mathrm{r}}$ oraz $p_{\mathrm{m}}$:

$⟨m(H,t+1)⟩\ge \frac{f(H,t)}{\overline{f}(t)}\cdot m(H,t)(1-p_{\mathrm{r}}\frac{\delta (H)}{l(H)-1})(1-p_{\mathrm{m}}{)}^{o(H)}$

W powyższym wzorze symbol $⟨\cdot ⟩$ jest wartością oczekiwaną a $m(H,t)$ jest liczbą genotypów obecnych w populacji w iteracji $t$ próbkujących schemat $H$.

Powyższe twierdzenie jest nieco ogólniejsze aniżeli podane oryginalnie przez Hollanda.

Twierdzenie o schematach może zostać sformułowane również w przypadku innych form obliczeń genetycznych, np. dla programowania genetycznego. Również w obrębie samych algorytmów genetycznych istnieje możliwość dostosowania twierdzenia o schematach do innych warunków ewolucji, np. do innego operatora selekcji.