Дифференциальная эволюция для решения задач оптимизации в C++

Дифференциальная эволюция для решения задач оптимизации в C++

Дифференциальная эволюция (ДЭ) – это эволюционный алгоритм, вдохновленный теорией эволюции Дарвина, который широко изучался для решения оптимизационных и инженерных задач с момента его введения Сторном и Прайсом в 1997 году.
Алгоритм DE — это эволюционный алгоритм, который имитирует биологические эволюционные механизмы, такие как скрещивание хромосом, мутация и естественный отбор. Концепция напоминает генетический алгоритм, рассмотренный в моей предыдущей статье.
DE принадлежит к группе эволюционных алгоритмов. Алгоритм генерирует новые решения, рекомбинируя решения при определенных условиях, в отличие от других советников, которые создают новое решение, изменяя решения с масштабированными векторами разности.
Текущее индивидуальное решение будет заменено, если оно превосходит новое вычисленное решение. DE считается высокопроизводительным методом. Его также легко развернуть (здесь на C++) и оптимизировать, поскольку процесс регулируется несколькими специфическими для алгоритма параметрами, такими как коэффициент масштабирования M (для операций мутации) и скорость кроссовера (CR). ). Подобно генетическому алгоритму, DE создает новые решения с помощью трех механизмов: мутации, кроссовера и отбора.

Для ознакомления с алгоритмом я прочитал эту статью.

В этой статье я решаю проблемы со специфическими для роботов планировщиками пути в 2D- и 3D-пространстве (подробности ниже). Чтобы проверить производительность алгоритма, я проверил вывод, выполнив простую квадратичную функцию. Пожалуйста, взгляните на то, как реализована эта простая функция, и определите свою собственную.
Исходный код со всеми обсуждаемыми здесь реализациями (планировщик функций и путей в 2D и 3D-пространстве на C++ вы найдете на моем GitHub .

Операции дифференциальной эволюции

DE состоит из трех операций, которые можно изобразить следующим образом (выполняются в следующем порядке):

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

Кроссовер — на этом этапе компоненты мутанта и текущего «целевого вектора» (текущее положение) вероятностно пересекаются для создания пробного вектора. Целевой раствор может приобрести черты донорского раствора или мутанта благодаря этому процессу кроссовера. Коэффициент кроссовера (CR) со значением между [0,1] управляет методом универсального кроссовера.

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

В случае планировщика пути алгоритм DE оптимизирует положение робота, чтобы найти свободное от столкновений (2D- или 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

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