Metaheuristika

С Википедије, слободне енциклопедије

Metaheuristika (енгл. metaheuristic) 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:[уреди | уреди извор]

Svojstva koja karakterišu većinu metaheuristika:[2]

  • Metaheuristike su strategije koje rukovode postupkom pretrage.
  • Cilj je efikasno istražiti prostor pretrage da bi se našlo rešenje približno optimalnom.
  • Tehnike koje konstituišu algoritme metaheuristike obuhvataju od prostih lokalnih postupaka pretrage do kompleksnih procesa učenja.
  • Algoritmi metaheuristike su približni i obično nedeterministički.
  • Metaheuristike specifične za problem

Klasifikacija:[уреди | уреди извор]

Različiti načini klasifikacija metaheuristika

Postoje raznovrsne metaheuristike[1] i određeni broj svojstava po kojima se razvrstavaju[2]:

Lokalna i globalna pretraga:[уреди | уреди извор]

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]

Metode jednog rešenje i Po osnovu populacije:[уреди | уреди извор]

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]

Hibridizacioni i memetički algoritmi:[уреди | уреди извор]

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.

Paralelne metaheuristike:[уреди | уреди извор]

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.

Metaheuristike inspirisane prirodom:[уреди | уреди извор]

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.

Aplikacije:[уреди | уреди извор]

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]

Kontribucije:[уреди | уреди извор]

Postoji mnoštvo različitih metaheuristika i nove varijante se stalno predlažu. Neke od najznačajnijih kontribucija u oblasti su:

  • 1952: Robins i Monro rade na metodi stohastičke optimizacije.[19]
  • 1954: Bariceli izvršava prvu simulaciju evolucionog postupka i koristi ih za generalnu optimizaciju problema.[20]
  • 1963: Rastrigin predlaže nasumičnu pretragu.[21]
  • 1965: Matias predlaže nesumičnu optimizaciju.[22]
  • 1965: Nelder and Mid predlažu a simpleks heuristiku, za koju je Pauel pokazao da konvergira ka pokretnim zarezima za neke probleme.[23]
  • 1966: Fogel predlaže evoluciono programiranje.[24]
  • 1970: Hejstings predlaže Metropolis-Hejstings algoritam..[25]
  • 1970: Kavićio predlaže prihvatanje kontrolnih parametara za prilagođivač.[26]
  • 1970: Kerigan i Lin predlažu metodu podele grafova, koja se odnosi na promenljivo duboku pretragu i tabu pretragu.[27]
  • 1975: Holand predlaže genetički algoritam.[14]
  • 1977: Glover predlaže rasejanu pretragu.[15]
  • 1978: Merser i Samson predlažu metaplan za podešavanje parametara prilagođivača koristeći drugi prilagođivač.[28]
  • 1980: Smit opisuje genetičko programiranje.[29]
  • 1983: Kirkpatrik predlaže simulirano prekaljivanje.[13]
  • 1986: Glover predlaže tabu pretragu, prvo korišćenje termina metaheuristika.[16]
  • 1989: Moskato predlaže memetičke algoritme.[9]
  • 1992: Dorigo predlaže Mravlji algoritam u svojoj doktorskoj disertaciji.[7]
  • 1995: Volpert i Mekredi dokazuju teoremu 'nema besplatnog ručka'.[30][31][32][33]

