Comparative electiveness of metaheuristic methods

Є. Сєлютiн; I. Козiн

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

Автор(и)

Є. Сєлютiн ДВНЗ "Ужгородський національний університет", Україна https://orcid.org/0000-0002-5458-9880
I. Козiн Zaporizhzhya National University, Zaporizhzhya,, Україна https://orcid.org/0000-0003-1278-8520

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щення виробництва.

Посилання

Skobtsov, Y. (2008). Fundamentals of evolutionary computing: textbook. benefits Donetsk: DonNTU. [in Russian].

Lin, S., & Kernighan, B. W. (1973). An Effective Heuristic Algorithm for

the Traveling-Salesman Problem. Operations Research. Vol. 21, No. 2. DOI: https://doi.org/10.1287/opre.21.2.498

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)

Narimani, M.R. (2011). A New Modified Shuffle Frog Leaping Algorithm for NonSmooth Economic Dispath. World Applied Sciences Journal, 803–814.

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

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-

(83)90181-9