Авторитетность издания
ВАК - К1
RSCI, ядро РИНЦ
Добавить в закладки
Следующий номер на сайте
№1
Ожидается:
16 Марта 2024
В Сибирском государственном аэрокосмическом университете им. академика М.Ф. Решетнева для решения задачи коммивояжера предлагается использовать самонастраивающиеся бионические алгоритмы.
06.11.2013Задача коммивояжера является обобщением задачи о гамильтоновых циклах в графах, относится к классу NP-полных задач и часто используется для тестирования вновь создаваемых алгоритмов комбинаторной оптимизации. Она формулируется следующим образом:
Пусть имеется заданное множество из n городов. Требуется найти замкнутый обход минимальной длины при условии, что каждый город должен быть посещен только один раз.
Задача коммивояжера имеет множество практических применений, таких как задачи маршрутизации, составления расписания с ограничениями, задачи игрового типа для поиска оптимальной стратегии и т.д.
Широкое применение при решении таких задач получили недетерминированные многоагентные алгоритмы, в том числе бионические. В данной статье рассматриваются генетический алгоритм (ГА), муравьиный алгоритм (Ant Colony Optimization, ACO), алгоритм умных капель (Intelligent Water Drops, IWDs), эвристика Лина–Кернигана и авторские адаптивные ГА и АСО.
Подробное описание дается в статье «Исследование эффективности бионических алгоритмов комбинаторной оптимизации», авторы: Семенкина О.Е., Семенкина О.Э. (Сибирский государственный аэрокосмический университет им. академика М.Ф. Решетнева, г. Красноярск).
