Как использовать дифференциальную эволюцию в Python Scipy

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

• Что такое дифференциальная эволюция
• Модуль scipy.optimize
• Стратегия
• Параллельная дифференциальная эволюция
• Ограничения
• Границы

Что такое дифференциальная эволюция

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

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

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

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

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

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

Модуль scipy.optimize

Модуль scipy.optimize имеет метод Different_evolution(), который находит глобальный минимум многомерной функции.

Синтаксис:

scipy.optimize.differential_evolution(func, bounds, strategy='best1bin', maxiter=1000, popsize=15, tol=0.01, mutation=(0.5, 1), recombination=0.7, seed=None, callback=None, disp=False, polish=True, init='latinhypercube', atol=0, updating='immediate', workers=1, constraints=(), x0=None, *, integrality=None, vectorized=False)

Где параметры:

• func (callable): цель — минимизировать целевую функцию. Должен иметь форму f(x, *args), где args — это кортеж всех дополнительных фиксированных параметров, необходимых для полного объяснения функции, а x — это входные данные в форме одномерного массива. N равно len по параметрам(x).
• bounds (последовательность): для переменных — границы. Границы можно указать одним из двух способов: 1. Экземпляр класса Bounds. 2.(min, max) пары, которые определяют конечные нижнюю и верхнюю границы аргумента оптимизации func для каждого элемента в x. Количество параметров N рассчитывается из суммы границ.
• Strategy (string): метод использования дифференциальной эволюции, должно быть одним из: «best1bin», «best1exp», «rand1exp», «randtobest1exp», «currenttobest1exp», «best2exp», «rand2exp», «randtobest1bin», «currenttobest1bin», «best2bin», «rand2bin», ‘ранд1бин’.
• maxiter (int): максимальное количество поколений, в течение которых может развиваться вся популяция.(maxiter + 1) * popsize * N — максимальное количество вычислений функции, которое можно выполнить(без полировки).
• popsize (int): множитель для определения общей численности населения. В популяции имеется popsize * N человек. Если ключевое слово init используется для предоставления начальной популяции, этот термин игнорируется. Размер популяции определяется путем взятия следующей степени двойки после popsize * N при использовании init=’sobol’.
• tol (float): когда решатель достигает относительного допуска для сходимости, np.std(pop) = atol + tol * np.abs(np.mean(энергия населения)), где и atol и tol — соответствующие абсолютные и относительные значения. допуски.
• mutation (число с плавающей запятой или кортеж): мутагенная константа. Термин «дифференциальный вес» также используется в литературе и обозначается буквой F. Если указано число с плавающей запятой, следует использовать диапазон [0, 2]. Дизеринг используется, когда значение задано в виде кортежа(мин, макс). Для каждого поколения сглаживание случайным образом изменяет константу мутации. Для генерации U[min, max] используется для расчета константы мутации. Сходимость можно значительно ускорить с помощью дизеринга. Хотя это замедлит конвергенцию, увеличение константы мутации расширит горизонт поиска.
• recombination (float): диапазон [0, 1] должен быть константой рекомбинации. В литературе это также называется вероятностью пересечения и обозначается буквой CR. Увеличение этого значения позволяет большему количеству мутантов выжить в следующем поколении, но делает это за счет стабильности популяции.
• seed: Numpy.random используется, если семя имеет значение None(или np.random). Он использует синглтон RandomState. Если начальное число является целым числом, создается новый экземпляр RandomState и заполняется этим начальным значением. Экземпляр Generator или RandomState используется, если начальное число уже имеет его. Для повторной минимизации укажите начальное значение.
• disp (bool): на каждой итерации печатает оцененную функцию.
• обратный вызов: функция для отслеживания процесса минимизации. Лучшим ответом на данный момент был xk. val представляет собой дробное значение конвергенции генеральной совокупности. Функция останавливается, когда val больше 1. Когда обратный вызов возвращает True, минимизация прекращается(любая полировка все еще выполняется).
• Polish (boolean): если True(по умолчанию), лучший член совокупности полируется в конце с использованием метода L-BFGS-B, который может незначительно улучшить минимизацию. Подход «доверие-конструкция» используется вместо него при исследовании ограниченной проблемы.
• init (string, array_data): указывает тип выполняемой инициализации населения. должно быть одним из: «латинский гиперкуб», «соболь», «халтон», «случайный».
• atol (float): при достижении абсолютного допуска конвергенции np.std(pop) = atol + tol * np.abs(np.mean(энергия населения)), где atol и tol — соответствующие абсолютные и относительные допуски, проблема не может быть решена.
• updating (отложенное, немедленное): если «немедленно», вектор оптимального решения обновляется неоднократно в течение одного поколения. В результате конвергенция может произойти быстрее, поскольку пробные векторы могут выиграть от постоянного развития идеального результата. Вектор наилучшего решения обновляется один раз в каждом поколении, когда выбран этот параметр. Единственный вариант, совместимый с распараллеливанием или векторизацией, — это «задержка», которую можно переопределить с помощью рабочих и векторизованных ключевых слов.
• workers (int или подобные карте): популяция разделяется на рабочие части и оценивается параллельно(с использованием многопроцессорной обработки), если рабочие являются целым числом. Бассейн). Чтобы использовать все ядра ЦП, укажите -1. В качестве альтернативы предоставьте вызываемый объект, напоминающий карту, например многопроцессорность. Pool.map используется для одновременной оценки популяции. Эту оценку выполняют рабочие (func, iterable). Если worker!= 1, этот параметр заменит ключевое слово обновления на update=’deferred’. Если Workers!= 1, этот параметр имеет приоритет над ключевым словом Vectorized. Это также требует, чтобы func можно было мариновать.
• constraints (баундс, LinearConstraint, NonLinearConstraint): дополнительные ограничения, налагаемые на решатель, помимо тех, которые налагаются границами kwd. использует стратегию Лампинена.
• x0 (array_like или None): вначале дает приблизительную оценку минимизации. Этот вектор занимает место начального (лучшего) члена после инициализации популяции. Даже если init задана начальная популяция, эта замена все равно выполняется. Форма == x0(N,).
• Integrity (1-D массив): логическое значение, указывающее, ограничена ли переменная решения целочисленными значениями для каждой переменной решения. Массив передает в(N,). Если какие-либо переменные решения должны быть целыми, процесс полировки не изменит их. Мы используем только целые числа, попадающие в нижнюю и верхнюю границу. ValueError возникает, если между границами нет целочисленных значений.
• vectorized (логический): Учитывая массив x с x.shape ==(N, S), функция func должна возвращать массив с формой(S,), где S — количество векторов решения, которые необходимо сгенерировать, если для векторизованного установлено значение True.

