МУРАВЬИНЫЙ АЛГОРИТМ ДЛЯ ПОЛНОЙ И НЕПОЛНОЙ ПОСТАНОВОК ЗАДАЧИ

ANT ALGORITHMS FOR COMPLETE AND INCOMPLETE STATEMENTS OF PROBLEMS

Irina Tokareva

student of Saint Petersburg State University,

Russia, Saint Petersburg

Anastasya Goncharova

phD in Physical-mathematical sciences, assistant professor of Saint Petersburg State University,

Russia, Saint Petersburg

Elena Sergeeva

teacher, Head of Student Scientific Society of St. Petersburg state budgetary professional educational institutions “College of the Water Resources”,

Russia, Saint Petersburg

АННОТАЦИЯ

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

ABSTRACT

The article deals with the traveling salesman problem and researching of the speed this problem’s solution in complete and incomplete statement using ant algorithm. Solutions research was conducted at a different number of vertices and the distance matrix with different number of ways in this matrix of distances.

Ключевые слова: муравьиный алгоритм; задача коммивояжера; полная и неполная постановки задачи.

Keywords: ant algorithm; traveling salesman problem; complete and incomplete statements of problem.

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

Каждый муравей устроен довольно примитивно: он может реагировать на окружающую среду и осуществлять прямой или непрямой обмен информацией с другими муравьями. Прямой обмен включает в себя визуальные и химические контакты. Непрямым обменом является взаимодействие, при котором один муравей каким-то образом изменяет часть окружающей среды, а позже другие муравьи используют эту информацию. Было установлено, что этот обмен осуществляется с помощью феромона – специального химического вещества, откладываемого муравьями; его концентрация определяет предпочтительность движения по данному пути.

В 1992 году Марко Дориго [5] предложил использовать идею непрямого взаимодействия муравьев для решения оптимизационных задач.

В настоящий момент с их помощью получены хорошие результаты для оптимизации таких задач, как задача раскраски графа, задача оптимизации сетевых графиков и другие [1-3].

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

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

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

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

Муравьиный алгоритм. В простом муравьином [2] алгоритме, использованном в данной статье, рассматривается колония из  муравьев ( –количество вершин в графе), в начальный момент времени находящихся в разных вершинах графа.

Вероятность перехода муравья из вершины  вершину  задается следующим образом:

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

Количество феромона на ребре описывается следующим выражением:

где  – параметр, имеющий значение порядка длины оптимального пути,  – длина маршрута . Испарение феромона задается в виде:

где  – коэффициент испарения, .

Приведем псевдокод простого муравьиного алгоритма:

1. Ввод матрицы расстояний .

2. Инициализация параметров ,,  и .

3. Инициализация ребер: присвоение длины  и начальной концентрации феромона .

4. Цикл по времени жизни колонии .

5. Цикл по всем муравьям .

6. Построить маршрут  на основе распределения вероятности по ребрам (1) и рассчитать длину .

7. Сравнить  и . В случае, если  - наименьшее из них, обновленить  и .

8. Инициализация .

9. Цикл по всем ребрам графа.

10. Обновить следы феромона на ребре в соответствии с (2) и (3).

11. Конец цикла по ребрам.

12. Конец цикла по муравьям.

13. Конец цикла по времени.

14. Вывести кратчайший маршрут  и его длину .

Экспериментальные исследования. Для решения поставленной задачи была создана программа в среде разработки VisualStudio C#. Внешняя оболочка программы представлена на рисунке 1.

Экспериментальные исследования проводились для матрицы расстояний, заполненной на 100%, 75%, 50% и 25%, и различного количества вершин (от 5 до 50).

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

Рисунок 1. Внешний вид программы «Муравьиный алгоритм»

Также из графика видно, что это время зависит от количества вершин нелинейно. Для установления данной зависимости была проведена аппроксимация графиков полиномом с помощью программы Microsoft Excel. Были получены следующие результаты:

1) для матрицы, заполненной на 100%, уравнение зависимости времени от количества вершин имеет вид:

2) для матрицы, заполненной на 75%, уравнение этой зависимости имеет вид:

3) для матрицы, заполненной на 50%, уравнение этой зависимости имеет вид:

4) для матрицы, заполненной на 25%, уравнение этой зависимости имеет вид:

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

Заключение. В работе приведена постановка задачи коммивояжера в полном и неполном случаях, на основе муравьиного алгоритма. Произведена программная реализация данного алгоритма. Проведены исследования зависимости времени работы программной реализации от числа вершин и заполненности матрицы расстояний. Найдено, что чем меньше заполнена эта матрица, тем меньше время работы программы, приведены уравнения зависимости времени работы программной реализацииот количества вершин для матриц расстояний, заполненных на 25%, 50%, 75% и 100%.

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

1. Гончарова А. Б., Поборчий И. В. Исследование методов решения задачи коммивояжера при управлении транспортными потоками предприятия. // Процессы глобальной экономики. Сборник научных трудов XX Всероссийской научно-практической конференции с международным участием. 2016, с.318-324
2. Егоров Д. В. Решение оптимизационной задачи коммивояжера с использованием интеллектуального муравьиного алгоритма. // Научное сообщество студентов XXI столетия. Технические науки: сборник статей по математике IV международной студенческой научно-практическая конференция №4. URL: http://sibac.info/archive/technik/4.pdf (Дата обращения: 16.12.2016)
3. Кажаров А. А., Курейчик В. М. Муравьиные алгоритмы для решения транспортных задач. // Известия РАН. Теория и системы управления, 2010, № 1, с. 32-45
4. Чураков М., Якушев А. Биологические принципы поведения муравьиной колонии. // http://rain.ifmo.ru/cat/data/theory/unsorted/ant-algo-2006/article.pdf (Дата обращения: 18.12.2016)
5. Dorigo Marco, Optimization, learning and natural algorithms. Ph. D. Thesis, Politecno di Milano, Italy, 1992