Popis predmeta

Opis predmeta

Uvod u optimizacije i heuristike. Kompleksnost algoritama i problema. 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, PSO. Pregled dodatnih heurističkih tehnika. Studije slučaja: primjena konstruktivnih, hibridnih i meta heuristika za rješavanje praktičnih problema.

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.

Samostalni zadaci

Studenti kroz 2 domaće zadaće 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
Domaće zadaće 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

Studijski programi

Sveučilišni diplomski
Audiotehnologije i elektroakustika (profil)
Slobodni izborni predmeti (1. semestar) (3. semestar)
Automatika i robotika (profil)
Slobodni izborni predmeti (1. semestar) (3. semestar)
Elektroenergetika (profil)
Slobodni izborni predmeti (1. semestar) (3. semestar)
Elektroničko i računalno inženjerstvo (profil)
Slobodni izborni predmeti (1. semestar) (3. semestar)
Elektronika (profil)
Slobodni izborni predmeti (1. semestar) (3. semestar)
Elektrostrojarstvo i automatizacija (profil)
Slobodni izborni predmeti (1. semestar) (3. semestar)
Informacijsko i komunikacijsko inženjerstvo (profil)
Slobodni izborni predmeti (1. semestar) (3. semestar)
Komunikacijske i svemirske tehnologije (profil)
Slobodni izborni predmeti (1. semestar) (3. semestar)
Programsko inženjerstvo i informacijski sustavi (profil)
Izborni predmet profila (1. semestar) (3. semestar)
Računalno inženjerstvo (profil)
Slobodni izborni predmeti (1. semestar) (3. semestar)
Računalno modeliranje u inženjerstvu (profil)
Slobodni izborni predmeti (1. semestar) (3. semestar)
Računarska znanost (profil)
Slobodni izborni predmeti (3. semestar) Slobodni zborni predmeti (1. semestar)
Znanost o mrežama (profil)
Izborni predmeti profila (1. semestar) (3. semestar)
Znanost o podacima (profil)
Slobodni izborni predmeti (1. semestar) (3. semestar)

Literatura

(.), Handbook of Metaheuristics (International Series in Operations Research & Management Science, Band 272),
(.), Metaheuristics: From Design to Implementation,
(.), How to Solve it: Modern Heuristics, 2nd Edition,

Za studente

Izvedba

ID 222531
  Zimski semestar
5 ECTS
R3 Engleski jezik
R1 E-učenje
30 Predavanja
5 Seminar

Ocjenjivanje

85 izvrstan
75 vrlo dobar
65 dobar
55 dovoljan

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.

Samostalni zadaci

Studenti kroz 2 domaće zadaće 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
Domaće zadaće 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

Studijski programi

Sveučilišni diplomski
Audiotehnologije i elektroakustika (profil)
Slobodni izborni predmeti (1. semestar) (3. semestar)
Automatika i robotika (profil)
Slobodni izborni predmeti (1. semestar) (3. semestar)
Elektroenergetika (profil)
Slobodni izborni predmeti (1. semestar) (3. semestar)
Elektroničko i računalno inženjerstvo (profil)
Slobodni izborni predmeti (1. semestar) (3. semestar)
Elektronika (profil)
Slobodni izborni predmeti (1. semestar) (3. semestar)
Elektrostrojarstvo i automatizacija (profil)
Slobodni izborni predmeti (1. semestar) (3. semestar)
Informacijsko i komunikacijsko inženjerstvo (profil)
Slobodni izborni predmeti (1. semestar) (3. semestar)
Komunikacijske i svemirske tehnologije (profil)
Slobodni izborni predmeti (1. semestar) (3. semestar)
Programsko inženjerstvo i informacijski sustavi (profil)
Izborni predmet profila (1. semestar) (3. semestar)
Računalno inženjerstvo (profil)
Slobodni izborni predmeti (1. semestar) (3. semestar)
Računalno modeliranje u inženjerstvu (profil)
Slobodni izborni predmeti (1. semestar) (3. semestar)
Računarska znanost (profil)
Slobodni izborni predmeti (3. semestar) Slobodni zborni predmeti (1. semestar)
Znanost o mrežama (profil)
Izborni predmeti profila (1. semestar) (3. semestar)
Znanost o podacima (profil)
Slobodni izborni predmeti (1. semestar) (3. semestar)

Literatura

(.), Handbook of Metaheuristics (International Series in Operations Research & Management Science, Band 272),
(.), Metaheuristics: From Design to Implementation,
(.), How to Solve it: Modern Heuristics, 2nd Edition,

Za studente

Izvedba

ID 222531
  Zimski semestar
5 ECTS
R3 Engleski jezik
R1 E-učenje
30 Predavanja
5 Seminar

Ocjenjivanje

85 izvrstan
75 vrlo dobar
65 dobar
55 dovoljan