Источник алгоритма
Миржалили, Сейедали и Эндрю Льюис. «Алгоритм оптимизации кита. Достижения в инженерном программном обеспечении, vol. 95, 14 января 2015 г., стр. 51–67., https://doi.org/10.1155/2817. По состоянию на 20 сентября 2022 г.»
Хотя киты могут жить поодиночке или группами, чаще всего их наблюдают группами. Некоторые виды китов, например косатки, всю жизнь живут в семье. Для горбатых китов эта групповая динамика приводит к интересному поведению при охоте или поиске пищи, включая несколько тактик окружения больших косяков криля у поверхности океана. Алгоритм оптимизации китов (WOA) использует это биологическое поведение для решения сложных многомерных задач оптимизации.
В этом посте WOA представлен и кратко обсуждается. Алгоритм реализован на C++, а демонстративное использование дано посредством оптимизации функций Растригина и Сферы. Алгоритм быстро и эффективно оптимизирует эти функции, обеспечивая превосходную аппроксимацию их фактических минимальных значений.
Алгоритм оптимизации кита
Как упоминалось выше, алгоритм оптимизации китов — это биологический алгоритм, который использует преимущества охотничьего поведения горбатых китов. При охоте на криль (или косяки другой мелкой рыбы) у поверхности океана горбатый кит использует два основных маневра:
- Восходящие спирали, при которых киты ныряют вниз и создают форму пузырчатой спирали вокруг добычи, когда они снова всплывают.
- Двойные петли включают в себя три отдельных подэтапа: i) петли загона — восходящие спирали, которые загоняют добычу, ii) лобохвосты — шлепанье хвоста кита по поверхности океана (также известное как двуустка), и iii) петли захвата - второй выпад вверх для захвата загнанной добычи.
Эти операции определены математически ниже.
Окружение добычи
Для начала рассмотрим окружение добычи(восходящие спирали). Для тех, кто знаком с основами алгоритмов обучения, окружение добычи является эксплуатацией поведением. Горбатые киты будут распознавать косяки добычи и окружать их, для нашей популяции «китов» расположение косяков рыб (объект оптимизации) неизвестно, так как это оптимальное решение. Поэтому наши горбатые киты будут использовать расположение ближайшего к добыче кита, т.е. того кита, который минимизирует или максимизирует целевую функцию. Это заставляет популяцию алгоритмов двигаться к оптимальному значению.
Математически это достигается с помощью следующего набора уравнений:
Здесь A и C — векторы коэффициентов (вычисляются ниже), X* — вектор положения наилучшего решения, полученного на данный момент (наилучшее кит), X — это вектор положения обновляемого кита, а оператор периода . — это поэлементное умножение.
Векторы коэффициентов A и C вычисляются следующим образом.
где a линейно уменьшается от 2 до 0 в ходе итераций, а r — случайный вектор в [0,1].
Метод атаки Bubble-Net
Атака пузырчатой сетью является продолжением фазы эксплуатации. Поскольку горбатые киты плавают вокруг добычи по сужающемуся спиралевидному пути, для имитации этого типа атаки необходимы два подхода: сжимающееся окружение и спиралевидное обновление.
Для имитации первого вектор a (определенный выше) уменьшается на каждой итерации. Поскольку A зависит от a, вектор A также уменьшается на каждой итерации. Установка значений A на значения в [-1, 1] означает, что новое положение агента может быть где угодно между китом и текущим положением лучшего кита.
Для имитации спирального обновления рассчитывается расстояние между китом (X, Y) и добычей (X*, Y*). Следующее спиральное уравнение создается между положением кита и положением добычи, чтобы имитировать спиралевидное движение горбатых китов.
где b — константа, определяющая форму спирали (параметр алгоритма), а l — случайное число в диапазоне [-1, 1].
В природе оба эти действия происходят одновременно, в симуляции этого сделать нельзя. Вместо этого каждая отдельная операция, обновление спирали и сокращение окружности, происходят в алгоритме с вероятностью 50%. То есть,
где p — случайное значение в диапазоне [0, 1].
Поиск добычи
Затем WOA должен обрабатывать фазу исследования, типичную для алгоритмов обучения. Это делается через поиск симуляции добычи. Эта фаза алгоритма очень похожа на фазу эксплуатации, на которой киты перемещаются (случайным образом) ближе к текущему лучшему решению. Разница заключается в выборе кита, к которому будет приближаться текущий агент. На этапе исследования поиска добычи текущий кит выберет случайного эталонного кита и приблизится к его местоположению. Приведенные ниже уравнения описывают это поведение и почти такие же, как в фазе окружения добычи.
Здесь X_rand — это случайно выбранный агент, а другие переменные и операции определены, как указано выше.
Алгоритм
На этом фоне WOA определяется ниже.
1. Initialize the whale population
2. Calculate fitness of each whale and find X_best (the best agent)
while( t < maximum number of iterations )
for each search agent:
Update a, A, C, l, and p
if(p < 0.5):
if(|A|<1):
Update current agent via Encircling Prey
else:
Select a random agent (X_rand)
Update current agent via Search for Prey
else:
update search agent via Bubble-net Attacking
endfor
Amend the position of whales that are outside the search space
Calculate the fitness of each search agent
Determing new X_best (if need be)
t = t+1
endwhile
return X_best
В исходной статье приведен алгоритм выше для WOA. В приведенной ниже реализации была добавлена еще одна функция, позволяющая сократить расчет, если мы найдем оптимальное решение на ранней стадии выполнения (или если мы застрянем в долине). Одним из параметров алгоритма является значение UNCHANGED_ITERS. Если приспособленность лучшего кита (X_best) не изменилась за это количество итераций, алгоритм замыкается накоротко, и возвращается текущий лучший кит.
Выполнение
Реализация C++ разбита на два основных компонента: класс Whale, в котором хранятся данные о членах популяции китов, и файл WOA, содержащий некоторые вспомогательные функции и логику алгоритма оптимизации.
Китовый класс
Для начала нам нужно какое-то место для хранения информации, относящейся к индивидууму в нашей популяции, то есть китам. Это достигается с помощью класса Whale с помощью приведенного ниже кода.
Как видно из приведенного выше кода, объект Whale очень прост. По сути, все, что нам нужно от китов, — это способ вычисления, обновления и хранения местоположений и пригодности людей (update_postion, set_fitness, get_fitness, get_position), функциональность чтобы удерживать китов в проблемной области (amend_bounds) и, в качестве тонкости, способ определить, где в настоящее время находится кит и насколько близко он находится к добыче (оптимальное решение) ( распечатать). Эти методы и их реализации приведены выше.
Важным выводом является то, что кит будет хранить nмерное местоположение,где n зависит от решаемой проблемы, а значение приспособленности это позволяет алгоритму (а иногда и другим китам) знать, насколько он близок к оптимальному решению. Изначально положение кита устанавливается в какое-то случайное место в нашем домене, так создается начальная популяция. После выбора случайного местоположения вычисляется начальное значение пригодности. Все это происходит в функции Whale::initialize и выполняется для всех китов в популяции.
Алгоритм
Затем алгоритм оптимизации, определенный выше, реализуется на C++. Кроме того, по всей реализации разбросаны ссылки на функциональность matplotlibcpp. Я написал больше об этом в предыдущем сообщении в блоге. Для тех, кто не заинтересован в отображении данных (что в основном было сделано для этой записи в блоге), ссылки на matplotlibcpp и plt:: могут быть удалены из приведенной ниже логики, чтобы избавиться от этой зависимости.
Как показано выше, WOA принимает набор параметров, которые можно обновить в коде, чтобы изменить поведение алгоритма.
- POPULATION_SIZE: количество китов (агентов), используемых в алгоритме.
- DIMENSION: количество свободных переменных (т. е. входных данных для фитнес-функции).
- MAX_ITERS: максимальное количество итераций, прежде чем алгоритм остановится.
- UNCHANGED_ITERS: количество итераций, на которых алгоритм «застревает» на конкретном лучшем решении. После такого количества итераций алгоритм даст сбой.
- MAXPOS: определяет границы области поиска.
- MINPOS: определяет границы области поиска.
- B: спиральный коэффициент
- A_DEGRADE: деградация переменной a в ходе итераций.
Функции оптимизации и оптимальные решения
Для тестирования ВОА использовались два алгоритма: функция Растригина и сферическая функция. Функция Растригина определяется математически как
и имеет минимум, когда все x_i равны 0, т.е. когда
Внешний вид этой функции показан ниже.
Как видно здесь, функция Растригина содержит много пиков и впадин, что дает широкие возможности для функции оптимизации застрять на субоптимальных минимумах и максимумах, что делает ее хорошим тестом для алгоритмов оптимизации.
Вторая функция, используемая для проверки алгоритма, — это функция сферы, определяемая математически как
а также иметь минимум, когда все x_i = 0, или
График для этой функции, показанный ниже, очень похож на график функции Растригина, самое большое отличие заключается в отсутствии «бугристой» поверхности, которая вместо этого является гладкой.
Реализации этих функций можно увидеть в лямбда-функциях, содержащихся в woa.cpp.
Полученные результаты
Как показано в приведенном выше коде, фитнес-функции хранятся как лямбда-функции в коде C++, чтобы легко переключаться между ними. Код повторяется ниже.
Выполнение приведенного выше кода с использованием функции пригодности сферы быстро находит минимальное значение в (0,0,0), как показано на графике ниже.
На этом графике показаны итерации (ось x) и значение функции пригодности для лучшего кита. Минимальное значение функции сферы равно 0 в точке (0, 0, 0). WOA находит это значение очень быстро, прибл. 25 итераций, и алгоритм замыкается примерно после 175 итераций (он был настроен на выполнение не более 500 итераций). На GIF-изображении ниже мы видим, как популяция китов ищет оптимальное решение.
Этот GIF показывает значения X и Y для лучшего кита (лучшее положение кита) по мере выполнения алгоритма. Как видно здесь, киты очень быстро приближаются к оптимальному решению. Графики координат (X, Z) и (Z, Y) очень похожи.
Далее мы проверим алгоритм на фитнес-функции Растригина.
Результаты для этой функции очень похожи на результаты для функции пригодности сферы. График ниже показывает, что WOA требуется больше времени, чтобы найти минимальное значение функции, но снова происходит короткое замыкание через прибл. 150 итераций.
Опять же, построение двумерного среза наилучшего положения кита во времени показывает, что популяция китов очень быстро оттачивает оптимальное решение.
Заключение
В этом посте представлен алгоритм оптимизации китов (WOA), а операции определены математически. Объясняется алгоритм и предоставляется реализация на C++. Были описаны две выбранные фитнес-функции, сфера и Растригин, и WOA использовался для определения оптимальных решений для обеих функций. Как видно из раздела «Результаты», WOA быстро находит оптимальные решения для этих двух функций. Было бы интересно посмотреть, как WOA работает с другими, более сложными функциями пригодности, чтобы определить, является ли алгоритм жизнеспособной заменой другим алгоритмам оптимизации.
Поддержите мой контент, став участником Medium или совершив покупку на Amazon, чтобы стать лучшим программистом на C++ или узнать больше об алгоритмах оптимизации.
