nelder-mead法のアルゴリズム.
画像認識系深層学習のハイパパラメータチューニングで定評あり.
Nelder-Mead法は単体をパタパタと折り返すことで最適解を探索するアルゴリズム.
後々,詳細を追加していきます...
import numpy as np
import random
class nelder_mead():
def __init__(
self,
boundaries, # type: (np.ndarray)
iteration, # type: int
func, # type: Callable[[int], int]
coef = {"r": 1.0, "ic": - 0.5, "oc": 0.5, "e": 2.0, "s": 0.5}, # type: dict
):
self.func = func
self.bdrys = boundaries
self.coef = coef
self.itr = iteration
n_dim = len(boundaries)
self.y = np.array([[random.random() * (b[1] - b[0]) + b[0] for b in boundaries]
for j in range(n_dim + 1)])
self.f = np.array([self.F(y) for y in self.y])
self.yc = None
self.storage = {"r": None, "ic": None, "oc": None, "e": None, "s": None}
def order_by(self):
order = np.argsort(self.f)
self.y = self.y[order]
self.f = self.f[order]
def centroid(self):
self.storage = {"r": None, "ic": None, "oc": None, "e": None, "s": None}
self.order_by()
self.yc = self.y[:-1].mean(axis=0)
def reflect(self):
yr = self.yc + self.coef["r"] * (self.yc - self.y[-1])
self.storage["r"] = yr
return self.F(yr)
def expand(self):
ye = self.yc + self.coef["e"] * (self.yc - self.y[-1])
self.storage["e"] = ye
return self.F(ye)
def inside_contract(self):
yic = self.yc + self.coef["ic"] * (self.yc - self.y[-1])
self.storage["ic"] = yic
return self.F(yic)
def outside_contract(self):
yoc = self.yc + self.coef["oc"] * (self.yc - self.y[-1])
self.storage["oc"] = yoc
return self.F(yoc)
def shrink(self):
for i in range(1, len(self.y)):
self.y[i] = self.y[0] + self.coef["s"] * (self.y[i] - self.y[0])
self.f[i] = self.F(self.y[i])
def F(self, y):
if not self.out_of_boundary(y):
return self.func(y)
else:
return 1000000
def out_of_boundary(self, y):
for yi, b in zip(y, self.bdrys):
if b[0] <= yi <= b[1]:
pass
else:
return True
return False
def search(self):
for t in range(self.itr):
self.centroid()
fr = self.reflect()
if self.f[0] <= fr < self.f[-2]:
self.y[-1] = self.storage["r"]
self.f[-1] = fr
elif fr < self.f[0]:
fe = self.expand()
if fe < fr:
self.y[-1] = self.storage["e"]
self.f[-1] = fe
else:
self.y[-1] = self.storage["r"]
self.f[-1] = fr
elif self.f[-2] <= fr < self.f[-1]:
foc = self.outside_contract()
if foc <= fr:
self.y[-1] = self.storage["oc"]
self.f[-1] = foc
else:
self.shrink()
elif self.f[-1] <= fr:
fic = self.inside_contract()
if fic < self.f[-1]:
self.y[-1] = self.storage["ic"]
self.f[-1] = fic
else:
self.shrink()