この記事について
過去に配送最適化の文脈で焼きなまし法（SA）や遺伝的アルゴリズム（GA）を、整数計画の文脈で分枝限定法を扱ってきました。これらの「厳密解は諦めて、そこそこ良い解を現実的な時間で見つける」タイプの手法をメタヒューリスティクス（metaheuristics） と呼びます。
世の中には PSO・ACO・GA・CMA-ES といった定番から、Grey Wolf Optimizer・Harris Hawks Optimization・Manta Ray Foraging Optimization のような「動物の名前がついた亜種」まで、数百種類（と言ってもいいぐらいの笑）のメタヒューリスティクスが存在します。正直、多すぎて全体像がつかめないんですよね。。。
そこで本シリーズでは、有名なメタヒューリスティクスを1本ずつ図鑑のように、共通のテンプレートとベンチマークで解説していこうかなと思います。各記事は独立して読めますが、最後に「で、結局どれを使えばいいの？」に答えます。（いろいろ調べながらでもあるのでちょっと変な解説になってしまうことご容赦ください。）
メタヒューリスティクス図鑑シリーズの記事一覧はこちら。
| 記事 | 内容 |
|---|---|
| ⓪（本記事） | メタヒューリスティクスとは？／探索の地図 |
| ① | 粒子群最適化（PSO） |
| ② | 蟻コロニー最適化（ACO） |
| ③ | CMA-ES |
| ④ | 遺伝的アルゴリズム（GA） |
| ⑤ | Cuckoo Search |
| ⑥〜⑪ | Grey Wolf / Harris Hawks / Moth-Flame / Grasshopper / Golden Jackal / Manta Ray |
| ⑫ | まとめ：メタファー系の正体と使い分け |
メタヒューリスティクスとは
ひとことで言うと、問題の構造に依存しない、汎用的な「良い解の探し方」のレシピです。
「ヒューリスティック（heuristic）」が問題ごとの発見的な解法を指すのに対し、「メタヒューリスティック」はその上位（meta）にある、問題を選ばない探索の枠組みを指します。
- 厳密解法（単体法・分枝限定法）：最適性を保証するが、規模が大きいと時間がかかる
- メタヒューリスティクス：最適性は保証しないが、巨大な問題でも「そこそこ良い解」を現実的な時間で返す
共通する考え方は驚くほどシンプルで、ほとんどの手法が次のループに当てはまります。
① 解の候補をいくつか持つ（1個でも集団でもよい）
② 評価関数（目的関数）で良し悪しを測る
③ 良い解の情報を使って、新しい候補を作る ← ここが手法ごとの個性
④ ②に戻って繰り返す
メタヒューリスティクスの違いは、ほぼ ③の「新しい候補の作り方」だけ だったりします。PSOは「群れの良い個体に引き寄せる」、ACOは「フェロモンの濃い道をたどる」、GAは「良い解を交叉させる」…という具合です。
探索の地図：2つの軸で整理する
数百種類のメタヒューリスティクスも、2つの軸で整理するとだいぶ見通しが良くなります。
軸1：探索（Exploration）と活用（Exploitation）のバランス
| 用語 | 意味 | 強すぎると |
|---|---|---|
| 探索（Exploration） | 広い範囲をまんべんなく調べる | いつまでも収束しない |
| 活用（Exploitation） | 良い解の近くを集中的に調べる | 局所最適にハマる |
メタヒューリスティクスの設計とは、結局この2つのバランスをどう取るかに尽きます。多くの手法が「最初は探索重視、だんだん活用重視」と切り替える仕組み（PSOの慣性係数、SAの温度、GWOの係数 $a$ など）を持っています。
軸2：1つの解を動かす vs. 集団を動かす
| タイプ | 代表 | イメージ |
|---|---|---|
| 単一解ベース | 焼きなまし法（SA）、タブー探索 | 1人の探検家が地図を歩く |
| 集団（個体群）ベース | GA、PSO、ACO、CMA-ES | 大勢で手分けして探す |
このシリーズで扱うのはほとんどが集団ベースです。集団ベースは多様性を保ちやすく、並列化しやすいのが強みです。
地図にすると、ざっくりこんな分類になります。
メタヒューリスティクス
├─ 単一解ベース
│ ├─ 焼きなまし法（SA） … 配送⑤で解説
│ └─ タブー探索
└─ 集団ベース
├─ 進化計算（Evolutionary Computation）
│ ├─ 遺伝的アルゴリズム（GA） … ④
│ └─ 進化戦略 → CMA-ES … ③
└─ 群知能（Swarm Intelligence）
├─ 粒子群最適化（PSO） … ①
├─ 蟻コロニー最適化（ACO） … ②
└─ 動物模倣系（GWO/HHO/…） … ⑥〜⑪
大前提：No Free Lunch 定理
「じゃあ一番強いメタヒューリスティクスはどれ？」という疑問が真っ先に出ると思いますが、これには有名な答えがあります。
No Free Lunch (NFL) 定理：あらゆる問題を平均すれば、どんな最適化アルゴリズムの性能も互いに等しい。
D. Wolpert と W. Macready が示した定理で、ざっくり言うと「すべての問題に万能な最強アルゴリズムは存在しない」ということです。ある問題で速い手法は、別の問題では遅くなる。タダ飯（free lunch）はないわけです。
D. H. Wolpert and W. G. Macready, "No free lunch theorems for optimization,"
IEEE Trans. on Evolutionary Computation, vol. 1, no. 1, pp. 67-82, 1997.
これは後半で出てくる「動物模倣系メタヒューリスティクス乱立問題」を考えるうえで超重要な前提なので、頭の隅に置いておいてください。「新しい動物アルゴリズムが既存手法に全勝した」という主張は、NFL定理の観点からは眉に唾をつけて読む必要があるんです。
共通のベンチマーク関数
このシリーズでは、各手法を同じテスト関数で動かして比較します。最適化の世界には定番のベンチマーク関数があり、いずれも大域最適は原点で $f=0$、という分かりやすい設計になっています。
import numpy as np
def sphere(x):
"""お椀型。最も簡単な単峰性関数"""
x = np.asarray(x)
return np.sum(x ** 2)
def rastrigin(x):
"""格子状に無数の局所最適を持つ多峰性関数"""
x = np.asarray(x)
n = len(x)
return 10 * n + np.sum(x ** 2 - 10 * np.cos(2 * np.pi * x))
def ackley(x):
"""外周は平坦、中央に深く細い谷を持つ多峰性関数"""
x = np.asarray(x)
n = len(x)
s1 = np.sum(x ** 2)
s2 = np.sum(np.cos(2 * np.pi * x))
return -20 * np.exp(-0.2 * np.sqrt(s1 / n)) - np.exp(s2 / n) + 20 + np.e
3つの関数を2次元で等高線図にすると、難しさの違いが一目でわかります。
- Sphere：きれいなお椀型。どこから降りても中央（赤い星＝大域最適）に着く。単峰性で簡単
- Rastrigin：格子状に局所最適が多く存在します。一歩間違えると近くの凹みでハマる。多峰性で難しい
- Ackley：外周はほぼ平坦で勾配の情報が乏しく、中央にだけ深い谷がある。「谷を見つけられるか」が勝負
各関数で代表的な点の値を確認しておきます。
for name, f in [('Sphere', sphere), ('Rastrigin', rastrigin), ('Ackley', ackley)]:
print(f'{name:10s} f(0,0)={f([0,0]):.4f} f(2,2)={f([2,2]):.4f}')
Sphere f(0,0)=0.0000 f(2,2)=8.0000
Rastrigin f(0,0)=0.0000 f(2,2)=8.0000
Ackley f(0,0)=0.0000 f(2,2)=6.5936
どの関数も大域最適 $f(0,0)=0$ です。各手法が どれだけ 0 に近づけるか で性能を見ていきます。上の地形図を生成したコードは以下のとおりです。
import matplotlib
matplotlib.use('Agg')
import matplotlib.pyplot as plt
plt.rcParams['font.family'] = 'Yu Gothic'
def grid(func, lim, n=300):
xs = np.linspace(-lim, lim, n)
X, Y = np.meshgrid(xs, xs)
Z = np.array([[func([X[i, j], Y[i, j]]) for j in range(n)] for i in range(n)])
return X, Y, Z
funcs = [('Sphere（お椀型・簡単）', sphere, 5.0),
('Rastrigin（無数の局所最適）', rastrigin, 5.12),
('Ackley（中央に深い谷）', ackley, 5.0)]
fig, axes = plt.subplots(1, 3, figsize=(15, 4.6))
for ax, (name, f, lim) in zip(axes, funcs):
X, Y, Z = grid(f, lim)
ax.contourf(X, Y, Z, levels=30, cmap='viridis')
ax.plot(0, 0, marker='*', color='red', markersize=18,
markeredgecolor='white', label='大域最適')
ax.set_title(name); ax.set_xlabel('x₁'); ax.set_ylabel('x₂')
ax.legend(loc='upper right')
plt.tight_layout()
plt.savefig('20260801_landscape.png', dpi=150)
このシリーズの読み方
各記事は次の共通テンプレートで進めていこうと思います。
| セクション | 内容 |
|---|---|
| 〇〇とは | 元になった発想・論文 |
| 核心 | 更新式を1本ずつ意味づけ |
| 擬似コード | 具体的な手順をステップで追跡 |
| Python実装 | 上のベンチマークで実際に動かす |
| 他手法との比較 | 何が新しくて何が同じか |
「更新式のどこに探索と活用が現れているか」を毎回チェックすると、一見バラバラな手法が同じ骨格を持っていることが見えてきて面白いかと思います。
まとめ
- メタヒューリスティクス＝問題の構造に依存しない汎用的な「良い解の探し方」のレシピ
- ほとんどの手法は「集団を持つ→評価→良い解の情報で新候補を作る」の繰り返しで、大きな違いは新候補の作り方だけ
- 整理の軸は「探索 vs. 活用」と「単一解 vs. 集団」の2つ
- No Free Lunch 定理より、すべての問題で最強の手法は存在しない（万能アルゴリズムへの過剰な期待は禁物）
- 比較には Sphere / Rastrigin / Ackley の定番ベンチマークを使う
次回はまず群知能の代表格、粒子群最適化（PSO） から見ていきます。
参考にした記事や本、論文等
- D. H. Wolpert and W. G. Macready, "No free lunch theorems for optimization," IEEE Trans. on Evolutionary Computation, vol. 1, no. 1, pp. 67-82, 1997.
- K. Sörensen, "Metaheuristics—the metaphor exposed," International Transactions in Operational Research, vol. 22, no. 1, pp. 3-18, 2015.
- M. Gendreau and J.-Y. Potvin (eds.), "Handbook of Metaheuristics," Springer, 2019.