Schemat (algorytmy genetyczne) - Schema (genetic algorithms)

Schemat jest szablon w informatyce stosowany w dziedzinie algorytmów genetycznych , które identyfikuje podzbiór ciągów z podobieństw w pewnych pozycjach smyczkowych. Schematy to szczególny przypadek zestawów cylindrów ; i w ten sposób tworzą przestrzeń topologiczną .

Opis

Na przykład rozważmy ciągi binarne o długości 6. Schemat 1 ** 0 * 1 opisuje zbiór wszystkich słów o długości 6 z 1 na pierwszej i szóstej pozycji oraz 0 na czwartej pozycji. * Jest symbolem wieloznacznym , co oznacza, że pozycje 2, 3 i 5 mogą mieć wartość 1 lub 0. Kolejność schematu jest definiowana jako liczba ustalonych pozycji w szablonie, podczas gdy definiująca długość to odległość między pierwszą a ostatnią określoną pozycją. Rząd 1 ** 0 * 1 to 3, 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. ${\ Displaystyle \ delta (H)}$

Długość

Długość wywoływanego schematu jest definiowana jako całkowita liczba węzłów w schemacie. jest również równa liczbie węzłów w pasujących programach . ${\ displaystyle H}$ ${\ Displaystyle N (H)}$ ${\ Displaystyle N (H)}$ ${\ displaystyle H}$

Zakłócenie

Jeśli dziecko od osobnika, który pasuje do schematu H nie sama dopasować h, schemat jest powiedziane, że zostały zakłócone .

Propagacja schematu

W obliczeniach ewolucyjnych, takich jak algorytmy genetyczne i programowanie genetyczne , rozmnażanie odnosi się do dziedziczenia cech jednego pokolenia przez następne. Na przykład schemat jest propagowany, jeśli osoby w obecnym pokoleniu pasują do niego, podobnie jak w następnym pokoleniu. Ci w następnym pokoleniu mogą być (ale nie muszą) dziećmi rodziców, którzy go dopasowali.

Operatory ekspansji i kompresji

Ostatnio schematy były badane przy użyciu teorii porządku .

Dla schematu zdefiniowano dwa podstawowe operatory: rozszerzanie i kompresję. Rozszerzenie odwzorowuje schemat na zestaw słów, które reprezentuje, podczas gdy kompresja odwzorowuje zestaw słów na schemat.

W poniższych definicjach oznacza alfabet, oznacza wszystkie słowa o długości nad alfabetem , oznacza alfabet z dodatkowym symbolem . oznacza cały schemat długości alfabetu, a także pusty schemat . ${\ displaystyle \ Sigma}$ ${\ displaystyle \ Sigma ^ {l}}$ ${\ displaystyle l}$ ${\ displaystyle \ Sigma}$ ${\ displaystyle \ Sigma _ {*}}$ ${\ displaystyle \ Sigma}$ ${\ displaystyle *}$ ${\ displaystyle \ Sigma _ {*} ^ {l}}$ ${\ displaystyle l}$ ${\ displaystyle \ Sigma _ {*}}$ ${\ displaystyle \ epsilon _ {*}}$

Dla dowolnego schematu następujący operator , zwany of , który odwzorowuje podzbiór słów w : ${\ Displaystyle s \ in \ Sigma _ {*} ^ {l}}$ ${\ displaystyle {\ uparrow} s}$ ${\ displaystyle rozwinięcie}$ ${\ displaystyle s}$ ${\ displaystyle s}$ ${\ displaystyle \ Sigma ^ {l}}$

{\ Displaystyle {\ uparrow} s: = \ {b \ in \ Sigma ^ {l} | b_ {i} = s_ {i} {\ mbox {lub}} s_ {i} = * {\ mbox {dla każdego }} i \ in \ {1, ..., l \} \}}

