2.4 Ostali heuristički algoritmi

U prethodnim podpoglavljima je dana podjela heurističkih algoritama i opisana nekolicina algoritama putanje i algoritama baziranih na populaciji rješenja. U ovom podpoglavlju se izlaže kratki opis ostalih heurističkih algoritama.

Pretraživanje najboljim prvim (Best-first search) je heuristički algoritam koji optimizira pretraživanje po širini (Breadth-first search). Funkcijom heuristike se procjenjuju čvorovi u grafu i odabire se najbolje procijenjeni čvor za daljnje istraživanje. U tu skupinu algoritama spada i A* pretraživanje. A* pretraživanje i njegova  posebna varijanta Dijkstrin algoritam su heuristički algoritmi  koji služe za pronalaženje najkraćeg puta između dvaju vrhova u grafu. A* pretraživanje i  Dijsktrin algoritam nas uvijek dovode do optimalnog rješenja ako ono postoji, tj. oni su završni algoritmi.

Algoritam penjanja uzbrdo (Hill Climbing, HC) po svom načinu optimiziranja pripada familiji algoritama lokalnog pretraživanja. Temeljen je na logici uspona: algoritam počinje od nekog rješenja i ukoliko postoji susjed koji bolje optimizira funkciju, novo rješenje postaje taj susjed. Veliki problem HC-a je mogućnost zapinjanja u lokalnom optimumu. Ovakva inačica algoritma je poznata pod nazivom jednostavni HC (Simple HC). Bolja inačica HC-a je stohastičko-restartiran HC (Random-Restart HC, RRHC). RRHC u svakoj iteraciji slučajno odabire početno rješenje i nad njime provodi SHC. Kao svoje rješenje odabire najbolje rješenje iz svih iteracija. Ovakvo rješenje je slično iterativnom lokalnom pretraživanju.

Ponavljajuća pohlepa (Iterated Greedy, IG) je algoritam koji uzastopnim iteracijama provodi pohlepnu destrukciju i konstrukciju postojećeg rješenja. U svakoj iteraciji se novostvoreno rješenje prihvaća u ovisnosti  o kriteriju prihvaćanja.

GRASP (The Greedy Randomized Adaptive Search Procedure, GRASP) je hibridna metaheuristička metoda. GRASP je kombinacija konstruktivne heuristike i lokalnog pretraživanja. Rješenje se sastavlja korak po korak uzimajući u svakoj iteraciji, slučajnim odabirom, komponentu rješenja iz ograničene liste kandidata. Ograničena lista kandidata se sastoji od α najboljih elemenata rangiranih prema vrijednosti pohlepne funkcije, tj. prema kvaliteti rješenja koje bi mogli postići. Ukoliko je α jednak jedinici dobivamo osnovni pohlepni algoritam, a ukoliko je α jednak broju komponenata dobivamo slučajno pretraživanje. Algoritam je osjetljiv na parametar α i najčešće ga algoritam mijenja iz iteracije u iteraciju (adaptacija algoritma).

Squeeky Wheel (SW) je metaheuristčki algoritam koji se može smatrati posebnim slučajem IG-a ili GRASP-a. SW gradi rješenje pomoću pohlepnog algoritma, a elementima rješenja koja uzrokuju pogrešku pridjeljuje kaznene bodove. Kazneni bodovi služe da bi se popravio prethodno odabran poredak elemenata rješenja, pri čemu se elementi sa više kaznenih bodova guraju naprijed.

Usmjereno lokalno pretraživanje (Guided Local Search, GLS), mijenja funkciju cilja da bi  izbjegao upadanje u lokalni optimum. Prilikom optimizacije funkcije se koristi lokalno pretraživanje koje često može dati suboptimalno rješenje. Neko suboptimalno rješenje se može često pojavljivati i treba ga učiniti nepoželjnim. GLS se koristi svojstvima rješenja, primjerice bridovima u TSP-u,  da bi diskriminirao rješenja koja vode k lokalnom optimumu. U svakoj iteraciji se za svako svojstvo koje se pojavljuje u rješenju povećava kazna, a funkcija cilja se preoblikuje tako da se poveća za izraz koji ovisi o kaznama svojstava koja su uključena u rješenje. Dakle, GLS ne mijenja okolinu poput VNS-a da bi što bolje pretražilo prostor rješenja, već to čini mijenjanjem funkcije koju optimizira (funkcija objekta).

