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

<marzec 2024>
PnWtŚrCzPtSoN
26272829123
45678910
11121314151617
18192021222324
25262728293031
1234567

Metody heurystyczne

Kierunek: Mechatronika
Specjalność: Modelowanie i symulacja systemów mechatronicznych (ME3)
Rodzaj studiów i semestr: stacjonarne II st. sem. III
Punkty ECTS: 2
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: 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. Kolokwium z wykładu.

 OCENA KOŃCOWA: O=0.65K+0.35L

K - ocena z kolokwium (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.

  • Strategie ślepe.

  • Strategie heurystyczne

  • Gry dwuosobowe.

  • Dobór metody heurystycznej.

  • Algorytmy genetyczne (AG) i ewolucyjne (AE).

  • Sztuczne sieci neuronowe (SSN)

  • Zbiory rozmyte, logika rozmyta i systemy rozmyte (SR)

  • Inne metody inteligencji obliczeniowej.


Tematyka laboratoriów

  • Przeszukiwanie grafów - strategie ślepe.

  • Przeszukiwanie grafów - strategie heurystyczne.

  • Algorytmy ewolucyjne.

  • Sztuczne sieci neuronowe.

  • Sterowanie rozmyte.

  • Problem komiwojażera.


Literatura

  • L. Rutkowski, Metody i techniki sztucznej inteligencji, Wydawnictwa Naukowe PWN, Warszawa, 2006.

  • J. Mulawka, Systemy ekspertowe, WNT, Warszawa, 1997.

  • J. Arabas, Wykłady z algorytmów ewolucyjnych, WNT, Warszawa, 2001.

  • R. Tadeusiewicz, Elementarne wprowadzenie do techniki sieci neuronowych z przykładowymi programami, Akad. Oficyna Wyd. PLJ, Warszawa, 1998.


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