optimize_ga_swarm_remc.py 技術ドキュメント

プログラムの動作

optimize_ga_swarm_remc.py は、複数の最適化アルゴリズム（遺伝的アルゴリズム、粒子群最適化、レプリカ交換モンテカルロ法、Nelder-Meadシンプレックス法）を使用して、Ackley関数をベースとした多次元関数を最小化するためのPythonスクリプトです。このプログラムは、特にグローバル最適化問題を解決することを目的としており、異なるアルゴリズムの性能比較や、特定の問題に対する最適な探索戦略の評価に役立ちます。

主な機能は以下の通りです。

  • 多種類の最適化アルゴリズムの実装: 遺伝的アルゴリズム (GA)、粒子群最適化 (PSO)、レプリカ交換モンテカルロ (REMC)、および scipy.optimize.minimize を用いたNelder-Meadシンプレックス法をサポートします。

  • Ackley関数の最小化: 2次元または4次元のAckley関数を最適化対象としています。4次元の場合は、2つの2次元Ackley関数の和として定義されます。

  • 柔軟な設定: コマンドライン引数を通じて、使用するアルゴリズム、個体（粒子、レプリカ）数、収束許容誤差、最大イテレーション数、探索範囲などを調整できます。

  • 2次元問題の可視化: 2次元問題の場合、最適化対象関数の3Dプロットを動的に表示し、探索空間を視覚的に確認できます。

  • 収束状況の表示: 探索の進行状況や、現在の最良スコア、探索パラメータが標準出力に表示されます。

このプログラムは、複雑な多峰性を持つ関数（複数の局所最適解を持つ関数）のグローバル最適解を見つけるという課題に取り組んでいます。

原理

Ackley関数

本プログラムで最適化対象となるのはAckley関数です。標準的な2次元Ackley関数 \(f(x, y)\) は以下の数式で定義されます。

\[f(x, y) = -20 \exp\left(-0.2\sqrt{0.5(x^2+y^2)}\right) - \exp\left(0.5(\cos(2\pi x) + \cos(2\pi y))\right) + 20 + e\]

この関数は多くの局所最適解を持ち、グローバル最適解は \((0,0)\) で \(f(0,0) = 0\) となります。プログラムでは、nparameters の設定に応じて、このAckley関数を以下のように組み合わせて使用します。

  • nparameters = 2 の場合: \(f(x_0, x_1) = \text{AckleyFunc}(x_0, x_1)\)

  • nparameters = 4 の場合: \(f(x_0, x_1, x_2, x_3) = \text{AckleyFunc}(x_0, x_1) + 2.0 \cdot \text{AckleyFunc}(x_2, x_3)\)

ここで AckleyFunc はプログラム内で \(X, Y\) を引数にとる関数として実装されています。

遺伝的アルゴリズム (GA)

遺伝的アルゴリズムは、ダーウィンの進化論に着想を得た探索メタヒューリスティクスです。個体群（population）を世代交代させながら、より適応度の高い個体（より良い解）を探索します。

  1. 初期化: 探索空間内でランダムに個体群を生成します。

  2. 評価: 各個体（パラメータの組）を目的関数で評価し、適応度（スコア）を算出します。

  3. 選択: 適応度の高い個体が次の世代の親として選択される確率が高くなります（本プログラムではトーナメント選択に似た手法を使用）。

  4. 交叉 (Crossover): 選択された親個体の遺伝情報（パラメータ）を組み合わせて、新しい子個体を生成します。プログラムでは、ランダムな交叉点で2つの親の情報を交換します。

  5. 突然変異 (Mutation): 子個体の一部の遺伝情報（パラメータ）をランダムに変化させます。これにより、多様性を維持し、局所最適解からの脱出を促します。

  6. 世代交代: 新しく生成された子個体群が次の世代となります。このプロセスを収束条件または最大イテレーション数に達するまで繰り返します。

粒子群最適化 (PSO)

粒子群最適化は、鳥の群れや魚の群れの社会行動をモデルにした最適化アルゴリズムです。各粒子は探索空間内で移動し、自身の最良の経験（個人的最良点）と群れ全体の最良の経験（全体的最良点）に基づいて移動方向を決定します。

各粒子 \(i\) の位置 \(x_i\) と速度 \(v_i\) は、以下の更新式に従って更新されます。

  1. 速度の更新: $\(v_i(t+1) = w v_i(t) + c_1 r_1 (p_{best,i} - x_i(t)) + c_2 r_2 (g_{best} - x_i(t))\)$ ここで、

    • \(w\): 慣性重み。現在の速度への慣性を表します。

    • \(c_1\): 認知成分係数。粒子自身の最良経験 (p_best_i) へ向かう傾向を制御します。

    • \(c_2\): 社会成分係数。群れ全体の最良経験 (g_best) へ向かう傾向を制御します。

    • \(r_1, r_2\): \(0\) から \(1\) の範囲のランダムな値。

    • \(p_{best,i}\): 粒子 \(i\) がこれまでに発見した最も良い位置（個人的最良点）。

    • \(g_{best}\): 群れ全体がこれまでに発見した最も良い位置（全体的最良点）。

  2. 位置の更新: $\(x_i(t+1) = x_i(t) + v_i(t+1)\)$ 粒子の位置は探索空間の境界内に制限されます。

