scipy.optimize.

basinhopping

scipy.optimize.basinhopping(функция, x0, niter=100, T=1.0, шаг=0.5, minimizer_kwargs=None, take_step=None, accept_test=None, callback=None, интервал=50, disp=False, niter_success=None, rng=None, *, target_accept_rate=0.5, stepwise_factor=0.9, seed=None)

Найти глобальный минимум функции с помощью алгоритма basin-hopping.

Basin-hopping — это двухфазный метод, сочетающий глобальный алгоритм шагов с локальной минимизацией на каждом шаге. Разработанный для имитации естественного процесса минимизации энергии кластеров атомов, он хорошо работает для аналогичных задач с "воронкообразными, но неровными" энергетическими ландшафтами [5].

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

Параметры:

функцияcallable f(x, *args)

Функция для оптимизации. args может быть передан как необязательный элемент в словаре minimizer_kwargs

x0array_like

Начальное приближение.

niterцелое число, опционально

Количество итераций basin-hopping. Всего будет niter + 1 запуски локального минимизатора.

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

Параметр "температура" для критерия принятия или отклонения. Более высокие "температуры" означают, что будут приниматься большие скачки значения функции. Для лучших результатов T должно быть сравнимо с разделением (по значению функции) между локальными минимумами.

шагfloat, опционально

Максимальный размер шага для использования в случайном смещении.

minimizer_kwargsdict, optional

Дополнительные ключевые аргументы для передачи локальному минимизатору scipy.optimize.minimize Некоторые важные опции могут быть:

методstr

Метод минимизации (например, "L-BFGS-B")

argsкортеж

Дополнительные аргументы, передаваемые в целевую функцию (функция) и его производные (Якобиан, Гессиан).

take_stepcallable take_step(x), опционально

Заменить стандартную процедуру выбора шага на эту процедуру. Стандартная процедура выбора шага — случайное смещение координат, но другие алгоритмы выбора шага могут быть лучше для некоторых систем. take_step может опционально иметь атрибут take_step.stepsize. Если этот атрибут существует, то basinhopping будет корректировать take_step.stepsize чтобы попытаться оптимизировать поиск глобального минимума.

accept_testвызываемый, accept_test(f_new=f_new, x_new=x_new, f_old=fold, x_old=x_old), опционально

Определяет тест, который будет использоваться для принятия решения о принятии шага. Этот тест будет использоваться в дополнение к тесту Метрополиса, основанному на "температуре". T. Допустимые возвращаемые значения: True, False или "force accept". Если любой из тестов возвращает False, то шаг отклоняется. Если последнее, то это переопределит любые другие тесты, чтобы принять шаг. Это можно использовать, например, для принудительного выхода из локального минимума, который basinhopping заперта в.

callbackвызываемый, callback(x, f, accept), опционально

Функция обратного вызова, которая будет вызываться для всех найденных минимумов. x и f являются координатами и значением функции пробного минимума, и accept принят ли этот минимум. Это можно использовать, например, для сохранения N наименьших найденных минимумов. Также, callback может использоваться для указания пользовательского критерия остановки, опционально возвращая True для остановки basinhopping подпрограмма.

интервалцелое число, опционально

интервал для частоты обновления шаг

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

Установите True для вывода статусных сообщений

niter_successцелое число, опционально

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

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 ключевое слово должно использоваться в новом коде.

Сгенерированные случайные числа влияют только на стандартный Метрополис accept_test и значение по умолчанию take_step. Если вы предоставляете свои собственные take_step и accept_test, и эти функции используют генерацию случайных чисел, то эти функции отвечают за состояние своего генератора случайных чисел.

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

Целевой уровень принятия, используемый для корректировки шаг. Если текущая частота принятия больше целевой, то шаг увеличивается. В противном случае она уменьшается. Диапазон (0, 1). По умолчанию 0.5.

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

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

The шаг умножается или делится на этот пошаговый коэффициент при каждом обновлении. Диапазон (0, 1). По умолчанию 0.9.

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

