Реализация муравьиного алгоритма для решения задачи коммивояжера



Скачать 34.02 Kb.
Дата01.01.2013
Размер34.02 Kb.
ТипДокументы
Реализация МУРАВЬИНОГО АЛГОРИТМА для решения ЗАДАЧИ КОММИВОЯЖЕРА

А.С. Комаров

С.Ю. Ржеуцкая, научный руководитель, канд. техн. наук, доцент

Вологодский государственный технический университет

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

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

Для достижения поставленных целей в ходе исследования были решены следующие задачи:

  • изучение теории муравьиных алгоритмов

  • изучить алгоритм для задачи коммиявожера и детали реализации

  • изучение точного метода (метод ветвей и границ)

  • реализация на с++

  • создание визуализатора

  • экспериментальная оценка точности и быстродействия алгоритма;

Муравьиные алгоритмы основаны на имитации природных механизмов самоорганизации муравьев. Опишем основную идею алгоритма.

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

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

Задача о коммивояжере формулируется так: коммивояжер, выходящий из какого-нибудь города, желает посетить (n-1) других городом и вернуться к исходному пункту. Известны расстоянии между всеми этими городами. Требуется устновить, в каком порядке он должен посещать города, чтобы общее пройденное расстояние было миниальным.


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

Муравей - это программный агент, который является членом большой колонии. Муравей снабжается набором простых правил, которые позволяют ему выбирать путь в графе. Он поддерживает список узлов, которые он уже посетил. Таким образом, муравей должен проходить через каждый узел только один раз. Путь между двумя узлами графа, по которому муравей посетил каждый узел только один раз, называется путем Гамильтона.

Узлы в списке "текущего путешествия" располагаются в том порядке, в котором муравей посещал их. Позже список используется для определения протяженности пути между узлами. Настоящий муравей во время перемещения по пути будет оставлять за собой феромоны. В алгоритме муравья агент оставляет феромоны на ребрах графа после завершения путешествия.

Данный алгоритм был реализован на языке С++, для сравнения одновременно был реализован метод ветвей и границ. Проведенный эксперимент показал, что муравьиный алгоритм требует намного меньше ресурсов. Точный метод нашел кратчайший путь на графе с 29 вершинами за 4 минуты, оно равно 27600. А муравьиный алгоритм после определенной настройки его параметров смог найти решение 28040 за время меньше, чем 2 секунды. Это приблизительное решение, но оно не намного отличается от точного, и получается за несравнимо меньшее время. Если в графе больше 20 вершин, то точный метод ветвей и границ для своей работы требует слишком много ресурсов, а муравьиный алгоритм продолжает выдавать приблизительные решения за приемлемое время.

Одновременно эксперимент показал, что на работу муравьиного алгоритма очень сильно влияют регулируемые параметры, т.е. чтобы использовать муравьиный алгоритм, необходимо иметь опыт работы с ним. Такой положительный опыт был приобретен в ходе выполненного исследования.


  1. Штовба С. Д. Муравьиные алгоритмы. Exponenta Pro. Математика в приложениях, 2003, №4, стр. 70-75.

  2. МакКоннелл Дж. Основы современных алгоритмов. – М.: Техносфера, 2004. – 368 с.

Похожие:

Реализация муравьиного алгоритма для решения задачи коммивояжера iconПрименение нейросетевых методов для решения задачи коммивояжера
В настоящем сообщении излагаются результаты исследования возникающих при этом проблем и возможностей для модельной ситуации в случае...
Реализация муравьиного алгоритма для решения задачи коммивояжера iconЗадача коммивояжера Общее описани Методы решения задачи коммивояжера
Комбинаторика раздел математики, посвящённый решению задач выбора и расположения элементов некоторого, обычно конечного множества...
Реализация муравьиного алгоритма для решения задачи коммивояжера iconСравнение различных методов решения задачи коммивояжера на многопроцессорных системах
Необходимо найти такую последовательность посещения городов, при которой суммарная длина пути минимальна. Асимметричной называется...
Реализация муравьиного алгоритма для решения задачи коммивояжера iconПодготовка руки к письму для детей зпр
Способствовать развитию мыслительных операций: анализа, синтеза, сравнения, обобщения. Научить разным способам решения мыслительной...
Реализация муравьиного алгоритма для решения задачи коммивояжера iconГладкие приближения в задаче коммивояжера
Существующие алгоритмы нахождения точного решения сводятся, в сущности, к организации полного перебора вариантов. Несмотря на то,...
Реализация муравьиного алгоритма для решения задачи коммивояжера iconПрограмма по дисциплине программирование маслянкин В. И. Для очной формы обучения всего 260
Целью изучения дисциплины является изучение основ программирования, включая постановку задачи, выбор метода решения задачи, создание...
Реализация муравьиного алгоритма для решения задачи коммивояжера iconПрименение генетического алгоритма к решению задачи коммивояжёра студент гр. 07-иу-1 Степанов М. М. д т. н., доц. Новицкий В. О
Вот и транспортная задача не стала исключением. С возрастанием количества точек для развоза грузов переборные алгоритмы хотя и продолжают...
Реализация муравьиного алгоритма для решения задачи коммивояжера iconРазработка алгоритма и программного обеспечения для решения прикладной задачи теории графов
Тема: Разработка алгоритма и программного обеспечения для решения прикладной задачи теории графов
Реализация муравьиного алгоритма для решения задачи коммивояжера iconРазработка алгоритма решения задачи ортогональной упаковки прямоугольных объектов в двухмерный контейнер
Для решения np-трудной задачи ортогональной упаковки прямоугольных объектов в двухмерный контейнер предлагается эффективный метод...
Реализация муравьиного алгоритма для решения задачи коммивояжера iconИспользование алгоритмов муравьиных колоний при решении задач оптимизации календарного планирования
...
Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org