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

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

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

Введение

Актуальность темы исследования. За последние несколько лет не малый интерес возрос к природным алгоритмам, в которых объедены математические методы, в которые заложен принцип природного механизма принятия решения. Эти механизмы обеспечивают эффективную адаптацию флоры и фауны к окружающей среде на протяжении нескольких миллионов лет.

Цель исследования. Разработка, средствами высокоуровнего языка программирования Borland Delphi, программного продукта для решения задачи коммивояжера.

          Задачи исследования.

• Изучить применение муравьиного алгоритма для задачи коммивояжера.
• Разработать интерфейс и структуру программы.
• Реализовать средствами Borland Delphi муравьиный алгоритм для задачи коммивояжера.
• Провести вычислительные эксперименты.

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

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

Объём и структура исследования.

     Статья состоит из введения, двух глав, заключения.

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

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

 

 

Глава1. Муравьиный подход к задаче коммивояжера.

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

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

 

где m – количество муравьёв в колонии, а есть коэффициент испарения.

   Опишем три составляющих поведения муравьёв при выборе пути.

1. Память муравья. Обозначим через список городов, которые необходимо посетить муравью k, находящемуся в городе i.

         2. Зрение муравья. Видимость есть эвристическое желание посетить город j, если муравей находится в городе i.

,где - расстояние между городами.

3. Виртуальный след феромона на ребре (i,j) – подтверждающий желание муравья посетить город j из города i на  основании опыта других муравьёв. Сформулируем вероятностно-пропорциональное правило, определяющее вероятность перехода k-ого муравья из города i в город j:

       (1)

  Где α, β – параметры, задающие веса следа феромона, а количество феромона на ребре (i,j) в момент времени t . При α =0 алгоритм вырождается до жадного алгоритма (будет выбран ближайший город). Обратим внимание, что правило (1) определяет лишь вероятности выбора того или иного города. Собственно выбор города осуществляется по принципу «колеса рулетки».

 После завершения маршрута каждый муравей k откладывает на ребре (i j) такое количество феромона:

где T_k (t) - маршрут, пройденный муравьем k на итерации t;

L_k (t) - длина этого маршрута;

Q - регулируемый параметр, значение которого выбирают одного порядка с длиной оптимального маршрута

 

 

Глава 2. Реализация в псевдокоде муравьиного алгоритма  для задачи коммивояжера.

Муравьиный алгоритм для задачи коммивояжера был запрограммирован  в среде Borland Delphi .

Был задан взвешанный граф с пятью вершинами(т.е. пять городов и пять муравьёв), таблица расстояний между вершинами и таблица интенсивности феромона:

    

 

После нажатия  кнопки «Подсчёт» получили список вершин 1-4-2-3-5 и кратчайший путь равный 25, а также изменилась таблица интенсивности феромона:

 

 

 

Заключение

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

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