Пређи на садржај

Метахеуристика

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

Метахеуристика (енгл. metaheuristic) поступак је високог нивоа у информатици и математичкој оптимизацији, чији је циљ да нађе, генерише или одабере хеуристику (делимични алгоритам претраге) која пружа довољно добро решење проблема оптимизације, нарочито у случајевима недовољне или несавршене информације или ограничене рачунарске снаге.[1] Метахеуристика обухвата скуп решења који је превише велики да му се узима узорак. Метахеуристике могу правити претпоставке о оптимизацији порблема који се решава, тако да могу бити коришћене за разноврсне проблеме.[2]

У поређењу са алгоритмима оптимизације и итеративним методама, метахеуристика не гарантује да глобално оптимално решење може бити нађено за неку класу проблема.[2] Многе метахеуристике имплементирају неку врсту стохастичке оптимизације, тако да нађено решење зависи од скупа генерисаних насумичних променљивих.[1] У комбинаторној оптимизацији, претраживањем великог скупа могућих решења, обично може наћи добра решења са мање рачунарске снаге од оптимизационих алгоритама, итеративних метода или просте хеуристике.[2] Као такве, корисне су у решавању оптимизационих проблема.[1] Више књига и стручних чланака је објављено на ову тему.[1][2][3][4][5]

Већина литературе о метахеуристици је експерименталне природе и описује емпиријске резултате базиране на рачунарским експериментима са алгоритмима. Поред тога постоје и формални теоријски резултати везани за конвергацију и могућност проналажења глобалног оптимума.[2] Многе метахеуристичке методе су објављене са тврдњом иновације и практичне ефективности. Нажалост већина објављеног садржаја је лошег квалитета, мане су обично: нејасноћа, мањак концептуалног објашњења, лоши експерименти и игнорисање предходне литературе. Али област такође садржи и истраживања великог квалитета.[6]

Својства:[уреди | уреди извор]

Својства која карактеришу већину метахеуристика:[2]

  • Метахеуристике су стратегије које руководе поступком претраге.
  • Циљ је ефикасно истражити простор претраге да би се нашло решење приближно оптималном.
  • Технике које конституишу алгоритме метахеуристике обухватају од простих локалних поступака претраге до комплексних процеса учења.
  • Алгоритми метахеуристике су приближни и обично недетерминистички.
  • Метахеуристике специфичне за проблем

Класификација:[уреди | уреди извор]

Различити начини класификација метахеуристика

Постоје разноврсне метахеуристике[1] и одређени број својстава по којима се разврставају[2]:

Локална и глобална претрага:[уреди | уреди извор]

Једна начин разврставања је по стратегији претраге.[2] Са једне стране је стратегија побољшавања простих алгоритама локалне претраге. Добро познати алгоритам локалне претраге је метода "планинарење" која се користи за налажење локалних оптимума. Међутим, "планинарење" не гарантује налажење глобално оптималне солуције.

Многе метахеуристичке идеје су предложене за побољшање хеуристике локалних претрага, ради проналажења бољих резултата. Неке од тих метахеуристика су симулирано прекаљивање, табу претрага, итеративна локална претрага, метода променљивих околина и ГРАСП.[2]

Са друге стране су метахеуристике глобалне претраге, које нису базиране на методама локалне претраге, већ на методама претраге на основу популације. Неке од ових метахеуристика су Мрављи алгоритам, Пчелињи алгоритам, генетички алгоритми и еволуциона израчунавања.[2]

Методе једног решење и По основу популације:[уреди | уреди извор]

Друга начин разврставања је на метахеуристике са једним решењем или претраге на основу популације.[2][5] Методе са једним решењем се фокусирају на модификовање и унапређење решења са једним кандидатом. Неке од метахеуристика са једним решењем су симулирано прекаљивање, итеративна локална претрага, метода променљивих околина и навођена локална претрага.[5]

Метахеуристике на основу популације се фоксирају на модификовање и унапређење решења са више кандидата, често се користећи карактеристикама популације за навођење претраге. Неке од метахеуристика на основу популације су генетички алгоритми и еволуциона израчунавања.[5]

Као посебна категорија метахеуристика се може сматрати и метахеуристика заснована на колективној интелигенцији, која представља колективно понашање јединки у популацији или роју. Неке од метахеуристика на основу популације су Мрављи алгоритам,[7] и Пчелињи алгоритам.[8]

Хибридизациони и меметички алгоритми:[уреди | уреди извор]

Хибридна метахеуристика је она која комбинује метахеуристику са другим методама оптимизације, као што су: математичко програмирање и програмирање ограничености. Обе компоненте хибридне метахеуристике могу да раде упоредо и размењују информације ради навођена претраге.

Са друге стране, меметички алгоритми[9] представљају синергију еволуционог приступа и приступа на основу популације са засебним индивидуалним учењем или локалним побољшањима поступака претраге. Пример меметичке метахеуристике је коришћење алгоритма локалне претраге уместо оператора основне мутације у еволуционим алгоритмима.

Паралелне метахеуристике:[уреди | уреди извор]

Паралелна метахуристика је она која користи технику паралелног програмирања како би више метахеуристика паралелно радило претраге. Оне обухватају од простих дистрибуираних шема до истовремених претрага које узајамно делују ради побољшања решења проблема.

Метахеуристике инспирисане природом:[уреди | уреди извор]

Веома активно поље истраживања метахеуристика су дизајни инспирисани природом. Многе скорашње метахеуристике, поготову оне засноване на еволуционим израчунавањима, су инспирисане природом, неке од њих су: Мрављи алгоритам, кукавичије хеширање и Пчелињи алгоритам.

