PSOのアルゴリズムは、以下の手順で進む。
- 個体群を初期化する: 初期位置と初期速度をランダムに決定する。各個体は、探索空間内のランダムな位置に配置され、ランダムな速度を持つ。
- 各個体の評価関数を計算する: 各個体の位置を使って、評価関数の値を計算する。
- 各個体が持つ「自分がこれまでに発見した中での最良解」を更新する: 各個体がこれまでに発見した中で最良の解を記憶する。これをパーソナルベストと呼ぶ。
- 個体群が持つ「全体で最良の解」を更新する: 個体群全体で最も優れた解をグローバルベストと呼ぶ。グローバルベストは、パーソナルベストよりも優れた解であれば更新される。
- 各個体の速度を更新する: 各個体は、現在の速度と加速度を使って、新しい速度を計算する。加速度は、以下の式で求められる。\[a_i = c_1 \times rand() \times (p_{best_i} – x_i) + c_2 \times rand() \times (g_{best} – x_i)\]ここで、aiは加速度、c1とc2は乱数の係数、pbestiは個体iが持つパーソナルベスト、xiは個体iの現在の位置、gbestは全体のグローバルベストを表す。
- 各個体の位置を更新する: 各個体は、現在の位置と新しい速度を使って、新しい位置を計算する。
- 終了条件をチェックする: 終了条件が満たされたら、探索を終了r.。そうでなければ、ステップ2に戻る。
PSOは、上記の手順を繰り返すことで最適解を探索する。探索空間内の個体群の位置と速度が変化することによって、最適解に近づくように探索が進む。
PSOは、様々な問題に適用できる。以下にいくつかの具体的な適用例について述べる。
- パターン認識: PSOは、ニューラルネットワークの重みを最適化するために使用されることがある。例えば、顔認識や音声認識などのパターン認識問題において、PSOは高い精度を発揮することが報告されている。
- ロボット制御: PSOは、ロボット制御問題にも適用される。例えば、逆運動学問題や軌道生成問題において、PSOは高い制御精度を発揮することが報告されている。
- 組合せ最適化問題: 組合せ最適化問題は、ある制約の下で最適な解を見つける問題となる。例えば、巡回セールスマン問題やバックパッキング問題などがある。PSOは、これらの問題にも適用されており、高い解の品質を得ることができる。
- パラメータ最適化: PSOは、関数のパラメータを最適化するためにも使用される。例えば、シミュレーションや最適制御問題において、PSOはパラメータの最適化に使用されることがある。
- ニューラルネットワークのトレーニング: PSOは、ニューラルネットワークのトレーニングにも使用される。例えば、多層パーセプトロンの重みやバイアスを最適化するために、PSOが使用されることがある。
これらの例以外にも、PSOは様々な問題に適用されている。
PSOを使った実際の実装には以下のようなものがある。
Pythonでの実装
python環境構築に関しては”Pythonと機械学習“を参照のこと。
Python には PySwarms というライブラリがあり、pip で簡単に入れることができるものを利用した例。
pip install pyswarms
# Import modules
import numpy as np
# Import PySwarms
import pyswarms as ps
from pyswarms.utils.functions import single_obj as fx
# Some more magic so that the notebook will reload external python modules;
# see http://stackoverflow.com/questions/1907993/autoreload-of-modules-in-ipython
%load_ext autoreload
%autoreload 2
独自の実装。コードはgithubに掲載されている。
RでのPSO実装
Rの環境構築に関しては”R言語と機械学習“を参照のこと。
理論とtutorialが丁寧に記載されているRを使ったPSOの実装のページ。単純なhello worldではなく様々な実用例に即したサンプルコードがある。
例1: Engineering: Optimizing Spring Weight
この問題は，Hu et al.(2003) 3.の問題を複製したもので，最小たわみ，せん断応力，サージ周波数，外径の制限，設計変数の制約を受けた引張圧縮ばねの重量を最小化するものである。設計変数は，平均コイル径D，線径d，有効コイル数Nである：
例2:Finance: Portofolio Optimization
この問題はZhu et al.(2011)5から複製されたもので、この研究では投資管理におけるポートフォリオの選択と最適化にPSOアルゴリズムが採用されている。
ポートフォリオ最適化問題は、与えられたレベルのリターンを保証するための制約条件下で、リスク目標を最小化する資産のポートフォリオを管理することに関係します。金融投資の基本原則の1つは分散投資であり、投資家は異なる種類の資産に投資を分散させる。ポートフォリオの分散は、投資家のリスクへのエクスポージャーを最小化し、ポートフォリオのリターンを最大化する。
フィットネス関数は、制限されたポートフォリオの調整済みシャープレシオです。これは、資産の平均と分散からの情報を組み合わせ、平均リターンのリスク調整尺度として機能するもので、ポートフォリオのパフォーマンスを評価するためによく使用される。
シャープレシオは、ポートフォリオの超過収益が賢い投資判断によるものか、それともリスクが高すぎた結果なのかを説明するのに役立ちます。あるポートフォリオやファンドは、同業他社よりも高いリターンを享受できますが、その高いリターンが過剰な追加リスクを伴わない場合にのみ、良い投資となります。
ポートフォリオのシャープレシオが大きいほど、リスク調整後のパフォーマンスが優れていることを意味します。分析の結果、シャープレシオがマイナスになった場合は、リスクフリーレートがポートフォリオのリターンを上回っているか、ポートフォリオのリターンがマイナスになることが予想されることを意味します。
Clojureでの実装
Clojureの環境立ち上げに関しては”SublimeText4とVS code、LightTableでのClojureの開発環境立ち上げ“を参照のこと。
CAPSOS (Cellular Automata, Particle Swarm Optimization, Synth)のgitのページ
(ns capsos.pso-test
(:use midje.sweet
capsos.pso))
;; (defn update-particle-xy
;; [gbest p]
;; (let [pbest (:pbest p)
;; nvelx (+ (* 2 (rand) (- (first pbest) (:x p)))
;; (* 2 (rand) (- (first gbest) (:x p))))
;; nvely (+ (* 2 (rand) (- (second pbest) (:y p)))
;; (* 2 (rand) (- (second gbest) (:y p))))]
;; (assoc p :x (+ nvelx (:x p)) :y (+ nvely (:y p)) :vel [nvelx nvely])))
(def ^:dynamic ^java.util.Random *rnd* (java.util.Random. 42))
;;(.nextDouble *rnd*)
(make-particle 1000 1000)
;; => {:x 740, :y 815, :pbest [740 815]}
(last (take 90000 (iterate (partial update-particle-xy [50 50]) {:x 740, :y 815, :pbest [740 815]})))
(update-particle-xy [50 50] {:x 740, :y 815, :pbest [740 815]})
{:norm-vel [-0.36547344376116647 -0.930821766991594], :vel [-473.25580940929353 -1205.3319229434064], :y 814.0691782330084, :x 739.6345265562388, :pbest [740 815]}
{:norm-vel [-0.4051418860917991 -0.9142538225974118], :vel [-633.3074826612985 -1429.138301368925], :y 649.0857461774026, :x 637.5948581139082, :pbest [1 1]}
;; (facts "Particle XY updating"
;; (update-particle-xy [0 0] {:pbest [0 0] :x 1 y 1})
;; =>
;; )
コメント
[…] 粒子群最適化(PSO)の概要と実装について […]