Программная система решения задачи коммивояжёра с использованием муравьиного алгоритма

В рамках разрабатываемой системы создано программное обеспечение для решения задачи коммивояжёра с использованием муравьиного алгоритма. Задача формулируется как задача поиска минимального по стоимости замкнутого маршрута по всем вершинам без повторений на полном взвешенном графе с n вершинами. Вершины графа являются городами, которые должен посетить коммивояжёр, а веса рёбер отражают расстояния (длины) или стоимости проезда. Задача является NP-трудной, и точный переборный алгоритм её решения имеет факториальную сложность. Моделирование поведения муравьёв связано с распределением феромона на тропе – ребре графа в задаче коммивояжёра. При этом вероятность включения ребра в маршрут отдельного муравья пропорциональна количеству феромона на этом ребре, а количество откладываемого феромона пропорционально длине маршрута. Чем короче маршрут, тем больше феромона будет отложено на его рёбрах, следовательно, большее количество муравьёв будет включать его в синтез собственных маршрутов. Моделирование такого подхода, использующего только положительную обратную связь, приводит к преждевременной сходимости – большинство муравьёв двигается по локально оптимальному маршруту. Поскольку в основе муравьиного алгоритма лежит моделирование передвижения муравьёв по некоторым путям, то такой подход является эффективным способом поиска рациональных решений для задач оптимизации, допускающих графовую интерпретацию.

Дата регистрации охранного документа:	09.01.2013
№ охранного документа:	2013610987
Автор(ы):	Михелев Владимир Михайлович, Великая Яна Геннадиевна, Егоров Денис Владимирович
№ заявки:	2012617907
Дата приоритета:	20.09.2012
Подразделение БелГУ:	Кафедра математического и программного обеспечения информационных систем
Охранный документ:	Загрузить