1 Uvod

Jedna od glavnih odlika računala je da u kratkom vremenu egzaktno riješi probleme koji u sebe uključuju složene računske operacije. Ipak, uz svu tehnologiju i napredak postignut u računarskoj znanosti, postoje problemi koji današnjim metodama nisu rješivi u stvarnom vremenu. Posebnu skupinu problema čine NP-teški i NP-potpuni problemi. U NP-teške i NP-potpune probleme spadaju i mnogi kombinatorni problemi, poput problema trgovačkog putnika i problem zadovoljenja Booleove funkcije. Poznati algoritmi za rješavanje NP-teških problema su u najboljem slučaju eksponencijalne složenosti, tj. vrijeme izvođenja je eksponencijalnog rasta. Za ilustraciju, to znači da se pojedini problemi ne mogu poznatim algoritmima riješiti milijardama godina. Pitanje je kako pristupiti takvim problemima.

Jedan od načina je da poboljšamo sklopovske performanse računala. Dobar primjer  tomu je kvantno računalo, koje bi, zbog svojih fizikalnih mogućnosti, moglo riješiti probleme eksponencijalne složenosti u razumnom vremenu. No kvantno računalo ostavimo za blisku budućnost i pokušajmo pristupiti problemu na drugačiji način. Inženjerska praksa nas uči da često nije potrebno riješiti probleme egzaktno, tj. dovoljno ih je riješiti približno. U tu svrhu koristimo se nekakvim iskustvenim metodama čija je  učinkovitost eksperimentalno potvrđena. Neke od tih metoda su i heuristički algoritmi.

Riječ heuristika potječe od grčke riječi heurisko što znači pronašao sam. Odavde se da naslutiti da su heuristički algoritmi zapravo algoritmi nastali eksperimentiranjem u svrhu dobivanja zadovoljavajućeg rješenja. Bitno svojstvo heurističkih algoritama je da mogu približno (dovoljno dobro) riješiti probleme eksponencijalne i faktorijelne složenosti. Ipak, valja napomenuti da rješavanje problema heurističkim algoritmima ne mora voditi k zadovoljavajućem rješenju, a za neke probleme, heuristički algoritmi pokazuju relativno loše rezultate. To se pogotovo odnosi na probleme za koje postoje egzaktni algoritmi polinomske složenosti. Isto tako, heuristički algoritmi nisu jednoznačno određeni. Pojedini dijelovi heurističkih algoritama se razlikuju ovisno o situaciji u kojoj se koriste.  Ti su dijelovi uglavnom funkcije cilja (transformacije) i njihovo definiranje znatno utječe na efikasnost algoritma.

Cilj seminarskog rada je dati pregled osnovnih heurističkih algoritama, a neke i pobliže opisati. U prvom djelu se daje kratak opis heurističkih algoritama i nabrajaju se moguće podjele metaheurističkih algoritama. Odabire se podjela na algoritme putanje i algoritme bazirane na populaciji rješenja. Pobliže se opisuje devet algoritama: pohlepni algoritam, lokalno pretraživanje, algoritam simuliranog kaljenja, tabu pretraživanje, pretraživanje promjenjivom okolinom, stohastičko difuzno pretraživanje, optimizacija mravljom kolonijom, optimizacija rojem čestica i evolucijski algoritmi. Na kraju je dan kratak opis preostalih heurističkih algoritma.