Katedra Wytrzymałości Materiałów i Metod Komputerowych Mechaniki
  
Wydział Mechaniczny Technologiczny
   Politechnika Śląska

 Strona głównaWyniki i ocenyPrzedmiotyPliki do pobraniaKontaktAdministrator
Icon Struktura Katedry
Icon Pracownicy
Icon Oferta współpracy
Icon Z życia Katedry
Icon Nasi absolwenci
Icon Wirtualny spacer
Icon Na wesoło
Dydaktyka
Icon Specjalności
Icon Przedmioty
Icon Wyniki i oceny
Icon Pliki do pobrania
Icon Prace dyplomowe
Icon Studenckie Koło Metod Komp. Mechaniki
Icon Studenckie Koło Mechaniki Eksperymentalnej "STRESS"
Icon Podręczniki i skrypty
Icon Praktyki studenckie
Działalność naukowa
Icon Profil naukowy
Icon Przykłady badań eksperymentalnych i analiz numerycznych
Icon Projekty badawcze
Icon Konferencje naukowe
Icon Rozprawy doktorskie
Icon Wybrane zagadnienia
Icon
 

 

Metody heurystyczne

Kierunek: Mechatronika
Specjalność: Modelowanie i symulacja systemów mechatronicznych (ME3)
Rodzaj studiów i semestr: stacjonarne II st. sem.I
Punkty ECTS: 3
Prowadzący: dr 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: 15 godzin w semestrze
  • Laboratorium: 15 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.35L

E - ocena z egzaminu (musi być pozytywna)

L - ocena z laboratorium


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


 
  Laboratorium Zastosowań Metod Sztucznej Inteligencji
  INTEREDU
  Sekcja Optymalizacji i Sterowania Komitetu Mechaniki PAN
  Sekcja Nauk Obliczeniowych KI PAN
  Studenckie Koło Naukowe Metod Komputerowych
  Programy MES do książki T. Burczyński, R.Bąk Wytrzymałość Materiałów z elementami ujęcia komputerowego (www.mes.polsl.pl)
  Strona poświęcona podręcznikowi "Badania operacyjne. Teoria i zastosowania."
  Konferencja EUROGEN2009
  Polskie Towarzystwo Metod Komputerowych Mechaniki
  DSMCM Grid Team
  Centrum Doskonałości AI-METH
  Konferencja AI-METH
  Strona główna Politechniki Ślaskiej
  Strona główna Wydziału MT
  Ministerstwo Nauki i Szkolnictwa Wyższego
  Poczta na polsl.pl
 Dodaj nowe łącze
Aktualnie nie ma żadnych nadchodzących wydarzeń. Aby dodać nowe wydarzenie, kliknij przycisk Dodaj nowe wydarzenie poniżej.
 Dodaj nowe wydarzenie