scipy.optimize.

basinhopping#

scipy.optimize.basinhopping(func, x0, niter=100, T=1.0, stepsize=0.5, minimizer_kwargs=None, take_step=None, accept_test=None, callback=None, interval=50, disp=False, niter_success=None, rng=None, *, target_accept_rate=0.5, stepwise_factor=0.9)[源代码]#

使用盆地跳跃算法查找函数的全局最小值。

盆地跳跃是一种两阶段方法，它将全局步进算法与每一步的局部最小化相结合。它旨在模仿原子团簇能量最小化的自然过程，对于具有“漏斗状但崎岖”能量景观的类似问题效果良好 [5]。

由于步进、步进接受和最小化方法都是可定制的，因此此函数还可用于实现其他两阶段方法。

参数:

func可调用对象 f(x, *args)

要优化的函数。args 可以作为字典 minimizer_kwargs 中的可选项目传递

x0类数组

初始猜测。

niter整数，可选

盆地跳跃迭代的次数。局部最小化器总共将运行 niter + 1 次。

T浮点数，可选

接受或拒绝标准的“温度”参数。较高的“温度”意味着将接受函数值中较大的跳跃。为了获得最佳结果，T 应该与局部最小值之间的分隔（以函数值表示）相当。

stepsize浮点数，可选

随机位移中使用的最大步长。

minimizer_kwargs字典，可选

要传递给局部最小化器 scipy.optimize.minimize 的额外关键字参数。一些重要的选项可能是

method字符串: 最小化方法（例如 "L-BFGS-B"）
args元组: 传递给目标函数（func）及其导数（雅可比矩阵，黑塞矩阵）的额外参数。

take_step可调用对象 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 的 Metropolis 测试之外，还将使用此测试。可接受的返回值是 True、False 或 "force accept"。如果任何测试返回 False，则该步骤将被拒绝。如果是后者，则这将覆盖任何其他测试，以便接受该步骤。例如，这可用于强制从 basinhopping 被困住的局部最小值中逃脱。

callback可调用对象，callback(x, f, accept)，可选

一个回调函数，该函数将为找到的所有最小值调用。x 和 f 是试验最小值的坐标和函数值，而 accept 是是否接受该最小值。例如，这可用于保存找到的最低 N 个最小值。此外，callback 可用于通过选择性返回 True 来停止 basinhopping 例程来指定用户定义的停止标准。

interval整数，可选

更新 stepsize 的频率间隔

disp布尔值，可选

设置为 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 是一个整数，则使用新的 RandomState 实例，并使用 seed 进行初始化。
如果 seed 已经是 Generator 或 RandomState 实例，则使用该实例。

1.15.0 版本更改：作为从使用 numpy.random.RandomState 过渡到使用 numpy.random.Generator 的 SPEC-007 规范的一部分，此关键字已从 seed 更改为 rng。在过渡期间，这两个关键字将继续有效，但一次只能指定一个。在过渡期结束后，使用 seed 关键字的函数调用将发出警告。以上概述了 seed 和 rng 的行为，但在新代码中应仅使用 rng 关键字。

生成的随机数仅影响默认的 Metropolis accept_test 和默认的 take_step。如果您提供自己的 take_step 和 accept_test，并且这些函数使用随机数生成，则这些函数负责其随机数生成器的状态。

target_accept_rate浮点数，可选

用于调整 stepsize 的目标接受率。如果当前接受率大于目标值，则增加 stepsize。否则，减小它。范围为 (0, 1)。默认值为 0.5。

1.8.0 版本新增。

stepwise_factor浮点数，可选

每次更新时，stepsize 乘以或除以此步长因子。范围为 (0, 1)。默认值为 0.9。

1.8.0 版本新增。

返回:

resOptimizeResult: 优化结果表示为 OptimizeResult 对象。重要的属性有：x 解数组，fun 解处函数的值，以及 message，它描述了终止的原因。在最低最小值处所选最小化器返回的 OptimizeResult 对象也包含在此对象中，可以通过 lowest_optimization_result 属性访问。有关其他属性的描述，请参阅 OptimizeResult。

