Базовый муравьиный алгоритм. Система муравьиных колоний. Параметры муравьиных алгоритмов

1.

Национальный исследовательский ядерный университет
МИФИ
Кафедра 42 «Криптология и кибербезопасность»
Базовый муравьиный алгоритм. Система
муравьиных колоний. Параметры
муравьиных алгоритмов.
Исполнитель:
студенты гр. Б18-505
Преподаватель:
д.т.н., профессор
НИЯУ МИФИ / Москва / 19 марта 2022
www.kaf42.mephi.ru, info@kaf42.ru
Шаханова Д.С.
Шувалов А.К.
Борзунов Г.И.

2.

Введение
Термины используемые в рамках муравьиных алгоритмов:
Cтигметрия - разнесенное во времени взаимодействие, при
котором одна особь изменяет некоторую область окружающей
среды, а другие особи используют эту информацию в процессе
решения задачи;
Феромон - определенный след который порождает
асинхронную и непрямую схему коммуникации, где муравьи
передают информацию друг другу.
2 из 10

3.

Движение муравьев с точки зрения вероятности
Вероятность выбора моста в момент времени t
где c - степень "привлекательности" неисследованной ветви, и a
определяет смещение при использовании феромона в процессе
выбора варианта решения.
- правило выбора
пути
3 из 10

4.

Простой (базовый) муравьиный алгоритм
Поиск кратчайшего пути между двумя узлами графа G = (V, E)
Где V - множество узлов, E - матрица связей между узлами, n_g - число узлов, L^k длина пути в графе, пройденного k-м муравьем, Tij - значение феромона между
вершинами i и j.
Вероятность перехода
Отложение феромона
Концентрация феромона
4 из 10

5.

Псевдокод простого МА
5 из 10

6.

Результаты компьютерных экспериментов
Эксперименты показали, что [2]:
1. ПМА работает хорошо для очень маленьких графов и в большинстве
случаев находит кратчайший путь;
2. Для больших графов характеристики ухудшаются, алгоритм становится
менее стабильным и более чувствительным к выбору параметров;
3. Сходимость к кратчайшему пути хорошая при малом числе муравьев, в
то время как большое количество муравьев часто ведет к тому, что
процесс поиска не сходится;
4. Эффект испарения более важен для сложных графов. В этом случае при
const=0 (нет испарения) алгоритм часто не сходится. С другой стороны,
если феромон испаряется слишком быстро (большие значения const),
алгоритм часто сходится к субоптимальным решениям;
5. При малых значениях алгоритм в основном сходится к кратчайшему
пути. Для сложных задач (высокой размерности) большое значение
ведет к плохой сходимости.
6 из 10

7.

Муравьиная система
Вероятность перехода из i-ой вершины в j-ю
Вероятность перехода в МС отличается от МА тем, что:
1. В МС используется балансировка влияния интенсивности
феромона и эвристической информации;
2. Введено множество допустимых вершин для k-ого муравья.
Испарение феромона в МС происходит аналогично МА.
7 из 10

8.

Модификации вычисления количества феромона
8 из 10

9.

Система муравьиных колоний
Правило перехода
9 из 10

10.

Система муравьиных колоний
10 из 10

11.

Параметры муравьиных алгоритмов
11 из 10

12.

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

13.

Вывод
Достоинства
Недостатки
Наилучшая эффективность при решении задач
комивояжора
Затруднителен теоретический анализ
1) В результате последовательности случайных (не
независимых) решений;
2) Распределение вероятностей меняется при
итерациях;
3) Исследование больше экспериментальное,
нежели теоретическое.
Опираются на память обо всей колонии вместо
памяти только о предыдущем поколении, в
сравнении с ГА
Сходимость гарантируется, но время сходимости не
определено
Меньше подвержены неоптимальным начальным
решениям (из-за случайного выбора пути и памяти
колонии) (в сравнении с ГА)
Обычно необходимо применение дополнительных
методов таких, как локальный поиск
Поддерживают динамическое изменение
параметров
Сильно зависят от настроечных параметров, которые
подбираются только исходя из экспериментов
13 из 10