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