另请参阅

minimize: 为每个 basinhopping 步骤调用一次的局部最小化函数。minimizer_kwargs 传递给此例程。

说明

盆地跳跃是一种随机算法，它试图找到一个或多个变量的光滑标量函数的全局最小值 [1] [2] [3] [4]。当前形式的算法由 David Wales 和 Jonathan Doye 描述 [2] http://www-wales.ch.cam.ac.uk/。

该算法是迭代的，每个周期由以下特征组成

坐标的随机扰动
局部最小化
根据最小化的函数值接受或拒绝新的坐标

此处使用的接受测试是标准蒙特卡洛算法的 Metropolis 准则，尽管还有许多其他可能性 [3]。

这种全局最小化方法已被证明在物理和化学领域的各种问题中非常有效。当函数有许多被大障碍隔开的最小值时，它特别有用。有关主要使用盆地跳跃优化的分子系统数据库，请参阅剑桥集群数据库。该数据库包括超过 300 个自由度的最小化问题。

有关盆地跳跃的 Fortran 实现，请参阅免费软件程序 GMIN。此实现具有上述过程的许多变体，包括更高级的步长算法和备选的接受准则。

对于随机全局优化，无法确定是否已找到真正的全局最小值。相反，作为一致性检查，该算法可以从许多不同的随机起点运行，以确保每个示例中找到的最低最小值已收敛到全局最小值。因此，basinhopping 默认情况下将仅运行 niter 次迭代并返回找到的最低最小值。用户有责任确保这实际上是全局最小值。

选择 stepsize：这是 basinhopping 中的关键参数，取决于所解决的问题。在每个维度中，步长在从 x0-stepsize 到 x0+stepsize 的区域内均匀选择。理想情况下，它应该与被优化函数的局部最小值之间的典型间隔（在自变量值中）相当。basinhopping 默认情况下将调整 stepsize 以找到最佳值，但这可能需要多次迭代。如果您为 stepsize 设置合理的初始值，您将获得更快的结果。

选择 T：参数 T 是 Metropolis 准则中使用的“温度”。如果 func(xnew) < func(xold)，则始终接受盆地跳跃步骤。否则，它们将以概率

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

因此，为了获得最佳结果，T 应与局部最小值之间的典型差异（在函数值中）相当。（局部最小值之间“墙”的高度无关紧要。）

如果 T 为 0，则该算法变为单调盆地跳跃，其中所有增加能量的步骤都被拒绝。

0.12.0 版本新增。

参考文献

[1]

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

[2] (1,2)

Wales, D J, 和 Doye J P K, Global Optimization by Basin-Hopping and the Lowest Energy Structures of Lennard-Jones Clusters Containing up to 110 Atoms. Journal of Physical Chemistry A, 1997, 101, 5111.

[3] (1,2)

Li, Z. 和 Scheraga, H. A., Monte Carlo-minimization approach to the multiple-minima problem in protein folding, Proc. Natl. Acad. Sci. USA, 1987, 84, 6611.

[4]

Wales, D. J. 和 Scheraga, H. A., Global optimization of clusters, crystals, and biomolecules, Science, 1999, 285, 1368.

[5]

Olson, B., Hashmi, I., Molloy, K., 和 Shehu1, A., Basin Hopping as a General and Versatile Optimization Framework for the Characterization of Biological Macromolecules, Advances in Artificial Intelligence, Volume 2012 (2012), Article ID 674832, DOI:10.1155/2012/674832

示例

以下示例是一个一维最小化问题，在抛物线上叠加了许多局部最小值。

>>> 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 将调整 stepsize 的大小以优化搜索。我们将使用与之前相同的二维函数

>>> 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 个盆地跳跃步骤。

>>> 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

实际上，在第 8 次迭代中就已经找到了-1.0109 处的最小值，它是全局最小值。