Differential Evolution (差分進化)

import random
from typing import Tuple

import numpy


def Ackley(x: numpy.array) -> float:
    """目的関数"""
    a = 20
    b = 0.2
    c = 2 * numpy.pi
    ret = a - a * numpy.exp(-b * numpy.sqrt(numpy.sum(x ** 2) / len(x))) \
        + numpy.e - numpy.exp(numpy.sum(numpy.cos(c * x)) / len(x))
    return ret


def DE(target, ranges, np=40, cr=0.5, f=0.5, loop=10, verbose=False) -> Tuple[numpy.array, float]:
    """最適化の実行

    Parameters
    ----------
    target: numpy.array -> float
        最小化する目的関数
    ranges: List[Tuple(float, float)]
        パラメータ空間（超区間とする）
    np: int
        num of population
        シードを保存するプールのサイズ
    cr: float
        交叉確率
        assert 0 < cr < 1
    f: float
        交叉のさせ方（混ぜ方）
        assert 0 < f < 1
    loop: int
        ステップ実行回数
    """

    def make_random():
        x = numpy.array([numpy.random.uniform(left, right) for left, right in ranges])
        return x

    xs = [make_random() for _ in range(np)]
    ys = [target(x) for x in xs]
    mini = ys[0]
    min_index = 0

    for _ in range(loop):
        for i in range(np):
            j1, j2, j3 = random.sample(range(np - 1), 3)
            a = xs[(i + j1 + 1) % np]
            b = xs[(i + j2 + 1) % np]
            c = xs[(i + j3 + 1) % np]
            x_new = xs[i] + 0.0
            # cross
            k = random.choice(range(len(ranges)))
            for j in range(len(ranges)):
                if j == k or random.random() < cr:
                    x_new[j] = a[j] + f * (b[j] - c[j])
            x_new = numpy.array(x_new)

            y_new = target(x_new)
            if y_new < ys[i]:
                xs[i] = x_new
                ys[i] = y_new
                if y_new < mini:
                    mini = y_new
                    min_index = i
                    if verbose:
                        print(mini)

    return xs[min_index], ys[min_index]


result = DE(Ackley, [[0, 20], [-100, 100]], loop=100, verbose=True)
print(result)