Twierdzenie o schemacie Hollanda - Holland's schema theorem

Twierdzenie o schemacie Hollanda , zwane także podstawowym twierdzeniem algorytmów genetycznych , jest nierównością wynikającą z gruboziarnistego równania dynamiki ewolucyjnej . Twierdzenie o schemacie mówi, że krótkie, niskiego rzędu schematy z ponadprzeciętną sprawnością zwiększają się wykładniczo w kolejnych pokoleniach. Twierdzenie zostało zaproponowane przez Johna Hollanda w latach 70. Początkowo uważano, że jest to podstawa do wyjaśniania mocy algorytmów genetycznych . Jednak ta interpretacja jej implikacji była krytykowana w kilku recenzowanych publikacjach, w których wykazano, że twierdzenie o schemacie jest szczególnym przypadkiem równania Price z funkcją wskaźnika schematu jako pomiarem makroskopowym.

Schemat jest szablon, który identyfikuje podzbiór ciągów z podobieństw w pewnych pozycjach smyczkowych. Schematy są szczególnym przypadkiem zbiorów cylindrów , a zatem tworzą przestrzeń topologiczną .

Opis

Rozważmy ciągi binarne o długości 6. Schemat 1*10*1opisuje zbiór wszystkich ciągów o długości 6 z 1 na pozycjach 1, 3 i 6 oraz 0 na pozycji 4. * jest symbolem wieloznacznym , co oznacza, że ​​pozycje 2 i 5 mogą mieć wartość 1 lub 0. Kolejność schematu jest definiowana jako liczba ustalonych pozycji w szablonie, podczas gdy długość definiująca to odległość między pierwszą a ostatnią określoną pozycją. Rząd wynosi 4, a jego długość definiująca to 5. Dopasowanie schematu to średnia przydatność wszystkich ciągów pasujących do schematu. Dopasowanie ciągu jest miarą wartości zakodowanego rozwiązania problemu, obliczoną przez funkcję oceny specyficzną dla problemu. Stosując określone metody i operatory genetyczne o algorytmach genetycznych , schemat twierdzenie stwierdza, że krótkie, schematów niskiej zamówienie z ponadprzeciętnego wzrostu przydatności wykładniczo w kolejnych pokoleniach. Wyrażone jako równanie: ${\ Displaystyle o (H)}$ ${\ Displaystyle \ delta (H)}$1*10*1

${\ displaystyle \ operatorname {e} (m (h, t + 1)) \ geq {m (h, t) f (h) \ przez a_ {t}} [1-p].}$

Oto liczba ciągów należących do schematu w momencie generowania , jest to obserwowana średnia przydatność schematu i jest to obserwowana średnia przydatność podczas generowania . Prawdopodobieństwo zakłócenia to prawdopodobieństwo, że crossover lub mutacja zniszczą schemat . Można to wyrazić jako: ${\ Displaystyle m (H, t)}$${\ displaystyle H}$${\ displaystyle t}$${\ displaystyle f (H)}$${\ displaystyle H}$${\ displaystyle a_ {t}}$${\ displaystyle t}$${\ displaystyle p}$${\ displaystyle H}$

${\ Displaystyle p = {\ delta (H) \ ponad l-1} p_ {c} + o (H) p_ {m}}$

gdzie jest kolejnością schematu, jest długością kodu, jest prawdopodobieństwem mutacji i jest prawdopodobieństwem krzyżowania. Tak więc schemat z krótszą długością definiowania jest mniej podatny na zakłócenia. Często niezrozumianym argumentem jest to, dlaczego twierdzenie o schemacie jest raczej nierównością niż równością. Odpowiedź jest w istocie prosta: Twierdzenie pomija małe, ale niezerowe prawdopodobieństwo, że ciąg należący do schematu zostanie utworzony „od zera” przez mutację pojedynczego ciągu (lub rekombinacji dwóch ciągów), które nie należały do w poprzedniej generacji. ${\ Displaystyle o (H)}$${\ displaystyle l}$${\ displaystyle p_ {m.}}$${\ displaystyle p_ {c}}$${\ Displaystyle \ delta (H)}$
${\ displaystyle H}$${\ displaystyle H}$

Ograniczenie

Wykres funkcji multimodalnej w dwóch zmiennych.

Twierdzenie o schemacie utrzymuje się przy założeniu algorytmu genetycznego, który utrzymuje nieskończenie dużą populację, ale nie zawsze przenosi się do (skończonej) praktyki: z powodu błędu próbkowania w populacji początkowej algorytmy genetyczne mogą zbiegać się na schematach, które nie mają selektywnej przewagi . Dzieje się tak w szczególności w przypadku optymalizacji multimodalnej , w której funkcja może mieć wiele szczytów: populacja może dryfować, aby preferować jeden ze szczytów, ignorując pozostałe.

Powodem, dla którego twierdzenie o schemacie nie może wyjaśnić mocy algorytmów genetycznych, jest to, że odnosi się ono do wszystkich przypadków problemów i nie umożliwia rozróżnienia między problemami, w których algorytmy genetyczne działają słabo, a problemami, w przypadku których algorytmy genetyczne działają dobrze.

Bibliografia

• J. Holland, Adaptacja w systemach naturalnych i sztucznych , MIT Press; Przedruk wydania 1992 (pierwotnie opublikowany w 1975).
• J. Holland, Hidden Order: How Adaptation Builds Complexity , Helix Books; 1996.