AlegsaOnline.com

Twierdzenie schematu Hollanda w algorytmach genetycznych

Omówienie twierdzenia schematu Hollanda w algorytmach genetycznych: sformułowanie, klasyczna nierówność i przybliżenia, warunki wzrostu krótkich schematów oraz ograniczenia i założenia modelu.

Autor: Leandro Alegsa

09-04-2026

Twierdzenie Hollanda o schematach (również nazywane fundamentalnym twierdzeniem algorytmów genetycznych) jest nierównością wynikającą z gruboziarnistego modelu dynamiki populacji w algorytmach genetycznych. Twierdzenie formułuje warunki, przy których krótkie, niskiego rzędu schematy o ponadprzeciętnej średniej kondycji mają tendencję do wzrostu liczebności w kolejnych pokoleniach. Zostało zaproponowane przez Johna Hollanda w latach 70. XX wieku i przez długi czas bywało cytowane jako podstawowy argument wyjaśniający działanie algorytmów genetycznych, choć jego interpretacja i zakres zastosowań zostały później poddane krytycznej analizie.

W uproszczonej i często podawanej postaci twierdzenie można zapisać za pomocą oczekiwanej liczby wystąpień schematu H w populacji. Oznaczając m(H,t) liczbę osobników zgodnych ze schematem H w pokoleniu t, f(H) średnią kondycję tych osobników, f̄ średnią kondycję całej populacji, p_c prawdopodobieństwo wykonania krzyżowania jednopunktowego, p_m prawdopodobieństwo mutacji pojedynczego genu, o(H) rząd schematu (liczba określonych pozycji) oraz δ(H) długość definiującą schematu (odległość między pierwszą a ostatnią określoną pozycją, przy długości łańcucha l), uzyskuje się klasyczną nierówność:

E[m(H,t+1)] ≥ m(H,t) · (f(H)/f̄) · (1 − p_c · (δ(H)/(l − 1))) · (1 − p_m)^{o(H)}.

W praktyce często stosuje się liniaryzowaną przybliżoną postać (dla małych p_c i p_m):

E[m(H,t+1)] ≈ m(H,t) · (f(H)/f̄) · [1 − p_c · (δ(H)/(l − 1)) − o(H) · p_m].

Obie formy należy rozumieć jako wynik przyjętych założeń modelowych: reprezentacja binarna, proporcjonalny dobór reprodukcyjny, jednopunktowe krzyżowanie i niezależna mutacja bitowa oraz analiza oczekiwanej wartości w modelu dużej (w praktyce często zakładanej nieskończonej) populacji. W rzeczywistych populacjach skończonych działanie doboru i operatorów losowych oraz różne warianty operatorów (np. krzyżowania wielopunktowego, selekcji turniejowej) mogą istotnie zmieniać zachowanie systemu.

Definicje i własności schematów

Schemat to wzorzec (szablon) określający wartości w wybranych pozycjach łańcucha genotypowego; zbiór wszystkich łańcuchów zgodnych ze schematem tworzy podzbiór łańcuchów.
Rząd schematu o(H) to liczba określonych (nie‑joker) pozycji.
Długość definiująca δ(H) to odległość między pierwszą a ostatnią określoną pozycją; od niej zależy podatność schematu na zniszczenie przez krzyżowanie.
Schematy można traktować jako specjalne zbiory walcowe, które nadają strukturę przestrzenną, przez co tworzą naturalną przestrzeń topologiczną wzorców w zbiorze łańcuchów.

Ocena i rozwój koncepcji

Twierdzenie dostarcza użytecznej, intuicyjnej reguły mówiącej, że krótkie i niskiego rzędu schematy o relatywnie wysokiej średniej kondycji mają większe szanse na utrzymanie lub wzrost liczebności w kolejnych pokoleniach, o ile nie zostaną zbyt często zniszczone przez operatory genetyczne.
Nie jest to jednak dowód, że algorytmy genetyczne zawsze efektywnie odkrywają lub łączą „najlepsze budulce” ani że są lepsze od innych metod optymalizacji — takie interpretacje są nadmiernym uproszczeniem. Krytycy zwracali uwagę na ograniczenia założeń i na to, że nierówność dotyczy oczekiwanej wartości, a więc nie uwzględnia w pełni wariancji i efektów dyskretnych przy skończonych populacjach.
Późniejsze analizy powiązały twierdzenie schematu z równaniem Price'a i innymi uogólnieniami matematycznymi, co pozwoliło lepiej zrozumieć jego zakres i granice stosowalności w analizie ewolucyjnej.
W literaturze powstały także precyzyjniejsze i alternatywne sformułowania opisujące propagację wzorców w populacjach, a także prace empiryczne badające praktyczne skutki założeń twierdzenia.

Znaczenie praktyczne

Współcześnie twierdzenie Hollanda o schematach bywa używane przede wszystkim jako heurystyczne narzędzie do rozumienia mechanizmów, które mogą sprzyjać tworzeniu lepszych rozwiązań w algorytmach genetycznych (np. wpływ długości kodowania, częstości krzyżowania i mutacji). Jednocześnie projektanci algorytmów powinni pamiętać o ograniczeniach twierdzenia i opierać decyzje także na analizie eksperymentalnej oraz na innych ramach teoretycznych.

Opis