Возвращает:

resOptimizeResult

Результат оптимизации, представленный как OptimizeResult объект. Важные атрибуты: x массив решения, fun значение функции в решении, и message который описывает причину завершения. The OptimizeResult объект, возвращаемый выбранным минимизатором в наименьшем минимуме, также содержится в этом объекте и может быть доступен через lowest_optimization_result атрибут. lowest_optimization_result будет обновляться только если локальная минимизация была успешной. См. OptimizeResult для описания других атрибутов.

Смотрите также

minimize

Функция локальной минимизации, вызываемая один раз для каждого шага basinhopping. minimizer_kwargs передается в эту процедуру.

Примечания

Basin-hopping — это стохастический алгоритм, который пытается найти глобальный минимум гладкой скалярной функции одной или нескольких переменных [1] [2] [3] [4]. Алгоритм в его текущей форме был описан Дэвидом Уэльсом и Джонатаном Дой [2] http://www-wales.ch.cam.ac.uk/.

Алгоритм итеративный, каждый цикл состоит из следующих этапов

1. случайное возмущение координат

2. локальная минимизация

3. принять или отклонить новые координаты на основе минимизированного значения функции

Используемый здесь критерий принятия – критерий Метрополиса стандартных алгоритмов Монте-Карло, хотя существует множество других возможностей [3].

Этот глобальный метод минимизации показал чрезвычайную эффективность для широкого разнообразия задач в физике и химии. Он особенно полезен, когда функция имеет много минимумов, разделенных большими барьерами. См. Cambridge Cluster Database для баз данных молекулярных систем, которые были оптимизированы в основном с использованием алгоритма basin-hopping. Эта база данных включает задачи минимизации, превышающие 300 степеней свободы.

См. программу свободного ПО GMIN для реализации на Fortran алгоритма basin-hopping. Эта реализация имеет множество вариаций процедуры, описанной выше, включая более продвинутые алгоритмы шагов и альтернативные критерии принятия.

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

Выбор шаг: Это ключевой параметр в basinhopping и зависит от решаемой задачи. Шаг выбирается равномерно в области от x0-stepsize до x0+stepsize в каждом измерении. В идеале он должен быть сопоставим с типичным расстоянием (в значениях аргументов) между локальными минимумами оптимизируемой функции. basinhopping будет, по умолчанию, корректировать шаг чтобы найти оптимальное значение, но это может занять много итераций. Вы получите более быстрые результаты, если установите разумное начальное значение для stepsize.

Выбор T: Параметр T — это «температура», используемая в критерии Метрополиса. Шаги Basinhopping всегда принимаются, если func(xnew) < func(xold). В противном случае они принимаются с вероятностью:

exp( -(func(xnew) - func(xold)) / T )

Таким образом, для наилучших результатов, T должно быть сравнимо с типичной разницей (в значениях функции) между локальными минимумами. (Высота "стен" между локальными минимумами не имеет значения.)

Если T равен 0, алгоритм становится Monotonic Basin-Hopping, в котором все шаги, увеличивающие энергию, отклоняются.

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

Ссылки

[1]

Wales, David J. 2003, Energy Landscapes, Cambridge University Press, Cambridge, UK.

[2] (1,2)

Уэльс, Д. Дж., и Дой Дж. П. К., Глобальная оптимизация методом Basin-Hopping и структуры с наименьшей энергией кластеров Леннарда-Джонса, содержащих до 110 атомов. Журнал физической химии A, 1997, 101, 5111.

[3] (1,2)

Ли, З. и Шерага, Х. А., Подход Монте-Карло-минимизации к проблеме множественных минимумов в сворачивании белков, Proc. Natl. Acad. Sci. USA, 1987, 84, 6611.

[4]

Уэйлс, Д. Дж. и Шерага, Х. А., Глобальная оптимизация кластеров, кристаллов и биомолекул, Science, 1999, 285, 1368.

[5]

