Пор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щення виробництва.
Посилання
- 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
##submission.downloads##
Опубліковано
Як цитувати
Номер
Розділ
Ліцензія
Авторське право (c) 2020 Є. Сєлютiн, I. Козiн
Ця робота ліцензується відповідно до Creative Commons Attribution 4.0 International License.
Автори залишають за собою право на авторство своєї роботи та передають журналу право першої публікації цієї роботи на умовах ліцензії Creative Commons Attribution License, котра дозволяє іншим особам вільно розповсюджувати опубліковану роботу з обов'язковим посиланням на авторів оригінальної роботи та першу публікацію роботи у цьому журналі.