Przeskocz do głównej zawartości



Katedra Mechaniki i Inżynierii Obliczeniowej
Wydział Mechaniczny Technologiczny, Politechnika Śląska
44-100 Gliwice, ul. Konarskiego 18A
tel. +48 32 2371204   fax. +48 32 2371282

Strona główna
Przedmioty
Pliki do pobrania
Kontakt
  

Skip Navigation Links
Struktura Katedry
Oferta współpracy
LaboratoriaExpand Laboratoria
Nasi absolwenci
Wydarzenia
PracownicyExpand Pracownicy

Dydaktyka
Skip Navigation Links
Prace dyplomowe
Projekty inżynierskie
Specjalności
Przedmioty
Pliki do pobrania
Podręczniki i skrypty
Praktyki studenckie
Koła naukoweExpand Koła naukowe

Działalność
naukowa
Skip Navigation Links
Profil naukowy
Przykłady badańExpand Przykłady badań
Projekty badawcze
Rozprawy doktorskie
Konferencje naukowe

<listopad 2024>
PnWtŚrCzPtSoN
28293031123
45678910
11121314151617
18192021222324
2526272829301
2345678

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


 

           webadmin


© Copyright MiIO. Wszelkie prawa zastrzeżone. Wszelkie materiały tekstowe, zdjęciowe, graficzne, dźwiękowe, filmowe zamieszczone na stronach są prawnie chronione i stanowią własność intelektualną MiIO.
Kopiowanie dla celów komercyjnych, dystrybucja, modyfikacja oraz publikacja, bez pisemnej zgody Kierownika Katedry Mechaniki i Inżynierii Obliczeniowej są zabronione.

Zasady wykorzystywania „ciasteczek” (ang. cookies) w serwisach internetowych Politechniki Śląskiej