Олсон, Б., Хашми, И., Моллой, К. и Шеху, А., Basin Hopping как общая и универсальная оптимизационная структура для характеристики биологических макромолекул, Advances in Artificial Intelligence, Том 2012 (2012), статья ID 674832, DOI:10.1155/2012/674832

Примеры

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

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

>>> import numpy as np
>>> from scipy.optimize import basinhopping
>>> func = lambda x: np.cos(14.5 * x - 0.3) + (x + 0.2) * x
>>> x0 = [1.]

Basinhopping внутренне использует алгоритм локальной минимизации. Мы будем использовать параметр minimizer_kwargs чтобы указать basinhopping, какой алгоритм использовать и как настроить этот минимизатор. Этот параметр будет передан в scipy.optimize.minimize.

>>> minimizer_kwargs = {"method": "BFGS"}
>>> ret = basinhopping(func, x0, minimizer_kwargs=minimizer_kwargs,
...                    niter=200)
>>> # the global minimum is:
>>> ret.x, ret.fun
-0.1951, -1.0009

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

>>> def func2d(x):
...     f = np.cos(14.5 * x[0] - 0.3) + (x[1] + 0.2) * x[1] + (x[0] +
...                                                            0.2) * x[0]
...     df = np.zeros(2)
...     df[0] = -14.5 * np.sin(14.5 * x[0] - 0.3) + 2. * x[0] + 0.2
...     df[1] = 2. * x[1] + 0.2
...     return f, df

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

>>> minimizer_kwargs = {"method":"L-BFGS-B", "jac":True}
>>> x0 = [1.0, 1.0]
>>> ret = basinhopping(func2d, x0, minimizer_kwargs=minimizer_kwargs,
...                    niter=200)
>>> print("global minimum: x = [%.4f, %.4f], f(x) = %.4f" % (ret.x[0],
...                                                           ret.x[1],
...                                                           ret.fun))
global minimum: x = [-0.1951, -0.1000], f(x) = -1.0109

Вот пример использования пользовательской процедуры шага. Представьте, что вы хотите, чтобы первая координата делала большие шаги, чем остальные координаты. Это можно реализовать так:

>>> class MyTakeStep:
...    def __init__(self, stepsize=0.5):
...        self.stepsize = stepsize
...        self.rng = np.random.default_rng()
...    def __call__(self, x):
...        s = self.stepsize
...        x[0] += self.rng.uniform(-2.*s, 2.*s)
...        x[1:] += self.rng.uniform(-s, s, x[1:].shape)
...        return x

Поскольку MyTakeStep.stepsize существует, basinhopping будет регулировать величину шаг для оптимизации поиска. Мы будем использовать ту же 2-D функцию, что и ранее

>>> mytakestep = MyTakeStep()
>>> ret = basinhopping(func2d, x0, minimizer_kwargs=minimizer_kwargs,
...                    niter=200, take_step=mytakestep)
>>> print("global minimum: x = [%.4f, %.4f], f(x) = %.4f" % (ret.x[0],
...                                                           ret.x[1],
...                                                           ret.fun))
global minimum: x = [-0.1951, -0.1000], f(x) = -1.0109

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

>>> def print_fun(x, f, accepted):
...         print("at minimum %.4f accepted %d" % (f, int(accepted)))

Мы запустим его только на 10 шагах basinhopping на этот раз.

>>> rng = np.random.default_rng()
>>> ret = basinhopping(func2d, x0, minimizer_kwargs=minimizer_kwargs,
...                    niter=10, callback=print_fun, rng=rng)
at minimum 0.4159 accepted 1
at minimum -0.4317 accepted 1
at minimum -1.0109 accepted 1
at minimum -0.9073 accepted 1
at minimum -0.4317 accepted 0
at minimum -0.1021 accepted 1
at minimum -0.7425 accepted 1
at minimum -0.9073 accepted 1
at minimum -0.4317 accepted 0
at minimum -0.7425 accepted 1
at minimum -0.9073 accepted 1

Минимум в -1.0109 фактически является глобальным минимумом, найденным уже на 8-й итерации.

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