Анализ алгоритма, инспирированного поведением роя жуков-светляков
ART 86767
С.
А. ПивоваровБиблиографическое описание статьи для цитирования:
Пивоваров
С.
А.,
Романов
Л.
Л.,
Мохов
В.
А. Анализ алгоритма, инспирированного поведением роя жуков-светляков // Научно-методический электронный журнал «Концепт». –
2016. – Т. 11. – С.
3646–3650. – URL:
http://e-koncept.ru/2016/86767.htm.
Аннотация. Авторы статьи занимаются задачами исследования популяционных алгоритмов. В данной работе выполнен анализ алгоритма, вдохновлённого поведением роя жуков-светляков. Для выполнения экспериментов и последующего анализа за основу был взят алгоритм, созданный Кришнанандом (Krishnanand) и Госе (Ghose).Реализация алгоритма выполнена на языке программирования Java. В качестве источников, которые были исследованы для выполнения работы, выступили несколько статей отечественных и зарубежных авторов, а также интернет-ресурсы, находящиеся в открытом доступе.
Текст статьи
Романов Леонид Леонидович,
Студент Факультета Информационных Технологий и Управления «ЮжноРоссийский государственный политехнический университет (НПИ) имени М.И. Платова», г. Новочеркасск
Пивоваров Сергей Александрович, Студент Факультета Информационных Технологий и Управления «ЮжноРоссийский государственный политехнический университет (НПИ) имени М.И. Платова», г. Новочеркасск
Мохов Василий Александрович,Доцент кафедры «Программное обеспечение вычислительной техники» Факультета Информационных Технологий и Управления «ЮжноРоссийский государственный политехнический университет (НПИ) имени М.И. Платова», г. Новочеркасскmokhov_v@mail.ru
Анализ алгоритма инспирированного поведениемроя жуковсветляков
Аннотация.Авторы статьи занимаются задачами исследования популяционных алгоритмов. В данной работе выполнен анализ алгоритма, вдохновлённого поведением роя жуковсветляков. Для выполнения экспериментовипоследующего анализа за основу был взят алгоритм, созданный Кришнанандом(Krishnanand) и Госе (Ghose).Реализацияалгоритмавыполнена на языке программирования Java. В качестве источников, которые были исследованы для выполнения работы, выступили несколько статей отечественных и зарубежных авторов, а также интернетресурсы, находящиеся в открытом доступе.
Ключевые слова:популяционные алгоритмы, оптимизация, фитнесс функция, люциферин.
В последние годы широкое практическое применение нашли популяционные (роевые) алгоритмы [1, 2, 3]. В данной работе уделяется внимание рассмотрению алгоритма роя жуковсветляков (glowworm swarm optimization). Идея указанного алгоритмапредложена Кришнанадом (Krishnanand) и Госе(Ghose).Как и в светлячковом алгоритме[4], менее яркий жуксветляк перемещается к более яркому. При этом яркость определяется количеством люцефирина(люминесцентного вещества), котороевычисляется на основе функции цели. Позиция каждого жукасветляка в пространстве соответствует решению. Алгоритм состоит из двух фаз: модификацииколичества люциферина и движения. В течениидвижения каждый жуксветляк полагается только на локальную информацию[5]. На заключительных итерациях множество жуковсветляков сходится к одному или нескольким оптимумам[6, 7].Авторами был реализован алгоритм жуковсветляков для оптимизации числовых функций. Рассмотрим более детально шаги данного алгоритма.Перечень используемых переменных, с их обозначениями внутри алгоритма и описанием назначений, представлен в табл. 1.
Таблица №1Параметры алгоритма
№ОбозначениеОписание1xminМинимальное значение области поиска2xmaxМаксимальное значение области поиска3��Вектор позиции4���Вероятность движения одного жука к другому 5ݎ�Инициализация радиуса окрестности6ݎ0Начальный радиус7݈0Начальная яркость8nТекущее значение итерации9kНомер жука светляка10݇∗Лучший жуксветляк по функции цели11gСвободный параметр12��Окрестность для kго жука светляка13|��|Размер текущей окрестности14݈�Количество люциферина15yСвободный член алгоритма для яркости16pСвободный член алгоритма17mДлина вектора позиции светлячка18δПараметр для генерации новой позиции (P<δ1)19βПараметр определения радиуса окрестности (P<β1)20ρПараметр определения уровня люциферина
Схема реализованного авторами алгоритма представлена на рис. 1 и описана ниже в виде последовательности действий.
Рис. 1 Схема алгоритма роя жуковсветляков
1.Задание параметров β и nUдля определения радиуса окрестности; параметра для генерации новой позиции, параметров для определения уровня люциферина , параметра для определения начального уровня люциферина, начального радиуса окрестности.2.Задание максимального числа итераций N, размера популяции K,длины вектора позиции светлячка M, минимальных и максимальных значений для вектора позиций.3.Задание функции цели.F(x)→min, где xвектор позиции жукасветляка.4.Создание случайным образом вектора лучшей позиции.
x=(x1, …,xM), xj=xjmin+(xjmaxxjmin)rand(),гдеrand()функция возвращающая равномерно распределённое случайное число в диапазоне [P,1].5.Создание исходной популяции P.6.Создание случайным образом вектора позицииxk.
xk=(xk1, …,xkM), xkj=xjmin+(xjmaxxjmin)rand().7.Инициализация количества люциферина lk.
lk=l0.8.Инициализация радиуса окрестности rk.
rk=r0.9.Модификация количества люцефипина.
lk=(1−ρ)lk+γF(xk), k∉ 1,K̅̅̅̅̅.10.Миграция жуковагентов (перемещение).11.Создание окрестности для kго жукасветляка.
Uk={m|||xm−xk||rk,lklm, m∈1,K̅̅̅̅̅}.
12.Вычисление вероятности движения одного жука к другому.Pkm=lm−lk∑(ls−lk)s∈Uk, m∈1,K̅̅̅̅̅.13.Выбор номера жукасветляка.
Если ∑Pksс−1s=1<ݎ���()≤∑Pkscs=1, то m=c.
14.Модификация позиции жукасветляка.xk=xk+δxm−xk||xm−xk||.
15.Модификация радиусаокрестности.rk=min{rmax,max{rmin,rk+β(nU−|Uk|)}},где |Uk|размер текущей окрестности.16.Определениелучшего жукасветляка по функции цели.݇∗=argmin F(xk).17.Если F(xk)F(�∗), то �∗=xk.18.Вывод результата
�∗.
Интерфейсреализованной программыс результатами работы алгоритмапредставленниже на рис.2 и рис.3.Для проведения опытов были использованы две действительные функции:f(x)=sin�и f(x)=−2x2+11x−9 (рис.2и рис.3).
Рис. 2 Результаты исследования функции�(�)=ݏ���
На рис.2представлены результаты поиска в интервале от 2 до 1P радиан для функцииf(x)=sin(x). Положение агентов в момент последней итерации показано на графике в виде кружков.
Рис. 3 Результаты исследования функции�(�)=−�+�−�
На рис.3аналогичным образом представлены результаты исследования функции f(x)=−2x2+11x−9.
Все исходные данные, такие какколичество агентов, начальный радиус окрестности, начальная яркость светлячка, количество итераций, начальная скорость и вид функции движениязадаются программно, как представлено на рис.4.
Рис.4фрагмент исходного кода программы с заданными значениями параметров алгоритма
В табл.2приведены результаты опытных измерений времени, затрачиваемого программой на расчёт наилучшего агента. Данные измеренийсобраны дляразных значенийколичестваагентов впопуляций, итераций, а так же для двух различных функции.Измерения приведены в секундах.Таблица №2Результаты измерений времени
В табл.3 приведены результаты опытных измерений значения абсолютной погрешности при различном количестве итераций, количестве агентов. Здесьнагляднопредставлены значенияпогрешностидля лучшего агента.
№КоличествоитерацийФункцииРазмер популяции510152050100110f(x)=sin(x)6.2311.5117.0622.8651.07103.29f(x)=2�2+11x+94.8011.4517.0622.4155.48111.95220f(x)=sin(x)10.8622.0731.1341.3101.62205.09f(x)=2�2+11x+911.2321.8133.4944.48110.49222.15350f(x)=sin(x)12.925.5337.0950.56125.72252.64f(x)=2�2+11x+912.9226.0834.3851.08127.65249.424100f(x)=sin(x)26.5350.8375.92101.2253.36504.62f(x)=2�2+11x+9 26.9349.1478.6497.32254.11510.17
Таблица №3Результаты измерений значения абсолютной погрешности№КоличествоитерацийФункцииРазмер популяции510152050100110f(x)=sin(x)0.0570.02740.01430.01280.00050.001f(x)=2�2+11x+90.0440.02290.0090.01400.00340.004220f(x)=sin(x)0.0210.02790.02560.01450.00450.000f(x)=2�2+11x+90.0240.01410.04240.00310.00390.003350f(x)=sin(x)0.0120.00090.01230.01000.01280.001f(x)=2�2+11x+90.1280.0060.0190.02130.00150.1634100f(x)=sin(x)0.0390.0130.01140.03390.00230.010f(x)=2�2+11x+90.0210.00710.01560.10640.00010.213
Приведённые результаты измерений указывают на то, что при увеличении количества агентов и итераций, время работы алгоритма увеличивается. Однако, это практически не влияет на погрешностьполученных результатов. Даже при размере популяции в 1P агентов и при 1P итерациях погрешность очень мала и равна P.P274, что сравнимо по эффективности с алгоритмом летучих мышей[8].К положительным сторонам можно отнести высокую точность получаемых результатов. К отрицательным качествам относится длительное время работыалгоритма при совсем не критичных значениях количества итераций и размером популяций. Наиболее важнойвыявленной особенностью алгоритма является зависимость между люцеферином и радиусом окрестностископления агентов
жуков. Эта зависимость проявляется в том, что при увеличении люцеферина уменьшается радиус поиска и при этом увеличивается точность работы алгоритма.
Ссылки на источники1.КубилВ.Н.; Мохов В.А. К вопросу о применении роевого интеллекта в решении задач транспортной логистики // Проблемы модернизации инженерного образования в России : сб. науч. статей по проблемам высшей школы / Юж.Рос. гос. политехн. унт (НПИ) Новочеркасск : ЮРГПУ(НПИ), 2P14. С. 14P144.2.Гринченков Д.В.; Мохов В.А., Пивоваров С.А., Романов Л.Л. Вариант реализации роевого алгоритма летучих мышей // Изв. вузов. Сев.Кавк. регион. Техн. науки 2015. № 4. С. 2227.3.Кубил В.Н.; Мохов В.А. Применение муравьиного алгоритма в задачах многокритериальной оптимизации с изменяющимися условиями [Электронный ресурс] // Информационнотелекоммуникационные системы и технологии : сб. материалов Всерос. науч.практ. конф., г. Кемерово, 1617 окт. 2P1U г. / Кузбасский гос. техн.унт им. Т.Ф. Горбачева Кемерово, 2P1U. Режим доступа : http://sibscience.ru/page/ITSIT2015/ITSIT/1Informacionnyesistemyvnauke/1080.pdf.4.Метаэвристики: монография / Ю.А. Скобцов, Е.Е. Федоров. Донецк: Издво «Ноулидж» (Донецкое отделение), (2P13). 5.Современные Алгоритмы Поисковой Оптимизации: Алгоритмы, вдохновленные природой / А.П. Карпенко. Москва: Издательство МГТУ им. Н.Э. Баумана,(2P14).6.Популяционные алгоритмы глобальной поисковой оптимизации. Карпенко А.П.Приложение к журналу «Информационные Технологии» (№7/2P12).7.P.K. Krus, J. Ölvander (Andersson) "Performance index and metaoptimization of a direct search optimization method" // Engineering Optimization, 20138.Мохов В.А.; Туровская Е.В., ТуровскийФ.А. Анализ бинарного алгоритма летучих мышей при решении задач дискретной оптимизации // Новая наука: от идеи к результату : Междунар. науч. период. издание по итогам Междунар. науч.практ. конф., 29 декабря 2P1U г. : в 3 ч. / Агенство международных исследований Стерлитамак : РИЦ АМИ, 2P1U. Ч. 3. С. 1P1103.
Студент Факультета Информационных Технологий и Управления «ЮжноРоссийский государственный политехнический университет (НПИ) имени М.И. Платова», г. Новочеркасск
Пивоваров Сергей Александрович, Студент Факультета Информационных Технологий и Управления «ЮжноРоссийский государственный политехнический университет (НПИ) имени М.И. Платова», г. Новочеркасск
Мохов Василий Александрович,Доцент кафедры «Программное обеспечение вычислительной техники» Факультета Информационных Технологий и Управления «ЮжноРоссийский государственный политехнический университет (НПИ) имени М.И. Платова», г. Новочеркасскmokhov_v@mail.ru
Анализ алгоритма инспирированного поведениемроя жуковсветляков
Аннотация.Авторы статьи занимаются задачами исследования популяционных алгоритмов. В данной работе выполнен анализ алгоритма, вдохновлённого поведением роя жуковсветляков. Для выполнения экспериментовипоследующего анализа за основу был взят алгоритм, созданный Кришнанандом(Krishnanand) и Госе (Ghose).Реализацияалгоритмавыполнена на языке программирования Java. В качестве источников, которые были исследованы для выполнения работы, выступили несколько статей отечественных и зарубежных авторов, а также интернетресурсы, находящиеся в открытом доступе.
Ключевые слова:популяционные алгоритмы, оптимизация, фитнесс функция, люциферин.
В последние годы широкое практическое применение нашли популяционные (роевые) алгоритмы [1, 2, 3]. В данной работе уделяется внимание рассмотрению алгоритма роя жуковсветляков (glowworm swarm optimization). Идея указанного алгоритмапредложена Кришнанадом (Krishnanand) и Госе(Ghose).Как и в светлячковом алгоритме[4], менее яркий жуксветляк перемещается к более яркому. При этом яркость определяется количеством люцефирина(люминесцентного вещества), котороевычисляется на основе функции цели. Позиция каждого жукасветляка в пространстве соответствует решению. Алгоритм состоит из двух фаз: модификацииколичества люциферина и движения. В течениидвижения каждый жуксветляк полагается только на локальную информацию[5]. На заключительных итерациях множество жуковсветляков сходится к одному или нескольким оптимумам[6, 7].Авторами был реализован алгоритм жуковсветляков для оптимизации числовых функций. Рассмотрим более детально шаги данного алгоритма.Перечень используемых переменных, с их обозначениями внутри алгоритма и описанием назначений, представлен в табл. 1.
Таблица №1Параметры алгоритма
№ОбозначениеОписание1xminМинимальное значение области поиска2xmaxМаксимальное значение области поиска3��Вектор позиции4���Вероятность движения одного жука к другому 5ݎ�Инициализация радиуса окрестности6ݎ0Начальный радиус7݈0Начальная яркость8nТекущее значение итерации9kНомер жука светляка10݇∗Лучший жуксветляк по функции цели11gСвободный параметр12��Окрестность для kго жука светляка13|��|Размер текущей окрестности14݈�Количество люциферина15yСвободный член алгоритма для яркости16pСвободный член алгоритма17mДлина вектора позиции светлячка18δПараметр для генерации новой позиции (P<δ1)19βПараметр определения радиуса окрестности (P<β1)20ρПараметр определения уровня люциферина
Схема реализованного авторами алгоритма представлена на рис. 1 и описана ниже в виде последовательности действий.
Рис. 1 Схема алгоритма роя жуковсветляков
1.Задание параметров β и nUдля определения радиуса окрестности; параметра для генерации новой позиции, параметров для определения уровня люциферина , параметра для определения начального уровня люциферина, начального радиуса окрестности.2.Задание максимального числа итераций N, размера популяции K,длины вектора позиции светлячка M, минимальных и максимальных значений для вектора позиций.3.Задание функции цели.F(x)→min, где xвектор позиции жукасветляка.4.Создание случайным образом вектора лучшей позиции.
x=(x1, …,xM), xj=xjmin+(xjmaxxjmin)rand(),гдеrand()функция возвращающая равномерно распределённое случайное число в диапазоне [P,1].5.Создание исходной популяции P.6.Создание случайным образом вектора позицииxk.
xk=(xk1, …,xkM), xkj=xjmin+(xjmaxxjmin)rand().7.Инициализация количества люциферина lk.
lk=l0.8.Инициализация радиуса окрестности rk.
rk=r0.9.Модификация количества люцефипина.
lk=(1−ρ)lk+γF(xk), k∉ 1,K̅̅̅̅̅.10.Миграция жуковагентов (перемещение).11.Создание окрестности для kго жукасветляка.
Uk={m|||xm−xk||rk,lklm, m∈1,K̅̅̅̅̅}.
12.Вычисление вероятности движения одного жука к другому.Pkm=lm−lk∑(ls−lk)s∈Uk, m∈1,K̅̅̅̅̅.13.Выбор номера жукасветляка.
Если ∑Pksс−1s=1<ݎ���()≤∑Pkscs=1, то m=c.
14.Модификация позиции жукасветляка.xk=xk+δxm−xk||xm−xk||.
15.Модификация радиусаокрестности.rk=min{rmax,max{rmin,rk+β(nU−|Uk|)}},где |Uk|размер текущей окрестности.16.Определениелучшего жукасветляка по функции цели.݇∗=argmin F(xk).17.Если F(xk)F(�∗), то �∗=xk.18.Вывод результата
�∗.
Интерфейсреализованной программыс результатами работы алгоритмапредставленниже на рис.2 и рис.3.Для проведения опытов были использованы две действительные функции:f(x)=sin�и f(x)=−2x2+11x−9 (рис.2и рис.3).
Рис. 2 Результаты исследования функции�(�)=ݏ���
На рис.2представлены результаты поиска в интервале от 2 до 1P радиан для функцииf(x)=sin(x). Положение агентов в момент последней итерации показано на графике в виде кружков.
Рис. 3 Результаты исследования функции�(�)=−�+�−�
На рис.3аналогичным образом представлены результаты исследования функции f(x)=−2x2+11x−9.
Все исходные данные, такие какколичество агентов, начальный радиус окрестности, начальная яркость светлячка, количество итераций, начальная скорость и вид функции движениязадаются программно, как представлено на рис.4.
Рис.4фрагмент исходного кода программы с заданными значениями параметров алгоритма
В табл.2приведены результаты опытных измерений времени, затрачиваемого программой на расчёт наилучшего агента. Данные измеренийсобраны дляразных значенийколичестваагентов впопуляций, итераций, а так же для двух различных функции.Измерения приведены в секундах.Таблица №2Результаты измерений времени
В табл.3 приведены результаты опытных измерений значения абсолютной погрешности при различном количестве итераций, количестве агентов. Здесьнагляднопредставлены значенияпогрешностидля лучшего агента.
№КоличествоитерацийФункцииРазмер популяции510152050100110f(x)=sin(x)6.2311.5117.0622.8651.07103.29f(x)=2�2+11x+94.8011.4517.0622.4155.48111.95220f(x)=sin(x)10.8622.0731.1341.3101.62205.09f(x)=2�2+11x+911.2321.8133.4944.48110.49222.15350f(x)=sin(x)12.925.5337.0950.56125.72252.64f(x)=2�2+11x+912.9226.0834.3851.08127.65249.424100f(x)=sin(x)26.5350.8375.92101.2253.36504.62f(x)=2�2+11x+9 26.9349.1478.6497.32254.11510.17
Таблица №3Результаты измерений значения абсолютной погрешности№КоличествоитерацийФункцииРазмер популяции510152050100110f(x)=sin(x)0.0570.02740.01430.01280.00050.001f(x)=2�2+11x+90.0440.02290.0090.01400.00340.004220f(x)=sin(x)0.0210.02790.02560.01450.00450.000f(x)=2�2+11x+90.0240.01410.04240.00310.00390.003350f(x)=sin(x)0.0120.00090.01230.01000.01280.001f(x)=2�2+11x+90.1280.0060.0190.02130.00150.1634100f(x)=sin(x)0.0390.0130.01140.03390.00230.010f(x)=2�2+11x+90.0210.00710.01560.10640.00010.213
Приведённые результаты измерений указывают на то, что при увеличении количества агентов и итераций, время работы алгоритма увеличивается. Однако, это практически не влияет на погрешностьполученных результатов. Даже при размере популяции в 1P агентов и при 1P итерациях погрешность очень мала и равна P.P274, что сравнимо по эффективности с алгоритмом летучих мышей[8].К положительным сторонам можно отнести высокую точность получаемых результатов. К отрицательным качествам относится длительное время работыалгоритма при совсем не критичных значениях количества итераций и размером популяций. Наиболее важнойвыявленной особенностью алгоритма является зависимость между люцеферином и радиусом окрестностископления агентов
жуков. Эта зависимость проявляется в том, что при увеличении люцеферина уменьшается радиус поиска и при этом увеличивается точность работы алгоритма.
Ссылки на источники1.КубилВ.Н.; Мохов В.А. К вопросу о применении роевого интеллекта в решении задач транспортной логистики // Проблемы модернизации инженерного образования в России : сб. науч. статей по проблемам высшей школы / Юж.Рос. гос. политехн. унт (НПИ) Новочеркасск : ЮРГПУ(НПИ), 2P14. С. 14P144.2.Гринченков Д.В.; Мохов В.А., Пивоваров С.А., Романов Л.Л. Вариант реализации роевого алгоритма летучих мышей // Изв. вузов. Сев.Кавк. регион. Техн. науки 2015. № 4. С. 2227.3.Кубил В.Н.; Мохов В.А. Применение муравьиного алгоритма в задачах многокритериальной оптимизации с изменяющимися условиями [Электронный ресурс] // Информационнотелекоммуникационные системы и технологии : сб. материалов Всерос. науч.практ. конф., г. Кемерово, 1617 окт. 2P1U г. / Кузбасский гос. техн.унт им. Т.Ф. Горбачева Кемерово, 2P1U. Режим доступа : http://sibscience.ru/page/ITSIT2015/ITSIT/1Informacionnyesistemyvnauke/1080.pdf.4.Метаэвристики: монография / Ю.А. Скобцов, Е.Е. Федоров. Донецк: Издво «Ноулидж» (Донецкое отделение), (2P13). 5.Современные Алгоритмы Поисковой Оптимизации: Алгоритмы, вдохновленные природой / А.П. Карпенко. Москва: Издательство МГТУ им. Н.Э. Баумана,(2P14).6.Популяционные алгоритмы глобальной поисковой оптимизации. Карпенко А.П.Приложение к журналу «Информационные Технологии» (№7/2P12).7.P.K. Krus, J. Ölvander (Andersson) "Performance index and metaoptimization of a direct search optimization method" // Engineering Optimization, 20138.Мохов В.А.; Туровская Е.В., ТуровскийФ.А. Анализ бинарного алгоритма летучих мышей при решении задач дискретной оптимизации // Новая наука: от идеи к результату : Междунар. науч. период. издание по итогам Междунар. науч.практ. конф., 29 декабря 2P1U г. : в 3 ч. / Агенство международных исследований Стерлитамак : РИЦ АМИ, 2P1U. Ч. 3. С. 1P1103.
