Twierdzenie Hollanda o schematach

Twierdzenie Hollanda o schematach – centralne twierdzenie algorytmów genetycznych zaproponowane przez Johna Henry’ego Hollanda^[1]^[2]^[3]^[4]^[5]. 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^[2].

Definicje

Schemat (ang. l.p. schema, l.mn. schemata^[5]) jest podzbiorem przestrzeni genotypów, którego elementy są łańcuchami genetycznymi z góry ustalonymi wartościami wybranych alleli^[4]. 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 #)^[1]^[4]. Alternatywnie, schemat można zdefiniować z użyciem teorii grup^[4] lub z wykorzystaniem pojęcia zbioru cylindrowego.

Rzędem $o$ schematu $H$ nazywa się liczbę alleli ustalonych, tzn. różnych od $*$ ^[4]. 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 $*$ ^[4]. Długością $l$ schematu $H$ nazywa się łączną liczbę alleli ustalonych i zmiennych^[5]. 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ę^[5].

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$ ^[5]. Wartość ${\bar {f}}(t)$ jest równa średniej wartości funkcji przystosowania ze wszystkich genotypów obecnych w populacji w iteracji $t$ ^[5].

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

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ń^[5].

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

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} }$ :^[5]

\langle m(H,t+1)\rangle \geq {\frac {f(H,t)}{{\bar {f}}(t)}}\cdot m(H,t)\left(1-p_{\mathrm {r} }{\frac {\delta (H)}{l(H)-1}}\right)(1-p_{\mathrm {m} })^{o(H)}

W powyższym wzorze symbol $\langle \cdot \rangle$ 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^[5].

Twierdzenie o schematach może zostać sformułowane również w przypadku innych form obliczeń genetycznych, np. dla programowania genetycznego^[6]^[5]. 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^[3].

Przypisy

↑ ^a ^b John H. Holland: Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor, MI, USA, 1975, s. 1–183.
↑ ^a ^b Lee Altenberg: The Schema Theorem and Price’s Theorem. L. Darrell Whitley, Michael D. Vose (eds.). Elsevier, 1995, s. 23–49, seria: Foundations of Genetic Algorithms (3). DOI: 10.1016/B978-1-55860-356-1.50006-6. ISSN 1081-6593.
↑ ^a ^b David E. Goldberg: The Design of Innovation. Lessons from and for Competent Genetic Algorithms. Springer Science+Business Media Dordrecht, 2002, s. i-xxiv, 1-248, seria: Genetic Algorithms and Evolutionary Computation. DOI: 10.1007/978-1-4757-3643-4. ISBN 978-1-4757-3643-4.
↑ ^a ^b ^c ^d ^e ^f Alden H. Wright. The Exact Schema Theorem. „arXiv”, 2011. DOI: 10.48550/arXiv.1105.3538. arXiv:1105.3538. (ang.).
↑ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^j ^k ^l David White. An Overview of Schema Theory. „arXiv”, 2014. DOI: 10.48550/arXiv.1401.2651. arXiv:1401.2651. (ang.).
↑ Riccardo Poli, William B. Langdon. Schema Theory for Genetic Programming with One-Point Crossover and Point Mutation. „Evolutionary Computation”. 6 (3), s. 231-252, 1998. DOI: 10.1162/evco.1998.6.3.231. (ang.).

[Holland1975-1] John H. Holland: Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor, MI, USA, 1975, s. 1–183.

[Altenberg1995-2] Lee Altenberg: The Schema Theorem and Price’s Theorem. L. Darrell Whitley, Michael D. Vose (eds.). Elsevier, 1995, s. 23–49, seria: Foundations of Genetic Algorithms (3). DOI: 10.1016/B978-1-55860-356-1.50006-6. ISSN 1081-6593.

[Goldberg2002-3] David E. Goldberg: The Design of Innovation. Lessons from and for Competent Genetic Algorithms. Springer Science+Business Media Dordrecht, 2002, s. i-xxiv, 1-248, seria: Genetic Algorithms and Evolutionary Computation. DOI: 10.1007/978-1-4757-3643-4. ISBN 978-1-4757-3643-4.

[Wright2011-4] ↑ ^a ^b ^c ^d ^e ^f Alden H. Wright. The Exact Schema Theorem. „arXiv”, 2011. DOI: 10.48550/arXiv.1105.3538. arXiv:1105.3538. (ang.).

[White2014-5] ↑ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ ^j ^k ^l David White. An Overview of Schema Theory. „arXiv”, 2014. DOI: 10.48550/arXiv.1401.2651. arXiv:1401.2651. (ang.).

[Poli1998-6] Riccardo Poli, William B. Langdon. Schema Theory for Genetic Programming with One-Point Crossover and Point Mutation. „Evolutionary Computation”. 6 (3), s. 231-252, 1998. DOI: 10.1162/evco.1998.6.3.231. (ang.).

[1]

[2]

[3]

[4]

[5]

[6]