遺伝的アルゴリズム｜評価・選択・交叉で最適解へ近づく

遺伝的アルゴリズム

遺伝的アルゴリズムは、生物進化の原理（適者生存・交配・突然変異）を模倣して、組合せ最適化や連続最適化の近似解を探索するメタヒューリスティクスである。評価関数（適応度）により個体の良さを定量化し、世代を重ねて解候補の集団を改良する。勾配が取りにくいブラックボックス問題、多峰性で局所解が多い探索空間、離散・連続が混在する設計などに強みを持ち、設計最適化、工程計画、スケジューリング、機械学習のハイパーパラメータ探索など幅広く適用される。

Table Of Contents

遺伝的アルゴリズム

基本概念と着想

遺伝的アルゴリズム（GA）は、個体（解候補）を染色体として表現し、適応度に基づく選択、交叉、突然変異という操作で集団を進化させる。重要なのは、点探索ではなく集団探索で多様性を保ちながら、良解を含む領域へ探索資源を集中させるバランスである。確率的手法であるため同一設定でも得られる解は揺らぐが、エリート保存や乱数種の固定で再現性を一定程度確保できる。

アルゴリズムの流れ

初期集団の生成：ランダム生成や既知の可行解から始める。
評価：各個体の適応度を計算する（コスト最小化なら負に変換など）。
選択：適応度に応じて親個体を確率的に選ぶ（ルーレット、トーナメント）。
交叉：親の遺伝情報を組み替えて子個体を作る（1点・2点・均一、順列表現ではPMXやOX）。
突然変異：低確率で遺伝子を擾乱し多様性を維持する（ビット反転、実数摂動、スワップ）。
置換：新旧世代の統合方式を設計する（世代交代、エリート保存、定常GA）。
終了判定：世代上限、改善停滞、目標適応度到達などで停止する。

表現とオペレータ

符号化（染色体設計）

符号化は探索性能を左右する。ビット列は実装が容易で汎用だが、実数値最適化には実数値GA（BLX-αやSBXなど）が有効である。巡回路や順序制約をもつ問題では順列表現が適し、部分写像交叉や順序交叉が可行性を保つ。制約を強く受ける設計では、遺伝子の定義域、丸め、修復関数を工夫して実行可能解の生成率を高める。

選択・交叉・突然変異

選択：選択圧が高すぎると早熟収束を招く。トーナメントのサイズやランキング選択で圧を調整する。
交叉：探索の推進力であり、多様な親の組合せで探索範囲を広げる。実数値では親の外挿を許す交叉で局所最適からの脱出を促す。
突然変異：多様性の源泉である。確率は小さく保ちつつ、停滞時には適応的に引き上げる戦略が有効である。

適応度設計と制約の扱い

適応度（評価関数）のスケーリングは重要である。ばらつきが大きいと選択が偏り、逆に小さいと進化が停滞する。制約条件はペナルティ法（違反量に重み付け）、実行可能性優先（可行解を常に優先）、修復法（違反遺伝子を補正）などで扱う。多目的最適化では、遺伝的アルゴリズムを拡張したNSGA-II/IIIやSPEA2が非劣解集合（Pareto front）を近似し、トレードオフの可視化に適する。

パラメータ設計と収束挙動

集団サイズ、交叉率、突然変異率、選択圧、世代数は相互作用する。経験則として、探索空間が大きいほど集団を増やし、交叉率を高め、エリート保存で進捗を確保する。早熟収束の兆候（同質化、適応度分散の低下）が見えたら、突然変異率の上昇、ニッチングやクラウディング、移民戦略で多様性を回復する。並列化は容易で、評価関数をCPU/GPUで分散するだけでスケールする。

実務での適用領域

組合せ最適化：TSP、車両経路、ジョブショップスケジューリング。
設計最適化：形状・トポロジー設計、材料配合、ばね・ギアの寸法最適化。
運用計画：生産計画、在庫・配車、発電・需給最適化。
機械学習：特徴選択、ハイパーパラメータ探索、アンサンブル重み付け。
制御：PIDゲイン同定、モデル簡略化後のパラメータ調整。

ハイブリッド化と実装の要点

GAは局所探索と組み合わせると強力になる（メメティックアルゴリズム）。交叉で広域探索、局所法（勾配降下、2-opt、局所焼きなまし）で解を磨く二段構えが有効である。実装上は、可視化（進化曲線、フロント）、早期終了、チェックポイント、乱数管理、ユニットテスト、パラメータ自動同定（ベイズ最適化）を備えると運用性が高まる。

利点と限界

利点：勾配不要、目的・制約がブラックボックスでも扱える。多峰性・離散変数・混合領域に強く、並列計算に親和的である。
限界：計算コストが大きく、厳密最適性の保証はない。微細な精緻化には局所探索の併用が望ましい。適切な符号化とパラメータ設計を欠くと早熟収束に陥る。

遺伝的アルゴリズム｜評価・選択・交叉で最適解へ近づく