СРАВНИТЕЛЬНЫЙ АНАЛИЗ ПРОСТОГО АЛГОРИТМА ПОИСКА КУКУШКИ И АЛГОРИТМА С ПОЛЕТАМИ ЛЕВИ

Ключевые слова: генетические алгоритмы, биоинспирированные алгоритмы, поиск кукушки, полеты Леви, методы оптимизации, целевая функция, многокритериальная оптимизация.

Введение

Алгоритм поиска кукушек (Cuckoo Search Algorithm, CSA) – метаэвристический алгоритм, разработанный в 2009 году Янгом, имитирующий поведение кукушек во время откладывания яиц, а именно в процессе вынужденного гнездового паразитизма.

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

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

В статье рассматривается простой алгоритм поиска кукушек и поиск кукушек с полетами Леви. Так же проведен сравнительный анализ этих алгоритмов.

1. Алгоритм поиска кукушек.

Алгоритм поиска кукушек ¬ это разновидность роевого алгоритма, который разработали Янг и Деб в 2009 году. Этот алгоритм основан на естественном поведении биологических кукушек, точнее, на их способности паразитировать на других видах птиц, откладывая свои яйца в их гнезда.

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

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

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

Известно несколько модификаций алгоритма поиска кукушек. Некоторые из них представлены на Рисунке 1.

Рисунок 1. Разновидности поиска кукушек (Cuckoo Search)

Далее несколько подробнее рассмотрены канонический алгоритм поиска кукушек и алгоритм поиска кукушек с полетами Леви.

2. Канонический алгоритм поиска кукушек

Псевдо-код алгоритма выглядит следующим образом:

инициализация популяции хозяйских гнезд H случайным образом

инициализация кукушки cuckoo случайным образом

определение GBest

пока не выполнится критерий остановки

случайным образом выбрать некоторое гнездо Hi

если f(cuckoo) > f(Hi)

заменяем яйцо в гнезде на яйцо кукушки

с вероятностью p удаляем некоторое число худших гнезд

строим вместо удаленных гнезд новые (столько же, сколько удалили)

обновить значение GBest

конец цикла

В данной схеме использованы следующие обозначения: GBest – лучшее найденное решение, f(cuckoo), f(H_i) – значения функции пригодности для кукушки cuckoo и для некоторого гнезда H_i. Стоит отметить, что для решения той или иной задачи данным алгоритмом необходимо подобрать следующие параметры: размер популяции, и вероятность обнаружения яйца кукушки хозяином гнезда p_a.

3. Алгоритм поиска кукушек с полетами Леви

Далее представлена схема алгоритма поиска кукушек [2].

инициализация популяции хозяйских гнезд H случайным образом

инициализация кукушки cuckoo случайным образом

определение GBest

пока не выполнится критерий остановки

выполнить перемещение кукушки с помощью полетов Леви

определить новые координаты кукушки

случайным образом выбрать некоторое гнездо Hi

если f(cuckoo) > f(Hi)

заменяем яйцо в гнезде на яйцо кукушки

с вероятностью p удаляем некоторое число худших гнезд

строим вместо удаленных гнезд новые (столько же, сколько удалили)

обновить значение GBest

конец цикла

На схеме использованы те же обозначения, что и раньше.

Полеты Леви кукушки реализуются по формуле:  , где x_c' и x_c – новые и старые координаты кукушки соответственно,  – случайная величина распределения Леви, и обычно полагают все компоненты вектора v одинаковыми и равными, то есть , причем |X| – размерность пространства. Также величина компоненты этого вектора v должна быть связана с масштабами поисковой области [6].

4. Сравнение работы алгоритмов

Алгоритмы сравнивались на одном и том же наборе тестовых функций, при одинаковых входных данных. Для сравнения были выбраны 4 сложных функции оптимизации – это функция Эгхолдера, функция Растригина, функция Швефеля и функция Михалевича. Для каждой функции было сделано 5 попыток.

Алгоритм, использующий полеты Леви, значительно быстрее и, зачастую, точнее находит оптимальное значение функции. Это можно объяснить крайне сложной формой исследуемых функций. Их конфигурация такова, что алгоритм, не использующий полеты Леви постоянно оказывается в локальном оптимуме. В то время как второй алгоритм может выбраться из локальной ямы при помощи полетов Леви. В таблице 1 приведены данные по обоим алгоритмам при испытании их на вышеперечисленных функциях.

Таблица 1

Значения целевой функции при поиске оптимума.

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

Заключение

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

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

1. M. Mareli An adaptive Cuckoo search algorithm for optimization / M. Mareli, B. Twala // Applied Computing and Informatics – 2018. Vol. 3. № 14. – P. 107–115.
2. D. Fister A comprehensive review of cuckoo search: variants and hybrids / D. Fister, I. Fister // Mathematical Modelling and Numerical Optimization – 2013. Vol. 4, No. 4. – P. 387–409.
3. Родзин C.И., Родзина Л.С. Биоинспирированный поиск решений: теория и приложения для обработки проблемно-ориентированных знаний в геоинформатике // Известия ЮФУ. Технические науки. – 2015. № 4. – С. 210 – 222.
4. Родзин С.И., Курейчик В.В. Теоретические вопросы и современные проблемы развития когнитивных биоинспирированных алгоритмов оптимизации (обзор) // Кибернетика и программирование. – 2017. - № 3. – С. 51 – 79.
5. Родзин С.И., Скобцов Ю.А., Эль-Хатиб С.А. Биоэвристики: теория, алгоритмы и приложения: монография – Чебоксары: ИД «Среда», 2019. – 224 с.