Метод АСО для решения задач оптимизации

Размещено на http://www.allbest.ru/

МЕТОД АСО ДЛЯ РЕШЕНИЯ ЗАДАЧ ОПТИМИЗАЦИИ

Акименко Ангелина Сергеевна - студент,

кафедра информационных технологий, строительный факультет, Санкт-Петербургский государственный архитектурно-строительный университет, г. Санкт-Петербург

Аннотация

На сегодняшний день активно разрабатываются методы, включающие в себя природные механизмы. Natural Computing - «Природные вычисления» - научное направление, объединяющее математические и компьютерные методы с работой естественной системы флоры и фауны. Данное направление помогает найти наилучшее решение при работе со сложными оптимизационными задачами. Одним из таких методов является Ant Colony Algorithms - муравьиные алгоритмы, которые пользуются большой популярностью среди ученых всего мира и входят в класс «роевого интеллекта». Данные алгоритмы способствуют решению множества сложных комбинаторных задач, таких как: задача коммивояжёра, транспортные задачи, задачи полихромии графов, задачи о назначениях, распределениях и других.

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

Abstract

THE ACO METHOD FOR THE SOLUTION OF PROBLEMS OF OPTIMIZATION

Akimenko Angelina Sergeevna - Student,

DEPARTMENT OF INFORMATION TECHNOLOGIES, CONSTRUCTION FACULTY,

SAINT-PETERSBURG STATE UNIVERSITY OF ARCHITECTURE AND CIVIL ENGINEERING, SAINT-PETERSBURG

Today the methods that include natural mechanisms are actively developed. Natural Computing - "Natural calculations" - the scientific direction uniting mathematical and computer methods with work of natural system of flora and fauna. This direction helps to find the best solution during the work with difficult optimizing tasks. One of such methods is Ant Colony Algorithms - ant algorithms which enjoy wide popularity among scientists of the whole world and enter a class of "swarm intelligence". These algorithms promote the solution of a set of difficult combinatory tasks, such as: the commercial traveler task, transport tasks, graph polychromy problems, tasks about appointments, distributions and others. Keywords: ant algorithm, stages of an ant algorithm, commercial traveler task.

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

Моделируя подобный процесс на графе, ребра которого будут являться различными маршрутами на пути к цели для прохождения муравьев, получим наиболее концентрированный путь [2]. Именно он станет решением для задачи, полученным методом муравьиных колоний.

Муравьиный алгоритм включает следующие основные этапы [3]:

1. Задаем начальный уровень феромона, который должен будет находиться на пути.

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

3. Для определения маршрута движения, по формуле (1) рассчитываем вероятность перехода из i-ой точки в j-ую:

(1)

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

4. Чтобы получить новую информацию о количестве феромона на пути, пройденного агентом, используем формулу (2):

, (2)

где с - сила испарения, Q/Lk(t) - феромон, откладываемый k-м муравьем.

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

Для реализации метода рассмотрим задачу коммивояжера для n городов, составленную в среде MATLAB [4]. Программа осуществляет процедуру поиска кратчайшего пути и использует основные принципы, какие использует муравьи при поиске пищи. Роль муравьев выполняют агенты, несущие в себе информацию о состоянии пройденных каналов. На своем пути муравей оставляет феромоновый след, который существует в окружающей среде некоторое время, а затем исчезает. Следовательно, муравьи со временем будут использовать путь, на котором большее количество феромона. Через некоторый промежуток времени агенты будут следовать по одному оптимальному пути.

К тому же, возможно задание таких параметров, как: б, в - регулируемые параметры, определяющие вес ребра и уровень феромонов при выборе пути (при б = 0 алгоритм вырождается в жадный, т.к. выбор ближайшей вершины производится без учёта количества феромона, при в = 0 выбор основывается только на величине феромона, не учитывается длина пути); с - параметр, контролирующий интенсивность испарения феромона и позволяющий избегать бесконечного накапливания феромонов на рёбрах, чтобы алгоритм не «забывал» полученные до этого плохие решения; Q - константа, искусственно добавляющая феромон.

Проведем эксперимент, посмотрим, как будет меняться время для поиска оптимального пути муравьям, при изменении параметра, отвечающего за испарение феромона (см. Таблица 1). Значения б, в, Q не изменялись, им присвоены значения 1, 1 и 10 соответственно.

Таблица 1. Исследование на поиск оптимального пути

математический компьютерный алгоритм задача

Исходя из данных таблицы (Таблица 1), можно сделать вывод, что при малом испарении феромона, время поиска оптимального пути проходит дольше и за большее число итераций соответственно, чем при значениях выше. Но при максимальном значении, агенты проходят один круг и не более, так как феромон испаряется за круг прохода, муравьи будут проходить тот же путь, но он не оптимальный. Наилучший путь в данном исследовании равен 274 (Рисунок 1).

Рис. 1. Оптимальный путь

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

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

1. Кажаров А.А. Использование шаблонных решений в муравьиных алгоритмах. / А.А. Кажаров, В.М. Курейчик // Известия Южного федерального университета. Технические науки, 2013. № 7 (144). С. 17-22.

2. Ватутин Э.И. Анализ результатов применения алгоритма муравьиной колонии в задаче поиска пути в графе при наличии ограничений / Э.И. Ватутин, В.С. Титов // Известия Южного федерального университета. Технические науки, 2014. № 12 (161). С. 111-120.

3. Ватутин Э.И. Об одном подходе к использованию алгоритма муравьиной колонии при решении задач дискретной комбинаторной оптимизации / Э.И. Ватутин, В.С. Титов // Интеллектуальные и информационные системы (Интеллект 2015). Тула, 2015. С. 8-13.

4. Штовба С.Д. Муравьиные алгоритмы. Математика в приложениях / С.Д. Штовба // Exponenta Pro.

Размещено на Allbest.ru