Algoritamske heuristike

Prema tekućem nastavnom planu, nastava iz predmeta Algoritamske heuristike se odvija u toku I semestra Master studija kao predmet na usmerenju Embeded sistemi i algoritmi.

Većina inženjerskih problema od interesa su algoritamski teški, u pogledu trošenja kritičnih računarskih resursa (vreme, prostor, broj procesora). U nedostatku efikasnih determinističkih ili aproksimativnih algoritama za rešavanje algoritamski teških problema, adekvatno dizajnirane i primenjene (meta)heuristike daju prihvatljiva (suboptimalna) rešenja u prihvatljivom vremenu. Obrazovni cilj ovog kursa je da na organizovan način i na jednom mestu da uporedni pregled (meta)heuristika i soft-computing tehnika koje su široko rasprostranjene u praktičnom inženjerskom rešavanju algoritamski teških problema.

Specifikacija predmeta

Oznaka predmeta: EM503
Broj ESPB: 4
Broj časova aktivne nastave nedeljno: 2+2

Nastavni kadar

Nastavnik: kancelarija: NTP zgrada, 1. sprat, kabinet 132; telefon: 485-4516; email: dautovic(at)uns(tačka)ac(tačka)rs

Način polaganja ispita

Materijal za predavanja:

  • Zbigniew Michalewicz, David B. Fogel, "How to Solve It: Modern Heuristics", 2nd ed. Revised and Extended edition, Springer, 2004, Engleski jezik

  • Daniel Ashlock, "Evolutionary Computation for Modeling and Optimization", Springer, 2006, Engleski jezik

  • J.-S. R. Jang, C.-T. Sun, E. Mizutani, "Neuro-Fuzzy and Soft Computing", Prentice-Hall, 1996, Engleski jezik

  • T. Back, David B. Fogel, Z. Michalewicz "Handbook of Evolutionary Computation", Springer, 1997, Engleski jezik


Materijal za laboratorijske/računarske vežbe:
 

1: Classification of algorithms and introduction to (Meta)-Heuristic Algorithms and Soft Computing

  • N. Kokash, An Introduction to Heuristic Algorithms (pdf)

  • B. Azvine et al, An Introduction to Soft Computing - A Tool for Building Intelligent Systems (pdf)


2: Heuristic Algorithms and Local Search

  • The introductory chapter from the book “Theoretical Aspects of Local Search”, Springer Berlin Heidelberg, 2007, (An Introduction to Local Search)

  • Aarts and Lenstra, A Local Search Template (pdf)


3: Tabu Search

  • M. Gendreau, An Introduction to Tabu Search (pdf)

  • Glover and Laguna, Tabu Search (pdf)


4: Bio-inspired metaheuristic algorithms (Part 1): Evolutionary Computation in different forms: EA, ES, EP, GA, GP

  • Z. Michalewicz, D.B. Fogel, Chapters 6 and 7 from the book "How to Solve It: Modern Heuristics"


5: Bio-inspired metaheuristic algorithms (Part 2): Swarm Intelligence, Ant Colony Optimization

  • X. Hu, Particle Swarm Optimization (link)

  • M. Dorigo, Ant Colony Optimization (link)

  • M. Dorigo, T. Stützle, The Ant Colony Optimization Metaheuristic: Algorithms, Applications, and Advances (pdf)


6: Nature-inspired metaheuristic algorithms: Simulated Annealing and Quantum Annealing

  • S. Kirkpatrick, C. D. Gelatt Jr., M. P. Vecchi, Optimization by Simulated Annealing (pdf)

  • R. Martoòák et al, Quantum annealing of the traveling-salesman problem

  • D. A. Battaglia, G. E. Santoro, and E. Tosatti, Optimization by quantum annealing: Lessons from hard satisfiability problems (pdf)


7: Culture-inspired metaheuristic algorithms: Memetic algorithms

  • P. Moscato, C. Cotta, A Gentle Introduction to Memetic Algorithms (pdf)


8: Soft-computing (Part 1): Algorithms based on Fuzzy Logic

  • Z. Michalewicz, D.B. Fogel, Chapter 13 from the book "How to Solve It: Modern Heuristics"


9: Soft-computing (Part 2): Artificial Neural Networks and Cellular Neural Networks

  • Z. Michalewicz, D.B. Fogel, Chapter 12 from the book "How to Solve It: Modern Heuristics"


 10: Hybrid algorithms (neuro-fuzzy, fuzzy-GA, EA-TS…)

  • J. Jantzen, Neurofuzzy Modeling (pdf)

  • P. Galinier, J.K. Hao, Hybrid Evolutionary Algorithms for Graph Coloring (pdf)


11: Examples of hard engineering optimization problems: LP, IP, 0-1 IP; Example problems from Graph Theory

  • T. Ferguson, Linear Programming - A Concise Introduction (pdf)

  • M. Trick, A Tutorial on Integer Programming (pdf)

  • P. Crescenzi, V. Kann, A compendium of NP optimization problems (pdf)


12: Solving hard problems using Meta-Heuristics and Soft-Computing (Part 1)

  • Z. Michalewicz, D.B. Fogel, Examples 3.2., 4.1, 6.1 from the book "How to Solve It: Modern Heuristics"


13: Solving hard problems using Meta-Heuristics and Soft-Computing (Part 2)

  • Z. Michalewicz, D.B. Fogel, Examples 12.6, 13.8 from the book "How to Solve It: Modern Heuristics"


14: Using Meta-Heuristics and Soft-computing in Single objective and Multi-objective Optimization

  • E. Zitzler et al, A Tutorial on Evolutionary Multiobjective Optimization (pdf)

  • C. A. Coello Coello and G. B. Lamont, Am Introduction to Multi-objective Evolutionary

  • Algorithms and their Applications, Chapter 1

  • M. P. Hansen, Tabu Search for Multiobjective Optimization (pdf)


Dodatne informacije

Preduslov : Algoritmi i njihova složenost (EM402)