LoginSignup
3

More than 5 years have passed since last update.

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()

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
3