この記事について
前回（⓪）はメタヒューリスティクス全体の地図と、共通で使うベンチマーク関数を紹介しました。今回からは具体的な手法を1つずつ見ていきます。最初は群知能の代表格、粒子群最適化（PSO：Particle Swarm Optimization） です。
「鳥や魚の群れが、リーダーもいないのに整然と餌場を見つける」という集団行動をそのまま最適化に持ち込んだ手法で、実装が10行程度と異常に短いのに、よく効くのが魅力です。
メタヒューリスティクス図鑑シリーズの記事一覧はこちら。
| 記事 | 内容 |
|---|---|
| ⓪ | メタヒューリスティクスとは？／探索の地図 |
| ①（本記事） | 粒子群最適化（PSO） |
| ② | 蟻コロニー最適化（ACO） |
| ③ | CMA-ES |
| ④ | 遺伝的アルゴリズム（GA） |
| ⑤ | Cuckoo Search |
| ⑥〜⑪ | Grey Wolf / Harris Hawks / Moth-Flame / Grasshopper / Golden Jackal / Manta Ray |
| ⑫ | まとめ：メタファー系の正体と使い分け |
PSOとは
1995年に Kennedy（社会心理学者）と Eberhart（電気工学者）が提案した手法です。鳥の群れのシミュレーションを研究していたら、最適化に使えることに気づいた、というのが始まりだそうです。
J. Kennedy and R. Eberhart, "Particle swarm optimization,"
Proc. IEEE International Conference on Neural Networks, vol. 4, pp. 1942-1948, 1995.
たくさんの「粒子（particle）」を探索空間にばらまき、各粒子が速度を持って飛び回ります。各粒子は次の2つの記憶を頼りに進む方向を決めます。
- 個人ベスト（pbest）：自分がこれまでに見つけた一番良い場所
- 群ベスト（gbest）：群れ全体がこれまでに見つけた一番良い場所
「自分の成功体験」と「みんなの成功体験」の両方に引っ張られながら飛ぶ、というのが PSO の核心です。
核心：速度更新式
PSO の本体は、各粒子 $i$ の速度 $v_i$ と位置 $x_i$ を更新する、たった2本の式です。
v_i \leftarrow \underbrace{w\, v_i}_{\text{慣性}}
+ \underbrace{c_1 r_1 (p_i - x_i)}_{\text{自分のベストへ}}
+ \underbrace{c_2 r_2 (g - x_i)}_{\text{群れのベストへ}}
x_i \leftarrow x_i + v_i
各項の意味は次のとおりです。
| 項 | 名前 | 意味 |
|---|---|---|
| $w, v_i$ | 慣性項 | 今まで進んできた向きを保つ（探索）。$w$ が大きいほど直進し広く探す |
| $c_1 r_1 (p_i - x_i)$ | 認知項 | 自分のベスト $p_i$ に引き寄せられる（個人の経験） |
| $c_2 r_2 (g - x_i)$ | 社会項 | 群れのベスト $g$ に引き寄せられる（集団の経験） |
- $w$（慣性係数）、$c_1, c_2$（加速係数）はパラメータ
- $r_1, r_2$ は毎回ふり直す $[0,1]$ の一様乱数。これがランダム性を与え、全員が一点に殺到するのを防ぐ
この3つの項を1個の粒子の動きとして図にすると、次のようになります。慣性（グレー）・認知（緑）・社会（オレンジ）の3つのベクトルを足し合わせた向き（赤）に、粒子が次の一歩を踏み出す、というのが速度更新式の意味です。
⓪で出てきた「探索 vs 活用」の軸でいうと、慣性項が探索、認知項・社会項が活用に対応します。慣性係数 $w$ を反復とともに下げていくと、最初は広く探し、だんだん良い解の近くに収束する、という挙動になります。
擬似コード
① 粒子の位置 x と速度 v をランダムに初期化
② 各粒子の pbest を自分自身、gbest を群れの最良に設定
③ 以下を反復：
各粒子について：
v ← w·v + c1·r1·(pbest - x) + c2·r2·(gbest - x) ← 速度更新
x ← x + v ← 位置更新
if f(x) < f(pbest): pbest ← x ← 個人ベスト更新
gbest ← 全 pbest の中で最良 ← 群ベスト更新
④ gbest を返す
Python実装
⓪で定義した Rastrigin 関数（格子状に局所最適がびっしりの多峰性関数）で動かしてみます。本体は速度更新と位置更新だけで、本当に短いです。
import numpy as np
def pso(func, dim=2, n_particles=30, n_iter=50,
w=0.7, c1=1.5, c2=1.5, lim=5.12, seed=0):
rng = np.random.default_rng(seed)
# ① 位置と速度の初期化
X = rng.uniform(-lim, lim, (n_particles, dim))
V = rng.uniform(-1, 1, (n_particles, dim))
# ② pbest / gbest の初期化
pbest = X.copy()
pbest_val = np.array([func(x) for x in X])
g = np.argmin(pbest_val)
gbest, gbest_val = pbest[g].copy(), pbest_val[g]
history = [gbest_val]
for t in range(n_iter):
r1 = rng.random((n_particles, dim))
r2 = rng.random((n_particles, dim))
# 速度更新：慣性 + 自己ベスト + 群ベスト
V = w * V + c1 * r1 * (pbest - X) + c2 * r2 * (gbest - X)
X = np.clip(X + V, -lim, lim) # 位置更新（範囲内にclip）
val = np.array([func(x) for x in X])
improved = val < pbest_val # 個人ベストの更新
pbest[improved] = X[improved]
pbest_val[improved] = val[improved]
g = np.argmin(pbest_val) # 群ベストの更新
if pbest_val[g] < gbest_val:
gbest_val, gbest = pbest_val[g], pbest[g].copy()
history.append(gbest_val)
return gbest, gbest_val, history
実行してみます。
from rastrigin_module import rastrigin # ⓪で定義した関数
gbest, gbest_val, history = pso(rastrigin, seed=0)
print(f'PSO 最良解 x = [{gbest[0]:.4f}, {gbest[1]:.4f}]')
print(f'PSO 最良値 f = {gbest_val:.6f}')
print(f'初期の最良値 f = {history[0]:.4f} → 最終 f = {history[-1]:.6f}')
PSO 最良解 x = [-0.0010, 0.0010]
PSO 最良値 f = 0.000380
初期の最良値 f = 9.4803 → 最終 f = 0.000380
たった30粒子・50反復で、大域最適 $x=(0,0),\ f=0$ にほぼ到達しました。無数の局所最適解がある Rastrigin でこれは優秀です。
群れが収束していく様子
反復を進めると、ばらまかれた粒子が中央の大域最適（赤い星）へ群れとして吸い寄せられていきます。
- 0 反復目：粒子（白い点）は空間全体にばらまかれている＝探索フェーズ
- 5〜15 反復目：良い領域を見つけた粒子に群れが引き寄せられ始める
- 50 反復目：ほぼ全粒子が大域最適の周りに集まる＝活用フェーズ
「リーダーが指示を出しているわけではない」のに群れがまとまっていくのが、群知能らしいところです。
収束曲線（対数軸）も見ておきます。
最初の数十反復で一気に値が下がり、その後ゆっくり 0 に近づいていきます。上の2枚を生成したコードは以下のとおりです。
import matplotlib
matplotlib.use('Agg')
import matplotlib.pyplot as plt
plt.rcParams['font.family'] = 'Yu Gothic'
# snapshots に各反復の粒子位置を保存しておき、等高線図に重ねる
# （pso 関数内で X.copy() を毎反復 append するよう拡張）
xs = np.linspace(-5.12, 5.12, 200)
Xg, Yg = np.meshgrid(xs, xs)
Zg = np.array([[rastrigin([Xg[i, j], Yg[i, j]]) for j in range(200)]
for i in range(200)])
fig, axes = plt.subplots(1, 4, figsize=(17, 4.3))
for ax, it in zip(axes, [0, 5, 15, 50]):
ax.contourf(Xg, Yg, Zg, levels=30, cmap='viridis', alpha=0.9)
pts = snapshots[it]
ax.scatter(pts[:, 0], pts[:, 1], c='white', edgecolors='black', s=40)
ax.plot(0, 0, marker='*', color='red', markersize=16, markeredgecolor='white')
ax.set_title(f'{it} 反復目'); ax.set_xlabel('x₁'); ax.set_ylabel('x₂')
plt.tight_layout()
plt.savefig('20260801_pso_swarm.png', dpi=150)
plt.figure(figsize=(8, 4))
plt.plot(history, linewidth=1.8, color='#3498db')
plt.yscale('log')
plt.xlabel('反復回数'); plt.ylabel('最良評価値 f（対数軸）')
plt.title('PSO の収束曲線（Rastrigin 関数）')
plt.grid(True, alpha=0.3); plt.tight_layout()
plt.savefig('20260801_pso_convergence.png', dpi=150)
パラメータの勘どころ
PSO は短い反面、3つのパラメータの設定で挙動がガラッと変わります。
| パラメータ | 役割 | 大きくすると | 小さくすると |
|---|---|---|---|
| $w$（慣性） | 直進性 | 広く探索するが収束が遅い | すぐ収束するが局所最適に弱い |
| $c_1$（認知） | 自分のベストへの執着 | 各粒子が個別に探す | 集団行動が強まる |
| $c_2$（社会） | 群ベストへの執着 | 一気に集まる（早すぎると局所最適） | バラバラに探す |
定番の設定は $w=0.7,\ c_1=c_2=1.5$ あたりです。$w$ を反復とともに $0.9 \to 0.4$ へ線形に下げる「慣性重み減衰」もよく使われ、「最初は探索・最後は活用」をシンプルに実現できます。
他手法との比較
| PSO | GA（④） | SA | |
|---|---|---|---|
| 解の表現 | 位置ベクトル（連続値が得意） | 染色体（離散・順列も可） | 1つの解 |
| 新候補の作り方 | 速度更新（pbest・gbest へ移動） | 交叉・突然変異 | 近傍へランダム移動 |
| 集団か | 集団 | 集団 | 単一解 |
| パラメータ数 | 少ない（3個） | 多い（集団サイズ・交叉率・変異率） | 中（温度・冷却率） |
PSO は特に連続値の最適化（パラメータ調整・関数最小化）で手軽に効きます。一方、TSP のような順列を扱う離散問題はそのままでは表現しにくく、次回の ACO や ④の GA の方が向いています。
まとめ
- PSO は鳥の群れの集団行動を模した群知能で、速度更新と位置更新の2式だけのシンプルな手法
- 各粒子は「自分のベスト（pbest）」と「群れのベスト（gbest）」に引き寄せられながら飛ぶ
- 慣性項＝探索、認知・社会項＝活用、と⓪の枠組みにきれいに対応する
- 30粒子・50反復で多峰性の Rastrigin でも大域最適にほぼ到達できた
- 連続最適化に強く、実装も短い。まず試す価値のある定番
次回は群知能のもう一つの代表、蟻コロニー最適化（ACO） を TSP で動かします。
参考にした記事や本、論文等
- J. Kennedy and R. Eberhart, "Particle swarm optimization," Proc. IEEE Int. Conf. on Neural Networks, vol. 4, pp. 1942-1948, 1995.
- Y. Shi and R. Eberhart, "A modified particle swarm optimizer," Proc. IEEE ICEC, pp. 69-73, 1998.（慣性重みの導入）