レプリカ交換モンテカルロ (REMC)

レプリカ交換モンテカルロ法は、通常のモンテカルロ法が陥りやすい局所最適解の問題を克服するための手法です。異なる温度（または他のパラメータ）を持つ複数の「レプリカ」（独立したシミュレーション）を並行して実行し、周期的にレプリカ間で状態の交換を試みます。

  1. 各レプリカのモンテカルロ探索: 各レプリカは割り当てられた温度 \(T_j\) で通常のモンテカルロ法を実行します。新しい状態への遷移はメトロポリス基準に基づいて行われます。 $\(P_{accept} = \min(1, \exp(-\Delta E / T_j))\)\( ここで \)\Delta E$ は新しい状態と現在の状態の目的関数値の差です。

  2. レプリカ交換: 定期的に、隣接する温度のレプリカ（例: \(T_j\) と \(T_{j+1}\)）間で状態を交換するかどうかを決定します。交換の受容確率は以下の式で与えられます。 $\(P_{exchange} = \min(1, \exp((E_{j+1} - E_j) (1/T_j - 1/T_{j+1})))\)\( ここで \)E_j\( と \)E_{j+1}\( はそれぞれレプリカ \)j\( と \)j+1$ の現在の目的関数値です。高温のレプリカは広い範囲を探索しやすく、低温のレプリカは局所最適解を精密に探索する傾向があります。この交換によって、低温レプリカが局所最適解から脱出したり、高温レプリカが見つけた良い解を低温レプリカが引き継いだりすることが可能になります。

Nelder-Meadシンプレックス法

Nelder-Meadシンプレックス法は、勾配情報を使用しない直接探索法の一つで、多次元空間における関数の最小値を探索します。シンプレックス（N次元空間におけるN+1個の頂点を持つ多面体）を形成し、その中で最も悪い頂点を他の点に置き換える操作（反射、拡張、収縮など）を繰り返すことで、最小値に向かってシンプレックスを移動させ、収縮させます。

本プログラムでは、scipy.optimize.minimize 関数を method='Nelder-Mead' として呼び出すことで利用しています。

必要な非標準ライブラリとインストール方法

このプログラムを実行するには、以下の非標準Pythonライブラリが必要です。

  • numpy: 数値計算を効率的に行うためのライブラリです。

  • scipy: 科学技術計算のためのライブラリで、特に最適化機能（minimize）を使用します。

  • matplotlib: データの可視化（プロット）のためのライブラリです。

これらのライブラリは pip コマンドを使用してインストールできます。

pip install numpy scipy matplotlib

必要な入力ファイル

このプログラムは、外部の入力ファイルを直接読み込むことはありません。すべての設定はコマンドライン引数またはプログラム内部の定数として与えられます。

生成される出力ファイル

このプログラムは、最適化結果をファイルとして保存することはありません。 すべての最適化結果、収束情報、および実行中のログは標準出力（コンソール）に表示されます。

ただし、nparameters が 2 に設定されている場合、プログラム実行中に matplotlib によるAckley関数の3Dプロットウィンドウがポップアップ表示されます。これは一時的な可視化であり、ファイルとして保存されるものではありません。

コマンドラインでの使用例 (Usage)

プログラムは、以下の形式でコマンドライン引数を受け取ります。

python optimize_ga_swarm_remc.py [method] [nparents] [tol] [nmaxiter] [bounds_low_param1] [bounds_high_param1] [print_level]

引数の詳細:

  • method (文字列, 必須): 使用する最適化アルゴリズムを指定します。

    • ga: 遺伝的アルゴリズム

    • pso: 粒子群最適化

    • remc: レプリカ交換モンテカルロ

    • simplex: Nelder-Meadシンプレックス法

    • all: 上記の全てのアルゴリズムを順番に実行します。

  • nparents (整数, オプション):

    • GA, PSO, REMC: 集団サイズ (個体数、粒子数、レプリカ数)。デフォルトは 50。

    • Simplex: この引数は使用されません。

  • tol (浮動小数点数, オプション): 収束判定の許容誤差。目的関数値がこの値以下になった場合に収束とみなされます。デフォルトは 1.0e-3。

  • nmaxiter (整数, オプション): 最大イテレーション数（世代数、ステップ数）。この回数を超えると、収束していなくても探索を終了します。デフォルトは 100。

  • bounds_low_param1 (浮動小数点数, オプション): 探索範囲の全ての変数の下限値を設定します。

    • nparameters = 2 の場合: 両方の変数の下限がこの値に設定されます。

    • nparameters = 4 の場合: 最初の2つの変数の下限がこの値に設定されます（残りの変数はデフォルトのまま）。

  • bounds_high_param1 (浮動小数点数, オプション): 探索範囲の全ての変数の上限値を設定します。

    • nparameters = 2 の場合: 両方の変数の上限がこの値に設定されます。

    • nparameters = 4 の場合: 最初の2つの変数の上限がこの値に設定されます（残りの変数はデフォルトのまま）。

  • print_level (整数, オプション): 途中経過の出力レベル。0 で最小限の出力、1 で各イテレーションでの途中結果が出力されます。デフォルトは 0。