Iterativno lokalno pretraživanje (Iterated Lokal Search, ILS) se kroz niz iteracija koristi lokalnim pretraživanjem, ali početno rješenje lokalnog pretraživanja kreće na različitim mjestima. U svakoj iteraciji se najprije odredi početno rješenje za lokalno pretraživanje tako da se poremeti najbolje pronađeno rješenje. Nakon lokalnog pretraživanja se dobiveno rješenje usporedi sa najboljim dotadašnjim rješenjem. Ukoliko je ispunjen kriterij prihvaćanja dobiveno rješenje postaje novo najbolje rješenje (premda ono ne mora biti najbolje). Ovakav način optimiziranja je u nekim slučajevima u prednosti nad načinom optimiziranja koje odabire početno rješenje i neprestano ga poboljšava. Uglavnom je prednost brzina uz dobivanje dovoljno dobrog rješenja.

Kvantno kaljenje (Quantum Annealing, QA) je heuristički algoritam koji nadograđuje simulirano kaljenje. Velike prednosti ima nad funkcijama koje imaju velike, ali uske barijere. Simulirano kaljenje tada ima veću  mogućnost zapinjanja u lokalnom optimumu,tj. teži bijeg iz lokalnog optimuma zbog visine barijere. QA uvodi pojam neodređenosti po uzoru na valna svojstvo kvantnog svijeta i ima mogućnost tuneliranja kroz takve barijere. Smatra se da bi se QA trebalo puno bolje izvoditi na kvantnim računalima.

Pretraživanje promjenjivom širinom (Variable Depth Search, VDS) je generalizacija lokalnog pretraživanja. Osnovna ideja VDS-a je promijeniti veličinu okoline po kojoj se pretražuje tako da algoritam može učinkovito pretraživati složene probleme u razumnom vremenu. U skupinu VDS-a spada i Lin-Kernighanov algoritam.

Višerazinsko oplemenjivanje (Multilevel Refinement, MR) je metaheuristika koja rekurzivno aproksimira problem kroz niz razina. U svakoj razini se prvo uzima projekcija rješenja podređene razine. Zatim se upotrijebi jedna od metoda jednostavnih pretraživanja da se oplemeni projekcija niže razine.

Ekstremna optimizacija (Extremal optimization, EO)  vuče inspiraciju iz Bak-Sneppenovog modela samo-organizirane kritičnosti iz područja statističke fizike [3]. EO optimizira probleme koji se mogu rastaviti na komponente i neovisno procjenjivati. Vrši se evolucija pojedinih komponenti rješenja: najgore komponente se mijenjaju. Početno rješenje se može odabrati nasumično.

 

Harmonijsko pretraživanje (Harmony search, HS) je metaheuristički algoritam koji oponaša skupinu glazbenika u potrazi za savršenom harmonijom. Analogija je jednostavna: kao što glazbenici traže savršenu harmoniju i slušatelji daju estetičku procjenu, tako u HS-u pokušavamo riješiti optimizacijski problem procjenom pojedinih rješenja. Četiri su osnovna koraka u HS-a: inicijalizacija parametara i harmonijske memorije, improviziranje nove memorije, obnavljanje harmonijske memorije, provjera zaustavnog kriterija. Zadnja tri koraka pripadaju iterativnom postupku.

HS se pokazalo učinkovit u rješavanju NP-teških problema i dizajniranju cjevovodne mreže [28].

