Twierdzenie schematu Hollanda w algorytmach genetycznych

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)} jest zdefiniowany jako liczba stałych pozycji we wzorcu, natomiast długość definiująca δ ( H ) {przyp. tłum. o(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] }

Tutaj m ( H , t ) {{displaystyle m(H,t)} jest liczbą łańcuchów należących do schematu H {{displaystyle H}} w pokoleniu t {{displaystyle t}} , f ( H ) {f(H)} jest obserwowaną średnią kondycją schematu H, a a t {a_{t}} jest obserwowaną średnią kondycją w pokoleniu t {t}} . Prawdopodobieństwo zakłócenia p {p} jest prawdopodobieństwem, że krzyżowanie lub mutacja zniszczy schemat H {styl 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}}

gdzie o ( H ) {{displaystyle o(H)} to kolejność schematu, l {{displaystyle l}} to długość kodu, p m {{displaystyle p_{m}} to prawdopodobieństwo mutacji, a p c {{displaystyle p_{c}} to prawdopodobieństwo krosowania. Tak więc schemat o krótszej długości definiującej δ ( H ) { \displaystyle \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} powstanie "od zera" poprzez mutację pojedynczego ciągu (lub rekombinację dwóch ciągów), który w poprzednim pokoleniu nie należał do H {displaystyle H}.

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.