Twierdzenie Hollanda o schematach: Różnice pomiędzy wersjami

[wersja nieprzejrzana]

Usunięta treść Dodana treść

Jednokolumnowy

Wersja z 17:43, 5 lip 2024

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 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].

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.
↑ 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 David White. An Overview of Schema Theory. „arXiv”, 2014. DOI: 10.48550/arXiv.1401.2651. arXiv:1401.2651. (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 David White. An Overview of Schema Theory. „arXiv”, 2014. DOI: 10.48550/arXiv.1401.2651. arXiv:1401.2651. (ang.).

[1]

[2]

[3]

[4]

[5]

@@ Linia 1: / Linia 1: @@
-'''Twierdzenie Hollanda o schematach''' – centralne [[twierdzenie]] [[Algorytm genetyczny|algorytmów genetycznych]] zaproponowane przez [[John Henry Holland|Johna Henry’ego Hollanda]]<ref name="Holland1975" /><ref name="Altenberg1995" /><ref name="Wright2011" /><ref name="White2014" />. 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 [[Wzrost wykładniczy|wykładniczy]]<ref name="Altenberg1995" />.
+'''Twierdzenie Hollanda o schematach''' – centralne [[twierdzenie]] [[Algorytm genetyczny|algorytmów genetycznych]] zaproponowane przez [[John Henry Holland|Johna Henry’ego Hollanda]]<ref name="Holland1975" /><ref name="Altenberg1995" /><ref name="Goldberg2002" /><ref name="Wright2011" /><ref name="White2014" />. 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 [[Wzrost wykładniczy|wykładniczy]]<ref name="Altenberg1995" />.
 == Definicje ==
@@ Linia 32: / Linia 32: @@
 <ref name="Holland1975">{{Cytuj książkę |autor = John H. Holland |tytuł = Adaptation in Natural and Artificial Systems |wydawca = University of Michigan Press, Ann Arbor, MI, USA |rok = 1975 |strony = 1–183}}</ref>
 <ref name="Altenberg1995">{{Cytuj książkę |autor = Lee Altenberg |tytuł = The Schema Theorem and Price’s Theorem |inni = L. Darrell Whitley, Michael D. Vose (eds.) |seria = Foundations of Genetic Algorithms (3) |rok = 1995 |wydawca = Elsevier |strony = 23–49 |issn = 1081-6593 |doi = 10.1016/B978-1-55860-356-1.50006-6}}</ref>
+<ref name="Goldberg2002">{{Cytuj książkę |autor = David E. Goldberg |tytuł = The Design of Innovation. Lessons from and for Competent Genetic Algorithms |seria = Genetic Algorithms and Evolutionary Computation |rok = 2002 |wydawca = Springer Science+Business Media Dordrecht |strony = i-xxiv, 1-248 |isbn = 978-1-4757-3643-4 |doi = 10.1007/978-1-4757-3643-4}}</ref>
 <ref name="Wright2011">{{Cytuj pismo |autor = Alden H. Wright |tytuł = The Exact Schema Theorem |czasopismo = arXiv |rok = 2011 |doi = 10.48550/arXiv.1105.3538 |arxiv = 1105.3538 |język = en}}</ref>
 <ref name="White2014">{{Cytuj pismo |autor = David White |tytuł = An Overview of Schema Theory |czasopismo = arXiv |rok = 2014 |doi = 10.48550/arXiv.1401.2651 |arxiv = 1401.2651 |język = en}}</ref>