Gdzie indeks dolny oznacza znak na pozycji w słowie lub schemacie. Kiedy wtedy . Mówiąc prościej, jest to zestaw wszystkich słów, które można utworzyć, zamieniając symbole na symbole z . Na przykład, jeśli , a potem . ${\ displaystyle i}$ ${\ displaystyle i}$ ${\ displaystyle s = \ epsilon _ {*}}$ ${\ displaystyle {\ uparrow} s = \ emptyset}$ ${\ displaystyle {\ uparrow} s}$ ${\ displaystyle \ Sigma ^ {l}}$ ${\ displaystyle *}$ ${\ displaystyle s}$ ${\ displaystyle \ Sigma}$ ${\ displaystyle \ Sigma = \ {0,1 \}}$ ${\ displaystyle l = 3}$ ${\ Displaystyle s = 10 *}$ ${\ displaystyle {\ uparrow} s = \ {100,101 \}}$

I odwrotnie, dla dowolnego zdefiniowanego przez nas elementu , zwanego of , który jest mapowany na schemat : ${\ Displaystyle A \ subseteq \ Sigma ^ {l}}$ ${\ displaystyle {\ downarrow} {A}}$ ${\ kompresja displaystyle}$ ${\ displaystyle A}$ ${\ displaystyle A}$ ${\ Displaystyle s \ in \ Sigma _ {*} ^ {l}}$

{\ displaystyle {\ downarrow} A: = s}

gdzie jest schemat długości , tak że w pozycji symbolu w określony jest w następujący sposób: jeśli dla wszystkich następnie inaczej . Jeśli wtedy . Można myśleć o tym operatorze jako o ułożeniu wszystkich elementów w stos i jeśli wszystkie elementy w kolumnie są równoważne, symbol na tej pozycji przyjmuje tę wartość, w przeciwnym razie istnieje symbol wieloznaczny. Na przykład, niech potem .

{\ displaystyle s}

{\ displaystyle l}

{\ displaystyle i}

{\ displaystyle s}

{\ displaystyle x_ {i} = y_ {i}}

{\ Displaystyle x, y \ w A}

{\ displaystyle s_ {i} = x_ {i}}

{\ displaystyle s_ {i} = *}

{\ displaystyle A = \ emptyset}

{\ displaystyle {\ downarrow} A = \ epsilon _ {*}}

{\ displaystyle A}

{\ displaystyle s}

{\ Displaystyle A = \ {100 000 010 \}}

{\ displaystyle {\ downarrow} A = ** 0}

Schematy można zamówić częściowo . Dla każdego mówimy wtedy i tylko wtedy . Wynika z tego, że jest to częściowe uporządkowanie na zestawie schematów z zwrotności , antysymetrii i przechodniości z podzbioru relacji. Na przykład . To dlatego . ${\ Displaystyle a, b \ in \ Sigma _ {*} ^ {l}}$ ${\ displaystyle a \ leq b}$ ${\ displaystyle {\ uparrow} a \ subseteq {\ uparrow} b}$ ${\ displaystyle \ leq}$ ${\ Displaystyle \ epsilon _ {*} \ równoważnik 11 \ równoważnik 1 * \ równoważnik **}$ ${\ Displaystyle {\ uparrow} \ epsilon _ {*} \ subseteq {\ uparrow} 11 \ subseteq {\ uparrow} 1 * \ subseteq {\ uparrow} ** = \ emptyset \ subseteq \ {11 \} \ subseteq \ { 11,10 \} \ subseteq \ {11,10,01,00 \}}$

Operatory kompresji i ekspansji tworzą połączenie Galois , gdzie znajduje się dolny łącznik i górny łącznik. ${\ displaystyle \ downarrow}$ ${\ displaystyle \ uparrow}$

Schemat zakończenia i schemat kraty

Dla zbioru nazywamy proces obliczania kompresji na każdym podzbiorze A, to znaczy schematycznym uzupełnieniem , oznaczonym . ${\ Displaystyle A \ subseteq \ Sigma ^ {l}}$ ${\ displaystyle \ {{\ downarrow} X | X \ subseteq A \}}$ ${\ displaystyle A}$ ${\ displaystyle {\ mathcal {S}} (A)}$