"""
Pure Python/Numpy implementation of the Nelder-Mead algorithm.
Taken from `fchollet`_; also see `Wikipedia entry`_
.. _fchollet: https://github.com/fchollet/nelder-mead
.. _Wikipedia entry: https://en.wikipedia.org/wiki/Nelder%E2%80%93Mead_method
"""
import copy
from functools import partial
[docs]
def nelder_mead(
func,
x_start,
step=0.1,
no_improve_thr=10e-6,
no_improv_break=10,
max_iter=0,
alpha=1.0,
gamma=2.0,
rho=-0.5,
sigma=0.5,
converged=None,
*args,
**kwargs,
):
"""
@param f (function): function to optimize, must return a scalar score
and operate over a numpy array of the same dimensions as x_start
@param x_start (numpy array): initial position
@param step (float): look-around radius in initial step
@no_improv_thr, no_improv_break (float, int): break after no_improv_break iterations with
an improvement lower than no_improv_thr
@max_iter (int): always break after this number of iterations.
Set it to 0 to loop indefinitely.
@alpha, gamma, rho, sigma (floats): parameters of the algorithm
(see Wikipedia page for reference)
return: tuple (best parameter array, best score)
"""
# init
# define function call as a partial with kwargs as input
print("Creating opt func as", func.__name__, args, kwargs)
f = partial(func, *args, **kwargs)
dim = len(x_start)
prev_best = f(x_start)
no_improv = 0
res = [[x_start, prev_best]]
for i in range(dim):
x = copy.copy(x_start)
if isinstance(step, (list, tuple)) and len(x) == len(step):
x[i] = x[i] + step[i]
else:
x[i] = x[i] + step
score = f(x)
res.append([x, score])
# simplex iter
iters = 0
while 1:
# order
res.sort(key=lambda x: x[1])
best = res[0][1]
# break if <= converged
if converged is not None and best <= converged:
return res[0]
# break after max_iter
if max_iter and iters >= max_iter:
return res[0]
iters += 1
# break after no_improv_break iterations with no improvement
print("...best so far:", best)
if best < prev_best - no_improve_thr:
no_improv = 0
prev_best = best
else:
no_improv += 1
if no_improv >= no_improv_break:
return res[0]
# centroid
x0 = [0.0] * dim
for tup in res[:-1]:
for i, c in enumerate(tup[0]):
x0[i] += c / (len(res) - 1)
# reflection
xr = x0 + alpha * (x0 - res[-1][0])
rscore = f(xr)
if res[0][1] <= rscore < res[-2][1]:
del res[-1]
res.append([xr, rscore])
continue
# expansion
if rscore < res[0][1]:
xe = x0 + gamma * (x0 - res[-1][0])
escore = f(xe)
if escore < rscore:
del res[-1]
res.append([xe, escore])
continue
else:
del res[-1]
res.append([xr, rscore])
continue
# contraction
xc = x0 + rho * (x0 - res[-1][0])
cscore = f(xc)
if cscore < res[-1][1]:
del res[-1]
res.append([xc, cscore])
continue
# reduction
x1 = res[0][0]
nres = []
for tup in res:
redx = x1 + sigma * (tup[0] - x1)
score = f(redx)
nres.append([redx, score])
res = nres
if __name__ == "__main__":
# test
import math
import numpy as np
def f(x):
return math.sin(x[0]) * math.cos(x[1]) * (1.0 / (abs(x[2]) + 1))
print(nelder_mead(f, np.array([0.0, 0.0, 0.0])))