•   Wprowadzenie
  • Tradycyjna optymalizacja
  • Ewolucja biologiczna
  • Ogólna koncepcja AG
  • Terminologia
•   Podstawy teoretyczne
  • Schematy
  • Twierdzenie o schematach
  • Geometryczna interpretacja
  • Hipoteza cegiełki
•   Testowanie AG
  • Kryteria oceny
  • Badania de Jonga
•   Realizacje AG
  • Selekcja
  • Kodowanie
  • Operatory genetyczne
  • Skalowanie funkcji przyst.
•   Techniki specjalne
  • Przeszukiwanie lokalne
  • Limitowanie czasu zycia
  • Selekcja sterowana czasem
  • Algorytmy niszowe
•   Metody zaawansowane
  • Aparat diploidalny
  • Operatory specjalne
  • Specjalne kodowanie
  • Specjacja

Sprawdź swoją wiedzę.

W tym dziale zamieszczono kilka prostych zadań z ich rozwiązaniami

Zad.1

Obliczyć dolne ograniczenie prawdopodobieństwa przeżycia poniższych schematów przy krzyżowaniu:
H₁ = 1*********1
H₂ = ****10*****
H₃ = 11*********
H₄ = ***111*****
H₅ = ****1*0****
H₆ = **1***1*0*
Zakładamy, że ciągi są 11-pozycyjne, a punkt krzyżowania wybierany jest losowo.

pokaż rozwiązanie

Rozwiązanie zadania 1
Dolne ograniczenie prawdopodobieństwa przeżycia schematów wynosi:
$ p_s = 1-\frac{\delta(H)}{l-1}$
Zatem wyniki dla kolejnych schematów:
H₁: p_s=0
H₂: p_s=0.9
H₃: p_s=0.9
H₄: p_s=0.8
H₅: p_s=0.8
H₆: p_s=0.6

Zad.2

Niech x₁=7, x₂=8, x₃=13 reprezentują trzy rozwiązania w przestrzeni fenotypów. X₁, X₂ i X₃ będą zaś osobnikami w przestrzeni genotypów kodowanych binarnie, natomiast X₁^*, X₂^*,X₃^* będą osonikami w przestrzeni genotypów kodowanych według kodu Graya. Obliczyć i uszeregować odległościkażdej pary rozwiązań w każdej z przestrzeni ( p_m=0.2). Zastanowić się jaknametrykę przestrzeni genotypów wpływa wartość p_m ?
pokaż rozwiązanie

Rozwiązanie zadania 2
Najpierw zapiszmy zakodowane postacie osobników w przestrzeni genotypów:
X₁ = 0111
X₂ = 1000
X₃ = 1101
X₁^* = 0100
X₂^* = 1100
X₃^* = 1011
Obliczamy metrykę w przestrzeni fenotypu:
|x₁ - x₂| = 1 i |x₂ - x₃| = 5 i |x₃ - x₁| = 6
Odległości par rozwiązań przedstawione są za pomocą wzoru:
$\mid X - Y \mid =1-\frac{P_{\chi}(y)}{P_{\chi}(x)}=1-\frac{p_m^k(1-p_m)^l}{(1-p_m)^{k+l}}$
Otrzymane wyniki na podstawie powyższego wzoru:
|X₁ - X₂| = 255/256
|X₂ - X₃| = 240/256
|X₁ - X₃| = 240/256
|X₁^* - X₂^*| = 3/4
|X₂^* - X₃^*| = 252/256
|X₁^* - X₃^*| = 255/256

Zad.3

Rozważmy trzy ciągi kodowe: A₁=11101111, A₂=00010100, A₃=01000011 oraz sześć schematów H₁=1******* , H₂=0*******, H₃=******11, H₄=**0**00*, H₅=1******1, H₆=1110**1*. Które schematy pasują do których ciągów? Podaj rząd, rozpiętość i rozmiar każdego z tych schematów. Oszacuj prawdopodobieństwo przeżycia przy mutacji każdego z tych schematów dla prawdopodobieństwa mutacji p_m=0,001. Oszacuj prawdopodobieństwo przeżycia schematów przy krzyżowaniu dla prawdopodobieństwa krzyżowania P_c=0,85.
pokaż rozwiązanie

Rozwiązanie zadania 3
Schemat H₁ pasuje do ciągu A₁.
Schemat H₂ pasuje do ciągu A₂, A₃.
Schemat H₃ pasuje do ciągu A₁, A₃.
Schemat H₅ pasuje do ciągu A₁.
Schemat H₆ pasuje do ciągu A₁.
δ(H₁)=0 r(H₁)=1 p_s(H₁)=1 p_m(H₁)=0,999
δ(H₂)=0 r(H₂)=1 p_s(H₂)=1 p_m(H₂)=0,999
δ(H₃)=1 r(H₃)=2 p_s(H₃)=0,88 p_m(H₃)=0,998
δ(H₄)=4 r(H₄)=5 p_s(H₄)=0,52 p_m(H₄)=0,995
δ(H₅)=7 r(H₅)=8 p_s(H₅)=0,15 p_m(H₅)=0,992
δ(H₆)=6 r(H₆)=7 p_s(H₆)=0,27 p_m(H₆)=0,993

Zad.4

Roważmy funkcję dostosowania f(x) określoną w przestrzeni ciągów czterobitowych, której wartość równa jest liczbie jedynek w kodzie chromosomu. Poniższa tabela zawiera trzy pokolenia powstałe w AG:

Obliczyć zbieżność on-line i off-line po każdym pokoleniu.

pokaż rozwiązanie

Rozwiązanie zadania 4

Zad.5

Dwa ciągi kodowe: A₁=10011011 i A₂=00110101 podlegają krzyżowaniu ze sobą, przy czym punkt krzyżowania wybierany jest losowo. Oblicz prawdopodobieństwo przeżycia poniższych schematów w tym procesie: H₁=10******, H₂=**0***1*, H₃=**0****1,H₄=***1***1, H₅=**11**11.
pokaż rozwiązanie

Rozwiązanie zadania 5
P(H₁)=1
P(H₂)=3/7
P(H₃)=1
P(H₄)=1
P(H₅)=4/7

Głosuj na nas!

"Niniejsza strona bierze udział w konkursie "Notatki w internecie" organizowanym przez JM rektora AGH. Jeśli podoba Ci się nasza praca
» zagłosuj

 notatkikonkurs

 sprawdźwiedzę

 Bibliografialinki

 kontakt