この記事について
前回（①）は粒子群最適化（PSO）を連続関数で動かしました。今回は群知能のもう一つの代表格、蟻コロニー最適化（ACO：Ant Colony Optimization） です。
PSO が「連続空間を飛ぶ」手法だったのに対し、ACO は 経路を1本ずつ組み立てる手法で、TSP のような組合せ最適化に強いのが特徴です。ということで、今回はTSPを蟻に解かせてみます。
メタヒューリスティクス図鑑シリーズの記事一覧はこちら。
| 記事 | 内容 |
|---|---|
| ⓪ | メタヒューリスティクスとは？／探索の地図 |
| ① | 粒子群最適化（PSO） |
| ②（本記事） | 蟻コロニー最適化（ACO） |
| ③ | CMA-ES |
| ④ | 遺伝的アルゴリズム（GA） |
| ⑤ | Cuckoo Search |
| ⑥〜⑪ | Grey Wolf / Harris Hawks / Moth-Flame / Grasshopper / Golden Jackal / Manta Ray |
| ⑫ | まとめ：メタファー系の正体と使い分け |
ACOとは
1992年に Marco Dorigo が博士論文で提案した手法です。最初のバージョンは Ant System と呼ばれます。
M. Dorigo, V. Maniezzo, and A. Colorni, "Ant system: optimization by a colony of cooperating agents,"
IEEE Trans. on Systems, Man, and Cybernetics, Part B, vol. 26, no. 1, pp. 29-41, 1996.
着想は本物の蟻のフェロモンです。蟻は通った道にフェロモンを残し、他の蟻はフェロモンの濃い道を選びやすい。短い道ほど早く往復できるので単位時間あたりのフェロモンが濃くなり、短い道に正のフィードバックがかかって自然と最短経路が浮かび上がる── これを最適化に持ち込んだのが ACO です。
核心：確率的な経路構築 ＋ フェロモン更新
ACO は2つの仕組みの組み合わせでできています。
① 確率的に経路を作る
各蟻は都市 $i$ にいるとき、次にどの都市 $j$ へ行くかを確率的に選びます。その確率は2つの量で決まります。
p_{ij} = \frac{
\overbrace{\tau_{ij}^{\alpha}}^{\text{フェロモン}} \cdot
\overbrace{\eta_{ij}^{\beta}}^{\text{近さ}}
}{\displaystyle\sum_{k \in \text{未訪問}} \tau_{ik}^{\alpha} \cdot \eta_{ik}^{\beta}}
| 記号 | 意味 |
|---|---|
| $\tau_{ij}$ | 辺 $(i,j)$ のフェロモン量。みんなが通った道ほど濃い（集団の経験） |
| $\eta_{ij} = 1/d_{ij}$ | ヒューリスティック。距離の逆数で「近い都市ほど大きい」（目先の良さ） |
| $\alpha,\ \beta$ | フェロモンと近さのどちらを重視するかの重み |
$\alpha$ を大きくすると「みんなが通った道」を、$\beta$ を大きくすると「近い道」を重視します。⓪の枠組みでいうと、$\tau$ が活用（過去の経験の利用）、確率的に選ぶこと自体が探索にあたります。
② フェロモンを更新する
全部の蟻が経路を作り終えたら、フェロモンを更新します。
\tau_{ij} \leftarrow \underbrace{(1-\rho)\,\tau_{ij}}_{\text{蒸発}}
+ \underbrace{\sum_{k} \Delta\tau_{ij}^{k}}_{\text{付加}},
\qquad
\Delta\tau_{ij}^{k} = \frac{Q}{L_k}\ \ (\text{蟻 } k \text{ が辺 } (i,j) \text{ を通ったとき})
| 操作 | 意味 |
|---|---|
| 蒸発（$1-\rho$ 倍） | 全フェロモンを一定割合で減らす。古い情報を忘れ、局所最適への固執を防ぐ（探索の維持） |
| 付加（$Q/L_k$） | 蟻が通った辺にフェロモンを足す。短い経路 $L_k$ ほど多く足されるので、良い道が濃くなる |
蒸発があるおかげで「一度濃くなった道に全員が殺到して終わり」を防げる、というのが地味に重要なポイントだったりします。
擬似コード
① 全辺のフェロモン τ を一定値で初期化
② 以下を反復：
各蟻について：
ランダムな都市から出発
未訪問都市が残る間：
確率 p_ij ∝ τ^α · η^β で次の都市を選ぶ
1周のツアーが完成
フェロモンを蒸発： τ ← (1-ρ)·τ
各蟻のツアー長 L に応じて付加： τ_ij ← τ_ij + Q/L
最良ツアーを記録
③ 最良ツアーを返す
Python実装
配送シリーズと同じ要領で20都市をランダム生成し、Ant System で解きます。
import numpy as np
def aco_tsp(D, n_ants=30, n_iter=100, alpha=1.0, beta=5.0,
rho=0.5, Q=100.0, seed=0):
rng = np.random.default_rng(seed)
n = len(D)
eta = 1.0 / (D + np.eye(n)) # ヒューリスティック（距離の逆数）
np.fill_diagonal(eta, 0.0)
tau = np.ones((n, n)) # ① フェロモン初期化
best_tour, best_len, history = None, np.inf, []
for t in range(n_iter):
all_tours = []
for _ in range(n_ants):
start = rng.integers(n)
visited = [start]
unvisited = set(range(n)) - {start}
while unvisited: # 確率的に経路を構築
i = visited[-1]
js = list(unvisited)
w = np.array([tau[i, j] ** alpha * eta[i, j] ** beta for j in js])
w = w / w.sum()
nxt = int(rng.choice(js, p=w))
visited.append(nxt)
unvisited.discard(nxt)
all_tours.append(visited)
tau *= (1 - rho) # ② 蒸発
for tour in all_tours: # ② 付加（短い経路ほど多く）
L = sum(D[tour[k], tour[(k + 1) % n]] for k in range(n))
if L < best_len:
best_len, best_tour = L, tour[:]
for k in range(n):
a, b = tour[k], tour[(k + 1) % n]
tau[a, b] += Q / L
tau[b, a] += Q / L
history.append(best_len)
return best_tour, best_len, history
都市を生成して実行します。
def generate_cities(n=20, seed=42):
rng = np.random.default_rng(seed)
return rng.random((n, 2)) * 100
def dist_matrix(cities):
n = len(cities)
return np.array([[np.linalg.norm(cities[i] - cities[j])
for j in range(n)] for i in range(n)])
cities = generate_cities(20, seed=42)
D = dist_matrix(cities)
best_tour, best_len, history = aco_tsp(D, seed=0)
print(f'ACO 最良ツアー長 = {best_len:.2f}')
print(f'初期反復の最良長 = {history[0]:.2f} → 最終 = {history[-1]:.2f}')
print(f'ツアー = {best_tour}')
ACO 最良ツアー長 = 341.58
初期反復の最良長 = 357.60 → 最終 = 341.58
ツアー = [15, 11, 1, 9, 0, 10, 12, 8, 13, 17, 7, 16, 4, 18, 19, 14, 2, 5, 6, 3]
見つかったツアーを描くと、交差のほとんどない素直な巡回路になっています。
フェロモン行列が「経路を育てる」様子
ACO の面白さは、フェロモン行列 $\tau$ が反復とともに特定の辺に集中していくところです。最良ツアーの辺だけが明るく（フェロモン濃く）残っていきます。
- 1 反復後：まだ全体的にうっすら濃く、どの辺も似たり寄ったり（探索フェーズ）
- 5 反復後：良い辺が浮かび上がり始める
- 100 反復後：ごく一部の辺（＝最良ツアーを構成する辺）だけが明るく、他は蒸発で暗くなる
まさに「良い経路をフェロモンで育てている」のが見て取れます。上の2枚を生成したコードは以下のとおりです。
import matplotlib
matplotlib.use('Agg')
import matplotlib.pyplot as plt
plt.rcParams['font.family'] = 'Yu Gothic'
# ルート図
plt.figure(figsize=(6, 6))
plt.scatter(cities[:, 0], cities[:, 1], c='#34495e', s=80, zorder=3)
order = best_tour + [best_tour[0]]
plt.plot(cities[order, 0], cities[order, 1], '-', color='#e74c3c', linewidth=1.6)
for idx, (x, y) in enumerate(cities):
plt.annotate(str(idx), (x, y), fontsize=9, color='white', ha='center', va='center')
plt.title(f'ACO が見つけたツアー（長さ {best_len:.1f}）')
plt.tight_layout(); plt.savefig('20260801_aco_route.png', dpi=150)
# フェロモン行列のスナップショット（aco_tsp 内で τ.copy() を保存しておく）
fig, axes = plt.subplots(1, 3, figsize=(14, 4.5))
for ax, tau, ttl in zip(axes, tau_snaps, ['1 反復後', '5 反復後', '100 反復後']):
im = ax.imshow(tau, cmap='hot')
ax.set_title(f'フェロモン量 τ（{ttl}）')
ax.set_xlabel('都市 j'); ax.set_ylabel('都市 i')
fig.colorbar(im, ax=ax, fraction=0.046)
plt.tight_layout(); plt.savefig('20260801_aco_pheromone.png', dpi=150)
パラメータの勘どころ
| パラメータ | 役割 | 注意 |
|---|---|---|
| $\alpha$（フェロモン重み） | 過去の経験への依存 | 大きすぎると早期に収束し局所最適へ |
| $\beta$（ヒューリスティック重み） | 目先の近さの重視 | 大きいほど最近傍法に近づく。$\beta=2\sim5$ が定番 |
| $\rho$（蒸発率） | 忘却の速さ | 小さいと収束が遅い、大きいと情報が消えやすい |
| 蟻の数 | 1反復あたりの探索量 | 都市数程度にすることが多い |
実務では Ant System を改良した MMAS（Max-Min Ant System） や ACS（Ant Colony System） がよく使われます。フェロモン量に上下限を設けたり、最良の蟻だけがフェロモンを置いたりして、収束と多様性のバランスを取っています。
他手法との比較
| ACO | PSO（①） | GA（④） | |
|---|---|---|---|
| 得意な問題 | 組合せ最適化（TSP・経路・スケジューリング） | 連続最適化 | 両方（表現次第） |
| 新候補の作り方 | フェロモンに沿って経路を構築 | 速度更新で移動 | 交叉・突然変異で組換え |
| 解の表現 | 経路（辺の列） | 位置ベクトル | 染色体 |
| 特徴 | グラフ構造を自然に扱える | 実装が短い | 汎用性が高い |
ACO の強みは、「解を1要素ずつ構築する」問題にそのまま当てはまることです。TSP の「次にどの都市へ行くか」のように、逐次的に決めていく構造を持つ問題（経路・割当・スケジューリング）と相性が良いです。
まとめ
- ACO は蟻のフェロモンを模した群知能で、組合せ最適化（特に TSP） に強い
- 各蟻は「フェロモン $\tau$（集団の経験）」と「近さ $\eta$（目先の良さ）」の積に比例する確率で経路を構築する
- 蒸発で古い情報を忘れ、短い経路ほど濃くフェロモンを付加することで良い経路を育てる
- フェロモン行列が反復とともに特定の辺へ集中していく様子が可視化できた
- 連続最適化の PSO（①）と対をなす、離散問題の定番
次回は連続最適化の最強実用手法、CMA-ES に進みます。ここから「進化戦略」の世界に入ります。
参考にした記事や本、論文等
- M. Dorigo, V. Maniezzo, and A. Colorni, "Ant system: optimization by a colony of cooperating agents," IEEE Trans. SMC-B, vol. 26, no. 1, pp. 29-41, 1996.
- T. Stützle and H. Hoos, "MAX-MIN Ant System," Future Generation Computer Systems, vol. 16, no. 8, pp. 889-914, 2000.
- M. Dorigo and T. Stützle, "Ant Colony Optimization," MIT Press, 2004.