この記事について
前回は焼きなまし法（SA）で局所最適から脱出する方法を説明しました。SAは1つの解を発展させていきましたが、今回の遺伝的アルゴリズム（GA） は「複数の解（集団）を同時に進化させる」メタヒューリスティクスです。
生物の進化（選択・交叉・突然変異）を模倣した手法で、多様な解を保ちながら探索できることが特徴です。
配送最適化入門シリーズの記事一覧はこちら。
| 記事 | 内容 |
|---|---|
| ⓪ | 配送最適化とは？基礎概念 |
| ① | 近傍法の説明 |
| ② | 2-optの説明 |
| ③ | 3-optの説明 |
| ④ | Lin-Kernighan法の説明 |
| ⑤ | 焼きなまし法（SA）の説明 |
| ⑥（本記事） | 遺伝的アルゴリズム（GA）の説明 |
| ⑦ | VRPとは？ |
| ⑧ | VRPをアルゴリズムで解く |
遺伝的アルゴリズムとは？
GAは以下のサイクルを繰り返して解を進化させます。
① 初期集団の生成（複数のルートをランダムに生成）
② 評価（各ルートの総距離を計算）
③ 選択（良いルートを親として選ぶ）
④ 交叉（2つの親ルートを組み合わせて子ルートを生成）
⑤ 突然変異（一部のルートをランダムに変化させる）
⑥ ②に戻って繰り返す
TSPにおけるGAの難しさ
一般的な最適化問題では染色体（解の表現）を単純に切り貼りして子を作れますが、TSPでは「すべての都市をちょうど1回訪問する」という制約があるため、単純な切り貼りでは制約が壊れてしまいます。
例：
親1: [0, 1, 2, 3, 4]
親2: [2, 4, 1, 0, 3]
単純な切り貼りの子: [0, 4, 1, 0, 3] ← 都市0が2回、都市2がない！
そのため TSP 向けの専用の交叉演算子が必要です。
TSP向けの交叉演算子
OX（Order Crossover）
OXは最もよく使われるTSP向け交叉演算子です。
① 親1からランダムな区間をそのままコピーする
② 残りの都市を、親2の順序を保ちながら補完する
親1: [0, | 1, 2, 3 |, 4]
親2: [2, 4, 1, 0, 3]
ステップ①: 子 = [_, 1, 2, 3, _] （中央をコピー）
ステップ②: 親2から未使用の都市を順に補完 → 4, 0
子: [4, 1, 2, 3, 0]
def ox_crossover(parent1, parent2):
"""
OX（Order Crossover）
parent1, parent2: 親ルート
"""
n = len(parent1)
# ランダムな区間を選択
start = np.random.randint(0, n)
end = np.random.randint(start + 1, n + 1)
# 親1の区間をコピー
child = [-1] * n
child[start:end] = parent1[start:end]
copied = set(parent1[start:end])
# 親2の残り都市を順に補完
p2_idx = 0
for i in list(range(end, n)) + list(range(0, end)):
while parent2[p2_idx] in copied:
p2_idx += 1
child[i] = parent2[p2_idx]
copied.add(parent2[p2_idx])
p2_idx += 1
return child
PMX（Partially Mapped Crossover）
PMXは「区間を丸ごとコピーしつつ、重複が生じた都市は写像をたどって代替を見つける」演算子です。OXが「親2の順序を優先」するのに対し、PMXは「親1の区間の位置情報をより強く保持」するイメージです。
① 親1からランダムな区間をそのままコピーし、写像テーブル（親1の値→親2の値）を作る
② 残りの位置は親2の値を使う。ただしすでに子に含まれる値は、写像をたどって別の値に置き換える
親1: [0, | 1, 2, 3 |, 4]
親2: [2, 4, 1, 0, 3]
ステップ①: 区間を親1からコピー
子 = [_, 1, 2, 3, _]
写像テーブル: 1→4, 2→1, 3→0 ← 親1[i] → 親2[i] のペアから作成
ステップ②: 残りを親2で埋める（重複は写像をたどる）
位置0: 親2[0]=2 → すでに子にある → 2→1（写像）→ 1もある → 1→4（写像）→ 4はない ✓ child[0]=4
位置4: 親2[4]=3 → すでに子にある → 3→0（写像）→ 0はない ✓ child[4]=0
子: [4, 1, 2, 3, 0]
写像テーブルをたどることで、重複なく全都市を確実に1回ずつ含む子が完成します。
写像の意味：「弾き出された都市を追いかける」
区間のコピー時に何が起きているかを整理すると、写像の意味がわかりやすくなります。
| 位置 | 親1 | 親2 | 起きていること |
|---|---|---|---|
| 1 | 1 | 4 | 親1の「1」が親2の「4」を弾き出した |
| 2 | 2 | 1 | 親1の「2」が親2の「1」を弾き出した |
| 3 | 3 | 0 | 親1の「3」が親2の「0」を弾き出した |
写像 1→4, 2→1, 3→0 は「弾き出した→弾き出された」の対応です。
区間外で親2の値が子にすでにある（＝その都市が弾き出し側）場合、写像をたどって「弾き出されて行き場がない都市」を探します。位置0の 2→1→4 というチェーンはこの「弾き出しの連鎖」を逆にたどっているわけです。
OXとの強みの違い
| OX | PMX | |
|---|---|---|
| 何を保持するか | 親2の相対順序 | 親2の絶対位置 |
| 適した状況 | 「どの都市の次にどこへ行くか」が重要なとき | 「どの都市がルートのどの部分にいるか」が重要なとき |
OXは「AのあとにBが来る」という順序関係を継承します。PMXは「BはルートのN番目付近にいる」という位置関係を継承しようとします。TSPでは都市の地理的なまとまりが重要なことが多く、PMXは「北エリアの都市は北エリアに残りやすい」特性を持ちやすいです。
def pmx_crossover(parent1, parent2):
"""
PMX（Partially Mapped Crossover）
"""
n = len(parent1)
start = np.random.randint(0, n)
end = np.random.randint(start + 1, n + 1)
child = [-1] * n
child[start:end] = parent1[start:end]
# 写像関係を構築
mapping = {}
for i in range(start, end):
mapping[parent1[i]] = parent2[i]
for i in list(range(0, start)) + list(range(end, n)):
val = parent2[i]
while val in mapping:
val = mapping[val]
child[i] = val
return child
Python実装（フルGA）
import numpy as np
def genetic_algorithm_tsp(dist, pop_size=100, n_generations=500,
mutation_rate=0.02, elite_size=10):
"""
遺伝的アルゴリズムによるTSP
dist : 距離行列
pop_size : 集団サイズ
n_generations: 世代数
mutation_rate: 突然変異率
elite_size : エリート個体数（次世代にそのまま引き継ぐ）
"""
n = len(dist)
def fitness(route):
return sum(dist[route[i]][route[(i + 1) % n]] for i in range(n))
# ① 初期集団の生成
population = [list(np.random.permutation(n)) for _ in range(pop_size)]
best_route = min(population, key=fitness)
best_dist = fitness(best_route)
history = [best_dist]
for gen in range(n_generations):
# ② 評価・ソート
population.sort(key=fitness)
# エリート保存
new_pop = population[:elite_size]
# ③ 選択・交叉で新世代を生成
while len(new_pop) < pop_size:
# トーナメント選択
p1 = min(np.random.choice(len(population), 5, replace=False),
key=lambda i: fitness(population[i]))
p2 = min(np.random.choice(len(population), 5, replace=False),
key=lambda i: fitness(population[i]))
parent1 = population[p1]
parent2 = population[p2]
# OX交叉
child = ox_crossover(parent1, parent2)
# ⑤ 突然変異（2都市をランダムに入れ替え）
if np.random.rand() < mutation_rate:
i, j = np.random.choice(n, 2, replace=False)
child[i], child[j] = child[j], child[i]
new_pop.append(child)
population = new_pop
# 最良解の更新
gen_best = min(population, key=fitness)
gen_dist = fitness(gen_best)
if gen_dist < best_dist:
best_dist = gen_dist
best_route = gen_best[:]
history.append(best_dist)
return best_route, best_dist, history
実行してみる
import matplotlib
import matplotlib.pyplot as plt
plt.rcParams['font.family'] = 'Yu Gothic'
def generate_cities(n=20, seed=42):
np.random.seed(seed)
return np.random.rand(n, 2) * 100
def calc_distance(cities):
n = len(cities)
dist = np.zeros((n, n))
for i in range(n):
for j in range(n):
dist[i][j] = np.linalg.norm(cities[i] - cities[j])
return dist
cities = generate_cities(n=20, seed=42)
dist = calc_distance(cities)
np.random.seed(0)
ga_route, ga_dist, ga_history = genetic_algorithm_tsp(
dist, pop_size=200, n_generations=500, mutation_rate=0.02
)
print(f'GA後の総距離: {ga_dist:.1f}')
# 世代ごとの最良解推移
plt.figure(figsize=(8, 4))
plt.plot(ga_history, linewidth=1.5)
plt.xlabel('世代数', fontsize=12)
plt.ylabel('総距離（最良解）', fontsize=12)
plt.title('GAの収束曲線')
plt.grid(True, alpha=0.3)
plt.tight_layout()
plt.savefig('ga_history.png', dpi=150)
plt.show()
GA後の総距離: 473.6
SAとGAの比較
| 項目 | 焼きなまし法（SA） | 遺伝的アルゴリズム（GA） |
|---|---|---|
| 探索の仕組み | 1つの解を変化 | 複数の解を同時に進化 |
| 多様性 | 低い（1解のみ） | 高い（集団） |
| パラメータ | 冷却率・初期温度 | 集団サイズ・交叉率・突然変異率 |
| TSP向けの工夫 | 近傍解の設計 | 交叉演算子の設計（OX・PMX） |
| 実装の難しさ | 比較的簡単 | やや複雑 |
どちらが優れているかは問題依存ですが、実務ではSAをベースにしつつ、解の多様性を担保したい場合にGAを使うことが多いです。
まとめ
今回は遺伝的アルゴリズムを説明しました。
- GA：複数の解（集団）を選択・交叉・突然変異で進化させるメタヒューリスティクス
- TSPでは「全都市をちょうど1回訪問」の制約から、専用交叉演算子（OX・PMX）が必要
- エリート保存で良い解を次世代に引き継ぐことが重要
- SAとGAはトレードオフがあり、問題に応じて使い分ける
次回からはTSPの拡張であるVRP（Vehicle Routing Problem：配送計画問題） の説明に入ります。
参考にした記事や本、論文等
- D. E. Goldberg, "Genetic Algorithms in Search, Optimization and Machine Learning," Addison-Wesley, 1989.
- I. M. Oliver, D. J. Smith, and J. R. C. Holland, "A Study of Permutation Crossover Operators on the Traveling Salesman Problem," Proc. ICGA, pp. 224-230, 1987.