Апликације:[уреди | уреди извор]

Метахеуристике се користе за комбинаторичне оптимизације у којима се оптимално решење налази у дискретном простору претраге. Пример проблема за које се користе је проблем трговачког путника, где простор претраге кандидата за решење расте експоненцијално у односу на раст обима проблема, што чини исцрпну претрагу за оптималним решењем незводљивом. Осим тога мултидимензионални комбинаторични проблеми укључујући већину проблема дизајна у инжињерству[10][11][12], као што су налаз форме и налаз понашања, пате од проклетства димензионалности, што их чини неизводљивим за исцрпну претрагу или аналитичке методе. У популарне метахеуристике за комбинаторичне оптимизације спадају симулирано прекаљивање[13], генетички алгоритми[14] , расејана претрага[15] и табу претрага[16]. Преглед литературе о метахеуристичкој оптимизацији[17] предлаже да је термин метахеуристика сковао Фред Гловер.[18]

Контрибуције:[уреди | уреди извор]

Постоји мноштво различитих метахеуристика и нове варијанте се стално предлажу. Неке од најзначајнијих контрибуција у области су:

  • 1952: Робинс и Монро раде на методи стохастичке оптимизације.[19]
  • 1954: Барицели извршава прву симулацију еволуционог поступка и користи их за генералну оптимизацију проблема.[20]
  • 1963: Растригин предлаже насумичну претрагу.[21]
  • 1965: Матиас предлаже несумичну оптимизацију.[22]
  • 1965: Нелдер анд Мид предлажу а симплекс хеуристику, за коју је Пауел показао да конвергира ка покретним зарезима за неке проблеме.[23]
  • 1966: Фогел предлаже еволуционо програмирање.[24]
  • 1970: Хејстингс предлаже Метрополис-Хејстингс алгоритам..[25]
  • 1970: Кавићио предлаже прихватање контролних параметара за прилагођивач.[26]
  • 1970: Кериган и Лин предлажу методу поделе графова, која се односи на променљиво дубоку претрагу и табу претрагу.[27]
  • 1975: Холанд предлаже генетички алгоритам.[14]
  • 1977: Гловер предлаже расејану претрагу.[15]
  • 1978: Мерсер и Самсон предлажу метаплан за подешавање параметара прилагођивача користећи други прилагођивач.[28]
  • 1980: Смит описује генетичко програмирање.[29]
  • 1983: Киркпатрик предлаже симулирано прекаљивање.[13]
  • 1986: Гловер предлаже табу претрагу, прво коришћење термина метахеуристика.[16]
  • 1989: Москато предлаже меметичке алгоритме.[9]
  • 1992: Дориго предлаже Мрављи алгоритам у својој докторској дисертацији.[7]
  • 1995: Волперт и Мекреди доказују теорему 'нема бесплатног ручка'.[30][31][32][33]

Референце:[уреди | уреди извор]

  1. ^ а б в г д Бианцхи, Леонора; Дориго, Марцо; Луца Мариа Гамбарделла; Гутјахр, Wалтер Ј. (2009). „А сурвеy он метахеуристицс фор стоцхастиц цомбинаториал оптимизатион”. Натурал Цомпутинг: ан интернатионал јоурнал. 8 (2): 239—287. дои:10.1007/с11047-008-9098-4. 
  2. ^ а б в г д ђ е ж з и ј Блум, C.; Роли, А. (2003). „Метахеуристицс ин цомбинаториал оптимизатион: Овервиеw анд цонцептуал цомпарисон”. 35 (3). АЦМ Цомпутинг Сурвеyс: 268—308. 
  3. ^ Голдберг, D.Е. (1989). Генетиц Алгоритхмс ин Сеарцх, Оптимизатион анд Мацхине Леарнинг. Клуwер Ацадемиц Публисхерс. ИСБН 978-0-201-15767-3. 
  4. ^ Гловер, Ф.; Коцхенбергер, Г.А. (2003). Хандбоок оф метахеуристицс. 57. Спрингер, Интернатионал Сериес ин Оператионс Ресеарцх & Манагемент Сциенце. ИСБН 978-1-4020-7263-5. 
  5. ^ а б в г Талби, Е-Г. (2009). Метахеуристицс: фром десигн то имплементатион. Wилеy. ИСБН 978-0-470-27858-1. 
  6. ^ Сöренсен, Кеннетх. „Метахеуристицс—тхе метапхор еxпосед” (ПДФ). Интернатионал Трансацтионс ин Оператионал Ресеарцх. дои:10.1111/итор.12001. Архивирано из оригинала (ПДФ) 2. 11. 2013. г. Приступљено 14. 5. 2016. 
  7. ^ а б M. Дориго, Оптимизатион, Леарнинг анд Натурал Алгоритхмс, ПхД тхесис, Политецницо ди Милано, Италие, 1992.
  8. ^ Карабога, Дервис (2010). „Артифициал бее цолонy алгоритхм”. Сцхоларпедиа. 5 (3): 6915. дои:10.4249/сцхоларпедиа.6915. 
  9. ^ а б Мосцато, П. (1989). „Он Еволутион, Сеарцх, Оптимизатион, Генетиц Алгоритхмс анд Мартиал Артс: Тоwардс Меметиц Алгоритхмс”. Цалтецх Цонцуррент Цомпутатион Програм (репорт 826). 
  10. ^ Томоиагă Б, Цхиндриş M, Сумпер А, Судриа-Андреу А, Виллафафила-Роблес Р. Парето Оптимал Рецонфигуратион оф Поwер Дистрибутион Сyстемс Усинг а Генетиц Алгоритхм Басед он НСГА-II. Енергиес. 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”