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.