algorytmygenetyczne » informaja o konkursie | test umiejętnoci | kontakt  
Zmiana rozmiaru czcionki  Powiększ czcionkę Zmniejsz czcionkę MathML ON

Schematy.

Schemat H - wzorzec opisujący podzbiór ciągów podobnych ze względu na ustalone pozycje.

Alfabet schematów:
$ V^{+} = \{0, 1, \ast \}$
Alfabet składający się z k symboli i ciągów l elementowych posiada kl ciągów i (k+1)l schematów.
Rząd schematów - liczba ustalonych pozycji we wzorcu: o(H) $ o(011\ast 1 \ast \ast ) = 4$
$ o(0 \ast \ast \ast \ast \ast ) = 1$
Rozpiętość schematu - odległość między dwiema skrajnymi ustalonymi pozycjami δ(H)
$\delta(011\ast 1 \ast \ast ) = 5 - 1 = 4$
Schematy o małej rozpiętości mają większe szanse na przeżycie.

Rozmiar schematu - rozpiętość schematu + 1: r(H)=δ(H)+1

m=m(H,t)

m - liczba reprezentantów schematu, jak dużo osobników populacji pasuje do schematu populacji.

Prawdopodobieństwo, że i-ty osobnik rozmnoży się:
$ p_i=\frac{f_i}{\sum f_i}$

Wartość oczekiwana liczby reprezentantów schematu H w następnym pokoleniu:
$ E[m(H,t+1)]=m(H,t)\cdot n \cdot\frac{f(H)}{\sum f_i}$

Średni współczynnik dostosowania całej populacji:
$\overline f=\frac{\sum f_i}{n}$

Łącząc dwa powyższe wzory otrzymujemy:
$ m(H,t+1)=m(H,t)\cdot \frac{f(H)}{\overline f} $

Wynika z tego wniosek, że liczebność reprezentacji danego schematu w następnym pokoleniu będzie się zmieniała proporcjonalnie do stosunku średniego przystosowania schematu i średniego przystosowania całej populkacji.

Schematy o mniejszej średniej funkcji dostosowania w następnym pokoleniu będą miały mniejszą liczbę reprezentantów.

Schematy o małej rozpiętości mają większe szanse na przeżycie.

Prawdopodobieństwo przeżycia schematu:
$ p_s\geq 1-\frac{\delta(H)}{l-1}$

Maksymalne prawdopodobieństwo zniszczenia schematu:
$ p_d=\frac{\delta(H)}{l-1}$

Prawdopodobieństwo, że osobnik przeżyje w wyniku krzyżowania:
$ m(H,t+1)\geq m(H,t)\cdot \frac{f(H)}{\overline f}\cdot [1-p_c\frac{\delta(H)}{l-1}] $

Prawdopodobieństwo mutacji: pm

Aby schemat nie uległ zniszczeniu w wyniku mutacji:
(1-pm)o(H)

Liczba reprezentantów schematu H w pokoleniu t+1 z uwzględnieniem start wynikających z mutacji i krzyżowania:
$ m(H,t+1) \geq m(H,t)\cdot \frac{f(H)}{\overline f}\cdot [1-p_c\frac{\delta(H)}{l-1}-o(H)\cdot p_m]$