この記事について

前回は焼きなまし法（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.