この記事について
前回（④）は実数値GAを扱いました。今回は Cuckoo Search（カッコウ探索） です。カッコウの托卵（他の鳥の巣に卵を産みつける習性）を模した手法で、Lévyフライトという「たまに大きくジャンプする」乱歩を使って大域を探索するのが特徴です。
この Lévyフライトは、これ以降に出てくる HHO・GJO・MRFO といったメタファー系でも繰り返し使われる重要パーツなので、ここで仕組みを押さえておきます。
ちなみに私自身は昔このカッコウ探索にアレルギーがあったのですが、このLévyフライトの意味を理解してから確かに少し面白いかもなと思ったりそうでなかったりと、名前に惑わされることなく勉強しておけばよかったと思いました笑
メタヒューリスティクス図鑑シリーズの記事一覧はこちら。
| 記事 | 内容 |
|---|---|
| ⓪ | メタヒューリスティクスとは？／探索の地図 |
| ① | 粒子群最適化（PSO） |
| ② | 蟻コロニー最適化（ACO） |
| ③ | CMA-ES |
| ④ | 遺伝的アルゴリズム（GA） |
| ⑤（本記事） | Cuckoo Search |
| ⑥ | Grey Wolf Optimizer（GWO） |
| ⑦ | Harris Hawks Optimization（HHO） |
| ⑧ | Moth-Flame Optimization（MFO） |
| ⑨ | Grasshopper Optimization（GOA） |
| ⑩ | Golden Jackal Optimization（GJO） |
| ⑪ | Manta Ray Foraging（MRFO） |
| ⑫ | まとめ：メタファー系の正体と使い分け |
Cuckoo Searchとは
2009年に Xin-She Yang と Suash Deb が提案しました。
X.-S. Yang and S. Deb, "Cuckoo Search via Lévy Flights,"
Proc. World Congress on Nature & Biologically Inspired Computing (NaBIC), pp. 210-214, 2009.
設定は次の3つのルールに集約されます。
- 各カッコウは1個の卵（＝解）を産み、ランダムに選んだ巣に置く
- 良い卵（良い解）を持つ巣は次世代に残る
- 宿主の鳥は確率 $p_a$ で托卵を見破り、その巣を捨てて新しい巣を作る
ポイントは「卵を産む位置をLévyフライトで決める」ことです。
核心：Lévyフライト
Lévyフライトは、ほとんどは小さな移動だが、ときどき非常に大きくジャンプする乱歩です。アホウドリやサメの採餌行動がこの分布に従うことが知られています。
どこかで見たのですが、人間も実は同じような動きをしてるんではないかということを言ってる研究もありました。想像してみていただけるとわかるかと思うのですが、休日や仕事帰りに自宅の周辺や少し遠くの職場の周辺、遠くの遊び場に遊びに行くことは多いですが、2個先の駅周辺へ遊びに行ったり、遠くはないけど近くもない、みたいな場所は意外と訪問しなかったりするものです。そういうイメージだと思ってくれたら良いです。
新しい解は、現在の解 $x_i$ からLévyステップ分だけ動かして作ります。
x_i^{\text{new}} = x_i + \underbrace{\alpha}_{\text{歩幅}} \cdot
\underbrace{\text{Lévy}(\lambda)}_{\text{裾の重い乱数}} \cdot
\underbrace{(x_i - x_{\text{best}})}_{\text{最良解との差}}
- 通常のガウス乱歩と違い、Lévy分布は裾が重いため、大ジャンプがそれなりの頻度で起きる
- この大ジャンプが局所最適からの脱出を担う（探索）。最良解との差に比例させることで、収束も促す（活用）
図で見る
「裾が重い」がどういうことか、同じ400ステップだけ歩かせて比べてみます。 1歩の長さの中央値をそろえてある ので、違うのは裾の重さだけです。
- ①（左）ガウス乱歩：どの一歩も似たような長さで、もやもやと連続的に広がっていく
- ②（中）Lévyフライト：小さな移動でかたまり（クラスタ）を作っては、突然ぴゅっと遠くへ飛ぶ、の繰り返し。上の「自宅の周辺 → 職場の周辺 → 遠くの遊び場」というイメージがそのまま出ています
- ③（右）ステップ長の分布：横軸が一歩の長さ、縦軸が「それを超える確率」（両対数）。ガウスはある長さでストンと落ちるのに対し、Lévyはずるずると裾を引いています。この図では Lévy の最大ステップはガウスの20倍以上でした
最適化の言葉に翻訳すると、こうなります。
| ガウス乱歩 | Lévyフライト | |
|---|---|---|
| 近所の探索 | ○ | ○（かたまりを作る） |
| 遠くへの脱出 | ✕（届かない） | ◎（たまに大ジャンプ） |
| 局所最適 | はまりやすい | 抜け出せる |
「近所をていねいに探す」と「遠くへ飛ぶ」を、1つの分布で両立しているのがLévyフライトの美味しいところです。
Lévyステップは Mantegna のアルゴリズムで生成します。
\text{step} = \frac{u}{|v|^{1/\beta}},\quad
u \sim \mathcal{N}(0, \sigma_u^2),\ v \sim \mathcal{N}(0, 1),\quad
\sigma_u = \left[\frac{\Gamma(1+\beta)\sin(\pi\beta/2)}
{\Gamma(\frac{1+\beta}{2})\,\beta\,2^{(\beta-1)/2}}\right]^{1/\beta}
import numpy as np
from math import gamma, pi, sin
def levy(dim, rng, beta=1.5):
sigma = (gamma(1 + beta) * sin(pi * beta / 2) /
(gamma((1 + beta) / 2) * beta * 2 ** ((beta - 1) / 2))) ** (1 / beta)
u = rng.normal(0, sigma, dim)
v = rng.normal(0, 1, dim)
return u / np.abs(v) ** (1 / beta)
擬似コード
① n 個の巣をランダムに初期化
② 以下を反復：
各巣について：
Lévyフライトで新しい卵を作る
ランダムな巣 j と比較し、新しい卵が良ければ置き換える
確率 p_a で悪い巣を放棄し、ランダムな差分で作り直す
最良の巣を記録
③ 最良の巣を返す
Python実装
def cuckoo(func, dim, lb, ub, n_agents=25, n_iter=500, seed=0,
pa=0.25, alpha=0.01):
rng = np.random.default_rng(seed)
X = rng.uniform(lb, ub, (n_agents, dim))
fit = np.array([func(x) for x in X])
best_i = np.argmin(fit)
best_x, best_f = X[best_i].copy(), fit[best_i]
history = []
for t in range(n_iter):
# ① Lévyフライトで新しい卵を生成
for i in range(n_agents):
step = alpha * levy(dim, rng) * (X[i] - best_x)
cand = np.clip(X[i] + step * rng.normal(size=dim), lb, ub)
fc = func(cand)
j = rng.integers(n_agents)
if fc < fit[j]: # ランダムな巣と比較
X[j], fit[j] = cand, fc
# ② 悪い巣を割合 pa で放棄して作り直す
K = rng.random((n_agents, dim)) < pa
i1, i2 = rng.permutation(n_agents), rng.permutation(n_agents)
stepsize = rng.random((n_agents, dim)) * (X[i1] - X[i2])
Xnew = np.clip(X + stepsize * K, lb, ub)
fnew = np.array([func(x) for x in Xnew])
imp = fnew < fit
X[imp], fit[imp] = Xnew[imp], fnew[imp]
bi = np.argmin(fit)
if fit[bi] < best_f:
best_f, best_x = fit[bi], X[bi].copy()
history.append(best_f)
return best_x, best_f, history
Rastrigin（2次元）で実行します。
_, best_f, history = cuckoo(rastrigin, dim=2, lb=-5.12, ub=5.12, seed=0)
print(f'Cuckoo 最良値 f = {best_f:.6e} （初期 {history[0]:.3f} → 最終 {history[-1]:.3e}）')
Cuckoo 最良値 f = 5.678651e+00 （初期 9.480 → 最終 5.679e+00）
…正直、あまり良くありません笑。Rastrigin 2次元でも局所最適に取り残されています。収束曲線を見ても、途中から下がりが鈍くなっています。
Cuckoo Search は実装がシンプルでパラメータも少ない（$p_a, \alpha$ くらい）のが魅力ですが、素の設定では多峰性関数に弱いことがあります。歩幅 $\alpha$ や巣の数のチューニング、あるいは局所探索との併用で改善することが多いです。10次元での比較は⑫にまとめます（10シード平均で $44.9 \pm 10.1$ と、今回のラインナップでは苦戦組でした）。上図を生成したコードは以下のとおりです。
import matplotlib
matplotlib.use('Agg')
import matplotlib.pyplot as plt
plt.rcParams['font.family'] = 'Yu Gothic'
plt.figure(figsize=(7, 3.6))
plt.plot(np.maximum(history, 1e-12), color='#e67e22', linewidth=1.7)
plt.yscale('log'); plt.xlabel('反復回数'); plt.ylabel('最良 f（対数軸）')
plt.title('Cuckoo Search の収束曲線（Rastrigin 2D）')
plt.grid(True, alpha=0.3); plt.tight_layout()
plt.savefig('20260801_cuckoo_convergence.png', dpi=150)
Lévyフライトという発明
Cuckoo Search 自体の性能は今回ふるいませんでしたが、Lévyフライトを最適化に持ち込んだ功績は大きいと思います。「ほとんど小刻み、たまに大ジャンプ」という乱歩は、探索と活用のバランスを乱数の分布だけで自然に実現できる便利な道具で、以降のメタファー系（⑦HHO・⑩GJO・⑪MRFO）でも繰り返し使われます。
まとめ
- Cuckoo Search はカッコウの托卵を模し、Lévyフライトで解を更新する手法
- Lévyフライトは「ほとんど小移動・たまに大ジャンプ」の裾の重い乱歩で、局所最適脱出に効く
- 実装は短くパラメータも少ないが、素の設定では多峰性関数で苦戦することがある（今回も Rastrigin で停滞）
- 手法そのものより、Lévyフライトという部品が後続のメタファー系に与えた影響が大きい（と思う）
次回は生物模倣系の代表格、Grey Wolf Optimizer（GWO） に入ります。
参考にした記事や本、論文等
- X.-S. Yang and S. Deb, "Cuckoo Search via Lévy Flights," Proc. NaBIC, pp. 210-214, 2009.
- R. N. Mantegna, "Fast, accurate algorithm for numerical simulation of Lévy stable stochastic processes," Physical Review E, vol. 49, no. 5, pp. 4677-4683, 1994.