scipy.optimize.

differential_evolution

scipy.optimize.differential_evolution(функция, границы, args=(), стратегия='best1bin', maxiter=1000, popsize=15, tol=0.01, мутация=(0.5, 1), рекомбинация=0.7, rng=None, callback=None, disp=False, полировка=True, init='latinhypercube', atol=0, обновление='immediate', workers=1, ограничения=(), x0=None, *, integrality=None, векторизованный=False, seed=None)

Находит глобальный минимум многомерной функции.

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

Алгоритм принадлежит Шторну и Прайсу [2].

Параметры:

функцияcallable

Целевая функция для минимизации. Должна быть в форме f(x, *args), где x является аргументом в виде одномерного массива и args является кортежем любых дополнительных фиксированных параметров, необходимых для полного определения функции. Количество параметров, N, равно len(x).

границыпоследовательность или Bounds

Границы для переменных. Есть два способа указать границы:

1. Экземпляр Bounds класс.

2. (min, max) пары для каждого элемента в x, определяя конечные нижнюю и верхнюю границы для оптимизируемого аргумента функция.

Общее количество границ используется для определения числа параметров, N. Если есть параметры с равными границами, общее количество свободных параметров равно N - N_equal.

argsкортеж, необязательный

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

стратегия{str, callable}, optional

Стратегия дифференциальной эволюции для использования. Должна быть одной из:

• ‘best1bin’

• ‘best1exp’

• ‘rand1bin’

• ‘rand1exp’

• 'rand2bin'

• ‘rand2exp’

• ‘randtobest1bin’

• ‘randtobest1exp’

• 'currenttobest1bin'

• ‘currenttobest1exp’

• 'best2exp'

• 'best2bin'

По умолчанию используется 'best1bin'. Стратегии, которые могут быть реализованы, описаны в разделе 'Примечания'. Альтернативно стратегия дифференциальной эволюции может быть настроена путем предоставления вызываемого объекта, который строит пробный вектор. Вызываемый объект должен иметь форму strategy(candidate: int, population: np.ndarray, rng=None), где candidate является целым числом, указывающим, какой элемент популяции эволюционирует, population является массивом формы (S, N) содержащий всех членов популяции (где S - общий размер популяции), и rng используется ли генератор случайных чисел внутри решателя. candidate будет в диапазоне [0, S). strategy должен возвращать пробный вектор с формой (N,). Пригодность этого пробного вектора сравнивается с пригодностью population[candidate].

Изменено в версии 1.12.0: Настройка стратегии эволюции через вызываемый объект.

maxiterint, необязательный

Максимальное количество поколений, в течение которых эволюционирует вся популяция. Максимальное количество вычислений функции (без полировки) составляет: (maxiter + 1) * popsize * (N - N_equal)

popsizeint, необязательный

Множитель для установки общего размера популяции. Популяция имеет popsize * (N - N_equal) отдельных особей. Этот ключевой параметр переопределяется, если начальная популяция предоставляется через init ключевое слово. При использовании init='sobol' размер популяции вычисляется как следующая степень 2 после popsize * (N - N_equal).

tolfloat, опционально

Относительный допуск для сходимости, решение останавливается, когда np.std(population_energies) <= atol + tol * np.abs(np.mean(population_energies)), где и atol и tol являются абсолютной и относительной погрешностью соответственно.

мутацияfloat или tuple(float, float), опционально

Константа мутации. В литературе это также известно как дифференциальный вес, обозначаемый \(F\). Если указано как float, должно быть в диапазоне [0, 2). Если указано как кортеж (min, max) применяется дизеринг. Дизеринг случайным образом изменяет константу мутации от поколения к поколению. Константа мутации для этого поколения берётся из U[min, max). Дизеринг может значительно ускорить сходимость. Увеличение константы мутации увеличивает радиус поиска, но замедлит сходимость.

рекомбинацияfloat, опционально

Константа рекомбинации должна быть в диапазоне [0, 1]. В литературе это также известно как вероятность кроссовера, обозначаемая как CR. Увеличение этого значения позволяет большему числу мутантов перейти в следующее поколение, но с риском стабильности популяции.

