Heurističke metode optimizacija

Opis predmeta

Uvod u optimizacije i heuristike. Kompleksnost. Kategorizacija heuristika i granice. Egzaktne metode (iscrpno pretraživanje, dinamičko programiranje). Konstruktivne heuristike (pohlepni algoritmi). Poboljšavajuće heuristike (metoda uspona, lokalno pretraživanje). Metaheuristike: simulirano hlađenje, tabu pretraživanje, evolucijske strategije, kolonija mrava, GRASP. Pregled dodatnih heurističkih tehnika. Studije slučaja: primjena konstruktivnih, hibridnih i meta heuristika za rješavanje praktičnih problema.

Opće kompetencije

Očekuje se da studenti steknu razumijevanje temeljnih principa heurističkog pretraživanja kao optimizacijske metode za rješavanje kompleksnih problema. Nadalje, upoznat će se s najčešće korištenim heuristikama (pohlepni algoritmi, simulirano hlađenje, tabu pretraživanje, evolucijske strategije, kolonija mrava) i u potpunosti razumjeti njihovu metodologiju. Očekuje se da će studenti steći razumijevanje prednosti i nedostataka raznih heurističkih metoda, te moći procijeniti učinkovitost, ograničenja i kvalitetu različitih metoda. Najvažnije, očekuje se da će studenti moći primijeniti usvojeno znanje kako bi razvili i implementirali odgovarajuće i efikasne heurističke pristupe pri rješavanju novih kompleksnih problema.

Ishodi učenja

  1. objasniti temeljne principe heurističkog pretraživanja kao optimizacijske metode za rješavanje kompleksnih problema
  2. razlikovati kompleksnost problema i algoritama
  3. razlikovati egzaktne i heurističke metode
  4. identificirati potrebu za heuristikama
  5. objasniti metodologiju najčešće korištenih heuristika (pohlepni algoritmi, simulirano hlađenje, tabu pretraživanje, evolucijske strategije, kolonija mrava)
  6. objasniti prednosti i nedostatake raznih heurističkih metoda
  7. kreirati nove (hibridne) heurističke metode za pojedine probleme primjenom postojećih heurističkih metoda
  8. procijeniti kvalitetu rješenja dobivenu heurističkim metodama

Oblici nastave

Predavanja

Predavanja za grupu studenata.

Provjere znanja

Pisani ispit.

Pokusi na predavanjima

Primjeri izvođenja heurističkih metoda.

Konzultacije

Nastavnici su na raspolaganju u tjednom terminu konzultacija, kao i po dogovoru, uz najavu.

Ostali oblici skupnog ili samostalnog učenja

Studentski projekt

Način ocjenjivanja

Kontinuirana nastava Ispitni rok
Vrsta provjere Prag Udio u ocjeni Napomena / komentar Udio u ocjeni
Sudjelovanje u nastavi 0 % 5 % 0 % 5 %
Seminar/Projekt 0 % 25 % 0 % 25 %
Međuispit: Pismeni 0 % 35 % 0 %
Završni ispit: Pismeni 0 % 35 %
Ispit: Pismeni 0 % 70 %

Tjedni plan nastave

  1. Uvod u optimizacije; optimizacijski modeli; kombinatorička optimizacija
  2. Kompleksnost algoritama i problema; kategorizacija optimizacijskih metoda; zašto i kada koristiti heuristike
  3. Egzaktne metode: cjelobrojno programiranje; metoda grananja i granica
  4. Egzaktne metode: dinamičko programiranje
  5. Pohlepni algoritmi
  6. Studijski slučaj: planiranje mreža
  7. Temeljni koncepti metaheuristika
  8. Međuispit
  9. Lokalno pretraživanje
  10. Tabu pretraživanje
  11. Simulirano hlađenje
  12. Evolucijski algoritmi
  13. Optimizacija kolonijom mrava
  14. Studentski projekti
  15. Završni ispit

Studijski programi

Sveučilišni diplomski
Obradba informacija (profil)
preporučeni izborni predmeti (3. semestar)
Programsko inženjerstvo i informacijski sustavi (profil)
preporučeni izborni predmeti (3. semestar)
Računalno inženjerstvo (profil)
preporučeni izborni predmeti (3. semestar)
Računarska znanost (profil)
preporučeni izborni predmeti (3. semestar)
Telekomunikacije i informatika (profil)
preporučeni izborni predmet (3. semestar)

Literatura

Z. Michalewicz, D.B. Fogel (2004.), How to Solve it: Modern Heuristics, 2nd Edition, Springer-Verlag
V. J. Rayward-Smith, I. H. Osman, C. R. Reeves, G. D. Smith (1996.), Modern Heuristic Search Methods, Wiley
J. Dréo, A. Pétrowski, P. Siarry, E. Taillard (2005.), Metaheuristics for Hard Optimization: Methods and Case Studies, Springer
El-Ghazali Talbi (2009.), Metaheuristics: From Design to Implementation, Wiley
Xin-She Yang; (2008.), Nature-Inspired Metaheuristic Algorithms, Luniver Press