Katedra Inżynierskich Zastosowań Informatyki WSInf.
Opracował: Prof. dr hab. Krzysztof Dems Materiały pomocnicze do wykładu

25

STRATEGIE EWOLUCYJNE

W

ALGORYTMACH GENETYCZNYCH

Schemat prostego algorytmu genetycznego

P

t

- populacja bazowa

O

t

- populacja potomna

T

t

- populacja tymczasowa

Katedra Inżynierskich Zastosowań Informatyki WSInf.
Opracował: Prof. dr hab. Krzysztof Dems Materiały pomocnicze do wykładu

26

Przykładowy problem załadunku

Należy podjąć decyzje o załadowaniu n przedmiotów – z
których każdy ma określoną wagę w

i

i przynosi korzyść p

i

– w

taki sposób aby zmaksymalizować korzyść całkowitą, nie
przekraczając dopuszczalnej wagi całkowitej.



Zmienne decycyjne:
Chromosom x o genach x

i

równych 1 (i-ty

przedmiot załadowany) lub 0 (i-tego przedmiotu
brak).

Funkcja celu:

∑

=

=

n

i

i

i

x

p

f

1

)

(x

Ograniczenia:

∑

=

≤

−

n

i

i

i

W

x

w

1

0

Funkcja przystosowania(met. zewnętrznej funkcji kary):

n

i

w

p

K

W

x

w

K

x

p

i

i

n

i

i

i

n

i

i

i

.,

.

.

,

1

min

max

)

0

,

.(

max

)

(

1

1

=

=

−

−

=

Φ

∑

∑

=

=

x

Katedra Inżynierskich Zastosowań Informatyki WSInf.
Opracował: Prof. dr hab. Krzysztof Dems Materiały pomocnicze do wykładu

27

Prawdopodobieństwo reprodukcji (selekcji)
chromosomu:

Metoda skalowania funkcji przystosowania

min

min

)

(

)

(

)

(

Φ

−

Φ

Φ

−

Φ

=

∑

∈

t

r

p

P

x

x

x

x

Warunki eksperymentu:

•

n = 50

•

liczność populacji 100

•

prawdopodobieństwo krzyżowania = 0.7

•

prawdopodobieństwo mutacji = 0.02

•

kryterium stopu: przez 100 kolejnych iteracji nie

następuje poprawa rozwiązania.

Katedra Inżynierskich Zastosowań Informatyki WSInf.
Opracował: Prof. dr hab. Krzysztof Dems Materiały pomocnicze do wykładu

28

Jednorazowe uruchomienie algorytmu

Katedra Inżynierskich Zastosowań Informatyki WSInf.
Opracował: Prof. dr hab. Krzysztof Dems Materiały pomocnicze do wykładu

29

Wielokrotne uruchomienie algorytmu

Katedra Inżynierskich Zastosowań Informatyki WSInf.
Opracował: Prof. dr hab. Krzysztof Dems Materiały pomocnicze do wykładu

30

Strategia (1+1)

Reguła 1/5 sukcesów:

Jeżeli przez k iteracji:

1.

Więcej niż 1/5 mutacji jest zakończone sukcesem

to zasięg mutacji się zwiększa.

2.

Dokładnie 1/5 mutacji jest zakończone sukcesem

to zasięg mutacji się nie zmienia.

3.

Mniej niż 1/5 mutacji jest zakończone sukcesem

to zasięg mutacji się zmniejsza.

Katedra Inżynierskich Zastosowań Informatyki WSInf.
Opracował: Prof. dr hab. Krzysztof Dems Materiały pomocnicze do wykładu

31

Strategia

(

)

µ λ

+

µ

- liczność populacji bazowej

λ

- licznośc populacji potomnej

Proces reprodukcji:

•

Losowanie ( ze zwracaniem) chromosomu z populacji
bazowej i umieszczanie jego kopii w populacji
pomocniczej.

•

Następna populacja bazowa jest tworzona na podstawie
poprzedniej populacji bazowej i populacji potomnej.

Katedra Inżynierskich Zastosowań Informatyki WSInf.
Opracował: Prof. dr hab. Krzysztof Dems Materiały pomocnicze do wykładu

32

Strategia

( , )

µ λ

µ

- liczność populacji bazowej

λ

- licznośc populacji potomnej

Proces reprodukcji: losowanie ( ze zwracaniem) chromosomu
z populacji bazowej i umieszczanie jego kopii w populacji
pomocniczej.

Następna populacja bazowa jest tworzona wyłącznie na
podstawie populacji potomnej.