Rozważmy ciągi binarne o długości 6. Schemat 1*10*1 opisuje zbiór wszystkich ciągów o długości 6 z 1 na pozycjach 1, 3 i 6 oraz 0 na pozycji 4. Symbol * jest symbolem wieloznacznym, co oznacza, że pozycje 2 i 5 mogą mieć wartość 1 lub 0. Porządek schematu o ( H ) {przyp. tłum. o(H)} $o(H)$ jest zdefiniowany jako liczba stałych pozycji we wzorcu, natomiast długość definiująca δ ( H ) {przyp. tłum. o(H)} $\delta (H)$ to odległość między pierwszą i ostatnią określoną pozycją. Rząd 1*10*1 wynosi 4, a jego długość definiująca to 5. Zdatność schematu jest średnią zdatnością wszystkich ciągów pasujących do schematu. Zdatność łańcucha jest miarą wartości zakodowanego rozwiązania problemu, obliczoną przez specyficzną dla danego problemu funkcję oceny. Wykorzystując znane metody i operatory genetyczne algorytmów genetycznych, twierdzenie o schemacie mówi, że krótkie, niskiego rzędu schematy o ponadprzeciętnej kondycji rosną wykładniczo w kolejnych pokoleniach. Wyrażone jako równanie:

E ( m ( H , t + 1 ) ≥ m ( H , t ) f ( H ) a t [ 1 - p ] . {{displaystyle \\operatorname {\i0} (m(H,t+1))\geq {m(H,t)f(H) \over a_{t}}[1-p] } $\operatorname {E} (m(H,t+1))\geq {m(H,t)f(H) \over a_{t}}[1-p].$

Tutaj m ( H , t ) {{displaystyle m(H,t)} $m(H,t)$ jest liczbą łańcuchów należących do schematu H {{displaystyle H}} $H$ w pokoleniu t {{displaystyle t}} $t$ , f ( H ) {f(H)} $f(H)$ jest obserwowaną średnią kondycją schematu H, $H$ a a t {a_{t}} $a_{t}$ jest obserwowaną średnią kondycją w pokoleniu t {t}} $t$ . Prawdopodobieństwo zakłócenia p {p} $p$ jest prawdopodobieństwem, że krzyżowanie lub mutacja zniszczy schemat H {styl H} $H$ . Można je wyrazić jako:

p = δ ( H ) l - 1 p c + o ( H ) p m {{displaystyle p={delta (H) \over l-1}p_{c}+o(H)p_{m}} $p={\delta (H) \over l-1}p_{c}+o(H)p_{m}$

gdzie o ( H ) {{displaystyle o(H)} $o(H)$ to kolejność schematu, l {{displaystyle l}} $l$ to długość kodu, p m {{displaystyle p_{m}} $p_{m}$ to prawdopodobieństwo mutacji, a p c {{displaystyle p_{c}} $p_{c}$ to prawdopodobieństwo krosowania. Tak więc schemat o krótszej długości definiującej δ ( H ) { \displaystyle \delta (H)} $\delta (H)$ jest mniej prawdopodobne, że zostanie zakłócony.
Często niezrozumiałą kwestią jest to, dlaczego Twierdzenie o schemacie jest nierównością, a nie równością. Odpowiedź jest w gruncie rzeczy prosta: Twierdzenie pomija niewielkie, ale niezerowe prawdopodobieństwo, że ciąg należący do schematu H {displaystyle H} $H$ powstanie "od zera" poprzez mutację pojedynczego ciągu (lub rekombinację dwóch ciągów), który $H$ w poprzednim pokoleniu nie należał do H {displaystyle H}.

Ograniczenie

Twierdzenie o schemacie obowiązuje przy założeniu, że algorytm genetyczny utrzymuje nieskończenie dużą populację, ale nie zawsze przenosi się na (skończoną) praktykę: z powodu błędu próbkowania w populacji początkowej, algorytmy genetyczne mogą zbiegać się na schematach, które nie mają żadnej selektywnej przewagi. Zdarza się to w szczególności w optymalizacji wielomodalnej, gdzie funkcja może mieć wiele szczytów: populacja może dryfować w kierunku preferowania jednego z nich, ignorując pozostałe.

Powodem, dla którego Twierdzenie Schematu nie może wyjaśnić potęgi algorytmów genetycznych, jest to, że obowiązuje ono dla wszystkich przypadków problemów i nie może rozróżnić problemów, w których algorytmy genetyczne radzą sobie słabo, od problemów, w których algorytmy genetyczne radzą sobie dobrze.

Wykres funkcji multimodalnej w dwóch zmiennych.

Pytania i odpowiedzi

P: Czym jest twierdzenie Hollanda o schemacie?

O: Twierdzenie schematu Hollanda to twierdzenie dotyczące algorytmów genetycznych, które mówi, że osobniki o kondycji wyższej niż średnia mają większe szanse na zwycięstwo.

P: Kto i kiedy zaproponował twierdzenie Hollanda?

O: John Holland zaproponował twierdzenie Hollanda w latach 70. ubiegłego wieku.

P: Czym jest schemat w kontekście algorytmów genetycznych?

O: W kontekście algorytmów genetycznych schemat jest szablonem, który identyfikuje podzbiór ciągów z podobieństwami w określonych pozycjach ciągu.

P: Jaka jest interpretacja twierdzenia Hollanda o schematach, które zostało wykorzystane jako podstawa do wyjaśnienia mocy algorytmów genetycznych?

O: Interpretacja twierdzenia Hollanda, która została wykorzystana jako podstawa do wyjaśnienia mocy algorytmów genetycznych, jest taka, że osobniki o kondycji wyższej niż średnia mają większe szanse na zwycięstwo.

P: Co pokazała krytyka twierdzenia Hollanda o schematach?

O: Krytyka twierdzenia Hollanda pokazała, że jest ono szczególnym przypadkiem równania Price'a z funkcją wskaźnika schematu jako makroskopowym pomiarem.

P: Co jest szczególnym przypadkiem zbiorów cylindrycznych?

O: Schematy są szczególnym przypadkiem zbiorów cylindrycznych.

P: Jaki rodzaj przestrzeni tworzą schematy?

O: Schematy tworzą przestrzeń topologiczną.