Сагун А.В., Хайдуров В.В. и др.
Черкасский государственный технологический университет, Черкасский филиал ЧВУЗ «Европейский университет», Украина
Download in PDF: http://fmo-journal.fizmatsspu.sumy.ua/journals/2017-v2-12/2017_2-12-Sagun_Scientific_journal_FMO.pdf

МЕТОД СТАИ ВОЛКОВ И ЕГО МОДИФИКАЦИЯ ДЛЯ РЕШЕНИЯ ЗАДАЧИ ПОИСКА ОПТИМАЛЬНОГО ПУТИ

Аннотация. Сегодня все больше и больше реальных технических задач сводится к решению задачи поиска оптимального пути (задача коммивояжера). Как известно, эта задача относится к классу NP-полных задач. В данной работе рассматривается классическая задача коммивояжера. Решение задачи проводится алгоритмом «стаи волков» и его модификацией. Произведен сравнительный анализ рассмотренных алгоритмов с разными эффективными алгоритмами решения данного типа задач.
К сожалению, не существует универсальных алгоритмов решения задач оптимизации [2]. Практика показывает, что градиентные численные методы не могут быть применимы к данной задаче ввиду ряда причин [3]. Основная причина – это время работы этих алгоритмов на рассматриваемой задаче и их вычислительная сложность.
В статье предложена модификация классического метода поиска глобального оптимума целевой функции стаей волков.
Ключевые слова: задача коммивояжера, глобальный минимум функции, оптимизация методом «стаи волков», популяция, хромосома.

METHOD OF STAGE WOLVES AND ITS MODIFICATION FOR solving the problem of finding
the optimum way
A. Sagun¹, V. Haidurov², V. Kunchenko-Kharchenko^3
1Cherkasy State Technological University, Ukraine
²Cherkassy branch of the European University "European University", Ukraine
³Cherkassy State Technological University, Ukraine

Abstract. Today, more and more real technical problems is reduced to solving the problem of finding the optimal path (traveling salesman problem). As you know, this problem belongs to the class of NP-complete problems. In this paper we consider the classical traveling salesman problem. The decision problem is an algorithm "pack of wolves" and its modification. Comparative analysis of the considered algorithms with different efficient algorithms for solving problems of this type.
Unfortunately, there is no universal algorithms for solving optimization problems [2]. Practice shows that the gradient of the numerical methods may not be applicable to this task for a number of reasons [3]. The main reason is the operating time of these algorithms on the considered task and their computational complexity.
The paper proposes a modification of the classical method of finding the global optimum of the objective function by a pack of wolves.
Key words: traveling salesman problem, global minimum of function, optimization of wolf pack, population, chromosome.

Список использованных источников

1. Chiorean, I.; Lupsa, L. & Neamtiu, L. (2008). Markov Models for the Simulation of Cancer Screening Process, In International Conference on Numerical Analysis and Applied Mathematics proceedings, 143-147, ISBN 978-0-7354-0576-9, Kos, Greece, September 2008, American Institute of Physics
2. Lups¸a, R.; Lups¸a, L. & Neamtiu, L. (2008): Optimal Model to Solve the Transport Model for Mammography Screening, 2008 IEEE International Conference on Automation, Quality and Testing, Robotics (AQTR 2008) THETA 16th edition proceedings, tome 3, pp. 139-142, ISBN 978-1-4244-2576-1, Cluj-Napoca
3. Manthey, B. (2009). On Approximating Multi-Criteria TSP, In Symposium on Theoretical Aspects of Computer Science, 637648, Freiburg, 2009, www.stacs-conf.org
4. Neant¸iu, L. (2009). A Medical Resources Allocation Problem, Results in Mathematics, Vol. 53, nr. 3-4 (July), 341-348, ISSN 1422-6383