Аннотация
Иорданов Р.В., Завадская Т.В. Метаэвристический алгоритм летучих мышей для построения маршрута пути робота. Описаны обязательные правила поведения агентов в алгоритме летучих мышей. Определены этапы реализации алгоритма
Введение
Робототехника является наиболее прогрессирующей областью. С каждым годом ученые и инженеры находят новые пути для развития данной отрасли в хозяйстве, военном деле, медицине. Отдельной ветвью развития данной области является групповая робототехника [1].
Данная работа освящает проблему построения маршрута с обходом препятствий группой роботов, поведение которых описывается алгоритмом летучих мышей.
Постановка задачи
Алгоритм летучих мышей (Bat Algorithm, BA) был разработан Янгом (X.- Sh. Yang) в 2010 году [2]. BA является метаэвристическим алгоритмом, что позволяет ему быть непривязанным к конкретной задаче, в отличии от эвристических [3]. Данный алгоритм основывается на поведении коллективных животных (волки, птицы, рыбы, пч?лы ) и их способностям выживать в дикой природе.
Летучие мыши имеют совершенный эхолокационный аппарат, который позволяет им без труда находить добычу, препятствия и в полной темноте размещаться на насесте [4]. Они определяют расстояния до объекта, рассчитывая время между импульсом и его отражением.
В алгоритме летучих мышей обязательными являются следующие правила:
- Летучие мыши используют эхолокацию, чтобы определять расстояние, находить добычу, препятствия.
- Летучие мыши передвигаются случайным образом с некоторой скоростью vi, в позиции Si, c фиксированной частотой [fmax, fmin]. Регулируемыми параметрами являются: длина испускаемой волны λ, частота импульса r [0;1] и громкость a.
- Громкость меняется от максимального amax к минимальному (постоянному) amin [5].
Реализация
Рис. 1 – Блок-схема алгоритма летучих мышей
Работу алгоритма можно разделить на следующие этапы:
Этап 1: Инициализировать популяцию летучих мышей в позиции Si (i = 1,2 … n) и скорость vi.
Этап 2: Инициализировать частоту fi в позиции Si
Этап 3: Определить начальную частоту импульса ri и громкость ai.
Этап 4: Измерить расстояние между начальным и конечным значениями:
d = √(x2 - x1)2+(y2 - y1)2, где x1, y1 — координаты точки старта, x2, y2 — координаты точки финиша.
Этап 5: Вычислить частоту для новых решений через следующую формулу:
fi = fmin + (fmax — fmin) * U(0,1), где U — случайное число.
Этап 6: Обновить скорость и глобальное лучшее решение через следующие формулы:
где best — лучшее текущее решение.
Этап 7: Локальное лучшее решение для каждой из летучих мышей вычисляется следующим образом:
На этапе инициализации популяции летучих мышей начальные значения их громкости (a), частоты (f) и частоты импульса (r) представляется в виде значений на промежутках: [amin, amax], [fmax, fmin], [rmin, rmax]. Новое решение находится случайным полетом летучих мышей в границах предыдущего лучшего решения. После нахождения препятствия уменьшается громкость и увеличивается частота ультразвукового импульса [6].
Заключение
В работе был рассмотрен математический аппарат алгоритма летучих мышей для поиска маршрута пути робота. Этот алгоритм полностью описывает перемещение агентов в двумерном пространстве. Приведенное исследование в дальнейшем будет использовано для реализации алгоритма.
Список использованной литературы
1. Групповая роботехника. Интернет ресурс. Режим доступа: Материал из Википедии – свободной энциклопедии.
2. Частикова В.А., Новикова Е. Ф. Алгоритм летучих мышей для решения задачи глобальной оптимизации. – 2015. – С. 2.
3. Yogita Gigras, Kusum Gupta, Vandana, Kavita Choudhary. A Comparison between Bat Algorithm and
Cuckoo Search for Path Planning. – 2015. – С. 1—2.
4. Карпено А. П. Популяционные алгоритмы глобальной поисковой оптимизации. Обзор новых и малоизвестных алгоритмов. – 2012. – С. 20—24.
5. Yogita Gigras, Kusum Gupta, Vandana, Kavita Choudhary. A Comparison between Bat Algorithm and
Cuckoo Search for Path Planning. – 2015. – С. 5—8.
6. Карпенко А. П. Популяционные алгоритмы глобальной поисковой оптимизации. Обзор новых и малоизвестных алгоритмов. – 2012. – С. 24—28.