На правах рекламы:
ISSN 0236-235X (P)
ISSN 2311-2735 (E)

Авторитетность издания

ВАК - К1
RSCI, ядро РИНЦ

Добавить в закладки

Следующий номер на сайте

2
Ожидается:
16 Июня 2024

В Сибирском государственном аэрокосмическом университете им. академика М.Ф. Решетнева для решения задачи коммивояжера предлагается использовать самонастраивающиеся бионические алгоритмы.

06.11.2013

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