Heurističke metode optimizacija

Prikazani su podaci za akademsku godinu: 2024./2025.

Nositelji

Prof. dr. sc.
Lea Skorin-Kapov
Izv. prof. dr. sc.
Nina Skorin-Kapov

Laboratorijske vježbe

Dr. sc.
Krunoslav Tržec

Seminar

Dr. sc.
Krunoslav Tržec

Opis predmeta

Uvod u optimizacije i heuristike. Kompleksnost algoritama i problema. Kategorizacija heuristika i granice. Egzaktne metode. Konstruktivne heuristike (pohlepni algoritmi). Poboljšavajuće heuristike (metoda uspona, lokalno pretraživanje). Metaheuristike: iterativno lokalno pretraživanje, varijabilno pretraživanje susjedstva, pretraživanje velikog susjedstva, simulirano hlađenje, tabu pretraživanje, evolucijske strategije, kolonija mrava, GRASP, PSO. Pregled dodatnih heurističkih tehnika. Primjena konstruktivnih, hibridnih i metaheuristika u kontekstu rješavanje praktičnih problema.

Preduvjeti

Osnovno programiranja algoritama.

Studijski programi

Sveučilišni diplomski
[FER3-HR] Audiotehnologije i elektroakustika - profil
Izborni predmeti (1. semestar) (3. semestar)
[FER3-HR] Automatika i robotika - profil
Izborni predmeti (1. semestar) (3. semestar)
[FER3-HR] Elektroenergetika - profil
Izborni predmeti (1. semestar) (3. semestar)
[FER3-HR] Elektroničko i računalno inženjerstvo - profil
Izborni predmeti (1. semestar) (3. semestar)
[FER3-HR] Elektronika - profil
Izborni predmeti (1. semestar) (3. semestar)
[FER3-HR] Elektrostrojarstvo i automatizacija - profil
Izborni predmeti (1. semestar) (3. semestar)
[FER3-HR] Informacijsko i komunikacijsko inženjerstvo - profil
Izborni predmeti (1. semestar) (3. semestar)
[FER3-HR] Komunikacijske i svemirske tehnologije - profil
Izborni predmeti (1. semestar) (3. semestar)
[FER3-HR] Programsko inženjerstvo i informacijski sustavi - profil
Izborni predmeti (1. semestar) (3. semestar)
Izborni predmet profila (1. semestar) (3. semestar)
[FER3-HR] Računalno inženjerstvo - profil
Izborni predmeti (1. semestar) (3. semestar)
[FER3-HR] Računalno modeliranje u inženjerstvu - profil
Izborni predmeti (1. semestar) (3. semestar)
[FER3-HR] Računarska znanost - profil
Izborni predmeti (1. semestar) (3. semestar)
[FER3-HR] Znanost o mrežama - profil
Izborni predmeti (1. semestar) (3. semestar)
Izborni predmeti profila (1. semestar) (3. semestar)
[FER3-HR] Znanost o podacima - profil
Izborni predmeti (1. semestar) (3. semestar)
[FER2-HR] Obradba informacija - profil
preporučeni izborni predmeti (3. semestar)
[FER2-HR] Programsko inženjerstvo i informacijski sustavi - profil
preporučeni izborni predmeti (3. semestar)
[FER2-HR] Računalno inženjerstvo - profil
preporučeni izborni predmeti (3. semestar)
[FER2-HR] Računarska znanost - profil
preporučeni izborni predmeti (3. semestar)
[FER2-HR] Telekomunikacije i informatika - profil
preporučeni izborni predmet (3. semestar)

Ishodi učenja

  1. objasniti temeljne principe heurističkog pretraživanja kao optimizacijske metode za rješavanje kompleksnih problema
  2. izračunati kompleksnost problema i algoritama
  3. razlikovati egzaktne i heurističke metode, te kada primijeniti koje metoda
  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, PSO)
  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 se provode u dva ciklusa. Prvi ciklus sadrži 7 tjedana predavanja a drugi ciklus 6 tjedana predavanja, s tjednim opterećenjem od 2 sata.

Laboratorij

Studenti kroz 2 laboratorijske vježbe samostalno osmišljavaju, implementiraju i testiraju heurističke algoritme za rješavanje zadanih kombinatoričkih problema.

Ostalo

Projekt: osmišljavanje, implementacija i testiranje vlastitih heuristički algoritama za rješavanje zadanog kombinatoričkog problema.

Način ocjenjivanja

Kontinuirana nastava Ispitni rok
Vrsta provjere Prag Udio u ocjeni Prag Udio u ocjeni
Laboratorijske vježbe 25 % 25 % 25 % 25 %
Seminar/Projekt 50 % 25 % 50 % 25 %
Međuispit: Pismeni 0 % 25 % 0 %
Završni ispit: Pismeni 0 % 25 %
Ispit: Pismeni 0 % 50 %

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, dinamičko programiranje.
  4. Pohlepni algoritmi. Osnovni koncepti metaheuristika.
  5. Lokalno pretraživanje. Postupci pohlepnog nasumičnog prilagodljivog pretraživanja (GRASP)
  6. Varijabilno pretraživanje susjedstva. Pretraživanje velikih susjedstva.
  7. Tabu pretraga.
  8. Međuispit
  9. Simulirano kaljenje.
  10. Optimizacija kolonijom mrava.
  11. Optimizacija rojem čestica. Projektni zadatak: upute.
  12. Evolucijski algoritmi.
  13. Studijski slučajevi: hibridne i meta heuristike.
  14. Prezentacije projekata.
  15. Završni ispit

Literatura

Michel Gendreau, Jean-Yves Potvin (2018.), Handbook of Metaheuristics (International Series in Operations Research & Management Science, Band 272), Springer
El-Ghazali Talbi (2009.), Metaheuristics: From Design to Implementation, Wiley
Zbigniew Michalewicz , David B. Fogel (2004.), How to Solve it: Modern Heuristics, 2nd Edition, Springer

Izvedba

ID 240664
  Zimski semestar
5 ECTS
R3 Engleski jezik
R1 E-učenje
30 Predavanja
5 Seminar
0 Auditorne vježbe
12 Laboratorijske vježbe
0 Konstrukcijske vježbe
0 Vježbe tjelesnog odgoja

Ocjenjivanje

85 izvrstan
75 vrlo dobar
65 dobar
55 dovoljan

Sličan predmet