遺伝的アルゴリズム（GA）とは？

仕組み・手順・具体例までやさしく解説

「遺伝的アルゴリズム（Genetic Algorithm：GA）」は、生物の進化（自然淘汰・交叉・突然変異）をヒントにした最適化手法のひとつです。正解を一発で当てにいくというより、たくさんの候補解（個体）を並行して改良しながら、より良い解へ近づけていくという考え方が特徴です。

最適化問題（たとえば「コストを最小に」「精度を最大に」「距離を最短に」など）で、

• 探索空間が広すぎる
• 目的関数が凸でない・凸性が不明
• 微分が使えない／ブラックボックス
• 局所解にはまる

といった場面で、GAは有力な選択肢になります。

GAが得意なこと・苦手なこと

✅ 得意なこと

• 組合せ最適化（ルート最短、スケジューリング、割当問題など）
• ブラックボックス最適化（中身が複雑で勾配が取れない）
• 非線形・多峰性（山がいくつもある）
• 複数解の探索（集団を持つので多様性を保ちやすい）

⚠️ 苦手なこと

• 厳密解の保証は基本しない（近似解・準最適が中心）
• パラメータ調整（集団サイズ、変異率など）次第で性能が大きく変わる
• 計算コストが高くなりやすい（評価関数が重いと特に）

遺伝的アルゴリズムの基本アイデア

GAは、次のサイクルを何世代も繰り返します。

1. 初期集団をランダムに作る（たくさんの候補解）
2. 各個体を評価する（適応度：fitness）
3. 良い個体を選択する（親にする）
4. 親同士を交叉して子を作る（情報を混ぜる）
5. 子に突然変異を入れる（ランダムな揺らぎ）
6. 次世代に入れ替え、また評価へ

この繰り返しで、だんだん「良い解」寄りに集団が進化していきます。

GAの重要用語（ここだけ押さえれば読める）

• 個体（individual）：解候補
• 遺伝子（gene）：解を構成する要素
• 染色体（chromosome）：遺伝子の並び（解の表現）
• 集団（population）：個体の集合
• 適応度（fitness）：良さのスコア（高いほど望ましい場合が多い）
• 選択（selection）：良い個体を親に選ぶ
• 交叉（crossover）：親の情報を混ぜて子を作る
• 突然変異（mutation）：遺伝子をランダムに変えて多様性を維持
• 世代（generation）：更新の1サイクル

「解の表現」がGAの肝（コーディング／エンコーディング）

GAでは、解を「染色体」として表現します。表現の設計は性能に直結します。

1) ビット列（0/1）

• 例：機械のON/OFF、選択する／しない
• 典型的で扱いやすい

2) 実数ベクトル

• 例：パラメータ最適化（係数や重み）
• 交叉・変異を実数向けに工夫する

3) 順列（permutation）

• 例：巡回セールスマン問題（TSP）の訪問順
• 交叉すると重複や欠落が起きやすいので専用の交叉がよく使われます

GAの手順（もう少し具体的に）

手順1：初期集団の生成

• ランダムにN個の個体を作る
• 既存の良い解があるなら、混ぜると収束が早いことも

手順2：適応度の計算

• 目的関数をそのまま使う場合もあれば、
• 制約違反にペナルティを与える形にすることも多いです

手順3：選択（代表的な方法）

• ルーレット選択：適応度が高いほど選ばれやすい
• トーナメント選択：何体かを比べて勝者を親にする（実装が簡単）
• エリート保存：最良個体をそのまま次世代へ残す（改善が安定）

手順4：交叉（例）

• 一点交叉：ある地点で区切って親同士を入れ替え
• 二点交叉：二点で区切って中身を交換
• 一様交叉：遺伝子ごとに親A/Bどちらから取るか決める

手順5：突然変異

• ビットなら 0↔1 の反転
• 実数なら小さなノイズを加える
• 順列なら入れ替え（swap）など

手順6：世代交代

• 全入れ替え（世代交代モデル）
• 一部置換（定常状態モデル）

具体例：簡単な最適化（最大化問題のイメージ）

たとえば「式の値を最大にする x を見つけたい」という問題で、x をビット列で表して探索するとします。

• 個体：x のビット表現
• 適応度：f(x)
• 交叉：ビット列を途中で入れ替えて新しい x を生成
• 変異：一部ビットを反転して探索を広げる

このときGAは、

• たまたま当たりに近い個体が高評価になり
• 親として残りやすくなり
• 交叉で良い部分が子に受け継がれ
• 変異で局所解から抜けるチャンスも作り

結果として、良い x が見つかりやすくなります。

よくある応用分野（身近なものも多い）

• 🗺️ 配送ルート最適化（車両ルーティング、巡回順）
• 🧑‍🏭 生産計画・シフト作成（制約付きスケジューリング）
• 🎛️ パラメータ調整（機械学習モデルのハイパーパラメータ、制御器のゲイン）
• 🧩 組合せ設計（部品の組合わせ、配置、レイアウト）
• 🎮 ゲームAIの戦略探索
• 🧬 進化計算の一部として、探索・生成問題全般

うまく動かすコツ（実務で効くポイント）

1) 適応度関数を丁寧に設計する

GAの「賢さ」は、かなりの部分が評価関数の設計に依存します。制約があるなら、

• 制約違反のペナルティ
• 実現可能解を優先する仕組み

を明確にしておくと安定します。

2) 多様性を失わない

良い個体ばかりに偏ると、探索が早期に止まります（早期収束）。

• 変異率を少し上げる
• トーナメントの圧力を下げる
• 多様性維持（ニッチング、距離ベース）

といった工夫が使われます。

3) エリート保存は強いが、やりすぎ注意

最良個体を残すのは安定しますが、多様性が死ぬこともあります。少数エリートがちょうど良いことが多いです。

4) まずは小さく試して当たりをつける

集団サイズや世代数をいきなり大きくすると時間が溶けます。

• 小さめ設定で挙動を見る
• 目的関数の癖（山の形）を掴む
• 徐々にスケール

が安全です。

ありがちな誤解Q&A

Q1. GAは万能？

A. 万能ではありません。ですが「解空間が広い・勾配が使えない・局所解が多い」状況では強い味方になります。

Q2. GAは必ず最適解を見つける？

A. 必ずではありません。近似的に良い解を探す手法です。

Q3. 変異率は高いほど良い？

A. 高すぎるとほぼランダム探索になります。低すぎると多様性が失われて詰みやすいです。

GAのシンプルな擬似コード

population = init_population(N)
for gen in 1..G:
  fitness = evaluate(population)
  elites = keep_best(population, k)
  parents = select(population, fitness)
  children = crossover(parents)
  children = mutate(children, p_mut)
  population = elites + children
return best(population)

まとめ：遺伝的アルゴリズムは「集団で賢く探索する」最適化

遺伝的アルゴリズム（GA）は、

• 候補解を集団で持ち
• 選択・交叉・突然変異で世代交代し
• ブラックボックス的な問題でも解の改善を狙える

という、実務でも研究でも息の長い最適化手法です。

「何をどのように遺伝子として表現し、どう評価するか」が成功のカギになります。まずは小さな問題で試し、挙動を見ながらパラメータを調整すると理解が一気に進みます。