この記事について
メタファー系の4つめ、Grasshopper Optimization Algorithm（GOA：バッタ最適化） です。バッタの群れの動き ── お互いに近すぎると反発し、遠すぎると引き合う ── を社会的な引力・斥力としてモデル化した手法です。
GWO・HHO・MFO が「リーダーへ向かう」型だったのに対し、GOA はエージェント同士の相互作用を計算する点が少し毛色が違います。
メタヒューリスティクス図鑑シリーズの記事一覧はこちら。
| 記事 | 内容 |
|---|---|
| ⓪〜⑤ | 入門・地図／PSO・ACO・CMA-ES・GA・Cuckoo |
| ⑥⑦⑧ | GWO／HHO／MFO |
| ⑨（本記事） | Grasshopper Optimization（GOA） |
| ⑩ | Golden Jackal Optimization（GJO） |
| ⑪ | Manta Ray Foraging（MRFO） |
| ⑫ | まとめ：メタファー系の正体と使い分け |
GOAとは
2017年に Saremi、Mirjalili らが提案しました。
S. Saremi, S. Mirjalili, and A. Lewis, "Grasshopper Optimisation Algorithm: Theory and application,"
Advances in Engineering Software, vol. 105, pp. 30-47, 2017.
バッタの幼虫は密集してゆっくり動き、成虫は大きく跳ぶ ── この「近距離では群れ、遠距離では拡散」という性質を最適化に使います。
核心：社会的相互作用 ＋ 縮小係数
まず全体の形を眺める
各バッタ $X_i$ の次の位置は、**「他の全バッタから受ける力の合計（社会項）」＋「獲物＝最良解の位置」**という、たった2つの足し算で決まります。
X_i^{t+1} = \underbrace{c\sum_{j\ne i} c\,\frac{ub-lb}{2}\, s(d_{ij})\,\frac{X_j - X_i}{d_{ij}}}_{\text{社会項：他のバッタから受ける力}}
\;+\; \underbrace{\hat{T}}_{\text{獲物（最良解）}}
ここで $d_{ij} = |X_j - X_i|$ は2匹の距離です。
いきなり記号が多いので、まず気づいておきたい構造を1つ。右辺で「自分の現在地 $X_i^t$」は社会項の中にしか出てこず、位置の基準になっているのは $\hat T$（最良解）だけです。つまりGOAは、
毎回すべてのバッタを最良解の位置にワープさせ、そこから社会項のぶんだけズラして置き直す
というアルゴリズムです。PSOのように「今いる場所から速度で進む」のではありません。この時点で「最良解の周りに置き直す＋摂動」という骨格が透けて見えます。
そのうえで社会項を分解すると、こうなります。
| 部分 | 記号 | 役割 |
|---|---|---|
| 動く軸 | $\dfrac{X_j - X_i}{d_{ij}}$ | $i$ と $j$ を結ぶ直線の単位ベクトル（長さ1）。距離で割ってあるので長さの情報は消えていて、「どの直線に沿って動くか」だけを決める |
| 軸上の符号と大きさ | $s(d_{ij})$ | 正なら $j$ の側へ、負なら反対側へ（＝軸のどちら向きか）。絶対値がそのまま力の強さ |
| スケール | $\dfrac{ub-lb}{2}$ | 探索範囲の半幅（Rastriginなら $10.24/2 = 5.12$）。問題の広さに合わせる定数 |
| 縮小 | $c$（2か所） | 反復とともに $1 \to 0$。2回かかるので社会項は実質 $c^2$ で縮む |
| 目的地 | $\hat T$ | これまでの最良解。全バッタ共通の「獲物」 |
つまり単位ベクトルは軸を決めるだけで、その軸をどちら向きにどれだけ進むかは $s$ が一手に引き受けています。両者を掛けた $s(d_{ij})\cdot\dfrac{X_j-X_i}{d_{ij}}$ で初めて「$j$ に寄る／$j$ から離れる」という力のベクトルになる、という分業です。
s(d_{ij}) > 0 \;\Rightarrow\; j \text{ の方へ}, \qquad
s(d_{ij}) < 0 \;\Rightarrow\; j \text{ の逆へ}
これを他の $N-1$ 匹ぶん足し合わせたものが社会項です。
$s(r)$：引力と斥力を1本の式で切り替える
$s$ は social forces（社会的な力） の $s$ で、原論文の記号そのままです。やっていることは見た目より単純で、
2匹の距離 $r$ だけを受け取って、「引き合うのか（正）／反発するのか（負）」と「その強さ」を、符号つきの数値1つで返す関数
です。返すのはベクトルではなくスカラー1つで、向きの情報は前節の単位ベクトルが持っています。
| $s$ の値 | 意味 |
|---|---|
| $s < 0$ | 斥力（相手から離れる） |
| $s = 0$ | つり合い（快適距離） |
| $s > 0$ | 引力（相手に寄る） |
魚群や鳥の群れのモデルでよく出てくる「反発ゾーン → 快適ゾーン → 引力ゾーン」という3層構造を、場合分けなしに1本の連続関数で表したもの、と思うと分かりやすいと思います。
s(r) = f\,e^{-r/l} - e^{-r}
指数関数の引き算ですが、2つの減衰の速さが違うのがミソです。
| 項 | 符号 | 減衰の速さ | 意味 |
|---|---|---|---|
| $f,e^{-r/l}$ | ＋ | $l>1$ なのでゆっくり減衰 | 遠くまで届く引力 |
| $-e^{-r}$ | − | 速く減衰 | 近距離でだけ効く斥力 |
パラメータは引力側にしか付いていません。$f$ が引力の強さ（既定 $0.5$）、$l$ が引力の届く範囲（既定 $1.5$）です。斥力側の $-e^{-r}$ は係数なしの固定で、いわば「基準の物差し」。$l>1$ でないと引力側が斥力側より速く減ってしまい、 **どの距離でも $s<0$（反発しかしない）** 関数になってしまうので、$l>1$ は必須条件です。
近距離では速く減る側（斥力）がまだ大きいので $s<0$、距離が伸びるとそちらが先に消えて立場が逆転し $s>0$ になる ── これが「近くでは反発、遠くでは引力」の正体です。$r=0$ では $s(0) = f - 1$ なので、$f<1$ である限り必ず反発から始まります。
境目の距離（快適距離）は $s(r)=0$ を解くだけで求まります。
f e^{-r/l} = e^{-r}
\iff \ln f = r\cdot\frac{1-l}{l}
\iff r^{*} = \frac{l\,\ln(1/f)}{l-1}
既定値 $f=0.5,\ l=1.5$ なら $r^{*} = 1.5\ln 2 / 0.5 = 2.079$。これが下の図①で $s$ が0を横切る点です。同じく $s'(r)=0$ から引力が最大になる距離も出て、$r = \dfrac{l\ln(l/f)}{l-1} = 3.296$、そのときの $s = 0.0185$ です。
この式を使えば、$f$ と $l$ をいじったときの挙動も手計算で読めます。
| パラメータ | 快適距離 $r^{*}$ | 引力の最大値 |
|---|---|---|
| $f=0.2$（$l=1.5$） | 4.83 | 0.0012 |
| $f=0.5,\ l=1.5$（既定） | 2.08 | 0.0185 |
| $f=0.8$（$l=1.5$） | 0.67 | 0.0759 |
| $l=3.0$（$f=0.5$） | 1.04 | 0.1361 |
$f$ も $l$ も、大きくすると引力が強まって快適距離が縮む（バッタが密集する）方向に効きます。逆に小さくすると群れは広がりますが、引力そのものが桁で弱くなるので、ほとんど相互作用しなくなります。
ここで力の非対称さに注目してください。
| $r$ | $s(r)$ | 状態 |
|---|---|---|
| $0$ | $-0.5$ | 最大の斥力 |
| $1$ | $-0.111$ | 斥力 |
| $2.079$ | $0$ | 快適距離（つり合う） |
| $3.296$ | $+0.0185$ | 最大の引力 |
| $6$ | $+0.0067$ | 弱い引力 |
| $10$ | $+0.0006$ | ほぼ無力 |
斥力は最大 $0.5$ まで出るのに、引力は最大でも $0.0185$ ── 27倍の開きがあります。図①で引力側（緑）がほとんど平らに見えるのはそのためで、GOAは「強く反発し、ごく弱く引き合う」手法だと読めます。
落とし穴：実装では距離が $[2,4]$ に潰されている
ここが $s(r)$ でいちばん引っかかるところです。論文の付属コード（下のPython実装も同じ）では、$s$ に渡す距離は実距離ではありません。
rij = 2 + dist % 2 # 距離を[2,4]へ写像
dist % 2 は2で割った余りなので、実距離 $0.1$ も $2.1$ も $4.1$ も $8.1$ も、すべて $2.1$ として扱われます。この写像を通すと $s$ の振る舞いはこうなります。
- $s$ が取りうる値は $[-0.0035,\ +0.0185]$ だけ（本来の $[-0.5,\ +0.0185]$ から斥力側がごっそり消える）
- 距離をいろいろ振ってみると、$s<0$（斥力）になるのは全体の約4%
つまり、あれだけ丁寧にモデル化した「近すぎたら強く反発」は、実装上ほとんど発動しません。実際に効いているのは「距離とほぼ無関係な、弱い引力＋のこぎり波状のゆらぎ」です。
論文側の言い分としては「距離が10も離れると $s\approx0$ になって力が働かなくなるので、距離を狭い区間に写像する」というものです。動機は分かるのですが、$\bmod$ による写像は距離の大小関係そのものを壊します（$0.1$ と $8.1$ が同じ扱いになる）。比喩と実装がここで大きく乖離しているわけですね。単調な写像（例：$2 + 2,d/(d+d_0)$）にすれば比喩は保てるので、気になる方は差し替えて実験してみると面白いと思います。
係数 $c$：探索→活用のつまみ
c = c_{\max} - t\cdot\frac{c_{\max}-c_{\min}}{T}
$c_{\max}=1,\ c_{\min}=4\times10^{-5}$ を、反復とともに線形に $1 \to 0$ へ落とすだけの式です。ポイントは更新式の中に $c$ が2回出てくること。論文では「外側の $c$ は移動幅を縮め、内側の $c$ は快適距離（comfort zone）を狭める」と説明されますが、実装ではどちらも $s$ に掛かるただの係数なので、正味の効果は「社会項の大きさが $c^2$ で縮む」です。
実際に走らせて、社会項の長さ（＝最良解からどれだけ離れた場所に置き直されるか）を測るとこうなりました。
| 反復 $t$ | $c$ | 社会項の大きさ（平均） |
|---|---|---|
| 0 | 1.00 | 1.30 |
| 100 | 0.80 | 0.95 |
| 250 | 0.50 | 0.24 |
| 400 | 0.20 | 0.010 |
| 499 | 0.002 | ほぼ 0 |
$c$ が半分（0.5）になった時点で、社会項は $1.30 \to 0.24$ と1/5以下に落ちています。$c^2$ で効いているためですね。序盤は最良解の周囲 $\pm1.3$ くらいに散らばり、終盤は最良解にほぼ重なる ── これが図③の青（序盤）と赤（終盤）の違いです。
GWO の $a$、MFO の炎の数と同じ「探索→活用のつまみ」です。やはり骨格③ですね。
図で見る
- ①（左）$s(r)$ の形：横軸が2匹の距離。近距離では $s<0$（赤い領域）＝反発**、そこを抜けると **$s>0$（緑の領域）＝引力に変わります。$s=0$ になる距離（$r^{*}=2.079$）が「快適距離」で、2匹はこの距離で落ち着きます。緑の領域がほぼ平らに見えますが、目の錯覚ではなく本当に引力が弱い（斥力の1/27）のがGOAの特徴です
- ②（中）力の向き：近すぎれば外向き（離れる）、遠すぎれば内向き（寄る）、快適距離ならつり合って動かない、という3パターン
- ③（右）係数 $c$ の効果：$c$ が大きい序盤（青）は群れが広く散らばり、$c$ が小さい終盤（赤）は獲物（最良解）の周りに密集します。社会項が $c^2$ で縮むので、この収縮は見た目以上に急です
「近づきすぎない」という性質が、GOAの多様性の源 ── というのが建前です。PSOやGWOは「リーダーへ引き寄せる」力しか持たないので、放っておくと全員が1点に潰れます。GOAは斥力を式に組み込むことで、勝手に潰れないようにしている ── 鳥の群れや魚群が「ぶつからずに群れる」のと同じ理屈で、アイデアとしてはとても好きです。
ただし①はあくまで式どおりの $s(r)$ です。前述の $[2,4]$ 写像を通した実装では、この図の左半分（強い斥力）はほぼ使われません。理屈は魅力的なのに、実装がそれを打ち消しているという、なかなかもったいない構造になっています。
Python実装
エージェント同士の総当たり（$O(N^2)$）が入るのが他手法との違いです。
import numpy as np
def goa(func, dim, lb, ub, n_agents=30, n_iter=500, seed=0,
cmax=1.0, cmin=4e-5, f=0.5, l=1.5):
rng = np.random.default_rng(seed)
X = rng.uniform(lb, ub, (n_agents, dim))
fit = np.array([func(x) for x in X])
target = X[np.argmin(fit)].copy(); ftar = fit.min()
history = []
for t in range(n_iter):
c = cmax - t * (cmax - cmin) / n_iter # 縮小係数
Xnew = np.zeros_like(X)
for i in range(n_agents):
s_total = np.zeros(dim)
for j in range(n_agents): # 他の全バッタとの相互作用
if i == j:
continue
d = X[j] - X[i]
dist = np.linalg.norm(d) + 1e-12
rij = 2 + dist % 2 # 距離を[2,4]へ写像
s = f * np.exp(-rij / l) - np.exp(-rij) # 引力/斥力
s_total += c * (ub - lb) / 2 * s * (d / dist)
Xnew[i] = c * s_total + target # 最良解へ向けて合成
X = np.clip(Xnew, lb, ub)
fit = np.array([func(x) for x in X])
bi = np.argmin(fit)
if fit[bi] < ftar:
ftar, target = fit[bi], X[bi].copy()
history.append(ftar)
return target, ftar, history
Rastrigin（2次元）で実行します。
_, best_f, history = goa(rastrigin, dim=2, lb=-5.12, ub=5.12, seed=0)
print(f'GOA 最良値 f = {best_f:.6e} （初期 {history[0]:.3f} → 最終 {history[-1]:.3e}）')
GOA 最良値 f = 8.274270e-12 （初期 6.154 → 最終 8.274e-12）
2次元ではほぼ大域最適（$8\times10^{-12}$）に到達しました。
ただし高次元では今回最も苦戦しました。10次元・10シード平均では Rastrigin で $53.5 \pm 15.7$、Ackley で $2.69 \pm 5.77$ と、PSO や GA にも及びません。$O(N^2)$ の相互作用計算が重いわりに、高次元の多峰性ではうまく収束しきれない、という結果です（パラメータ $f, l$ の調整で改善する余地はあります）。
「相互作用型」も結局は骨格に収まる
GOA は一見「リーダー追従ではない」ように見えますが、核心の式を分解して分かったとおり、更新の基準点は最後に足される獲物 $\hat{T}$（最良解）そのものでした。相互作用は「$\hat T$ からどれだけズラすか」を決めているだけで、そのズレ幅は $c^2$ で0に絞られていきます。しかも実装では距離が $[2,4]$ に潰され、斥力はほとんど働きません。
結局のところ、やはりメタファー系の骨格③（最良解＋縮小する摂動）に収まります。違いは「摂動の作り方を、エージェント間の引力・斥力で味付けした」点だけです。
| 手法 | 探索→活用のつまみ | 特徴的な味付け |
|---|---|---|
| GWO（⑥） | 係数 $a$ | 上位3頭の平均 |
| MFO（⑧） | 炎の数 | 対数らせん |
| GOA（本記事） | 係数 $c$ | エージェント間の引力・斥力 |
まとめ
- GOA はバッタの群れの社会的引力・斥力（近距離で反発・中距離で引力）を模した手法
- 更新式は「最良解 $\hat T$ ＋ 社会項」で、自分の現在地は社会項の中にしか出てこない
- $s(r)=fe^{-r/l}-e^{-r}$ は減衰の速さが違う2項の差。快適距離は $r^{*}=l\ln(1/f)/(l-1)=2.079$ と解析的に求まる
- ただし斥力（最大 $0.5$）に対して引力は最大 $0.0185$ と27倍の非対称があり、さらに実装では距離が $[2,4]$ に潰されて斥力がほぼ発動しない
- 係数 $c$ が二重に効いて（実質 $c^2$）探索→活用を切り替える（GWOの $a$ と同役割）
- エージェント同士の総当たり $O(N^2)$ が必要で、計算は重め
- 2次元では大域最適に届くが、高次元では今回最も低調（Rastrigin 10次元で $53.5$）
- 「相互作用型」に見えても、最良解への引力＋縮小係数という骨格は共通
次回は2022年提案の新しい手法、Golden Jackal Optimization（GJO） です。
参考にした記事や本、論文等
- S. Saremi, S. Mirjalili, and A. Lewis, "Grasshopper Optimisation Algorithm: Theory and application," Advances in Engineering Software, vol. 105, pp. 30-47, 2017.
最適化 メタヒューリスティクス GrasshopperOptimization 群知能 Python