Metody heurystyczne
Kierunek:
Mechanika i Budowa Maszyn
Specjalność: Mechanika komputerowa (MB4)
Rodzaj studiów i semestr: II st. sem. II,
Punkty ECTS: 3
Prowadzący:
dr hab. inż. Witold Beluch
Opis przedmiotu
Jedną z najważniejszych metod
informatyki jest przeszukiwanie, często utożsamiane ze sztuczną
inteligencję (Artificial intelligence, AI). Często zadania
praktyczne można traktować jako konkretne przypadki ogólnego zadania
przeszukiwania, w szczególności wiele zagadnień technicznych,
ekonomicznych, logistycznych i innych problemów praktycznych ma postać
zadań optymalizacji. Optymalizacja w sensie dokładnym jest poszukiwaniem
najlepszego ze wszystkich możliwych rozwiązań (tzw. optimum globalnego).
Częstokroć rzeczywiste zagadnienia są zbyt skomplikowane, by można je
opisać tradycyjnym modelem matematycznym. Często też wystarczające jest
podanie tzw. rozwiązania quasi-optymalnego, co może być uzasadnione np.
ograniczeniami czasowymi.
W wielu praktycznych problemach, gdy
np. nie jest znana analityczna postać funkcji celu, nie wiadomo
również, jak znalezione rozwiązanie bliskie jest rozwiązaniu
optymalnemu. Istotnym zagadnieniem jest także efektywność algorytmu
poszukiwania najlepszego rozwiązania, mierzona czasem wykonania i
wielkością zajętej pamięci. Dla wielu rodzajów zadań optymalizacji, jak
np. zadanie komiwojażera, nie istnieją efektywne algorytmy
optymalizacji. W związku z
powyższym wiele współczesnych zagadnień optymalizacji rozwiązywanych
jest metodami zaliczanymi do metod heurystycznych czy też metaheurystyk.
Optymalne rozwiązanie zadania
komiwojażera dla 24978 miast w Szwecji (2004r)
(http://www.tsp.gatech.edu//sweden/index.html)
Heurystyka
(z greckiego: heuresis – odnaleźć, odkryć) to metoda znajdowania
rozwiązań („niepełny algorytm”) która pozwala na znalezienie w
akceptowalnym czasie przynajmniej „dostatecznie dobrego” przybliżonego
rozwiązania problemu. Metod tych używa się np. wtedy, gdy pełny algorytm
jest nieznany lub zbyt kosztowny obliczeniowo.
Z kolei metaheurystyka
to ogólny algorytm (czyli heurystyka) do rozwiązywania problemów
obliczeniowych, zazwyczaj optymalizacyjnych. Określenie oznacza
„heurystykę wyższego poziomu” co wynika z faktu, że algorytmy tego typu
nie rozwiązują bezpośrednio żadnego problemu, a jedynie podają sposób na
utworzenie odpowiedniego algorytmu. Metody te często są inspirowane
mechanizmami biologicznymi czy fizycznymi. Zaliczyć do nich można np.:
algorytmy ewolucyjne, sztuczne sieci neuronowe, systemy rozmyte,
algorytmy immunologiczne czy systemy mrówkowe.
Program przedmiotu
-
Wykład: 9 godzin w semestrze
-
Laboratorium: 9 godzin w semestrze
Warunki zaliczenia
1. Zaliczenie na
ocenę pozytywną ćwiczeń (warunki podaje prowadzący na zajęciach)
2. Egzamin z
wykładu.
OCENA
KOŃCOWA: O=0.65E+0.35C
E - ocena z
egzaminu (musi być pozytywna)
C - ocena z ćwiczeń
Tematyka wykładów
-
Wprowadzenie do metod przeszukiwania. Zagadnienia
„łatwe” i „trudne”. Złożoność algorytmu. Przykładowe
problemy dla metod heurystycznych (problem N hetmanów,
kolorowanie mapy itp.).
-
Strategie ślepe (przeszukiwanie wszerz, przeszukiwanie
wgłąb, strategia jednolitego kosztu).
-
Metody heurystyczne. Funkcja heurystyczna. Metoda
wzrostu, poszukiwanie zachłanne, strategia A*,
symulowane wyżarzanie.
-
Gry
dwuosobowe. Strategie: min-max i obcięty min-max. Dobór
metody heurystycznej.
-
Algorytmy genetyczne (AG) i ewolucyjne (AE): a) opis,
historia, nazewnictwo; b) kodowanie: binarne, kod Graya,
logarytmiczne, rzeczywistoliczbowe; c) ocena działania
algorytmu; d) reprodukcja i sukcesja; e) operatory
ewolucyjne; f) wyniki działania algorytmu; g) krzywe
zbieżności; h) kryteria zatrzymania algorytmu;.
-
Sztuczne sieci neuronowe (SSN): a) historia i klasy
zastosowań; b) inspiracje biologiczne; c) funkcje
aktywacji neuronu; d) budowa sztucznego neuronu; e)
sieci neuronowe; f) metody uczenia sieci; g) metoda
momentum; h) wsteczna propagacja błędów; i) sieci
samouczące się i konkurencja w sieciach; j) sieci
samoorganizujące się (Kohonena); k) sieci Hopfielda jako
przykład sieci rekurencyjnych.
-
Systemy rozmyte (SR): a. zbiory rozmyte; b. funkcje
przynależności i operacje na zbiorach rozmytych; c.
wnioskowanie przybliżone; d. sterowniki rozmyte; e.
projektowanie baz reguł; f. sterowniki
rozmyto-neuronowe.
-
Inne metody inteligencji obliczeniowej: a). eksploracja
danych (data mining); b) systemy wieloagentowe; c)
systemy ekspertowe; d) programowanie genetyczne; e)
algorytmy mrówkowe.
Literatura
-
L.
Rutkowski, Metody i techniki sztucznej inteligencji,
Wydawnictwa Naukowe PWN, Warszawa, 2006.
-
J.
Arabas, Wykłady z algorytmów ewolucyjnych, WNT,
Warszawa, 2001.
-
Z.
Michalewicz, Algorytmy genetyczne + struktury danych
= programy ewolucyjne, WNT, Warszawa, 1996.
-
R.
Tadeusiewicz, Elementarne wprowadzenie do techniki
sieci neuronowych z przykładowymi programami, Akad.
Oficyna Wyd. PLJ, Warszawa, 1998.
-
R.
Tadeusiewicz, Sieci neuronowe, Akademicka Oficyna
Wydawnicza RM, Warszawa 1993.
-
D.E. Goldberg, Algorytmy genetyczne i ich
zastosowania, WNT, Warszawa, 1995.
-
S.
Osowski, Sieci neuronowe w ujęciu algorytmicznym,
WNT, Warszawa 1996.
-
L.
Bolc, J. Cytowski, Metody przeszukiwania
heurystycznego. Tom 1,2. PWN, Warszawa, 1989, 1991.
Odnośniki:
Do pobrania
|