XIII Международная студенческая научная конференция Студенческий научный форум - 2021

Введение:

Задача коммивояжера (ЗК) является одной из самых известных задач по комбинаторной оптимизации. Так как ЗК относится к NP-трудным задачам, то для неё не существует доказанного алгоритма, который решал бы её за полиномиальное время, выдавая при этом точное решение. ЗК имеет много применений на практике, особенно, в области транспортных компаний.

Цель работы:

Рассмотрение различных алгоритмов решения задачи коммивояжера.

Постановка задачи:

Коммивояжеру необходимо найти кратчайший маршрут, проходящий через все промежуточные пункты по одному разу с последующим возвратом в исходную точку, т.е. решение данной задачи - нахождение гамильтонова цикла.

Описание алгоритмов

Самым простым вариантом является алгоритм полного перебора (АПП). Его суть заключается в переборе всех вариантов и нахождения кратчайшего пути. Преимуществом является его результат - точное решение, недостатком - длительность вычислений при относительно небольшом пространстве поиска.

Метод ветвей и границ (МВиГ) заключается в разбиении множества всех замкнутых маршрутов на два непересекающихся подмножества с их последующим вычислением. Далее берется подмножество с минимальным значением и так же разбивается на два, вычисляется. Повторяя эти действия, мы получим замкнутый маршрут, удовлетворяющий наложенным ограничениям.

“Жадный” метод. Строится N-ое количество маршрутов, где N - количество городов. Исходный город равен номеру маршрута, все последующие города выбираются по принципу ближайшего. Данный метод часто используется для построения эталонного маршрута и его дальнейшего использования в других алгоритмах.

Метод включения дальнего (МВД). Основа МВД состоит в мысли, что два максимально удаленных города не могут находиться рядом в цепи (маршруте). С них и начинается построение: находится вершина, находящаяся наиболее далеко от двух городов, уже находящихся в цепи. Ищется минимальная сумма расстояний между найденной вершиной и парой смежных вершин в цепи. Такое решение не дает точного ответа, лишь приблизительное.

При решении задачи коммивояжера нередко заимствуют идеи у природы. Среди таких решений можно выделить генетический алгоритм (ГА) и муравьиный алгоритм (МА).

Генетический алгоритм (ГА) начинается с создания исходного множества альтернативных решений. Эти решения назовем “родительскими”. Затем совершаются комбинированные, случайные, направленные преобразования, создающие “потомственные” альтернативные решения. Оценивается их эффективность и проводится селекция. Лучшие решения копируются для дальнейшего поиска. Создаются наборы пар из получившихся множеств решений. К ним применяется кроссинговер для получения новых решений, которые вновь анализируются. Новые, наиболее подходящие решения, вытесняют старые, чтобы поддерживать постоянное число. Затем применяются различные операторы инверсии, мутации, транслокации, т.е. действия аналогичные природным. После проведенных действий решения вновь проводится оценка “потомков”, и на её основе принимается решение о продолжении алгоритма.

Муравьиный алгоритм (МА) основан на поведении муравьиной колонии, способный находить кратчайший путь к пище, используя феромон, который они оставляют на пройденном маршруте. Путь, на котором концентрация феромонов будет наибольшей, является оптимумом.

Для достижения результатов за меньшее количество времени разрабатываются новые методы, среди которых хорошее соотношение времени к результату демонстрируют гибридные алгоритмы. Среди них можно выделить BV-алгоритм, который использует эталонный маршрут, полученный в ходе использования “жадного” метода оптимизирует с помощью различных модификаторов. Также существуют гибридные алгоритмы, основанные на включении генетического алгоритма в муравьиный.

Заключение:
В данной работе были рассмотрены основные алгоритмы решения задачи коммивояжера, которые задействуют различные механизмы.

Список литературы:

Борознов В. О. Исследование эвристического метода решения задачи коммивояжера // Электронный журнал «Исследовано в России». - 2008. - С. 322-328.

Борознов Владимир Олегович Исследование решения задачи коммивояжера // Вестник АГТУ. Серия: Управление, вычислительная техника и информатика. 2009. №2. URL: https://cyberleninka.ru/article/n/issledovanie-resheniya-zadachi-kommivoyazhera (дата обращения: 15.12.2020).

Курейчик В. В. Решение задач о коммивояжере методами эволюционного моделирования // Известия ЮФУ. Технические науки. 2003. №2. URL: https://cyberleninka.ru/article/n/reshenie-zadach-o-kommivoyazhere-metodami-evolyutsionnogo-modelirovaniya (дата обращения: 15.12.2020).

А.С. Поляков Популяционный алгоритм решения задачи коммивояжера // Прикладная математика: современные проблемы математики, информатики и моделирования. 2020. №II. URL: https://cyberleninka.ru/article/n/populyatsionnyy-algoritm-resheniya-zadachi-kommivoyazhera (дата обращения: 15.12.2020).

Курейчик B. M., Курейчик B. B. Генетические алгоритмы в комбинаторно-логических задачах искусственного интеллекта // Известия ЮФУ. Технические науки. 1999. №3. URL: https://cyberleninka.ru/article/n/geneticheskie-algoritmy-v-kombinatorno-logicheskih-zadachah-iskusstvennogo-intellekta (дата обращения: 15.12.2020).

Мартынов Артём Владимирович, Курейчик Виктор Михайлович Гибридный алгоритм решения задачи коммивояжера // Известия ЮФУ. Технические науки. 2015. №4 (165). URL: https://cyberleninka.ru/article/n/gibridnyy-algoritm-resheniya-zadachi-kommivoyazhera (дата обращения: 15.12.2020).