Если используются ограничения, каждая функция, создающая объект Constraint, должна принимать массив x с x.shape ==(N, S) и возвращать массив с формой(M, S), где M — количество компонентов ограничения. Эта альтернатива рабочему распараллеливанию может увеличить скорость оптимизации за счет минимизации накладных расходов интерпретатора из-за повторных вызовов функций. Если worker!= 1, это ключевое слово не будет использоваться. Опция update=’deferred’ будет иметь приоритет над ключевым словом update. Дополнительную информацию о том, когда использовать «векторизованный», а когда «работников», см. в разделе примечаний.

Метод Different_evolution() возвращает res: объект OptimizeResult используется для представления результата оптимизации. Массив решений x, успех, логическое указание, указывающее, успешно ли завершился оптимизатор, и сообщение, объясняющее причину завершения, являются важными функциями.

Давайте рассмотрим пример и поймем, как работает метод Differential_evolution().

Импортируйте необходимые библиотеки или методы, используя приведенный ниже код Python.

from scipy import optimize

Рассмотрим задачу минимизации функции Розенброка. В «scipy.optimize» эта функция реализована в Rosen с использованием приведенного ниже кода.

bounds_ = [(0,1),(0, 1),(0, 1),(0, 1),(0, 1)]
result_ = optimize.differential_evolution(optimize.rosen, bounds_)
result_.x, result_.fun

Стратегия

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

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

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

Дифференциальные стратегии описываются с использованием следующей общей терминологии.

«DE/x/y/z»: где DE означает «дифференциальную эволюцию», x обозначает первоначальное решение, которое будет изменено. Например, «ранд» представляет собой случайный результат, а «лучший» означает лучшее решение, найденное в совокупности.

