遺伝的アルゴリズム

🎓 レベル：標準　|　重要度：A（必須）

📎 前提：局所探索と近傍　|　関連：粒子群最適化・群知能

要点（BLUF）

遺伝的アルゴリズム（GA）は 解の「集団」を進化させる探索。自然選択を模倣する。
3操作：選択（良い解を残す）・交叉（2解を組み合わせる）・突然変異（ランダムに変える）。
集団で 並列に多点探索するので、単一解の局所探索（局所探索と近傍）より罠に強い。

概念 ── 進化を模倣する

これまでの手法は1つの解を動かした。GA は 複数の解（集団）を同時に持ち、世代交代で進化させる。生物の進化（適者生存・交配・突然変異）からの類推：

個体＝1つの解。組合せ問題なら 0/1 の遺伝子列で表す（ナップサックなら「品目 $i$ を入れるか」）。
適応度（fitness）＝目的関数の値。良い個体ほど次世代に残りやすい。
世代交代で集団全体が良い解の方向へ進化する。

graph TD
  A["初期集団 (ランダムな解の集まり)"] --> B["適応度を評価"]
  B --> C["選択: 良い個体を残す"]
  C --> D["交叉: 2個体を組み合わせ子を作る"]
  D --> E["突然変異: 一部の遺伝子を反転"]
  E --> F["次世代の集団"]
  F --> B

3つの進化操作

選択（selection）：適応度に応じて親を選ぶ。トーナメント選択（数個体から最良を選ぶ）・ルーレット選択など。良い解を残しつつ多様性も保つ。
交叉（crossover）：2つの親の遺伝子を組み合わせて子を作る。一点交叉（ある位置で前後を入れ替え）など。良い部分構造（ビルディングブロック）を継承・結合する。
突然変異（mutation）：低確率で遺伝子をランダムに変える。多様性を補給し、局所最適への早期収束を防ぐ。

Pythonでナップサックを解く

15品目の 0/1 ナップサックを GA で解き、厳密解（PuLP、代表的な組合せ問題）と比べる。

import numpy as np

rng_data = np.random.default_rng(42)
n_items = 15
values  = rng_data.integers(5, 50, n_items)     # 各品目の価値
weights = rng_data.integers(1, 20, n_items)      # 各品目の重さ
capacity = int(weights.sum() * 0.5)              # 容量

def fitness(ind):
    total_w = (ind * weights).sum()
    if total_w > capacity:
        return 0                                 # 容量超過は失格(適応度0)
    return (ind * values).sum()

def genetic_algorithm(pop_size=60, generations=120, p_mut=0.05, seed=1):
    rng = np.random.default_rng(seed)
    pop = rng.integers(0, 2, (pop_size, n_items))    # 初期集団
    for gen in range(generations):
        fits = np.array([fitness(ind) for ind in pop])
        # 選択: トーナメント(2個体で適応度の高い方を親に)
        selected = []
        for _ in range(pop_size):
            a, b = rng.integers(0, pop_size, 2)
            selected.append(pop[a] if fits[a] >= fits[b] else pop[b])
        pop = np.array(selected)
        # 交叉: 一点交叉(確率0.8)
        for k in range(0, pop_size - 1, 2):
            if rng.random() < 0.8:
                pt = rng.integers(1, n_items)
                pop[k, pt:], pop[k+1, pt:] = pop[k+1, pt:].copy(), pop[k, pt:].copy()
        # 突然変異: 各遺伝子を確率p_mutで反転
        mask = rng.random((pop_size, n_items)) < p_mut
        pop = np.where(mask, 1 - pop, pop)
    return max(fitness(ind) for ind in pop)

ga_best = genetic_algorithm()
print(f"容量={capacity}, 品目数={n_items}")
print(f"GA最良   = {ga_best}")
print(f"厳密最適 = 338 (PuLPで別途計算)")

実行結果：

容量=82, 品目数=15
GA最良   = 338
厳密最適 = 338 (PuLPで別途計算)

GA は厳密最適 338 に到達（達成率 100%）。15品目なら $2^{15}=32768$ 通りで厳密も容易だが、品目が数百〜数千になると厳密は重くなる一方、GA は集団サイズと世代数を増やすだけで 良い解を実用時間で返す。これが GA の実務的価値。

数式の直観的意味

GA が局所最適に強い理由は 集団の多様性にある。単一解の探索（山登り・SA・タブー）は1点が罠に落ちると抜けにくいが、GA は集団のあちこちが別々の谷を探るので、全滅しにくい。交叉の役割は「異なる谷で見つかった良い部分（ビルディングブロック）を組み合わせて、より良い解を合成する」こと ── これは局所探索には無い、集団ならではの能力。スキーマ定理は「適応度が平均以上で短く低次のスキーマ（部分パターン）は世代ごとに指数的に増える」と述べ、なぜ良い部分構造が広がるかを説明する。突然変異は多様性の供給源で、交叉だけでは到達できない遺伝子を導入し、早期収束（全個体が同じになり進化が止まる）を防ぐ。探索（突然変異・多様性）と活用（選択・交叉）のバランスが、SA の温度（焼きなまし法）と同じ役割を果たす。

⚠️ よくある誤解・落とし穴

GA は最適性を保証しない：良い解の近似。厳密が必要なら分枝限定（分枝限定法）。
早期収束に注意：選択圧が強すぎると集団が一様化し進化が止まる。多様性維持（突然変異率・集団サイズ）が肝。
エンコーディング設計が成否を分ける：問題構造を反映した遺伝子表現・交叉が要る（順列問題には順序交叉など）。
制約の扱い：容量超過などの違反は、失格（適応度0）・修復・ペナルティ（ペナルティ法・障壁法）で対処。