rng{None, int, numpy.random.Generator, опционально

Если rng передается по ключевому слову, типы, отличные от numpy.random.Generator передаются в numpy.random.default_rng для создания экземпляра Generator. Если rng уже является Generator экземпляр, то предоставленный экземпляр используется. Укажите rng для повторяемого поведения функции.

Если этот аргумент передаётся по позиции или seed передается по ключевому слову, устаревшее поведение для аргумента seed применяется:

• Если seed равно None (или numpy.random), numpy.random.RandomState используется синглтон.

• Если seed является int, новый RandomState используется экземпляр, инициализированный с seed.

• Если seed уже является Generator или RandomState экземпляр, тогда этот экземпляр используется.

Изменено в версии 1.15.0: В рамках SPEC-007 переход от использования numpy.random.RandomState to numpy.random.Generator, этот ключевое слово было изменено с seed to rng. В переходный период оба ключевых слова будут продолжать работать, хотя только одно может быть указано за раз. После переходного периода вызовы функций, использующие seed ключевое слово будет выдавать предупреждения. Поведение обоих seed и rng описаны выше, но только rng ключевое слово должно использоваться в новом коде.

dispbool, необязательно

Выводит вычисленное функция на каждой итерации.

callbackвызываемый объект, необязательный

Вызываемый объект, вызываемый после каждой итерации. Имеет сигнатуру:

callback(intermediate_result: OptimizeResult)

где intermediate_result является ключевым параметром, содержащим OptimizeResult с атрибутами x и fun, лучшее найденное на данный момент решение и целевая функция. Обратите внимание, что имя параметра должно быть intermediate_result для callback, чтобы передать OptimizeResult.

Обратный вызов также поддерживает сигнатуру вида:

callback(x, convergence: float=val)

val представляет дробное значение сходимости популяции. Когда val больше чем 1.0, функция останавливается.

Интроспекция используется для определения того, какая из сигнатур вызывается.

Глобальная минимизация остановится, если обратный вызов вызовет StopIteration или возвращает True; любая полировка все еще выполняется.

Изменено в версии 1.12.0: callback принимает intermediate_result ключевое слово.

полировкаbool, необязательно

Если True (по умолчанию), то scipy.optimize.minimize с L-BFGS-B метод используется для полировки лучшего члена популяции в конце, что может немного улучшить минимизацию. Если изучается задача с ограничениями, то trust-constr метод используется вместо этого. Для больших задач со многими ограничениями полировка может занимать много времени из-за вычислений матрицы Якоби.

Изменено в версии 1.15.0: Если workers указан, то вызываемый объект, подобный отображению, который оборачивает функция предоставляется minimize вместо использования функция напрямую. Это позволяет вызывающей стороне контролировать, как и где выполняются вызовы.

initstr или array-like, необязательный

Укажите, какой тип инициализации популяции выполняется. Должен быть одним из:

• 'latinhypercube'

• ‘sobol’

• 'halton'

• ‘random’

• массив, задающий начальную популяцию. Массив должен иметь форму (S, N), где S - общий размер популяции, а N - количество параметров.

init обрезается до границы перед использованием.

По умолчанию используется 'latinhypercube'. Латинский гиперкуб пытается максимизировать покрытие доступного пространства параметров.

‘sobol’ и ‘halton’ являются превосходными альтернативами и максимизируют пространство параметров еще больше. ‘sobol’ обеспечит начальный размер популяции, который рассчитывается как следующая степень двойки после popsize * (N - N_equal). ‘halton’ не имеет требований, но немного менее эффективен. См. scipy.stats.qmc для получения дополнительной информации.

‘random’ инициализирует популяцию случайным образом — это имеет недостаток, заключающийся в том, что может происходить кластеризация, препятствующая покрытию всего пространства параметров. Использование массива для указания популяции может быть применено, например, для создания плотной группы начальных приближений в области, где известно существование решения, тем самым сокращая время сходимости.

atolfloat, опционально

Абсолютная погрешность сходимости, решение останавливается, когда np.std(pop) <= atol + tol * np.abs(np.mean(population_energies)), где и atol и tol являются абсолютной и относительной погрешностью соответственно.

обновление{‘immediate’, ‘deferred’}, опционально

Если 'immediate', лучший вектор решения непрерывно обновляется в пределах одного поколения [4]. Это может привести к более быстрой сходимости, так как пробные векторы могут использовать преимущества непрерывных улучшений в лучшем решении. С 'deferred', лучший вектор решения обновляется один раз за поколение. Только 'deferred' совместим с параллелизацией или векторизацией, и workers и векторизованный ключевые слова могут переопределить эту опцию.

Добавлено в версии 1.2.0.

workersint или вызываемый объект, подобный отображению, необязательный

Если workers является целым числом, популяция подразделяется на workers разделы и вычисляются параллельно (использует multiprocessing.Pool). Укажите -1 для использования всех доступных ядер CPU. Альтернативно укажите вызываемый объект, подобный map, такой как multiprocessing.Pool.map для параллельной оценки популяции. Эта оценка выполняется как workers(func, iterable). Эта опция переопределит обновление ключевое слово для updating='deferred' if workers != 1. Эта опция переопределяет векторизованный ключевое слово if workers != 1. Требует, чтобы функция быть сериализуемым через pickle.

Добавлено в версии 1.2.0.

ограничения{NonLinearConstraint, LinearConstraint, Bounds}

Ограничения для решателя, помимо тех, что применяются границы kwd. Использует подход Лампинена [5].

Добавлено в версии 1.4.0.

x0None или array-like, опционально

Предоставляет начальное предположение для минимизации. После инициализации популяции этот вектор заменяет первого (лучшего) члена. Эта замена выполняется даже если init задана начальная популяция. x0.shape == (N,).

Добавлено в версии 1.7.0.

integrality1-D массив, необязательный

Для каждой переменной решения логическое значение, указывающее, ограничена ли переменная решения целыми значениями. Массив транслируется в (N,). Если какие-либо переменные решения ограничены целочисленными значениями, они не будут изменяться в процессе полировки. Используются только целые значения, лежащие между нижней и верхней границами. Если нет целых значений, лежащих между границами, то ValueError вызывается исключение.

Добавлено в версии 1.9.0.

векторизованныйbool, необязательно

Если vectorized is True, функция отправляется x массив с x.shape == (N, S), и ожидается, что вернёт массив формы (S,), где S количество векторов решений, которые необходимо вычислить. Если применяются ограничения, каждая из функций, используемых для построения Ограничение объект должен принимать x массив с x.shape == (N, S), и вернуть массив формы (M, S), где M — это количество компонентов ограничений. Эта опция является альтернативой параллелизации, предлагаемой workers, и может помочь в скорости оптимизации за счет уменьшения накладных расходов интерпретатора от множественных вызовов функций. Этот ключевой аргумент игнорируется, если workers != 1. Эта опция переопределит обновление ключевое слово для updating='deferred'. См. раздел примечаний для дальнейшего обсуждения, когда использовать 'vectorized', и когда использовать 'workers'.

Добавлено в версии 1.9.0.

Возвращает:

resOptimizeResult

Результат оптимизации, представленный как OptimizeResult объект. Важные атрибуты: x массив решения, success логический флаг, указывающий, успешно ли завершился оптимизатор, message которое описывает причину завершения, population векторы решений, присутствующие в популяции, и population_energies значение целевой функции для каждого элемента в population. См. OptimizeResult для описания других атрибутов. Если полировка был использован, и полировка дала более низкий минимум, тогда OptimizeResult также содержит jac атрибут. Если окончательное решение не удовлетворяет применённым ограничениям success будет False.

Примечания

Дифференциальная эволюция — это стохастический популяционный метод, который полезен для задач глобальной оптимизации. На каждом проходе по популяции алгоритм мутирует каждое кандидатное решение, смешивая его с другими кандидатными решениями для создания пробного кандидата. Существует несколько стратегий [3] для создания кандидатов на испытание, которые подходят для одних задач больше, чем для других. Стратегия 'best1bin' является хорошей отправной точкой для многих систем. В этой стратегии случайным образом выбираются два члена популяции. Их разность используется для мутации лучшего члена (где 'best' в 'best1bin' означает лучший). \(x_0\), до сих пор:

\[b' = x_0 + F \cdot (x_{r_0} - x_{r_1})\]

где \(F\) является мутация параметр. Затем строится пробный вектор. Начиная со случайно выбранного i-го параметра, пробный вектор последовательно заполняется (по модулю) параметрами из b' или исходный кандидат. Выбор, использовать ли b' или исходный кандидат создаётся с биномиальным распределением ('bin' в 'best1bin') - генерируется случайное число в [0, 1). Если это число меньше, чем рекомбинация константа, то параметр загружается из b', в противном случае он загружается из исходного кандидата. Финальный параметр всегда загружается из b'. После построения пробного кандидата оценивается его пригодность. Если пробный кандидат лучше исходного, то он занимает его место. Если он также лучше лучшего общего кандидата, он также заменяет его.

Другие доступные стратегии описаны в Qiang и Mitchell (2014) [3].

• rand1 : \(b' = x_{r_0} + F \cdot (x_{r_1} - x_{r_2})\)

• rand2 : \(b' = x_{r_0} + F \cdot (x_{r_1} + x_{r_2} - x_{r_3} - x_{r_4})\)

• best1 : \(b' = x_0 + F \cdot (x_{r_0} - x_{r_1})\)

• best2 : \(b' = x_0 + F \cdot (x_{r_0} + x_{r_1} - x_{r_2} - x_{r_3})\)

• currenttobest1 : \(b' = x_i + F \cdot (x_0 - x_i + x_{r_0} - x_{r_1})\)

• randtobest1 : \(b' = x_{r_0} + F \cdot (x_0 - x_{r_0} + x_{r_1} - x_{r_2})\)

где целые числа \(r_0, r_1, r_2, r_3, r_4\) выбираются случайным образом из интервала [0, NP) с NP где общий размер популяции и исходный кандидат имеет индекс i. Пользователь может полностью настроить генерацию пробных кандидатов, предоставив вызываемый объект в strategy.

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

По умолчанию лучший вектор решения обновляется непрерывно в течение одной итерации (updating='immediate'). Это модификация [4] оригинального алгоритма дифференциальной эволюции, что может привести к более быстрой сходимости, поскольку пробные векторы могут немедленно использовать улучшенные решения. Чтобы использовать оригинальное поведение Storn и Price, обновляя лучшее решение один раз за итерацию, установите updating='deferred'. 'deferred' подход совместим как с параллелизацией, так и с векторизацией ('workers' и 'vectorized' ключевые слова). Они могут улучшить скорость минимизации, используя ресурсы компьютера более эффективно. 'workers' распределять вычисления по нескольким процессорам. По умолчанию Python multiprocessing модуль используется, но также возможны другие подходы, такие как интерфейс передачи сообщений (MPI), используемый в кластерах [6] [7]. Накладные расходы от этих подходов (создание новых процессов и т.д.) могут быть значительными, что означает, что вычислительная скорость не обязательно масштабируется с количеством используемых процессоров. Параллелизация лучше всего подходит для вычислительно затратных целевых функций. Если целевая функция менее затратна, то 'vectorized' может помочь, вызывая целевую функцию только один раз за итерацию, а не несколько раз для всех членов популяции; накладные расходы интерпретатора уменьшаются.

Добавлено в версии 0.15.0.

Ссылки

[1]

Дифференциальная эволюция, Википедия, http://en.wikipedia.org/wiki/Differential_evolution

[2]

Шторн, Р. и Прайс, К., Дифференциальная эволюция — простой и эффективный эвристический метод глобальной оптимизации в непрерывных пространствах, Journal of Global Optimization, 1997, 11, 341 - 359.

[3] (1,2)

Qiang, J., Mitchell, C., A Unified Differential Evolution Algorithm for Global Optimization, 2014, https://www.osti.gov/servlets/purl/1163659

[4] (1,2)

Wormington, M., Panaccione, C., Matney, K. M., Bowen, D. K., - Characterization of structures from X-ray scattering data using genetic algorithms, Phil. Trans. R. Soc. Lond. A, 1999, 357, 2827-2848

[5]

Lampinen, J., Подход к обработке ограничений для алгоритма дифференциальной эволюции. Труды Конгресса по эволюционным вычислениям 2002 года. CEC’02 (Cat. No. 02TH8600). Том 2. IEEE, 2002.

[6]

https://mpi4py.readthedocs.io/en/stable/

[7]

https://schwimmbad.readthedocs.io/en/latest/

Примеры

Попробуйте в вашем браузере!

Рассмотрим задачу минимизации функции Розенброка. Эта функция реализована в rosen в scipy.optimize.

>>> import numpy as np
>>> from scipy.optimize import rosen, differential_evolution
>>> bounds = [(0,2), (0, 2), (0, 2), (0, 2), (0, 2)]
>>> result = differential_evolution(rosen, bounds)
>>> result.x, result.fun
(array([1., 1., 1., 1., 1.]), 1.9216496320061384e-19)

Теперь повторите, но с параллелизацией.

>>> result = differential_evolution(rosen, bounds, updating='deferred',
...                                 workers=2)
>>> result.x, result.fun
(array([1., 1., 1., 1., 1.]), 1.9216496320061384e-19)

Выполним ограниченную минимизацию.

>>> from scipy.optimize import LinearConstraint, Bounds

Мы добавляем ограничение, что сумма x[0] и x[1] должно быть меньше или равно 1.9. Это линейное ограничение, которое может быть записано как A @ x <= 1.9, где A = array([[1, 1]]). Это может быть закодировано как LinearConstraint экземпляр:

>>> lc = LinearConstraint([[1, 1]], -np.inf, 1.9)

Задать пределы с помощью Bounds объект.

>>> bounds = Bounds([0., 0.], [2., 2.])
>>> result = differential_evolution(rosen, bounds, constraints=lc,
...                                 rng=1)
>>> result.x, result.fun
(array([0.96632622, 0.93367155]), 0.0011352416852625719)

Далее найти минимум функции Акклея (https://en.wikipedia.org/wiki/Test_functions_for_optimization).

>>> def ackley(x):
...     arg1 = -0.2 * np.sqrt(0.5 * (x[0] ** 2 + x[1] ** 2))
...     arg2 = 0.5 * (np.cos(2. * np.pi * x[0]) + np.cos(2. * np.pi * x[1]))
...     return -20. * np.exp(arg1) - np.exp(arg2) + 20. + np.e
>>> bounds = [(-5, 5), (-5, 5)]
>>> result = differential_evolution(ackley, bounds, rng=1)
>>> result.x, result.fun
(array([0., 0.]), 4.440892098500626e-16)

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

>>> result = differential_evolution(
...     ackley, bounds, vectorized=True, updating='deferred', rng=1
... )
>>> result.x, result.fun
(array([0., 0.]), 4.440892098500626e-16)

Следующая пользовательская функция стратегии имитирует ‘best1bin’:

>>> def custom_strategy_fn(candidate, population, rng=None):
...     parameter_count = population.shape(-1)
...     mutation, recombination = 0.7, 0.9
...     trial = np.copy(population[candidate])
...     fill_point = rng.choice(parameter_count)
...
...     pool = np.arange(len(population))
...     rng.shuffle(pool)
...
...     # two unique random numbers that aren't the same, and
...     # aren't equal to candidate.
...     idxs = []
...     while len(idxs) < 2 and len(pool) > 0:
...         idx = pool[0]
...         pool = pool[1:]
...         if idx != candidate:
...             idxs.append(idx)
...
...     r0, r1 = idxs[:2]
...
...     bprime = (population[0] + mutation *
...               (population[r0] - population[r1]))
...
...     crossovers = rng.uniform(size=parameter_count)
...     crossovers = crossovers < recombination
...     crossovers[fill_point] = True
...     trial = np.where(crossovers, bprime, trial)
...     return trial

НазадОткрыть во вкладке