From Wikipedia, the free encyclopedia
Metaheuristika (енгл. ) postupak je visokog nivoa u informatici i matematičkoj optimizaciji, čiji je cilj da nađe, generiše ili odabere heuristiku (delimični algoritam pretrage) koja pruža dovoljno dobro rešenje problema optimizacije, naročito u slučajevima nedovoljne ili nesavršene informacije ili ograničene računarske snage.[1] Metaheuristika obuhvata skup rešenja koji je previše veliki da mu se uzima uzorak. Metaheuristike mogu praviti pretpostavke o optimizaciji porblema koji se rešava, tako da mogu biti korišćene za raznovrsne probleme.[2]
U poređenju sa algoritmima optimizacije i iterativnim metodama, metaheuristika ne garantuje da globalno optimalno rešenje može biti nađeno za neku klasu problema.[2] Mnoge metaheuristike implementiraju neku vrstu stohastičke optimizacije, tako da nađeno rešenje zavisi od skupa generisanih nasumičnih promenljivih.[1] U kombinatornoj optimizaciji, pretraživanjem velikog skupa mogućih rešenja, obično može naći dobra rešenja sa manje računarske snage od optimizacionih algoritama, iterativnih metoda ili proste heuristike.[2] Kao takve, korisne su u rešavanju optimizacionih problema.[1] Više knjiga i stručnih članaka je objavljeno na ovu temu.[1][2][3][4][5]
Većina literature o metaheuristici je eksperimentalne prirode i opisuje empirijske rezultate bazirane na računarskim eksperimentima sa algoritmima. Pored toga postoje i formalni teorijski rezultati vezani za konvergaciju i mogućnost pronalaženja globalnog optimuma.[2] Mnoge metaheurističke metode su objavljene sa tvrdnjom inovacije i praktične efektivnosti. Nažalost većina objavljenog sadržaja je lošeg kvaliteta, mane su obično: nejasnoća, manjak konceptualnog objašnjenja, loši eksperimenti i ignorisanje predhodne literature. Ali oblast takođe sadrži i istraživanja velikog kvaliteta.[6]
Svojstva koja karakterišu većinu metaheuristika:[2]
Postoje raznovrsne metaheuristike[1] i određeni broj svojstava po kojima se razvrstavaju[2]:
Jedna način razvrstavanja je po strategiji pretrage.[2] Sa jedne strane je strategija poboljšavanja prostih algoritama lokalne pretrage. Dobro poznati algoritam lokalne pretrage je metoda "planinarenje" koja se koristi za nalaženje lokalnih optimuma. Međutim, "planinarenje" ne garantuje nalaženje globalno optimalne solucije.
Mnoge metaheurističke ideje su predložene za poboljšanje heuristike lokalnih pretraga, radi pronalaženja boljih rezultata. Neke od tih metaheuristika su simulirano prekaljivanje, tabu pretraga, iterativna lokalna pretraga, metoda promenljivih okolina i GRASP.[2]
Sa druge strane su metaheuristike globalne pretrage, koje nisu bazirane na metodama lokalne pretrage, već na metodama pretrage na osnovu populacije. Neke od ovih metaheuristika su Mravlji algoritam, Pčelinji algoritam, genetički algoritmi i evoluciona izračunavanja.[2]
Druga način razvrstavanja je na metaheuristike sa jednim rešenjem ili pretrage na osnovu populacije.[2][5] Metode sa jednim rešenjem se fokusiraju na modifikovanje i unapređenje rešenja sa jednim kandidatom. Neke od metaheuristika sa jednim rešenjem su simulirano prekaljivanje, iterativna lokalna pretraga, metoda promenljivih okolina i navođena lokalna pretraga.[5]
Metaheuristike na osnovu populacije se foksiraju na modifikovanje i unapređenje rešenja sa više kandidata, često se koristeći karakteristikama populacije za navođenje pretrage. Neke od metaheuristika na osnovu populacije su genetički algoritmi i evoluciona izračunavanja.[5]
Kao posebna kategorija metaheuristika se može smatrati i metaheuristika zasnovana na kolektivnoj inteligenciji, koja predstavlja kolektivno ponašanje jedinki u populaciji ili roju. Neke od metaheuristika na osnovu populacije su Mravlji algoritam,[7] i Pčelinji algoritam.[8]
Hibridna metaheuristika je ona koja kombinuje metaheuristiku sa drugim metodama optimizacije, kao što su: matematičko programiranje i programiranje ograničenosti. Obe komponente hibridne metaheuristike mogu da rade uporedo i razmenjuju informacije radi navođena pretrage.
Sa druge strane, memetički algoritmi[9] predstavljaju sinergiju evolucionog pristupa i pristupa na osnovu populacije sa zasebnim individualnim učenjem ili lokalnim poboljšanjima postupaka pretrage. Primer memetičke metaheuristike je korišćenje algoritma lokalne pretrage umesto operatora osnovne mutacije u evolucionim algoritmima.
Paralelna metahuristika je ona koja koristi tehniku paralelnog programiranja kako bi više metaheuristika paralelno radilo pretrage. One obuhvataju od prostih distribuiranih šema do istovremenih pretraga koje uzajamno deluju radi poboljšanja rešenja problema.
Veoma aktivno polje istraživanja metaheuristika su dizajni inspirisani prirodom. Mnoge skorašnje metaheuristike, pogotovu one zasnovane na evolucionim izračunavanjima, su inspirisane prirodom, neke od njih su: Mravlji algoritam, kukavičije heširanje i Pčelinji algoritam.
Metaheuristike se koriste za kombinatorične optimizacije u kojima se optimalno rešenje nalazi u diskretnom prostoru pretrage. Primer problema za koje se koriste je problem trgovačkog putnika, gde prostor pretrage kandidata za rešenje raste eksponencijalno u odnosu na rast obima problema, što čini iscrpnu pretragu za optimalnim rešenjem nezvodljivom. Osim toga multidimenzionalni kombinatorični problemi uključujući većinu problema dizajna u inžinjerstvu[10][11][12], kao što su nalaz forme i nalaz ponašanja, pate od prokletstva dimenzionalnosti, što ih čini neizvodljivim za iscrpnu pretragu ili analitičke metode. U popularne metaheuristike za kombinatorične optimizacije spadaju simulirano prekaljivanje[13], genetički algoritmi[14] , rasejana pretraga[15] i tabu pretraga[16]. Pregled literature o metaheurističkoj optimizaciji[17] predlaže da je termin metaheuristika skovao Fred Glover.[18]
Postoji mnoštvo različitih metaheuristika i nove varijante se stalno predlažu. Neke od najznačajnijih kontribucija u oblasti su:
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.