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 її р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зацiя; метаевристика; генетичний алгоритм; алгоритм стрибаючих жаб; метод вiдпалу; алгоритм Лiн-Кернiгана

Повний текст:

PDF (English)

Посилання


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


Посилання

  • Поки немає зовнішніх посилань.


Copyright (c) 2020 Є. Сєлютiн, I. Козiн