2.1 Podjela heurističkih algoritama

.
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].