Кирюшина Е.Н., Козаченко А.А

Национальный горный университет, Украина

Роевой интеллект на основе естественных алгоритмов

В настоящее время активно развивается область робототехники, связанная с созданием мобильных роботов ( МР) различного назначения. Многие из них должны планировать и отрабатывать траектории своего движения к цели в условиях априорной неопределенности динамически изменяющейся естественной среды. Кроме того, МР могут контактировать не только с внешней средой, но и друг с другом, что также сможет влиять на принимаемые ими решения. Все вышеизложенное обобщается понятием групповой робототехники.[1]

Основные понятия

Роевой интеллект(англ. Swarm intelligence) описывает коллективное поведение многоагентной децентрализованной самоорганизующейся системы. Рассматривается в теории искусственного интеллекта как метод оптимизации. [2]

Относительно простые правила индивидуального поведения МР могут создавать сложное организованное поведение всего роя.

Интеллектуальный агент – в искусственном интеллекте рассматривается как разумная сущность, наблюдающая за окружающей средой и действующая в ней, при этом ее поведение рационально в том смысле, что она способна к пониманию и ее действия всегда направлены на достижение какой-либо цели. [3]

Существует несколько естественных алгоритмов, реализующих систему с роевым интеллектом. Практически все они были построены на основе наблюдений за поведением примитивных организмов и насекомых.

Муравьиные алгоритмы. [4]

Моделирует многоагентную систему. Назовем интеллектуальных агентов данной системы муравьями. Каждый из агентов имеет небольшое количество памяти для того, чтобы хранить список пройденных им узлов. Выбирая узел для следующего шага, муравей «помнит» об уже пройденных узлах и не рассматривает их в качестве возможных для перехода. На каждом шаге список запретов пополняется новым узлом, а перед новой итерацией алгоритма – то есть перед тем, как муравей вновь проходит путь – он опустошается. Также при выборе оптимального маршрута муравей руководствуется расстоянием между узлами и следом от феромонов муравьев, прошедших по этому маршруту ранее (т.е. его маркировкой). Пусть муравей находится в узле i , а узел j – это один из узлов, доступных для перехода: j є S_i . Обозначим вес ребра, соединяющего узлы i и j, как W_ij , а интенсивность феромона на нем – как t_ij . Тогда вероятность перехода муравья из i в j будет равна:

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

После того, как муравей успешно проходит маршрут, он оставляет на всех пройденных ребрах след, обратно пропорциональный длине пройденного пути:

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

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

Алгоритм роя частиц.

В 1995 году Джеймс Кеннеди (James Kennedy) и Рассел Эберхарт (Russel Eberhart) предложили метод для оптимизации непрерывных нелинейных функций, названный ими алгоритмом роя частиц [5] Разработанный ими алгоритм довольно прост и может быть реализован буквально в нескольких десятках строчек кода на любом высокоуровневом языке программирования. Он моделирует многоагентную систему, где агенты-частицы двигаются к оптимальным решениям, обмениваясь при этом информацией с соседями. Текущее состояние частицы характеризуется координатами в пространстве решений,а также вектором скорости перемещения. Оба этих параметра выбираются случайным образом на этапе инициализации. Кроме того, каждая частица хранит координаты лучшего из найденных ей решений, а также лучшее из пройденных всеми частицами решений.

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

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

Алгоритм роя частиц широко применяется в задачах машинного обучения (в частности, для обучения нейросетей и распознавания изображений), параметрической и структурной оптимизации в области проектирования. По эффективности он может соперничать с другими методами глобальной оптимизации, а низкая алгоритмическая сложность способствует простоте его реализации.

Алгоритм роя пчел.

Данный алгоритм моделирует поведение пчел в естественной среде. Идея пче-

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

Первым шагом в реализации МРП является выбор параметров, которые необходимо оптимизировать, и определение допустимого интервала для поиска оптимальных значений. Затем в допустимой области случайным образом располагаются пчёл, а также задаются векторы и скорости их движения. Затем каждая частица должна перемещаться через пространство решений, как если бы она была пчелой в рое. Алгоритм действует на каждую частицу отдельно, перемещая ее на небольшую величину, циклично двигая ее через весь рой. Следующие шаги выполняются для каждой частицы:

1.Оценка пригодности для частицы, сравнение с ПНП и ГНП. Функция пригодности, используя координаты частицы в пространстве решений, возвращает значение пригодности для текущей позиции. Если это значение больше, чем значение ПНП, соответствующее этой частице, или ГНП, тогда соответствующие позиции заменяются текущей позицией.

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

где:

— это скорость частицы в n-том измерении на предыдущем шаге,

x_n— это координата частицы в n-том измерении,

p_n — ПНП,

g_n — ГНП.

Расчет производится для каждого из N. Из этого уравнения видно, что новая скорость получается из старой скорости путем простого масштабирования на , и прибавления направления ГНП и ПНП для этого конкретного направления. C₁ и C₂ — это масштабные коэффициенты, которые определяют относительное взаимное «притяжение» к ПНП и ГНП. Они иногда рассматриваются как познавательный и социальный факторы. Функция случайных чисел rand() возвращает число в интервале между -1 и 1. В общем случае два появления функции rand() представляет собой два различных вызова функции. Большинство реализаций используют две независимые случайные величины для стохастического изменения относительного притяжения ГНП и ПНП. Это введение случайного элемента в оптимизацию предназначено для моделирования незначительного непредсказуемого компонента реального поведения роя. называют «инерционным весом» и это число (выбранное в интервале между 0 и 1) отражает в какой мере частица остается верной своему первоначальному курсу, не подвергшемуся влиянию ГНП и ПНП.

Метод роя пчёл можно эффективно распределить на несколько параллельных процессов, за счёт чего значительно увеличится его скорость.

Выводы

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

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

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

[1] Групповая робототехника. Википедия [Электронный ресурс]. Режим доступа: http://ru.wikipedia.org/wiki/Групповая_робототехника

[2]Роевой интеллект. Википедия [Электронный ресурс]. Режим доступа: http://ru.wikipedia.org/wiki/Роевой_интеллект

[3] Интеллектуальный агент. Википедия [Электронный ресурс]. Режим доступа: http://ru.wikipedia.org/wiki/Интеллектуальный_агент

[4] M. Dorigo, “Ottimizzazione, apprendimento automatico, ed algoritmi basati su metafora naturale (Optimization, Learning, and Natural Algorithms)”, диссертация на соискание ученой степени “Doctorate in Systems and Information Electronic Engineering”, Politecnico di Milano, 1992 г.

[5]J. Kennedy, R. C. Eberhart, “Particle swarm optimization” // In Proceedings of IEEE International Conference on Neural Networks, стр. 1942–1948, 1995 г.

[6] Курейчик В.В. Эволюционная оптимизация на основе алгоритма колонии пчёл / В.В. Курейчик, Е.Е. Полупанова. – 2009