Katedra Inżynierskich Zastosowań Informatyki WSInf.
Opracował: Prof. dr hab. Krzysztof Dems Materiały pomocnicze do wykładu
47
MECHANIZMY KRZYŻOWANIA
I.
Binarne kodowanie zmiennych w
chromosomie
•
Krzyżowanie jednopunktowe
Ch1
Ch2
x1
x2 x3 x4
1 1 0 1 0 1 0 1 |0 0 1 1 0 0 1 1 0 0 1 0 0 1 1 1
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 < p
k
to:
Ch1
Ch2
x1
x2 x3 x4
1 1 0 1 0 1 0 1
0 1 1 0
1 1 0 1 0 1 0 1 0 1 0 1
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 > p
k
to potomkowie są identyczni jak rodzice (brak
wymiany łańcuchów genów)
.
Katedra Inżynierskich Zastosowań Informatyki WSInf.
Opracował: Prof. dr hab. Krzysztof Dems Materiały pomocnicze do wykładu
48
•
Krzyżowanie dwupunktowe
Ch1
Ch2
x1
x2 x3 x4
1 1 |0 1 0 1 0 1 0 0 1 1 0 0 1 1 |0 0 1 0 0 1 1 1
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 p
1
< p
k
i p
2
<p
k
to:
Ch1
Ch2
x1
x2 x3 x4
1 1
1 1 1 1
1 1 0 1 1 0
1 1 0 1
0 0
1 0 0 1 1 1
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 p
1
< p
k
i p
2
<p
k
nie jest spełniony to łańcuchy
genów nie są wymieniane (brak krzyżowania)
.
Katedra Inżynierskich Zastosowań Informatyki WSInf.
Opracował: Prof. dr hab. Krzysztof Dems Materiały pomocnicze do wykładu
49
•
Krzyżowanie lokalne (dla każdej zmiennej)
-
Dla każdej zmiennej w łańcuchu losuje się
prawdopodopieństwo p
j
, j = 1, . . ,N.
-
Jeżeli p
j
≤
p
k
, 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 (
p
1
< p
k
, p
2
>p
k
,
p
3
< p
k
, p
4
>p
k
).
Ch1
Ch2
x1
x2 x3 x4
1 1 |0 1 0 1 0 1 0 0 1 1 0 0 1 1 |0 0 1 0 0 1 1 1
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 p
1
< p
k
, p
2
>p
k
,
p
3
< p
k
, p
4
>p
k
:
Ch1
Ch2
x1
x2 x3 x4
1 1
1 1 1 1
0 1 0 0 1 1
1 1 0 1
0 0
1 0 0 1 1 1
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
Katedra Inżynierskich Zastosowań Informatyki WSInf.
Opracował: Prof. dr hab. Krzysztof Dems Materiały pomocnicze do wykładu
50
II.
Zmiennoprzecinkowe kodowanie zmiennych w
chromosomie
•
Krzyżowanie jednopunktowe
Ch1
Ch2
x1
x2 x3 x4
x5
1 .4 6 3
2 .0 5 0
0 .3 8 9 4 .2 5 5
0 .7 4 4
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 < p
k
to:
Ch1
Ch2
x1
x2 x3 x4
x5
1 .4 6 3
2 .0 5 0
0 .3 8 9
3 .4 3 6
2 .2 9 1
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.
Katedra Inżynierskich Zastosowań Informatyki WSInf.
Opracował: Prof. dr hab. Krzysztof Dems Materiały pomocnicze do wykładu
51
•
Krzyżowanie arytmetyczne
Liniowa kombinacja dwóch chromosomów rodzicielskich.
Jeżeli p
t
< p
k
to:
Potomkowie:
⋅
+
⋅
−
=
⋅
−
+
⋅
=
+
+
t
t
t
t
t
t
a
a
a
a
ch2
ch1
ch2
ch2
ch1
ch1
)
1
(
)
1
(
1
1
a
– wybierane losowo lub zależne od wieku populacji (nr. iteracji)
np. a
= 0.645
Ch1
Ch2
x1
x2 x3 x4
x5
1 .4 6 3
2 .0 5 0
0 .3 8 9 4 .2 5 5
0 .7 4 4
4 .0 2 3
2 .8 1 9
4 .1 8 0 3 .4 3 6
2 .2 9 1
Potomkowie:
Ch1
Ch2
x1
x2 x3 x4
x5
2 .3 7 2
2 .3 2 3
1 .7 3 5 3 .6 9 4
1 .2 9 3
3 .1 1 4
2 .5 4 6
2 .8 3 4 3 .7 2 7
1 .7 4 2
Katedra Inżynierskich Zastosowań Informatyki WSInf.
Opracował: Prof. dr hab. Krzysztof Dems Materiały pomocnicze do wykładu
52
•
Lokalne krzyżowanie arytmetyczne
Liniowa kombinacja każdej zmiennej w dwóch chromosomów
rodzicielskich.
Jeżeli p
t
j
< p
k
to:
Potomkowie:
⋅
+
⋅
−
=
⋅
−
+
⋅
=
+
+
t
ch
j
t
ch
j
t
ch
j
t
ch
j
t
ch
j
t
ch
j
x
a
x
a
x
x
a
x
a
x
2
,
1
,
1
2
,
2
,
1
,
1
1
,
)
1
(
)
1
(
a
– wybierane losowo lub zalezne od wieku populacji (nr. iteracji)
np. a
= 0.379
Ch1
Ch2
x1
x2 x3 x4
x5
1 .4 6 3
2 .0 5 0
0 .3 8 9 4 .2 5 5
0 .7 4 4
4 .0 2 3
2 .8 1 9
4 .1 8 0 3 .4 3 6
2 .2 9 1
4
3
42
1
↓
zmienna
krzyżowana
Potomkowie:
Ch1
Ch2
x1
x2 x3 x4
x5
1 .4 6 3
2 .0 5 0
0 .3 8 9
3 .7 4 6
0 .7 4 4
4 .0 2 3
2 .8 1 9
4 .1 8 0
3 .9 4 5
2 .2 9 1
Katedra Inżynierskich Zastosowań Informatyki WSInf.
Opracował: Prof. dr hab. Krzysztof Dems Materiały pomocnicze do wykładu
53
MECHANIZMY MUTACJI
•
Jednorodna mutacja binarna
Bit w łańcuchu chromosomu podlega mutacji jeżeli
prawdopodobieństwo mutacji p < p
m
, gdzie p
m
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:
R
m
= p
m
p(n,t)
gdzie:
m
p
- graniczne prawdopodobieństwo mutacji jednorodnej.
P(n,t) – operator dynamiczny, określony np. w postaci:
(
)
( , )
1
nT
c t
N
a
p t n
a
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) < R
m
Katedra Inżynierskich Zastosowań Informatyki WSInf.
Opracował: Prof. dr hab. Krzysztof Dems Materiały pomocnicze do wykładu
54
•
Jednorodna mutacja zmiennoprzecinkowa
Chromosom x reprezentuje zbiór rzeczywistych wartości x
k
,
k=1, . .,N,
tzn. x = [x
1
x
2
x
3
. . . x
N
]
T
.
Mutacja przebiega następująco:
•
Losuje się liczbę k z przedziału [1,N].
•
Mutacja w chromosomie dotyczy składowej x
k
, zgodnie ze
wzorem:
x’ = [x
1
x
2
x
3
. . x
k
’ . x
N
]
T
gdzie
x
k
’ = x
k
d
+ w
k
(x
k
g
– x
k
d
)
oraz
w
k
zostało wylosowane z przedziału [0,1] zaś x
k
d
i x
k
g
są dolnym
i górnym ograniczeniem zmiennej x
k
.
Katedra Inżynierskich Zastosowań Informatyki WSInf.
Opracował: Prof. dr hab. Krzysztof Dems Materiały pomocnicze do wykładu
55
•
Niejednorodna mutacja zmiennoprzecinkowa
Chromosom x reprezentuje zbiór rzeczywistych wartości x
k
,
k=1, . .,N,
tzn. x = [x
1
x
2
x
3
. . . x
N
]
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 x
k
, zgodnie ze
wzorem:
x’ = [x
1
x
2
x
3
. . x
k
’ . x
N
]
T
gdzie
x
k
’ = x
k
+ f(t, x
k
g
– x
k
) dla l = 0
lub
x
k
’ = x
k
- f(t, x
k
– x
k
d
) dla l = 1
oraz t oznacza numer aktualnej iteracji.
Funkcja f(t,y) zawiera się w granicach [0,y], zaś prawdopo-
dobień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)