Алгоритм оптимизации Whale для решения задач с ограничениями в C++

Алгоритм оптимизации Whale для решения задач с ограничениями в C++

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

Исходный код этой статьи вы найдете на моем GitHub.

Алгоритм оптимизации кита (WOA)

Киты — изящные животные. Они считаются самыми большими животными в мире. Взрослый кит может достигать 30 метров в длину и 180 тонн веса. У этого огромного млекопитающего есть семь основных видов, в том числе убийца, полосатик, сей, горбатый, правый, плавниковый и синий. Большинство людей считают китов хищниками. Поскольку они должны дышать воздухом с поверхности океана, они не могут спать. На самом деле другая половина мозга спит. Удивительная особенность китов заключается в том, что они считаются очень умными, чувствующими животными (как и люди).
Одна из самых захватывающих вещей, которой посвящена эта статья, — это их
особый метод охоты. Этот метод называется методом кормления пузырьковой сетью. Горбатые киты охотятся на рыбу, создавая характерные пузыри по кругу, см. рисунок ниже.

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

Вот видео на YouTube, где эти необыкновенные животные могут вас вдохновить.

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

А. Окружение добычи

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

где A, C — векторы коэффициентов, X считается позицией. Вектор a инициализируется равным 2 и уменьшается во время выполнения оптимизации. Вектор r является случайным вектором [0,1].

Б. Метод атаки с помощью пузырчатой ​​сети (этап эксплуатации)

На этом этапе мы можем выделить два типа поведения. Один механизм сокращения окружности, в котором круг охоты уменьшается (пока мы запускаем алгоритм, процесс уменьшения происходит на каждой итерации). И вторая позиция обновления спирали,где обновляется расстояние между китом, расположенным
в точке ( X, Y ), и добычей, расположенной в точке ( X *, Y * ).

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

где (как в уравнении 1) и b — константа для определения формы логарифмической спирали, l — случайное число из [−1,1]

С. Поиск добычи (этап исследования)

Чтобы найти добычу, киты используют ту же стратегию, основанную на векторе А (разведка). На самом деле горбатые киты случайным образом ищут друг друга. Мы используем приведенное ниже уравнение обновления позиции, если A›1 (Eq3)

где p — случайное число из [0,1]. X_rand — это случайный вектор положения (случайный кит), выбранный из всей популяции.

Псевдокод можно изобразить следующим образом:

Как упоминалось выше, я использовал развернутый WOA на C++ для решения трех разных задач по оптимизации. Простая — это обычная квадратичная функция, которую я использовал для своей личной отладки.

Вторая проблема связана (проблема эталонной оптимизации) с пружиной растяжения/сжатия, где целью задачи является минимизация веса. Есть три конструктивных параметра: диаметр проволоки (d), средний диаметр катушки (D) и количество активных катушек (N). Это трехмерная задача (каждая переменная рассматривается как измерение).

Задачу оптимизации можно сформулировать следующим образом:

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

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

Целевая функция планировщика пути робота

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

где,

расстояние светлячок — препятствие,

• для планировщика 2D-пути

• для планировщика 3D-пути

расстояние светлячок — цель,

• для планировщика 2D-пути

• для планировщика 3D-пути

К1 и К2 – коэффициенты, взятые из статьи.

Оптимальные значения всех констант, изображенных в приведенных выше формулах, взяты из статьи, на которую я ссылаюсь.

Ниже я рисую пример при запуске планировщика пути.

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

//compile
g++ my_prog.cpp -o my_prog -I/usr/include/python3.8 -lpython3.8//

 //run
./my_prog

//folder tree

├── my_prog
├── my_prog.cpp
├── matplotlibcpp.h

Спасибо за чтение.