Home > Blog > プログラミング > Pythonによる粒子群最適化

Pythonによる粒子群最適化

数理最適化を応用した最適化問題の解決には、微分不可能な関数にも対応可能なメタヒューリスティック手法が広く利用されています。その中でも、生物の群れ行動を模倣した群知能は、複雑な問題に対して高い適応性を示します。今回は、代表的な群知能の1つである粒子群最適化（PSO）について詳しく解説します。

数理最適化とは？

数理最適化とは、特定の目標を達成するために、与えられた制約条件の下で、最も良い解（最適解）を数学的に求める手法です。

より具体的に言うと、目的関数と呼ばれる評価したい数値を、制約条件と呼ばれる様々な条件を満たしながら、最大化したり最小化したりすることを目指します。例えば、企業であれば利益を最大化したい、物流であれば輸送コストを最小化したいといった目標が考えられます。

線形計画法や非線形計画法など、数理最適化には様々な手法が存在します。これらの手法は、問題を数学的なモデルとして表現し、コンピュータを用いて効率的に解を求めることができます。

しかし、問題の規模が大きくなったり、問題に非線形性が強く含まれる場合、局所解と呼ばれる、真の最適解ではない解に収まってしまう可能性があります。このため、大規模な問題や複雑な問題に対しては、より高度な手法やアルゴリズムが必要となります。

数理最適化の代表的アルゴリズム

メタヒューリスティック最適化とは？

メタヒューリスティック最適化は、自然界に見られる現象や生物の行動から着想を得た、近似解を求めるための汎用的なアルゴリズムです。

厳密な数学的な証明に基づいて最適解を保証する手法とは異なり、メタヒューリスティック最適化は、多様な問題に対して、比較的短時間で高品質な解を得られることを目指します。その特徴から、複雑な問題や大規模な問題に対して特に有効です。

遺伝的アルゴリズム、蟻コロニー最適化、粒子群最適化などが代表的な手法として知られており、それぞれが異なる着想に基づいています。例えば、遺伝的アルゴリズムは生物の進化を模倣し、蟻コロニー最適化はアリの集団行動を模倣するなど、自然界の知恵を工学的な問題解決に活かしています。

引用：最適化手法:メタヒューリスティクスのアルゴリズム（池田 伸太郎）
https://ikeda-lab.com/webarchivefiles/overview_metaheuristics.pdf

群知能と粒子群最適化

粒子群最適化は、鳥の群れや魚の群れが協力して最適な場所を見つけ出す様子を模倣した、群知能と呼ばれる分野の代表的な最適化手法です。

探索空間内に複数の粒子と呼ばれる解候補を配置し、各粒子が自身のこれまでの最良の解（個体最良位置）と、群れ全体で発見された最良の解（全体最良位置）という2つの情報を参考にしながら、最適解を探します。各粒子は、これらの情報に基づいて自身の速度を更新し、探索空間を移動します。

粒子群最適化が得意な分野

  • 連続値最適化問題: 実数値をとる変数で表現される問題（例：関数最小化問題）
  • 多次元探索空間: 変数の数が多く、複雑な形状の探索空間を持つ問題
  • 局所解が多い問題: 局所最適解に陥りやすい問題
  • リアルタイム性が求められる問題: 迅速な解を求める必要がある問題
  • パラメータチューニング: モデルのパラメータを最適化する問題

粒子群最適化が不得意な分野

  • 離散最適化問題: 整数値や有限個の選択肢から解を選ぶ問題（例：ナップサック問題）
  • 制約条件が複雑な問題: 数多くの制約条件が課せられた問題
  • 動的な問題: 問題の環境が時間とともに変化する問題
  • 厳密解が必要な問題: 数学的に証明された最適解を求める必要がある問題
  • 非常に大きな探索空間: 解の候補数が膨大で、探索が困難な問題

粒子群最適化のアルゴリズムの概要

粒子群最適化では、各粒子は以下の情報を保持します。

  • 位置：探索空間における粒子の座標。最適化問題の解の候補となります。
  • 速度：次の位置への移動方向と速さを決定するベクトル。

各粒子は、自身の過去の最良の位置（pbest）と、群全体で最も良い位置（gbest）という2つの情報を参考に、自身の速度を更新し、新たな位置へと移動します。このプロセスを繰り返すことで、粒子は徐々に最適解へと収束していきます。

アルゴリズムの詳細

以下に、粒子群最適化のアルゴリズムを数式を踏まえて解説します。