Bakteriološki algoritmi (Bacteriologic Algorithms, BA) su algoritmi inspirirani evolucijskom ekologijom, tj. adaptacijom bakterija na okolinu u kojoj obitavaju [3]. Algoritam simulira adaptaciju bakterija na okolinu, a bitno svojstvo koje uzima u obzir je nemogućnost prilagodbe populacije bakterija na sve uvjete okoline. BA su se pokazali uspješnije od EA-a u područjima dubinske analize podataka i u problemima kompleksnog pozicioniranja [3].

Memetički Algoritam (Memetic Algorithm, MA) je kombinacija EA sa lokalnim pretraživanjem. Naziv je dobio po kulturološkom genu mem koji prenosi informacije iz jednog uma u drugi. Za razliku od gena, mem se ne prenosi razmnožavanjem.

MA imaju svojstvo da dobro pretražuju i iskorištavaju prostor rješenja, ali su naročito osjetljivi na odnos poremećaja informacije i njenog očuvanja prilikom mutacije: da bi se postigao bijeg iz lokalnog optimuma i zadovoljio uvjet stabilnosti algoritma, potrebno je taj odnos uravnotežiti.    

Razbacano pretraživanje (Scatter Search, SS) je metaheuristička metoda koja se od EA-a razlikuje po tome što omogućuje opće principe za rekombinaciju rješenja zasnovanih na konstrukciji puta u Euklidovom prostoru [2]. Koristi male populacije čijom kombinacijom nastaju nova rješenja. Jedinke se prikazuju kao točke u Euklidovom prostoru i njihovom linearnom kombinacijom nastaju rješenja sljedeće generacije. Općenitija verzija SS je nanovo vezivanje puta (Path relinking , PR).  

Procjena distribucijskih algoritama (Estimation of Distribution Algorithms, EDA) su skupina algoritama koji imaju podlogu u teoriji vjerojatnosti, ali koriste i populaciju koja se razvija kroz proces pretrage [1]. Nedostatak EA je u činjenici da se rekombinacijom mogu razbiti blokovi dobrih rješenja. EDA se koristi vjerojatnosnim modelom kojim se procjenjuje distribucija dobrih rješenja preko prostora pretrage i uzorkovanjem po toj distribuciji dobivamo rješenja sljedeće generacije [2]. Procjena distribucije se vrši u svakoj iteraciji na temelju postojećih rješenja.   

Metoda ukrštene entropije (Cross-Entropy Method, CEM) je metaheuristika koja potječe iz područja simulacije rijetkih događaja gdje je potrebno što točnije odrediti vjerojatnost pojave događaja male vjerojatnosti. Simulacija rijetkih događaja i uzorkovanje po važnosti osnove su ove metode. CEM ima dvije faze:

·        generiranje slučajnih uzoraka rješenja prema određenom mehanizmu

·        obnavljanje parametara mehanizma u svrhu dobivanja boljih uzoraka

Diferencijska evolucija (Differential evolution, DE) je metoda koja spada u skupinu ES-a. DE se koristi za optimizaciju funkcija više varijabli i ima veliku vjerojatnost pronalaska globalnog optimuma. Najvažniji dio DE-a je shema za generiranje probnih parametarskih vektora [3]. Shema je samoorganizirajuća pa nisu potrebne vjerojatnosne distribucije koje koriste ES. Diferencijska evolucija se od drugih evolucijskih strategija najviše razlikuje u fazi mutacije

Grupirajući genetski algoritam (Gruping Genetic Algorithm, GGA) je unaprjeđenje GA. Kod rješavanja nekih problema je bolje operirati nad grupom jedinki nego nad pojedinom jedinkom. GGA optimizira uz  pomoć grupe jedinki. Skup jedinki se razdvaja u disjunktne grupe i svakoj se grupi pridjeljuju svojstva ekvivalentna genima u običnom GA. Ovakav način optimizacije zahtijeva promjenjive veličine kromosoma pojedinih grupa jedinki i posebne operatore manipulacije nad grupama jedinki.

Interaktivni genetski algoritmi (Interactve genetc agorithms, IGA)  su skupina algoritama koji uključuju  ljudsku procjenu, a pronalazimo ih u područjima gdje funkciju dobrote nije lako pronaći (umjetnost) [3].