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 , 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 schematu nazywa się liczbę alleli ustalonych, tzn. różnych od . 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 . Długością schematu nazywa się łączną liczbę alleli ustalonych i zmiennych. 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ę.
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 . Wartość jest równa średniej wartości funkcji przystosowania ze wszystkich genotypów obecnych w populacji w iteracji .
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 oraz :
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.
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.
Przypisy
Kategoria:Algorytmy ewolucyjne Hollanda o schematach