例子了解scipy盆地跳跃优化函数

Question

我在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.

在常规的旧梯度下降中,该perturbation术语仅是确定性计算的量,如梯度方向上的一个步骤.但是在Metropolis-Hastings中,perturbation是随机生成的(有时通过使用渐变作为关于随机去哪里的线索......但有时只是随机地没有线索).

在你获得这一点的时候x1,你必须问自己:"我是通过随机扰动做了一件好事x0还是我把所有东西搞砸了？" 其中一部分与某些边界内部有关,例如你的mybounds功能.它的另一部分与目标函数的价值在新的点上变得更好/更差有关.

所以有两种方法可以拒绝这个提议x1:首先,它可能违反你设定的界限,并且是问题定义的不可行点; 第二,从Metropolis-Hastings的接受/拒绝评估步骤来看,它可能只是一个非常糟糕的观点,应该被拒绝.在任何一种情况下,你都会拒绝x1,而是设置x1 = x0并假装你只是呆在同一个地方再试一次.

与渐变式方法相比,无论如何,无论如何,总是至少进行某种运动(梯度方向的一步).

好的,没事.抛开这一切,让我们考虑一下这个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]来获取点就满足mybounds.

Answer 2

在编码时,盆地跳跃的行为是将扰动与局部最小化相结合.

由于局部优化部分,您的例行程序一直无法生成.基本上你正在使用的BFGS程序是完全不受约束的,所以它遵循渐变到负无穷大.然后这个结果被反馈到你的检查器.

因此,无论您的盆地跳跃点在哪里x1,BFGS部分总是会出现大的负值.

x - 4您使用的基准功能不是理想的目标.查看例如Rastrigin函数.如果您确实需要优化线性函数,那么可以使用一整套算法(请参阅维基百科上的线性编程).