Python SciPy : 大域的最適化アルゴリズム

今回は SciPy の 大域的最適化の関数 についてまとめます。

関数について

SciPy の大域的最適化の関数 には表 1 のものがあります。
SciPy には焼きなまし法の関数 anneal もありますが、これは今後削除される予定で、代わりに basin hopping の使用が推奨されています。

大域的最適化は求めた解が真の大域的最適値であるかわからないことなどから、取り扱いの難しい問題です。
また計算に時間もかかるので、どんな問題にでも使えば良いというものではないので注意が必要です。

Table 1: 大域的最適化
関数 説明
basinhoppping bashin hopping 法
brute 力まかせ法
differential_evolution 微分進化法

basin hopping 法は最初にランダムな初期値を作成し、そこから局所的最適化手法で局所的最小値を探索します。
求まった最小値に基づいて新たに初期値を作成し、そこからまた局所的最小値を探索します。
これを繰り返すことで、大域的最小値を探索します。
局所的最適化手法に偏導関数を与える高速なアルゴリズムを選択すれば、高速に大域的最適値を求めることができます。
うまく大域的最適値を計算するには、初期値を作成する際のステップ幅や、メトロポリス法により新しい初期値を採用するか決めるための制御パラメータ T の調整が必要です。

力まかせ法は指定した範囲の格子点から総当たりで最小値を探索します。
そのため、計算には時間がかかりますが、指定範囲に大域的最小値があることがわかっているなら、確実にそれを求めることができます。

differential_evolution は ver0.15 から追加された進化的アルゴリズムの大域的最適化手法です。
計算時間はかかりますが,局所的最小値が多い問題でも比較的にうまく大域的最小値を求めることができます。

differentail_evolution で Beale 関数 の最小値を求めてみます。

# coding: utf-8
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
      x: array([ 3. ,  0.5])
    fun: 5.7298214938248304e-21
   nfev: 1773
success: True
message: 'Optimization terminated successfully.'
    nit: 58

これをプロットするとこうなります。

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

15062401.png

コメント

Comments powered by Disqus
書籍更新情報
2016-10-21
Pythonによる科学技術計算 基礎編
PDF版の販売を開始しました。
販売ページはこちら

2016-09-09
Pythonによる科学技術計算 基礎編
1.2版への更新が可能になりました。
サポートページはこちら
電子書籍
Pythonによる科学技術計算 基礎編
Kindle ストア、Leanpubで販売中です
Pythonによる科学技術計算 基礎編
PDF版の販売はこちら
同人誌
技術書典(2016/6/25)
Emacs/org-modeのPDF作成術
電子版をBOOTHで販売中です
Emacs/org-modeのPDF作成術
Share