СТАТЬИ АРБИР
 

  2018

  Июль
  Август   
  Пн Вт Ср Чт Пт Сб Вс
30 31 1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30 31 1 2
   

  
Логин:
Пароль:
Забыли свой пароль?


Алгоритм летучих мышеи


АЛГОРИТМ ЛЕТУЧИХ МЫШЕИ

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

Ключевые слова: алгоритм летучих мышей, метаэвристика, поисковая оптимизация, роевой интеллект, искусственный интеллект

Многие алгоритмы нацеленные на решение задач поисковой оптимизации имеют аналоги в природе. Группа таких алгоритмов, инспирированных природой, известна под названием “метаэвристика”. Широко известной частью метаэвристики стали алгоритмы роевого интеллекта, которые описывают коллективное поведение децентрализованных самоорганизующихся многоагентных систем [1]. Термин «роевой интеллект» был выведен Херардо Бени и Ван Цзыном в 1989 году, в контексте системы клеточных роботов [2].

Алгоритм летучих мышей был описан Янгом (X - Sh.Yang) в 2010 году, а гармонический поиск и алгоритм роя частиц являются особыми случаями алгоритм летучих мышей [3]. Сам по себе алгоритм летучих мышей показывает отличные результаты в решении задач поисковой оптимизации.

Ниже представлена последовательность действий алгоритма летучих мышей.

Выбирается функция - F(x)= sin(x).

Выбирается количество агентов S, ie [0; S].

Случайным образом устанавливаем начальное положение агентов:

xe(xmm5 xmaxX xi=(x1,x2...xSX x=xmin (xmax—xmin) rand().

rand() - возвращает значения в интервале [0;1]

Задается начальная скорость для каждого агента: vi=(vbv2...vS), vi=v0.

Начальная частота wi=(w1,w2...wS), wi=wmin

Находится лучший агент. Значение xi подставляется в функцию F(X).

Ближайшее к экстремуму значение агента считается лучшим.

k - номер лучшего агента, x k=max(F(x)).

Агенты перемещаются на один шаг в соответствии с используемой миграционной процедурой.

Организуется выполнение итераций по n, ne[0;N].

Все агенты нумеруются по i, ie [0; S].

Вычисляются новые значения положения, скорости и частоты для агента - xIi, vIi и wIi.

Модифицируется частота:

wIi=wmin (wmax - wmin)*iandO.

Выполняется модификация скорости: vIi=viwi(x - xi), где (x - xi) -приближение всех агентов к лучшему.

Выполняется перемещение агента в соответствии с формулой: xIi=xivi.

Если E = rand(), то запускается процедура локального поиска (переход на шаг 16), иначе выполняется переход на шаг 21.

Процедура поиска в окрестности лучшего решения проводится с вероятностью Er. Полученное решение применяется в качестве нового текущего положения агента xi.

Все агенты нумеруются по i, ie [0; S].

Если поиск выполняется не в первый раз, то выполняется переход на шаг 19.

Иначе: вычисляется громкость:

ai=aba2...as); a’i=amin (amax - amin)*rand(), где aIi - новое значение громкости. и выполняется переход на шаг 18.

у?- а

Находится средняя громкость: asr = — (□ i=0a) / S.

Выполняется улучшение текущей позиции: xxIi = Xiasr*U[ - 1,1].

Функция U[ - 1,1] возвращает случайное значение в интервал [ - 1;1].

Процедура локального поиска выполняется до тех пор, пока агент не станет ближе к цели: F(xxi) F(xi).

Выполняется ограничение области поиска: xxi = max{xmin,xi},

xxi = min{xmax,xi}.

Проводится глобальный поиск: с вероятностью Ea проводится процедура глобального поиска в окрестности текущего решения для всех i - х агентов, iG [0; S].

Если F(x) F(xxi) и Earand(), то принимается новое решение: xi=xxi.

Если iS, то выполняется переход на шаг 22.

Выполняется ограничение области поиска для всех i - х агентов, iG [0; S].

Если xixmin, тогда: xi=xmin, Vi=Vo.

Если xixmax, тогда: xi=xmax, Vi=Vo.

Если iS, то выполняется переход на шаг 25.

Если nN, то выполняется переход на шаг 10.

После выполнения всех итераций в качестве ответа принимается значение x*.

Пример алгоритма реализованного на языке Java представлен на рис. 1.

Рис. 1 - результат работы программы алгоритма летучих мышей

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

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

ИЗВЕСТИЯ ВЫСШИХ УЧЕБНЫХ ЗАВЕДЕНИЙ СЕВЕРО - КАВКАЗСКИЙ РЕГИОН. 2015; 4: 22 - 27, ВАРИАНТ РЕАЛИЗАЦИИ РОЕВОГО АЛГОРИТМА ЛЕТУЧИХ МЫШЕЙ

Blum C., Rol, A. Metaheuristics in combinatorial optimization: Overview and conceptual comparison // ACM Computing Surveys. -2003. —№35 (3). -P. 268-308.

Карпенко А.П. Популяционные алгоритмы глобальной поисковой оптимизации. Обзор новых и малоизвестных алгоритмов // Приложение к журналу «Информационные технологии», №7,2012.

С.А. Пивоваров, Л.Л. Романов, А.С. Лазарев, 2017

ХИМИЧЕСКИЕ НАУКИ

УДК 504.054


С.А. Пивоваров Студент Факультета Информационных Технологий и Управления «Южно - Российский государственный политехнический университет (НПИ) имени М.И. Платова», г. Новочеркасск Л.Л. Романов Студент Факультета Информационных Технологий и Управления «Южно - Российский государственный политехнический университет (НПИ) имени М.И. Платова», г. Новочеркасск А.С. Лазарев Магистр Факультета Информационных Технологий и Управления «Южно - Российский государственный политехнический университет (НПИ) имени М.И. Платова», г. Новочеркасск





МОЙ АРБИТР. ПОДАЧА ДОКУМЕНТОВ В АРБИТРАЖНЫЕ СУДЫ
КАРТОТЕКА АРБИТРАЖНЫХ ДЕЛ
БАНК РЕШЕНИЙ АРБИТРАЖНЫХ СУДОВ
КАЛЕНДАРЬ СУДЕБНЫХ ЗАСЕДАНИЙ

ПОИСК ПО САЙТУ