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
