Twierdzenie Hollanda o schematach

Twierdzenie Hollanda o schematach, nazywane również fundamentalnym twierdzeniem algorytmów genetycznych, jest nierównością wynikającą z gruboziarnistego równania dynamiki ewolucyjnej. Twierdzenie Schema mówi, że krótkie, niskiego rzędu schematy o ponadprzeciętnej kondycji rosną wykładniczo w częstotliwości w kolejnych pokoleniach. Twierdzenie to zostało zaproponowane przez Johna Hollanda w latach 70. Początkowo było ono powszechnie uważane za podstawę wyjaśnień potęgi algorytmów genetycznych. Jednak taka interpretacja jego implikacji została skrytykowana w kilku publikacjach przejrzanych w , gdzie pokazano, że Twierdzenie Schematu jest szczególnym przypadkiem równania Price'a z funkcją wskaźnika schematu jako makroskopową miarą.

Schemat jest szablonem, który identyfikuje podzbiór łańcuchów z podobieństwami w określonych pozycjach łańcuchów. Schematy są szczególnym przypadkiem zbiorów walcowych, a więc tworzą przestrzeń topologiczną.

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