Порiвняльна ефективнiсть використання метаевристи- чних методiв

Автор(и)

DOI:

https://doi.org/10.24144/2616-7700.2020.1(36).105-111

Ключові слова:

дискретна оптимiзацiя, метаевристика, генетичний алгоритм, алгоритм стрибаючих жаб, метод вiдпалу, алгоритм Лiн-Кернiгана

Анотація

Розглянуто суть метаевристичних методiв та умови їх застосування, зокрема, обмежена кiлькiсть знань i наявнiсть деякого кандидата на оптимальнiсть. Наведена формальна постановка задачi комiвояжера i її рiшення 4 алгоритмами: генетичним, вiдпалу, Лiн-Кернiгана i методом стрибаючих жаб.


Проаналiзовано переваги та недолiки алгоритму вiдпалу. Проведена паралель мiж алгоритмом вiдпалу i градiєнтними методами. Заданi змiннi завдання комiвояжера в параметрах генетичного алгоритму. Наведено принципи дiї методу стрибаючих жаб та алгоритму Лiн-Кернiгана.


Для проведення експерименту була згенерована база випадкових даних, якi утворили задачу розмiрностi 1000 × 1000 з наперед вiдомим точним розв’язком. Для висновкiв по результативностi методiв були оцiненi швидкiсть збiжностi завдання за умови максимального наближення до глобального екстремуму i середньоквадратичне вiдхилення вiд точного розв’язку. Виявлено, що генетичний алгоритм за заданих умов демонструє найкращi результати. Перспективним є подальше застосування алгоритму стрибаючих жаб для задач оптимiзацiї, реалiзоване з великим числом iтерацiй. Одним з напрямкiв використання алгоритму стрибаючих жаб є завдання розмiщення виробництва.

Біографії авторів

Є. Сєлютiн, ДВНЗ "Ужгородський національний університет"

Post-graduate student

I. Козiн, Zaporizhzhya National University, Zaporizhzhya,

The professor of the Economic Cybernetics Department,
Doctor of Physics and Math Science

Посилання

  1. Skobtsov, Y. (2008). Fundamentals of evolutionary computing: textbook. benefits Donetsk: DonNTU. [in Russian].
  2. Lin, S., & Kernighan, B. W. (1973). An Effective Heuristic Algorithm for
  3. the Traveling-Salesman Problem. Operations Research. Vol. 21, No. 2. DOI: https://doi.org/10.1287/opre.21.2.498
  4. Eusuff, M.M. (2003). Optimization of water distribution network design using the shuffled frog leaping algorithm. J. Water Resour. Planning Mgmt. Vol. 129., 210 – 225. DOI: https://doi.org/10.1061/(ASCE)0733-9496(2003)129:3(210)
  5. Narimani, M.R. (2011). A New Modified Shuffle Frog Leaping Algorithm for NonSmooth Economic Dispath. World Applied Sciences Journal, 803–814.
  6. Khumawala, B.M. (1972). An Efficient Branch-Bound Algorithm for the Warehouse Location Problem. Management Science. v18., 718-731. DOI: https://doi.org/10.1287/mnsc.18.12.B718
  7. Krarup, J., & Pruzan, P.M. (1983). The simple plant location problem: Survey and synthesis. European Journal of Operational Research. v12, 36-81. DOI: https://doi.org/10.1016/0377-
  8. (83)90181-9

##submission.downloads##

Опубліковано

2020-06-25

Як цитувати

Сєлютiн Є., & Козiн I. (2020). Порiвняльна ефективнiсть використання метаевристи- чних методiв. Науковий вісник Ужгородського університету. Серія «Математика і інформатика», 1(36), 105–111. https://doi.org/10.24144/2616-7700.2020.1(36).105-111

Номер

Розділ

Iнформатика, комп’ютернi науки та прикладна математика