Python SciPy : 大域的最適化アルゴリズム
今回は SciPy の 大域的最適化の関数 についてまとめます。
関数について
SciPy の大域的最適化の関数 には表 1 のものがあります。 SciPy には焼きなまし法の関数 anneal もありますが、これは今後削除される予定で、代わりに basin hopping の使用が推奨されています。
大域的最適化は求めた解が真の大域的最適値であるかわからないことなどから、取り扱いの難しい問題です。 また計算に時間もかかるので、どんな問題にでも使えば良いというものではないので注意が必要です。
関数 | 説明 |
---|---|
basinhoppping | bashin hopping 法 |
brute | 力まかせ法 |
differential_evolution | 微分進化法 |
basin hopping 法は最初にランダムな初期値を作成し、そこから局所的最適化手法で局所的最小値を探索します。 求まった最小値に基づいて新たに初期値を作成し、そこからまた局所的最小値を探索します。 これを繰り返すことで、大域的最小値を探索します。 局所的最適化手法に偏導関数を与える高速なアルゴリズムを選択すれば、高速に大域的最適値を求めることができます。 うまく大域的最適値を計算するには、初期値を作成する際のステップ幅や、メトロポリス法により新しい初期値を採用するか決めるための制御パラメータ T の調整が必要です。
力まかせ法は指定した範囲の格子点から総当たりで最小値を探索します。 そのため、計算には時間がかかりますが、指定範囲に大域的最小値があることがわかっているなら、確実にそれを求めることができます。
differential_evolution は ver0.15 から追加された進化的アルゴリズムの大域的最適化手法です。 計算時間はかかりますが,局所的最小値が多い問題でも比較的にうまく大域的最小値を求めることができます。
例
differentail_evolution で Beale 関数 の最小値を求めてみます。
import numpy as np import matplotlib.pyplot as plt from scipy.optimize import rosen, differential_evolution, minimize, basinhopping from mpl_toolkits.mplot3d import Axes3D def simple_fitness(x): return (1.5-x[0]+x[0]*x[1])**2+(2.25-x[0]+x[0]*x[1]**2)**2+(2.625-x[0]+x[0]*x[1]**3)**2 bounds = [(-4.5, 4.5), (-4.5, 4.5)] res = differential_evolution(simple_fitness, bounds) res
fun: 2.3619858081802966e-20 message: 'Optimization terminated successfully.' nfev: 2163 nit: 71 success: True x: array([ 3. , 0.5])
これをプロットするとこうなります。
fig = plt.figure() ax = fig.gca(projection='3d') x = np.arange(-4.5, 4.5, 0.4) y = np.arange(-4.5, 4.5, 0.4) xx, yy = np.meshgrid(x, y, sparse=True) z = (1.5-xx+xx*yy)**2+(2.25-xx+xx*yy**2)**2+(2.625-xx+xx*yy**3)**2 ax.plot_wireframe(xx, yy, z) ax.scatter(res.x[0], res.x[1], simple_fitness(res.x), s=100, c="r") # plt.show()