まずは、数式中で使用する変数の説明です。

  • \( k \)：粒子番号
  • \( t \)：イテレーション回数
  • \( X_k(t) \)：\( k \)番目の粒子の \( t \) 回目の位置
  • \( V_k(t) \)：\( k \)番目の粒子の \( t \) 回目の速度
  • \( X_k^{pbest}(t) \)：\( k \)番目の粒子の \( t \) 回目までの最良の位置
  • \( X^{gbest}(t) \)：全粒子の中で \( t \) 回目までの最良の位置
  • \( \omega \)：慣性重み
  • \( c_1、c_2 \)：認知係数、社会係数
  • \( r_1、r_2 \)：0から1の一様乱数

粒子群最適化では、以下の1～5のステップを通して最適化を行います。

  1. 初期化
    すべての粒子に対して、位置\(X_k(0)\)と速度\(V_k(0)\)をランダムに初期化します。
    　　　　　
  2. 位置更新
    現在の速度に基づいて、粒子の位置を更新します。

    $$
    X_k(t+1) = X_k(t) + V_k(t)
    $$
    　
  3. 速度更新
    以下の式に基づいて、粒子の速度を更新します。

    $$
    V_k(t+1) = ωV_k(t) + c_1r_1(X_k^{pbest}(t) – X_k(t)) + c_2r_2(X^{gbest}(t) – X_k(t))
    $$
    ・慣性項 \(ωV_k(t)\)：過去の速度を反映し、探索のバランスを保ちます。
    ・認知項 \(c_1r_1(X_k^{pbest}(t) – X_k(t))\)：自身の過去の最良の位置に向かって移動する傾向を表します。
    ・社会項 \(c_2r_2(X^{gbest}(t) – X_k(t))\)：群全体の最良の位置に向かって移動する傾向を表します。
    　
  4. 評価
    現在の位置における目的関数の値を評価し、\( X_k^{pbest} \) と \( X^{gbest} \)を更新します。
    　　
  5. 終了判定
    設定された終了条件（最大イテレーション回数、目的関数の値の改善が一定以下など）を満たすまで、複数回のステップを繰り返します。

Pythonによる粒子群最適化の実装

上記で説明したアルゴリズムを直接実装するのもそこまで難しくないですが、Pythonでは粒子群最適化が実装されたライブラリとしてPySwarmsがあるので、今回はこのライブラリの使い方を紹介します。

まず、pipコマンドを使用してPySwarmsをインストールします。

$ pip install pyswarms

では、最適化対象の目的関数を定義しましょう。今回は、 \( f(x_0, x_1) = (x_0 – 2)^2 + (x_1 – 3)^2 \) を目的関数とします。これを、最小化する問題なので、期待値は \( x_0^{\mathrm{best}} = 2, \hspace{2mm} x_1^{\mathrm{best}} = 3 \) となります。

具体的な実装は次の通りです。引数の x は、解候補数 ✕ 探索パラメータ数の次元を持つNumpy形式の配列となります。今回は、単目的最適化なので、戻り値は解候補数 ✕ 1の次元とします。

import numpy as np

def objective(x: np.ndarray) -> np.ndarray:
    """目的関数

    引数:
        x (np.ndarray): x.shape => (解候補数, 探索パラメータ数)

    戻り値:
        np.ndarray: shape => (解候補数, 1)
    """
    return (x[:, 0] - 2.0) ** 2 + (x[:, 1] - 3.0) ** 2

次に、上記の目的関数を最小化するためのコードを実装します。単目的最適化の場合は、pyswarms.singleパッケージに実装されているGlobalBestPSOクラスを使用します。

import pyswarms as ps

# 粒子群最適化のハイパーパラメータ
options = {"c1": 0.5, "c2": 0.3, "w":0.9}

# 粒子群最適化のインスタンスを生成
optimizer = ps.single.GlobalBestPSO(
    n_particles=100,  # 解候補の個数
    dimensions=2,     # 探索パラメータ数
    options=options,
)

# 粒子群最適化を実行
best_cost, best_solution = optimizer.optimize(objective, iters=100)

print(f"Best cost: {best_cost}")
# => Best cost: 2.8245378896062163e-09

print(f"Best solution: {best_solution}")
# => Best solution: [1.99995045 2.99998079]

上記のコードを実行すると、最適化の結果は、\(x_0=1.99995045, \hspace{2mm} x_1=2.99998079 \)となり、期待値とほぼ一致していることが分かります。

以上のように、目的関数さえ定義できてしまえば、PySwarmsによる最適化は少量のコードで実行できてしまいます。

まとめ

粒子群最適化は、鳥の群れや魚の群れの行動を模倣した、直感的で実装しやすいメタヒューリスティックの一種です。特に、連続値最適化問題や複雑な探索空間を持つ問題に対して高い性能を発揮します。

Pythonには、SciPyやNumPyといった数値計算ライブラリや、専用のPSOライブラリが充実しており、実用的な問題に対して容易に粒子群最適化を適用することができます。