У меня есть функция Python с 64 переменными, и я попытался оптимизировать ее с использованием метода L-BFGS-B в функции минимизации, однако этот метод довольно сильно зависит от первоначальной догадки и не смог найти глобальный минимум,
Но мне понравилась его способность устанавливать границы для переменных. Есть ли способ/функция, чтобы найти глобальный минимум, имея границы для переменных?
Это можно сделать с помощью scipy.optimize.basinhopping. Basinhopping - это функция, предназначенная для определения глобального минимума целевой функции. Он выполняет повторные минимизации с помощью функции scipy.optimize.minimize и выполняет случайный шаг в пространстве координат после каждой минимизации. Basinhopping все еще может уважать границы, используя один из минимизаторов, которые реализуют границы (например, L-BFGS-B). Вот какой код, который показывает, как это сделать
# 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
Вышеприведенный код будет работать в простейшем случае, но вы все равно можете оказаться в запрещенном регионе, если вам понадобится процедура случайного перемещения базы данных. К счастью, это можно переопределить путем передачи пользовательского шага с использованием ключевого слова 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
Некоторые предложения здравого смысла для отладки и визуализации любого оптимизатора по вашей функции:
Являются ли ваши целевые функции и ваши ограничения разумными?
Если целевой функцией является сумма, скажем f() + g(),
напечатайте их отдельно для всех x в "fx-opt.nptxt" (см. ниже);
если f() составляет 99% от суммы и g() 1%, исследуйте.
Ограничения: сколько компонентов x_i в xfinal застревает в границах,
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.
(Эмпирическое правило имеет размер nsample ~ 5 * d или 10 * d в d.
Слишком медленно, слишком много? Уменьшите maxiter/maxeval, уменьшите ftol -
вам не нужно ftol 1e-6 для исследования, подобного этому.)
Если вы хотите воспроизводимые результаты,
то вы должны перечислить ВСЕ соответствующие параметры в title
и в производных файлах и графиках.
В противном случае вы спросите "откуда это взялось?"
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.
Например, если вы потерялись на проселочной дороге,
сначала найдите главную дорогу, затем перезапустите оттуда.
x, f, d = fmin_l_bfgs_b( func, x0, approx_grad=1,
m=ntermhess, factr=factr, pgtol=pgtol, epsilon=eps )
# give values for these -- explicit is better than implicit
versions: numpy 1.8.0 scipy 0.13.2 python 2.7.6 mac 10.8.3
Большое спасибо вашему подробному ответу, но поскольку я довольно новичок в python, я не знал, как реализовать код для моей программы, но вот моя попытка оптимизации:
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 с некоторыми другими значениями для формирования 6 контрольных точек для 8 кривых, затем вычисляет их длины, радиусы кривизны и т.д. Она возвращает окончательное достоинство в виде линейных комбинаций этих параметров с некоторыми весами.
i использовал basinhopping с низкими значениями, чтобы найти некоторые минимумы, а затем использовал minimize для повышения точности наименьшего munimum.
p.s. платформа, на которой я запущена, - это Enthoght canopy 1.3.0, numpy 1.8.0 scipy 0.13.2 mac 10.8.3