Twierdzenie Hollanda o schematach: Różnice pomiędzy wersjami
[wersja nieprzejrzana] | [wersja nieprzejrzana] |
Wartość oczekiwana. |
Referencja. |
||
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 == |
== 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="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="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="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> |
<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> |
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 , 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 schematu nazywa się liczbę alleli ustalonych, tzn. różnych od [4]. Długością definiującą schemat 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ą schematu nazywa się łączną liczbę alleli ustalonych i zmiennych[5]. Dla przykładu, jeśli , to , oraz .
Przez kruchość schematu rozumie się liczbę , która opisuje fragment schematu, który może zostać zakłócony przez wariację[5].
Wartość funkcji przystosowania obliczona dla schematu w iteracji numer jest równa średniej wartości funkcji przystosowania wszystkich genotypów próbkujących obecnych w populacji w iteracjij [5]. Wartość jest równa średniej wartości funkcji przystosowania ze wszystkich genotypów obecnych w populacji w iteracji [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 oraz :[5]
W powyższym wzorze symbol jest wartością oczekiwaną a jest liczbą genotypów obecnych w populacji w iteracji próbkujących schemat .
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 i j k David White. An Overview of Schema Theory. „arXiv”, 2014. DOI: 10.48550/arXiv.1401.2651. arXiv:1401.2651. (ang.).