Переменные y и z используются для представления количества векторов разностей, добавленных к базовому решению, например 1, а распределение вероятностей используется для принятия решения о том, будет ли каждое решение сохранено или заменено в совокупности, например биномиальное или экспоненциальное. соответственно.

Благодаря высокой производительности в широком диапазоне целевых функций конфигурации «DE/best/1/bin» и «DE/best/2/bin» являются очень популярными.

Аргумент «стратегия», который регулирует тип выполняемого поиска дифференциальной эволюции, является важнейшим гиперпараметром метода Different_evolution в Python Scipy. Обычно для него установлено значение «best1bin»(DE/best/1/bin), которое подходит для большинства проблем. Выбирая случайные решения из совокупности, разделяя их друг на друга и добавляя масштабированную версию результата к лучшему кандидату решения в совокупности, он генерирует новые решения-кандидаты.

Параллельная дифференциальная эволюция

Функция минимизирует параллель, поэтому, чтобы узнать, как работает параллель дифференциальной эволюции, обратитесь к обновлению параметров и рабочим процессам, которые описаны в подразделе выше.

Давайте возьмем тот же пример, что и в приведенном выше подразделе, но с распараллеливанием, выполнив следующие шаги:

Импортируйте необходимые библиотеки или методы, используя приведенный ниже код Python.

from scipy import optimize

Рассмотрим задачу минимизации функции Розенброка, используя приведенный ниже код.

bounds_ = [(1,3),(1, 3),(1, 3),(1, 3),(1, 3)]
result_ = optimize.differential_evolution(optimize.rosen, bounds_,updating='deferred',workers=2)
result_.x, result_.fun

Ограничения

Мы уже узнали, как вычислять дифференциальную эволюцию и ее параметры, поэтому в этом разделе мы выполним минимизацию ограничений, выполнив следующие шаги:

• Импортируйте необходимые библиотеки или методы, используя приведенный ниже код Python.

from scipy import optimize
import numpy as np

• Определите функцию ограничений, используя приведенный ниже код.

def constr_fun(x):
    return np.array(x[0] + x[1])

• Используйте метод NonLinearConstraint и Bounds, чтобы определить ограничения и границы или пределы, используя приведенный ниже код.

nlc_ = optimize.NonlinearConstraint(constr_fun, -np.inf, 1.8)
bounds_ = optimize.Bounds([0., 0.], [1., 2.])

• Теперь минимизируйте ограничение, используя приведенный ниже код.

result = optimize.differential_evolution(optimize.rosen, bounds_, constraints=(nlc_),
                                seed=1)
result.x, result.fun

Границы

Метод Different_evolution() Python Scipy принимает границы параметров.

Существует два метода определения границ:

1. Номер экземпляра класса Bounds.
2. Для каждого элемента x используются пары(min, max) для обеспечения конечных нижних и верхних границ параметра оптимизации func. Общее количество границ используется для расчета количества параметров, N.

Давайте возьмем тот же пример, который мы использовали в предыдущем подразделе, и поймем, как работают границы параметров, выполнив следующие шаги:

Импортируйте необходимые библиотеки или методы, используя приведенный ниже код Python.

from scipy import optimize
import numpy as np

Определите функцию ограничений, используя приведенный ниже код.

def constr_fun(x):
    return np.array(x[0] + x[1])

Используйте метод NonLinearConstraint и Bounds, чтобы определить ограничения и границы или пределы, используя приведенный ниже код.

nlc_ = optimize.NonlinearConstraint(constr_fun, -np.inf, 1.8)
bounds_ = optimize.Bounds([0., 0.], [1., 2.])

В приведенном выше коде граница определяется как Bounds([0., 0.], [1., 2.]).

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

result = optimize.differential_evolution(optimize.rosen, bounds_, constraints=(nlc_),
                                seed=1)
result.x, result.fun

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

nlc_ = optimize.NonlinearConstraint(constr_fun, -np.inf, 1.8)
bounds_ = optimize.Bounds([2., 0.], [1., 2.])

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

result = optimize.differential_evolution(optimize.rosen, bounds_, constraints=(nlc_),
                                seed=1)
result.x, result.fun

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