2.1 Podjela heurističkih algoritama


Najgrublja podjela heurističkih algoritama je na heuristike specifičnih problema i metaheuristike.

img002

.
Slika 2.1 Podjela algoritama

 

Heuristike specifičnih problema (Problem specific heuristics) su heuristički algoritmi namijenjeni za rješavanje točno određenog problema. U takve heuristike ubrajamo i funkcije procjene, tj. funkcije heuristike. Funkcije heuristike su sastavni dijelovi svih metaheurističkih algoritama.

Metaheuristički algoritmi obuhvaćaju širok skup algoritama namijenjenih optimizacijskim problemima. Oni su se pokazali izuzetno dobri u rješavanju NP-teških problema: problema nerješivih egzaktnim algoritmima u stvarnom vremenu. Metaheurističke algoritme možemo podijeliti po različitim osnovama, a najvažnije podjele su:

·Prirodom-inspirirani algoritmi i algoritmi koji nisu prirodom inspirirani. Primjeri prirodom-inspiriranih algoritama su optimizacija mravljom kolonijom i evolucijski algoritmi, a primjeri onih koji nisu prirodom inspirirani su tabu pretraživanje i lokalno pretraživanje.

·Algoritmi  koji imaju dinamičku funkciju objekta i algoritmi koji imaju statičku funkciju objekta. Većina algoritama ne mijenja svoju funkciju objekta (funkciju koju optimizira), no postoje algoritmi poput vođenog lokalnog traženja čija se funkcija objekta mijenja u svrhu bijega iz lokalnog optimuma. Takvi algoritmi imaju dinamičku funkciju objekta.

·Algoritmi koji koriste jednu strukturu okoline i algoritmi koji koriste skup struktura okoline. Algoritmi uglavnom koriste jednu strukturu okoline, no postoje algoritmi, poput pretraživanja promjenjivom okolinom, koji koriste skup struktura okoline.

·Algoritmi koji imaju mogućnost pamćenja prethodnih rješenja  i oni koji to nemaju. Primjerice, tabu pretraživanje ima mogućnost pamćenja prethodno odabranih rješenja, dok algoritam simuliranog kaljenja nema. On se koristi drugim metodama da bi odabrao dobro rješenje u sljedećoj iteraciji.

·Konstruktivni, poboljšavajući i hibridni algoritmi. Konstruktivni algoritmi grade rješenje (primjerice pohlepni algoritam). Poboljšavajući algoritmi odabiru rješenje i usavršavaju ga kroz niz iteracija (primjerice algoritam simuliranog kaljenja). Hibridni algoritmi su njihova kombinacija (primjerice GRASP).

·Algoritmi bazirani na populaciji rješenja i algoritmi putanje. Algoritmi koji se baziraju na populaciji rješenja koriste skup rješenja u procjeni trenutnog optimuma (primjerice Stohastic Diffusion Search), dok algoritmi putanje korste jedno trenutno rješenje u svakom koraku (primjerice Lokalno pretraživanje).

Tablica 2.1 Podjele metaheurističkih algoritama

 

 

 

 

 

 

 

 

Metaheuristički

algoritmi

Podjela 1

Prirodom-inspirirani algoritmi

Algoritmi koji nisu prirodom inspirirani

Podjela 2

Algoritmi  koji imaju dinamičku funkciju objekta

Algoritmi koji imaju statičku funkciju objekta

Podjela 3

Algoritmi koji koriste jednu strukturu okoline

Algoritmi koji koriste skup struktura okoline

Podjela 4

Algoritmi koji imaju mogućnost pamćenja prethodnih rješenja

Algoritmi koji nemaju mogućnost pamćenja prethodnih rješenja

Podjela 5

Konstruktivni algoritmi

Poboljšavajući algoritmi

Hibridni algoritmi

Podjela 6

Algoritmi bazirani na populaciji rješenja

Algoritmi putanje

U nastavku rada se daje naglasak na podjelu heurističkih algoritama na algoritme putanje i algoritme bazirane na populaciji rješenja [1, 2, 12].