Katedra Inżynierskich Zastosowań Informatyki WSInf.
Opracował: Prof. dr hab. Krzysztof Dems Materiały pomocnicze do wykładu MECHANIZMY KRZYŻOWANIA
I. Binarne kodowanie zmiennych w
chromosomie
• Krzyżowanie jednopunktowe
x1
x2 x3 x4
Ch1
1 1 0 1 0 1 0 1 |0 0 1 1 0 0 1 1 0 0 1 0 0 1 1 1
Ch2
0 1 1 1 1 1 1 1 |0 1 1 0 1 1 0 1 0 1 0 1 0 1 0 1
↓
losowo wybrany punkt krzyżowania ch1:
53
19
12
39
ch2:
31
54
53
21
Potomkowie: jeżeli p < pk to:
x1
x2 x3 x4
Ch1
1 1 0 1 0 1 0 1 0 1 1 0 1 1 0 1 0 1 0 1 0 1 0 1
Ch2
0 1 1 1 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 0 0 1 1 1
ch1:
53
22
53
21
ch2:
31
51
12
39
ale jeżeli p > pk to potomkowie są identyczni jak rodzice (brak wymiany łańcuchów genów).
47
Katedra Inżynierskich Zastosowań Informatyki WSInf.
Opracował: Prof. dr hab. Krzysztof Dems Materiały pomocnicze do wykładu
• Krzyżowanie dwupunktowe
x1
x2 x3 x4
Ch1
1 1 |0 1 0 1 0 1 0 0 1 1 0 0 1 1 |0 0 1 0 0 1 1 1
Ch2
0 1 |1 1 1 1 1 1 0 1 1 0 1 1 0 1 |0 1 0 1 0 1 0 1
↓ ↓
losowy I punkt losowy II punkt
krzyżowania krzyżowania
ch1:
53
19
12
39
ch2:
31
54
53
21
Potomkowie: jeżeli p1 < pk i p2 <pk to: x1
x2 x3 x4
Ch1
1 1 1 1 1 1 1 1 0 1 1 0 1 1 0 1 0 0 1 0 0 1 1 1
Ch2
0 1 0 1 0 1 0 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1
ch1:
63
54
52
39
ch2:
21
19
13
21
Jeżeli warunek jeżeli p1 < pk i p2 <pk nie jest spełniony to łańcuchy genów nie są wymieniane (brak krzyżowania).
48
Katedra Inżynierskich Zastosowań Informatyki WSInf.
Opracował: Prof. dr hab. Krzysztof Dems Materiały pomocnicze do wykładu
• Krzyżowanie lokalne (dla każdej zmiennej)
- Dla każdej zmiennej w łańcuchu losuje się
prawdopodopieństwo pj, j = 1, . . , N.
- Jeżeli pj ≤ pk, to w danej zmiennej zachodzi krzyżowanie w losowo wybranym punkcie, w
przeciwnym przypadku krzyżowanie nie zachodzi.
Np. wylosowano krzyżowanie dla zmiennej x1 i x3 w łańcuchu 4 zmiennych ( p1 < pk , p2 >pk , p3 < pk , p4 >pk).
x1
x2 x3 x4
Ch1
1 1 |0 1 0 1 0 1 0 0 1 1 0 0 1 1 |0 0 1 0 0 1 1 1
Ch2
0 1 |1 1 1 1 1 1 0 1 1 0 1 1 0 1 |0 1 0 1 0 1 0 1
↓ ↓
losowy I punkt losowy II punkt
krzyżowania krzyżowania
ch1:
53
19
12
39
ch2:
31
54
53
21
Potomkowie: dla p1 < pk , p2 >pk , p3 < pk , p4 >pk : x1
x2 x3 x4
Ch1
1 1 1 1 1 1 0 1 0 0 1 1 1 1 0 1 0 0 1 0 0 1 1 1
Ch2
0 1 0 1 0 1 1 1 0 1 1 0 0 0 1 1 0 1 0 1 0 1 0 1
ch1:
63
19
52
39
ch2:
21
54
13
21
49
Katedra Inżynierskich Zastosowań Informatyki WSInf.
Opracował: Prof. dr hab. Krzysztof Dems Materiały pomocnicze do wykładu II. Zmiennoprzecinkowe kodowanie zmiennych w
chromosomie
• Krzyżowanie jednopunktowe
x1
x2 x3 x4
x5
Ch1
1 .4 6 3
2 .0 5 0
0 .3 8 9 4 .2 5 5
0 .7 4 4
Ch2
4 .0 2 3
2 .8 1 9
4 .1 8 0 3 .4 3 6
2 .2 9 1
↓
losowo wybrany punkt krzyżowania
Potomkowie: jeżeli p < pk to:
x1
x2 x3 x4
x5
Ch1
1 .4 6 3
2 .0 5 0
0 .3 8 9 3 .4 3 6
2 .2 9 1
Ch2
4 .0 2 3
2 .8 1 9
4 .1 8 0 4 .2 5 5
0 .7 4 4
• Krzyżowanie dwu- i wielopunktowe
Jest realizowane podobnie.
50
Katedra Inżynierskich Zastosowań Informatyki WSInf.
Opracował: Prof. dr hab. Krzysztof Dems Materiały pomocnicze do wykładu
• Krzyżowanie arytmetyczne
Liniowa kombinacja dwóch chromosomów rodzicielskich.
Jeżeli pt < pk to:
t +
ch1 1 = a ⋅
t
ch1 + 1
( − a) ⋅
t
ch2
Potomkowie:
t +
ch2 1 = 1
( − a) ⋅
t
ch1 + a ⋅
t
ch2
a – wybierane losowo lub zależne od wieku populacji (nr. iteracji) np. a = 0.645
x1
x2 x3 x4
x5
Ch1
1 .4 6 3
2 .0 5 0
0 .3 8 9 4 .2 5 5
0 .7 4 4
Ch2
4 .0 2 3
2 .8 1 9
4 .1 8 0 3 .4 3 6
2 .2 9 1
Potomkowie:
x1
x2 x3 x4
x5
Ch1
2 .3 7 2
2 .3 2 3
1 .7 3 5 3 .6 9 4
1 .2 9 3
Ch2
3 .1 1 4
2 .5 4 6
2 .8 3 4 3 .7 2 7
1 .7 4 2
51
Katedra Inżynierskich Zastosowań Informatyki WSInf.
Opracował: Prof. dr hab. Krzysztof Dems Materiały pomocnicze do wykładu
• Lokalne krzyżowanie arytmetyczne
Liniowa kombinacja każdej zmiennej w dwóch chromosomów rodzicielskich.
Jeżeli ptj < pk to:
t+
x 1
j, ch 1 = a ⋅ t
x j, ch 1 + 1
( − a) ⋅ t
x
Potomkowie:
j, ch 2
t+1
t
t
x j, ch 2 = 1
( − a) ⋅ x j, ch 1 + a ⋅ x j, ch 2
a – wybierane losowo lub zalezne od wieku populacji (nr. iteracji) np. a = 0.379
x1
x2 x3 x4
x5
Ch1
1 .4 6 3
2 .0 5 0
0 .3 8 9 4 .2 5 5
0 .7 4 4
Ch2
4 .0 2 3
2 .8 1 9
4 .1 8 0 3 .4 3 6
2 .2 9 1
4
1
4
2 3
↓
zmienna
krzyżowana
Potomkowie:
x1
x2 x3 x4
x5
Ch1
1 .4 6 3
2 .0 5 0
0 .3 8 9 3 .7 4 6
0 .7 4 4
Ch2
4 .0 2 3
2 .8 1 9
4 .1 8 0 3 .9 4 5
2 .2 9 1
52
Katedra Inżynierskich Zastosowań Informatyki WSInf.
Opracował: Prof. dr hab. Krzysztof Dems Materiały pomocnicze do wykładu MECHANIZMY MUTACJI
• Jednorodna mutacja binarna
Bit w łańcuchu chromosomu podlega mutacji jeżeli
prawdopodobieństwo mutacji p < pm, gdzie pm jest granicznym prawdopodobieństwem mutacji.
• Niejednorodna mutacja binarna
Stosowana w przypadku, gdy w chromosomie zapisany jest ciąg zmiennych decyzyjnych.
Graniczne prawdopodobieństwo mutacji n-tego bitu w iteracji t: Rm = pm p(n,t)
gdzie:
p - graniczne prawdopodobieństwo mutacji jednorodnej.
m
P(n,t) – operator dynamiczny, określony np. w postaci:
a
p( t, n) = a −
nT
−
c ( t −
)
1
N
+ b ⋅ e
a,b,c – parametry
n – pozycja bitu w zmiennej w chromosomie N – liczba bitów na zmienna w chromosomie t – numer iteracji
T – max. liczba iteracji.
Bit podlega mutacji jeżeli prawdopodobieństwo mutacji p(n) < Rm 53
Katedra Inżynierskich Zastosowań Informatyki WSInf.
Opracował: Prof. dr hab. Krzysztof Dems Materiały pomocnicze do wykładu
• Jednorodna mutacja zmiennoprzecinkowa
Chromosom x reprezentuje zbiór rzeczywistych wartości x k, k=1, . .,N, tzn. x = [x1 x2 x3 . . . xN]T.
Mutacja przebiega następująco:
• Losuje się liczbę k z przedziału [1,N].
• Mutacja w chromosomie dotyczy składowej xk, zgodnie ze wzorem:
x’ = [x1 x2 x3 . . xk’ . xN]T
gdzie
x
d
g
d
k’ = xk + wk(xk – xk )
oraz
w
d
g
k zostało wylosowane z przedziału [0,1] zaś xk i xk są dolnym i górnym ograniczeniem zmiennej xk.
54
Katedra Inżynierskich Zastosowań Informatyki WSInf.
Opracował: Prof. dr hab. Krzysztof Dems Materiały pomocnicze do wykładu
• Niejednorodna mutacja zmiennoprzecinkowa
Chromosom x reprezentuje zbiór rzeczywistych wartości x k, k=1, . .,N, tzn. x = [x1 x2 x3 . . . xN]T.
Mutacja przebiega następująco:
• Losuje się liczbę k z przedziału [1,N], oraz liczbę l przybierającą wartości 0 lub 1.
• Mutacja w chromosomie dotyczy składowej xk, zgodnie ze wzorem:
x’ = [x1 x2 x3 . . xk’ . xN]T
gdzie
x
g
k’ = xk + f( t, xk – xk) dla l = 0
lub
x
d
k’ = xk - f( t, xk – xk ) dla l = 1
oraz t oznacza numer aktualnej iteracji.
Funkcja f( t,y) zawiera się w granicach [0,y], zaś prawdopodobieństwo, że osiągnie wartość bliską zeru wzrasta wraz ze wzrostem liczby iteracji.
Funkcja ta często ma postać:
f( t,y) = y r (1- t/ T) b gdzie
r – liczba losowa z przedziału [0,1],
T – maksymalna liczba iteracji,
b – parametr określający stopień zależności od numeru iteracji (np. b = 2)
55