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)