ALGORYTMY GENETYCZNE
(wykład + ćwiczenia)
Prof. dr hab. Krzysztof Dems
Treści programowe:
1. Metody rozwiązywania problemów matematycznych i
informatycznych.
2. Elementarny algorytm genetyczny: definicja algorytmu
genetycznego i jego schemat; analiza działania
algorytmu genetycznego.
3. Reprezentacja danych w algorytmie genetycznym,
kodowanie binarne i rzeczywiste.
4. Metody selekcji.
5. Operatory genetyczne.
6. Funkcja przystosowania i jej charakterystyka.
7. Reprezentacja genotypu – diploid i dominacja
8. Zastosowania algorytmów genetycznych.
Literatura:
•
T. Gwiazda, Algorytmy genetyczne, Biblioteka
Sztucznej Inteligencji, Warszawa, 1995
•
J. Cytowski, Algorytmy genetyczne – Podstawy i
zastosowania, Akademicka Oficyna Wydawnicza,
Warszawa, 1996
•
D. E. Goldberg, Algorytmy genetyczne i ich
zastosowania, WNT, Warszawa, 1998
Katedra Inżynierskich Zastosowań Informatyki WSInf.
Opracował: Prof. dr hab. Krzysztof Dems Materiały pomocnicze do wykładu
2
Treść ćwiczeń:
•
Kodowanie binarne i rzeczywiste chromosomu.
•
Przekształcenie i skalowanie funkcji przystosowania.
•
Ograniczenia zbioru rozwiązań.
•
Metody selekcji deterministycznej i stochastycznej.
•
Operatory genetyczne.
•
Analiza działania algorytmu genetycznego.
Katedra Inżynierskich Zastosowań Informatyki WSInf.
Opracował: Prof. dr hab. Krzysztof Dems Materiały pomocnicze do wykładu
3
Metody rozwiązywania problemów
matematycznych i informatycznych
Rzeczywistość
⇒
Model fizyczny
⇒
Model matematyczny
⇓
Rozwiązanie
⇐
∗
∗
max.)
lub
(min.
cyjny
optymaliza
Problem
równań
wiele
lub
Jedno
Rozwiązywanie równań można sprowadzić do rozwiązania
problemu optymalizacyjnego
.
min
)]
(
[
0
)
(
2
→
⇔
=
x
f
x
f
lub
[
]
.
min
)
,
.
.
.
,
,
(
0
)
,
.
.
.
,
,
(
2
1
2
1
,
.
.
.
,
2
,
1
2
1
→
⇔
=
∑
=
=
n
i
n
i
n
i
n
i
x
x
x
f
x
x
x
f
Przykład:
)
3
,
1
(
0
3
4
2
1
2
=
=
=
+
−
x
x
x
x
c
.
min
)
3
4
(
)
(
2
2
→
+
−
=
x
x
x
g
0
1
2
3
4
x
0
2
4
6
8
10
g
(x
)
Katedra Inżynierskich Zastosowań Informatyki WSInf.
Opracował: Prof. dr hab. Krzysztof Dems Materiały pomocnicze do wykładu
4
Metody rozwiązania:
•
Analityczne
•
Enumeracyjne
•
Losowe
Metody analityczne:
nieskończona przestrzeń poszukiwań
- (1) pośrednie
- (2) bezpośrednie
Ad. (1): poszukuje się lokalnych minimów rozwiązując układ
równań wynikający z warunku zerowania się gradientu
funkcji celu.
Ad. (2): ‘skakanie’ po wykresie funkcji w kierunku
wskazywa-nym przez lokalny gradient w celu osiągnięcia
lokalnego maximum (wierzchołka).
Wady:
•
Zakres lokalny.
•
Wymagana gładkość i
ciągłość funkcji.
Katedra Inżynierskich Zastosowań Informatyki WSInf.
Opracował: Prof. dr hab. Krzysztof Dems Materiały pomocnicze do wykładu
5
Metody enumeracyjne:
skończona przestrzeń poszukiwań
Oblicza się kolejno wartości funkcji celu przeglądając
wszyst-
kie możliwe
punkty przestrzeni.
Wady:
•
Metoda nieefektywna wraz ze wzrostem rozmiaru
problemu.
Niech będzie danych n niewiadomych, z których każda może
przyjąć m wartości:
Ilość możliwych rozwiązań:
n
m
Np.:
1. n = 5 , m =10
⇒
5
10
=
n
m
= 100 tys. rozwią
zań.
1000 rozwiązań jest sprawdzanych w ciągu 1 sekundy
⇒
czas
znalezienia rozwiązania:
100 sek
.
2. n = 20 , m =10
⇒
20
10
=
n
m
=
8
10
bilionów rozwiązań.
1000 rozwiązań jest sprawdzanych w ciągu 1 sekundy
⇒
czas
znalezienia rozwiązania:
3,17x10
9
lat
.
Katedra Inżynierskich Zastosowań Informatyki WSInf.
Opracował: Prof. dr hab. Krzysztof Dems Materiały pomocnicze do wykładu
6
Metody losowe:
skończona przestrzeń poszukiwań
Oblicza się kolejno wartości funkcji celu przeglądając
losowo
wybrane
punkty przestrzeni ⇒ czas znalezienia rozwiązania
może być istotnie skrócony w porównaniu z metodami
enumeracyjnymi
.
Cechy:
•
Ocena jak największej liczby rozwiązań w różnych
obszarach przestrzeni.
•
Dokładne zbadanie najbardziej obiecujących obszarów.
Rodzaje:
•
Metody czysto losowe – metoda Monte Carlo.
•
Algorytmy genetyczne
– wybór losowy jest traktowany
jako
„przewodnik”
w
prowadzeniu
wysoce
ukierunkowanego poszukiwania w przestrzeni rozwiązań.
Efektywność metod:
Katedra Inżynierskich Zastosowań Informatyki WSInf.
Opracował: Prof. dr hab. Krzysztof Dems Materiały pomocnicze do wykładu
7
ALGORYTMY GENETYCZNE
(AG)
Teoria AG powstała w oparciu o analogie do
procesów obserwowanych w ewolucji naturalnej.
Przyroda ożywiona:
•
W jądrach komórkowych żywych organizmów znajdują
się
łańcuchy
genów
(chromosomy)
w
których
zakodowana jest informacja o strukturze danego
organizmu.
•
W wyniku krzyżowania się organizmów, dobieranych w
wyniku selekcji, powstaje nowe potomstwo, któremu
rodzice przekazują geny tworząc nową strukturę
chromosomu – a więc informacje o strukturze
organizmu który powstaje (proces reprodukcji).
•
Pojawiający się rzadko proces mutacji zmienia łańcuch
genów, a więc i strukturę organizmu (proces
reprodukcji
).
•
Naturalna
selekcja
jest
pomostem
łączącym
chromosomy
i
‘jakość’
organizmów
przez
nie
‘opisywanych’.
•
Reprodukcja jest momentem w którym następuje
ewolucja organizmu.
•
Ewolucja nie posiada pamięci – wiedza o metodzie
stworzenia nowego organizmu zdolnego do wygrania
walki ‘o przetrwanie’ jest zawarta w genach
chromosomów przez nią wytwarzanych.
Katedra Inżynierskich Zastosowań Informatyki WSInf.
Opracował: Prof. dr hab. Krzysztof Dems Materiały pomocnicze do wykładu
8
Algorytmy genetyczne:
•
Początki zastosowań datują się od roku 1975.
•
Za ojca AG jest uważany J. Holland, który postawił tezę,
ż
e poprzez odpowiednie zaimplementowanie procesów
ewolucyjnych występujących w przyrodzie ożywionej w
formie algorytmu komputerowego otrzymamy metodę
rozwiązywania złożonych problemów tą samą drogą jaką
kroczy natura – drogą ewolucji.
(J. Holland, „Adaptation In natural and artifical
systems”, University of Michigan Press, 1975
)
⇓
Klasyczny model algorytmu genetycznego