Алгоритм распространения земляники в задачах глобальной оптимизации

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

Биологические основы

Некоторые растения (такие как земляника) могут размножаться при помощи ползущих стеблей, побегов.

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

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

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

Затем, целевая (объектная) функция оценивается в точках, образованных побегами и корнями, и половина из этих точек, которые имеют более высокие фитнес-значение, отбираются, например, при помощи метода рулетки, или элитарного отбора, и в дальнейшем рассматриваются, как материнские растения в следующие итерации. Оставшаяся часть растений «погибает». Эта процедура повторяется, пока не удовлетворится условие выхода из цикла.

Математическое описание алгоритма

Чтобы решить задачу оптимизации, сначала сгенерируем случайных точек в области рассмотрения проблемы. Каждую назовем материнским растением. Затем на каждой итерации, каждое материнское растение генерирует две случайные точки: одну очень близко к себе, и другую далеко от себя. Ближняя и дальняя точки моделируют корни и побеги соответственно. Корни используются для поиска вокруг локации материнского растения, а побеги используются для поиска в локациях далеко от него. С этого момента побеги играют очень важную роль для перемещения от одного локального минимума к другому, эффективно позволяя алгоритму избежать «ловушки» в этой точке.

В алгоритме распространения земляники представляет собой расположение j-го материнского растения в i-й итерации

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

 

Размещено: 10.12.2016