Анотація: Досліджено застосування трьох метаевристичних алгоритмів для розв’язання задачі комівояжера: імітації відпалу, табу пошуку та мурашиної колонії. Проведено експериментальні дослідження продуктивності програмної реалізації алгоритмів на чотирьох тестових задачах комівояжера з відомими оптимальними маршрутами. В результаті експерименту оцінені характеристики розв’язків, отриманих кожним алгоритмом в серії вимірів за однакову фіксовану кількість часу. Детально описано застосовані в експерименті параметри алгоритмів і особливості реалізації. Візуалізовано процес оптимізації кожним із алгоритмів. Зроблено висновки щодо ефективності досліджених алгоритмів для різних розмірів задач, використаних у експерименті.

Ключові слова: задача комівояжера, метаевристичні алгоритми оптимізації, алгоритм імітації відпалу, алгоритм табу пошуку, алгоритм мурашиної колонії.


Галузь науки: Технічні науки
Читати onlineЗавантажити статтю (pdf)