我有一个包含64个变量的Python函数,我尝试使用minimise函数中的L-BFGS-B方法进行优化,但是这种方法对初始猜测值有很强的依赖性,并且无法找到全局最小值。
但我喜欢它设置变量边界的能力。有没有一种方法/函数可以在具有变量边界的情况下找到全局最小值?
我有一个包含64个变量的Python函数,我尝试使用minimise函数中的L-BFGS-B方法进行优化,但是这种方法对初始猜测值有很强的依赖性,并且无法找到全局最小值。
但我喜欢它设置变量边界的能力。有没有一种方法/函数可以在具有变量边界的情况下找到全局最小值?
这可以使用scipy.optimize.basinhopping
来完成。Basinhopping是一个函数,旨在找到目标函数的全局最小值。它使用scipy.optimize.minimize
函数进行重复最小化,并在每次最小化后在坐标空间中随机移动一步。通过使用实现边界的最小化器之一(例如L-BFGS-B),Basinhopping仍然可以尊重边界约束。以下是一些代码,演示如何实现此操作。
# an example function with multiple minima
def f(x): return x.dot(x) + sin(np.linalg.norm(x) * np.pi)
# the starting point
x0 = [10., 10.]
# the bounds
xmin = [1., 1.]
xmax = [11., 11.]
# rewrite the bounds in the way required by L-BFGS-B
bounds = [(low, high) for low, high in zip(xmin, xmax)]
# use method L-BFGS-B because the problem is smooth and bounded
minimizer_kwargs = dict(method="L-BFGS-B", bounds=bounds)
res = basinhopping(f, x0, minimizer_kwargs=minimizer_kwargs)
print res
上述代码可以用于简单的情况,但是如果 basinhopping 的随机位移例程将您带到了禁止区域,则仍然可能会出现问题。幸运的是,这可以通过使用关键字 take_step
传递自定义步骤取样例程来覆盖。
class RandomDisplacementBounds(object):
"""random displacement with bounds"""
def __init__(self, xmin, xmax, stepsize=0.5):
self.xmin = xmin
self.xmax = xmax
self.stepsize = stepsize
def __call__(self, x):
"""take a random step but ensure the new position is within the bounds"""
while True:
# this could be done in a much more clever way, but it will work for example purposes
xnew = x + np.random.uniform(-self.stepsize, self.stepsize, np.shape(x))
if np.all(xnew < self.xmax) and np.all(xnew > self.xmin):
break
return xnew
# define the new step taking routine and pass it to basinhopping
take_step = RandomDisplacementBounds(xmin, xmax)
result = basinhopping(f, x0, niter=100, minimizer_kwargs=minimizer_kwargs,
take_step=take_step)
print result
return np.clip( x + random(...), xmin, xmax )
。(在所有维度中使用相同的步长,预缩放以使边界框大致为正方形。) - denis针对任何优化器的调试和可视化,以下是一些常识性建议:
你的目标函数和约束是否合理?
如果目标函数是一个求和形式,比如 f() + g()
,
请分别为所有的x
在 "fx-opt.nptxt"
(下面)中打印它们;
如果f()
占总和的 99%,而 g()
仅占 1%,请进行调查。
约束条件:有多少个xfinal
中的组成部分x_i
被限制在边界上,
如x_i <= lo_i
或>= hi_i
?
title = "%s n %d ntermhess %d nsample %d seed %d" % ( # all params!
__file__, n, ntermhess, nsample, seed )
print title
...
np.random.seed(seed) # for reproducible runs
np.set_printoptions( threshold=100, edgeitems=10, linewidth=100,
formatter = dict( float = lambda x: "%.3g" % x )) # float arrays %.3g
lo, hi = bounds.T # vecs of numbers or +- np.inf
print "lo:", lo
print "hi:", hi
fx = [] # accumulate all the final f, x
for jsample in range(nsample):
# x0 uniformly random in box lo .. hi --
x0 = lo + np.random.uniform( size=n ) * (hi - lo)
x, f, d = fmin_l_bfgs_b( func, x0, approx_grad=1,
m=ntermhess, factr=factr, pgtol=pgtol )
print "f: %g x: %s x0: %s" % (f, x, x0)
fx.append( np.r_[ f, x ])
fx = np.array(fx) # nsample rows, 1 + dim cols
np.savetxt( "fx-opt.nptxt", fx, fmt="%8.3g", header=title ) # to analyze / plot
ffinal = fx[:,0]
xfinal = fx[:,1:]
print "final f values, sorted:", np.sort(ffinal)
jbest = ffinal.argmin()
print "best x:", xfinal[jbest]
如果一些ffinal
值看起来相当不错,
尝试更多接近那些值的随机起点——这比纯随机要好。
如果x
是曲线或其他实际对象,绘制最佳的几个x0
和xfinal
。
(一个经验法则是在d
维度中使用nsample ~ 5*d或10*d。
过于缓慢或过多?减少maxiter
/maxeval
,减少ftol
——对于这种探索,你不需要ftol
1e-6。)
如果您想要可重复的结果,
那么您必须在title
和派生文件和图表中列出所有相关参数。
否则,您会问“这是从哪里来的?”
from scipy.optimize._numdiff import approx_derivative # 3-point, much better than
## from scipy.optimize import approx_fprime
for eps in [1e-3, 1e-6]:
grad = approx_fprime( x, func, epsilon=eps )
print "approx_fprime eps %g: %s" % (eps, grad)
[f, x, approx_fprime]
来观察它们;在Python中很容易做到-如果这不清楚,请告诉我。xmin
重新开始是很常见的。例如,如果你在乡间小道上迷路了,首先找到一条主要道路,然后从那里重新开始。x0=np.array((10, 13, f*2.5, 0.08, 10, f*1.5, 0.06, 20,
10, 14, f*2.5, 0.08, 10, f*1.75, 0.07, 20,
10, 15, f*2.5, 0.08, 10, f*2, 0.08, 20,
10, 16, f*2.5, 0.08, 10, f*2.25, 0.09, 20,
10, 17, f*2.5, -0.08, 10, f*2.5, -0.06, 20,
10, 18, f*2.5, -0.08, 10, f*2.75,-0.07, 20,
10, 19, f*2.5, -0.08, 10, f*3, -0.08, 20,
10, 20, f*2.5, -0.08, 10, f*3.25,-0.09, 20))
# boundary for each variable, each element in this restricts the corresponding element above
bnds=((1,12), (1,35), (0,f*6.75), (-0.1, 0.1),(1,35), (0,f*6.75), (-0.1, 0.1),(13, 35),
(1,12), (1,35), (0,f*6.75), (-0.1, 0.1),(1,35), (0,f*6.75), (-0.1, 0.1),(13, 35),
(1,12), (1,35), (0,f*6.75), (-0.1, 0.1),(1,35), (0,f*6.75), (-0.1, 0.1),(13, 35),
(1,12), (1,35), (0,f*6.75), (-0.1, 0.1),(1,35), (0,f*6.75), (-0.1, 0.1),(13, 35),
(1,12), (1,35), (0,f*6.75), (-0.1, 0.1),(1,35), (0,f*6.75), (-0.1, 0.1),(13, 35),
(1,12), (1,35), (0,f*6.75), (-0.1, 0.1),(1,35), (0,f*6.75), (-0.1, 0.1),(13, 35),
(1,12), (1,35), (0,f*6.75), (-0.1, 0.1),(1,35), (0,f*6.75), (-0.1, 0.1),(13, 35),
(1,12), (1,35), (0,f*6.75), (-0.1, 0.1),(1,35), (0,f*6.75), (-0.1, 0.1),(13, 35), )
from scipy.optimize import basinhopping
from scipy.optimize import minimize
merit=a*meritoflength + b*meritofROC + c*meritofproximity +d*(distancetoceiling+distancetofloor)+e*heightorder
minimizer_kwargs = {"method": "L-BFGS-B", "bounds": bnds, "tol":1e0}
ret = basinhopping(merit_function, x0, minimizer_kwargs=minimizer_kwargs, niter=10, T=0.01)
zoom = ret['x']
res = minimize(merit_function, zoom, method = 'L-BFGS-B', bounds=bnds, tol=1e-5)
print res
优点函数将x0与其他一些值结合起来形成8条曲线的6个控制点,然后计算它们的长度、曲率半径等。它将这些参数的线性组合与一些权重返回为最终的优点。
我使用低精度的basinhopping
找到了一些极小值,然后使用minimize
增加了最低极小值的精度。
附注:我正在运行的平台是Enthoght Canopy 1.3.0,numpy 1.8.0,scipy 0.13.2,mac 10.8.3。