Algorytm Genetyczny

i jego zastosowania

Zbigniew Doma ski
Instytut Matematyki i Informatyki, Politechnika Cz stochowska

Ewolucja w naturze

polega na tym, e

osobnik dopasowany

lepiej

do otaczaj cego go rodowiska

ma wi ksze szanse

prze ycia

ni ten, którego cechy mniej odpowiadaj warunkom

w jakich yje.

Algorytm genetyczny

to statystyczna

metoda poszukiwania

najlepszych rozwi za

po ród ogromnego zbioru mo liwych

rozwi za

danego problemu

.

Algorytm genetyczny jako metoda poszukiwania globalnego ekstremum

W wielu zastosowaniach jedyn

pewna metod

znalezienia optymalnego

rozwi zania jest przeszukanie całej przestrzeni parametrycznej

odpowiadaj cej problemowi. Przestrze ta

cz sto

jest tak du a, e

nie jest to praktycznie wykonalne

.

Wej cie

Wyj cie

Nawigacja robota

kod kroku w : tył = 00, lewo = 01, przód = 11, prawo = 10

Sekwencja kroków = Chromosom

kod sekwencji 100 kroków = Chromosom ma długo 200.

DOSTOSOWANIE

- miara poprawno ci rozwi zania - dla danej

sekwencji kroków -

CHROMOSOMU

- to dległo robota od

wyj cia po zadanej liczbie kroków.

Elementy algorytmu genetycznego

0 1 1 0 1 1

0 0 1 0 1

1

1 0 1 1 0 0

0 1 1 0 0 1

0 0 1 1 0 0

1 1 1 0 0 0

0 1 1

1

0 1 1

0 1 1

0 0 1

0 1 1 0 0

0 1 1 0 0 1

0 1 1 0 0 1

0 1 1 0 1 1

1 1 1 0 0 1

0 0 1 1 0 0

0 1 1 0 1 0

11

7

9

8

7

7

Dostosowanie

Se

le

kc

ja

0 1 1 0 1 1

1 0 1 1 0 0

0 0 1 1 0 0

K

rz

y

o

w

an

ie

M

ut

ac

ja

Selekcja (kółko ruletki)

Przykład zastosowania: upakowanie kontenera.

Elementy do upakowania

Warto

2

4 1 6 3

3

Kandydat upakowania Chromosom Dostosowanie

A

C

F

D

B

E

A

A

A

A

B

B

B

B

C

C

C

C

C

C

B

B

A

D

D

D

D

D

D

E

E

E

E

E

F

F

F

F

F

F

F

1 1 1 0 0 1

1 1 0 0 1

0

1 0 1 1 0 0

1 0 1 0 1 1

0 1 1 1 0 1

0 1 1 0 1 1

0 0 1 1 1 1

0 1 0 1 1 0

0 1 0 1 0 1

1 0 0 1 0 1

10

9

9

9

14

11

13

13

13

11

Rozmiar kontenera

0 1 1 0 0 1

0 1 1 0 1 1

1 1 1 0 0 1

0 0 1 1 0 0

0 1 1 1 0 0

1 0 1 0 1 1

0 1 1 0 1 1

0 0 1 0 1

1
1 0 1 1 0 0

0 1 1 0 0 1

0 0 1 1 0 0

1 1 1 0 0 0

0 1 1

1

0 1 1

0 1 1 0 0 1

0 1 1 0 1 1

1 1 1 0 0 1

0 0 1 1 0 0

1 0 1 0 1 1

0 1 1 1 0 0

0 1 1

0 0 1

0 1 1 0 0

0 1 1 0 0 1

0 1 1 0 1 1

1 0 1 1 0 0

11

7

9

8

7

7

Chromosom

Dostosowanie

8

11

11

10

7

9

0 1 1 0 1 1

0 1 1 0 1 1

1 1 1 0 0 1

0 1 1 1 0 0

0 1 1 1 0 0

1 0 1 0 1 1

0 1 1 0 1 1

1 0 1 0 1 1

1 1 1 0 0 0

0 1 1 1 0 1

0 1 1 1 0 0

0 1 1 0 1 1

Krzy owanie

11

11

11

14

9

7

49

+

56

+

+

63

Modelowanie systemów ekonomicznych, biologicznych, fizycznych

Automatyczne programowanie

Maszyny samoucz cze

Optymalizacja w projektowaniu in ynierskim

Zarz dzanie du ymi sieciami

Tworzenie strategii

Przykłady zatosowa Algorytmu Genetycznego

Problem

Modified Problem

Genetic Algorithm

Genetic algorithm approach

Genetic algorithm approach

Problem

Evolution Program

Genetic Algorithm

Genetic algorithm approach

Genetic algorithm approach