注意点:

  • プログラム内で nparameters が 2 または 4 に固定されています。スクリプトを編集しない限り、この変数の数を変更することはできません。

  • bounds_low_param1 および bounds_high_param1 は、nparameters=2 の場合はすべての変数の範囲を設定しますが、nparameters=4 の場合は最初の2つの変数の範囲のみを設定します。残りの変数の範囲は、プログラム内のデフォルト値（[-10, 10]）が適用されます。

コマンドラインでの具体的な使用例

以下の例では、プログラム内の nparameters が 2 に設定されているものと仮定します。

遺伝的アルゴリズム (GA) を使用した最適化

個体数 100、収束許容誤差 1e-5、最大イテレーション数 200 で遺伝的アルゴリズムを実行します。

python optimize_ga_swarm_remc.py ga 100 1e-5 200

実行結果例:

method: ga
bounds: [[-10, 10], [-10, 10]]
initial guess: [5, 5]
nmaxiter: 200

method: ga
Not converged

Best parameters: [ 0.00032918 -0.00078027]
Best score: 0.0039290076295519395
icall=19900  iter=0

Press ENTER to terminate>>

この例では、nparameters=2 の場合、プログラムの実行中にAckley関数の3Dプロットが表示されます。最適化結果として、Best parameters と Best score、そして関数呼び出し回数 (icall) とコールバック回数 (iter) が表示されます。この例では tol に到達せず、nmaxiter で終了したため "Not converged" と表示されていますが、目標に近い解が見つかっています。

粒子群最適化 (PSO) を使用した最適化

粒子数 80、最大イテレーション数 150 で粒子群最適化を実行します。探索範囲を [-5, 5] に設定します。

python optimize_ga_swarm_remc.py pso 80 1e-3 150 -5 5

実行結果例:

method: pso
bounds: [[-5.0, 5.0], [-5.0, 5.0]]
initial guess: [5, 5]
nmaxiter: 150

method: pso
Converged

Best parameters: [ 0.00000000e+00 -1.11022302e-16]
Best score: 0.0
icall=12000  iter=1

Press ENTER to terminate>>

この例では、指定された tol に到達し、"Converged" と表示されています。最適解 \((0,0)\) に非常に近い解が見つかり、スコアも 0.0 になっています。

レプリカ交換モンテカルロ (REMC) を使用した最適化

レプリカ数 30、最大イテレーション数 300 でレプリカ交換モンテカルロを実行します。

python optimize_ga_swarm_remc.py remc 30 1e-3 300

実行結果例:

method: remc
bounds: [[-10, 10], [-10, 10]]
initial guess: [5, 5]
nmaxiter: 300

method: remc
Not converged

Best parameters: [ 0.0003003  -0.00078345]
Best score: 0.003943962635398246
icall=9000  iter=0

Press ENTER to terminate>>

Nelder-Meadシンプレックス法を使用した最適化

シンプレックス法は nparents 引数を使用しないため、省略します。

python optimize_ga_swarm_remc.py simplex 1e-3 100

実行結果例:

method: simplex
bounds: [[-10, 10], [-10, 10]]
initial guess: [5, 5]
nmaxiter: 100

method: simplex
Converged

Best parameters: [-6.89201977e-07 -6.89201977e-07]
Best score: 1.8344331572979203e-10
icall=155  iter=27

Press ENTER to terminate>>

全てのアルゴリズムを実行する

all オプションを使用すると、指定された設定（ただし、アルゴリズムごとの nparents はデフォルトか指定があればそれを使用）で全ての最適化アルゴリズムを順番に実行します。

python optimize_ga_swarm_remc.py all 50 1e-3 100

実行結果例:

method: all
bounds: [[-10, 10], [-10, 10]]
initial guess: [5, 5]
nmaxiter: 100

method: ga
Not converged

Best parameters: [ 0.00109725 -0.00018593]
Best score: 0.004169623838428807
icall=9900  iter=0

method: pso
Converged

Best parameters: [-2.22044605e-16 -2.22044605e-16]
Best score: 0.0
icall=5000  iter=1

method: remc
Not converged

Best parameters: [ 0.00072535 -0.00010041]
Best score: 0.004071373979843656
icall=3000  iter=0

method: simplex
Converged

Best parameters: [-6.89201977e-07 -6.89201977e-07]
Best score: 1.8344331572979203e-10
icall=155  iter=27

Press ENTER to terminate>>