Reference:[уреди | уреди извор]

  1. ^ а б в г д Bianchi, Leonora; Dorigo, Marco; Luca Maria Gambardella; Gutjahr, Walter J. (2009). „A survey on metaheuristics for stochastic combinatorial optimization”. Natural Computing: an international journal. 8 (2): 239—287. doi:10.1007/s11047-008-9098-4. 
  2. ^ а б в г д ђ е ж з и ј Blum, C.; Roli, A. (2003). „Metaheuristics in combinatorial optimization: Overview and conceptual comparison”. 35 (3). ACM Computing Surveys: 268—308. 
  3. ^ Goldberg, D.E. (1989). Genetic Algorithms in Search, Optimization and Machine Learning. Kluwer Academic Publishers. ISBN 978-0-201-15767-3. 
  4. ^ Glover, F.; Kochenberger, G.A. (2003). Handbook of metaheuristics. 57. Springer, International Series in Operations Research & Management Science. ISBN 978-1-4020-7263-5. 
  5. ^ а б в г Talbi, E-G. (2009). Metaheuristics: from design to implementation. Wiley. ISBN 978-0-470-27858-1. 
  6. ^ Sörensen, Kenneth. „Metaheuristics—the metaphor exposed” (PDF). International Transactions in Operational Research. doi:10.1111/itor.12001. Архивирано из оригинала (PDF) 2. 11. 2013. г. Приступљено 14. 5. 2016. 
  7. ^ а б M. Dorigo, Optimization, Learning and Natural Algorithms, PhD thesis, Politecnico di Milano, Italie, 1992.
  8. ^ Karaboga, Dervis (2010). „Artificial bee colony algorithm”. Scholarpedia. 5 (3): 6915. doi:10.4249/scholarpedia.6915. 
  9. ^ а б Moscato, P. (1989). „On Evolution, Search, Optimization, Genetic Algorithms and Martial Arts: Towards Memetic Algorithms”. Caltech Concurrent Computation Program (report 826). 
  10. ^ Tomoiagă B, Chindriş M, Sumper A, Sudria-Andreu A, Villafafila-Robles R. Pareto Optimal Reconfiguration of Power Distribution Systems Using a Genetic Algorithm Based on NSGA-II. Energies. 2013; . 6 (3): 1439—1455 http://www.mdpi.com/1996-1073/6/3/1439/pdf.  Недостаје или је празан параметар |title= (помоћ).
  11. ^ Ganesan, T.; Elamvazuthi, I.; Ku Shaari, Ku Zilati; Vasant, P. (1. 3. 2013). „Swarm intelligence and gravitational search algorithm for multi-objective optimization of synthesis gas production”. Applied Energy. 103: 368—374. doi:10.1016/j.apenergy.2012.09.059. 
  12. ^ Ganesan, T.; Elamvazuthi, I.; Vasant, P. (1. 11. 2011). „Evolutionary normal-boundary intersection (ENBI) method for multi-objective optimization of green sand mould system”. 2011 IEEE International Conference on Control System, Computing and Engineering (ICCSCE): 86—91. doi:10.1109/ICCSCE.2011.6190501. 
  13. ^ а б Kirkpatrick, S.; Gelatt Jr., C.D.; Vecchi, M.P. (1983). „Optimization by Simulated Annealing”. Science. 220 (4598): 671—680. PMID 17813860. doi:10.1126/science.220.4598.671. 
  14. ^ а б Holland, J.H. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press. ISBN 978-0-262-08213-6. 
  15. ^ а б Glover, Fred (1977). „Heuristics for Integer programming Using Surrogate Constraints”. Decision Sciences. 8 (1): 156—166. doi:10.1111/j.1540-5915.1977.tb01074.x. 
  16. ^ а б Glover, F. (1986). „Future Paths for Integer Programming and Links to Artificial Intelligence”. Computers and Operations Research. 13 (5): 533—549. doi:10.1016/0305-0548(86)90048-1. 
  17. ^ X. S. Yang, Metaheuristic optimization, Scholarpedia, 6(8):11472 (2011).
  18. ^ Glover F., (1986). Future paths for integer programming and links to artificial intelligence, Computers and Operations Research,13,533-549 (1986).
  19. ^ Robbins, H.; Monro, S. (1951). „A Stochastic Approximation Method”. Annals of Mathematical Statistics. 22 (3): 400—407. doi:10.1214/aoms/1177729586. 
  20. ^ Barricelli, N.A. (1954). „Esempi numerici di processi di evoluzione”. Methodos: 45—68. 
  21. ^ Rastrigin, L.A. (1963). „The convergence of the random search method in the extremal control of a many parameter system”. Automation and Remote Control. 24 (10): 1337—1342. 
  22. ^ Matyas, J. (1965). „Random optimization”. Automation and Remote Control. 26 (2): 246—253. 
  23. ^ Nelder, J.A.; Mead, R. (1965). „A simplex method for function minimization”. Computer Journal. 7: 308—313. doi:10.1093/comjnl/7.4.308. 
  24. ^ Fogel, L.; Owens, A.J.; Walsh, M.J. (1966). Artificial Intelligence through Simulated Evolution. Wiley. ISBN 978-0-471-26516-0. 
  25. ^ Hastings, W.K. (1970). „Monte Carlo Sampling Methods Using Markov Chains and Their Applications”. Biometrika. 57 (1): 97—109. doi:10.1093/biomet/57.1.97. 
  26. ^ Cavicchio, D.J. (1970). „Adaptive search using simulated evolution”. Technical Report. University of Michigan, Computer and Communication Sciences Department. hdl:2027.42/4042.  templatestyles stripmarker у |id= на позицији 1 (помоћ)
  27. ^ Kernighan, B.W.; Lin, S. (1970). „An efficient heuristic procedure for partitioning graphs”. Bell System Technical Journal. 49 (2): 291—307. doi:10.1002/j.1538-7305.1970.tb01770.x. 
  28. ^ Mercer, R.E.; Sampson, J.R. (1978). „Adaptive search using a reproductive metaplan”. Kybernetes. 7 (3): 215—228. doi:10.1108/eb005486. 
  29. ^ Smith, S.F. (1980). A Learning System Based on Genetic Adaptive Algorithms (PhD Thesis). University of Pittsburgh. 
  30. ^ Wolpert, D.H.; Macready, W.G. (1995). „No free lunch theorems for search”. Technical Report SFI-TR-95-02-010. Santa Fe Institute. 
  31. ^ Igel, Christian, Toussaint, Marc (jun 2003). „On classes of functions for which No Free Lunch results hold”. Information Processing Letters. Elsevier North-Holland, Inc. 86 (6): 317—321. ISSN 0020-0190. doi:10.1016/S0020-0190(03)00222-9. 
  32. ^ Auger, Anne, Teytaud, Olivier (2010). „Continuous Lunches Are Free Plus the Design of Optimal Optimization Algorithms”. Algorithmica. Springer-Verlag. 57 (1): 121—146. ISSN 0178-4617. doi:10.1007/s00453-008-9244-5. 
  33. ^ Stefan Droste; Thomas Jansen; Ingo Wegener (2002). „Optimization with Randomized Search Heuristics – The (A)NFL Theorem, Realistic Scenarios, and Difficult Functions”. Theoretical Computer Science. 287 (1): 131—144. doi:10.1016/s0304-3975(02)00094-4. Приступљено 9. 4. 2013. 

Spoljašnji linkovi[уреди | уреди извор]

Преузето из „https://sr.wikipedia.org/w/index.php?title=Metaheuristika&oldid=27680029”