python - 理解 scipy basin hopping 优化函数的例子

Question

我遇到了 basin hopping algorithm在 scipy 中创建了一个简单的问题来了解如何使用它，但它似乎无法正确解决该问题。可能是我做的事情完全错了。

代码如下:

import scipy.optimize as spo
import numpy as np
minimizer_kwargs = {"method":"BFGS"}    
f1=lambda x: (x-4)
def mybounds(**kwargs):
    x = kwargs["x_new"]
    tmax = bool(np.all(x <= 1.0))
    tmin = bool(np.all(x >= 0.0))
    print x
    print tmin and tmax
    return tmax and tmin


def print_fun(x, f, accepted):
      print("at minima %.4f accepted %d" % (f, int(accepted)))
x0=[1.]     
spo.basinhopping(f1,x0,accept_test=mybounds,callback=print_fun,niter=200,minimizer_kwargs=minimizer_kwargs)

它给出的解是x: array([ -1.80746874e+08])

Answer 1

您正在测试的函数使用了一种称为 Metropolis-Hastings 的方法，该方法可以修改为称为模拟退火的过程，该过程可以随机方式优化函数。

其工作方式如下。首先你选择一个点，比如你的点 x0。从那时起，您会生成一个随机扰动(这称为“提议”)。一旦提出了扰动，您就可以通过将扰动应用于当前输出来获得新点的候选点。因此，您可以将其视为 x1 = x0 + perturbation。

在常规的旧梯度下降中，扰动 项只是一个确定性计算的量，就像梯度方向上的一步。但在 Metropolis-Hastings 中，扰动 是随机生成的(有时使用梯度作为随机去向的线索......但有时只是随机生成，没有任何线索)。

此时，当你得到 x1 时，你必须问自己:“我是通过随机扰动 x0 做了一件好事，还是我只是把一切都搞砸了向上？”其中一部分与坚持某些界限内有关，例如您的 mybounds 函数。它的另一部分与目标函数的值在新点上变得更好/更差的程度有关。

所以有两种方法可以拒绝x1的提议:第一，它可能违反你设定的界限，并且是问题定义的不可行点；其次，从 Metropolis-Hastings 的 accept/reject 评估步骤来看，这可能只是一个非常糟糕的点，应该被拒绝。在任何一种情况下，您都将拒绝 x1 并设置 x1 = x0 并假装您只是停留在同一个地方再试一次。

将其与渐变类型的方法进行对比，在这种方法中，无论如何，您肯定会始终至少进行某种类型的移动(向渐变方向迈出一步)。 p>

哇，好吧。撇开这些不谈，让我们考虑一下 basinhopping 函数是如何发挥作用的。从文档中我们可以看到，典型的接受条件是由 take_step 参数访问的，文档这样说:“默认的步进例程是坐标的随机位移，但其他步进算法对某些系统来说可能更好。”因此，即使除了您的 mybounds 边界检查器之外，该函数也会对坐标进行随机位移以生成其新的尝试点。由于此函数的梯度只是常量 1，因此它将始终在负梯度方向(用于最小化)上迈出相同的大步。

在实际层面上，这意味着 x1 的建议点将始终完全超出区间 [0,1] 并且您的边界检查器将总是否决他们。

当我运行您的代码时，我发现这种情况一直在发生:

In [5]: spo.basinhopping(f1,x0,accept_test=mybounds,callback=print_fun,niter=200,minimizer_kwargs=minimizer_kwargs)
at minima -180750994.1924 accepted 0
[ -1.80746874e+08]
False
at minima -180746877.5530 accepted 0
[ -1.80746873e+08]
False
at minima -180746877.3896 accepted 0
[ -1.80750991e+08]
False
at minima -180750994.7281 accepted 0
[ -1.80746874e+08]
False
at minima -180746878.2433 accepted 0
[ -1.80746874e+08]
False
at minima -180746877.5774 accepted 0
[ -1.80746874e+08]
False
at minima -180746878.3173 accepted 0
[ -1.80750990e+08]
False
at minima -180750994.3509 accepted 0
[ -1.80750991e+08]
False
at minima -180750994.6605 accepted 0
[ -1.80746874e+08]
False
at minima -180746877.6966 accepted 0
[ -1.80746874e+08]
False
at minima -180746877.6900 accepted 0
[ -1.80750990e+08]
False
at minima -180750993.9707 accepted 0
[ -1.80750990e+08]
False
at minima -180750994.0494 accepted 0
[ -1.80750991e+08]
False
at minima -180750994.5824 accepted 0
[ -1.80746874e+08]
False
at minima -180746877.5459 accepted 0
[ -1.80750991e+08]
False
at minima -180750994.6679 accepted 0
[ -1.80750991e+08]
False
at minima -180750994.5823 accepted 0
[ -1.80750990e+08]
False
at minima -180750993.9308 accepted 0
[ -1.80746874e+08]
False
at minima -180746878.0395 accepted 0
[ -1.80750991e+08]
False

# ... etc.

所以它从不接受posposal点。输出并没有告诉你它已经找到了解决方案。它告诉您，探索可能的解决方案的随机扰动不断导致优化器看起来越来越好，但始终无法满足您的标准。它找不到返回 [0,1] 的所有方式来获取 do 满足 mybounds 的点。