1 概要
遺伝的アルゴリズムは、生物進化の考え方を計算機上に取り入れた探索手法である。候補となる解を複数まとめて扱い、選別、交叉、突然変異を繰り返しながら、目的により近い解へ漸進的に近づける。厳密な最適解を必ず求める方法ではないが、複雑で探索範囲の広い問題に対して、実用上有力な近似解を見つけやすい。
1.1 定義
この手法は、解候補を染色体のように表現し、評価値に基づいて次世代を構成する反復的アルゴリズムとして定義される。各候補は集団の一員として扱われ、個々の性能と集団全体の性質の両方が更新の対象となる。
1.2 位置づけ
遺伝的アルゴリズムは、探索と最適化を目的とする広い枠組みの中で、確率的かつ経験的な方法に位置づけられる。数理的に厳密な収束保証を主眼に置く手法とは異なり、実装の柔軟さと問題適応のしやすさが重視される。
1.2.1 進化計算との関係
進化計算は、生物進化に着想を得たアルゴリズム群の総称であり、遺伝的アルゴリズムはその代表的な構成要素である。進化戦略や遺伝的プログラミングなど、類似の発想を持つ手法とともに扱われることが多い。
1.2.2 メタヒューリスティクスとしての特徴
本手法は、厳密解探索よりも、広い問題に対して妥当な解を効率よく得ることを目指すメタヒューリスティクスに属する。探索の進み方は確率要素に依存するため、局所的な停滞を避けつつ、多様な解を試せる点が特徴である。
1.3 利用分野
遺伝的アルゴリズムは、工学設計、機械学習の設定調整、経路探索、資源配分、研究用途のモデル選択などに用いられる。解の構造が複雑で、勾配情報を直接使いにくい場面で特に適している。
2 基本原理
遺伝的アルゴリズムの基本は、複数の候補解を同時に評価し、良好なものを残しながら新しい候補を生成することにある。選択によって有望な解を集め、交叉で情報を再構成し、突然変異で新規性を導入する。
2.1 集団
集団は、現在時点で保持している候補解の集合を指す。単一の解だけを逐次改良するのではなく、複数案を同時に並べることで、探索の幅を確保する。
2.1.1 個体
個体は、集団を構成する一つ一つの候補解である。表現形式は問題に応じて異なり、ビット列、実数列、順列などが用いられる。
2.1.2 適応度
適応度は、個体の良さを数値化した指標である。最大化問題では高い値が望ましく、最小化問題では評価値を変換して比較可能にすることが多い。
2.2 選択
選択は、次世代の親となる個体を決める操作である。評価の高い候補が残りやすい一方で、低い評価の個体にも一定の機会を与えることで、探索の偏りを抑える。
2.2.1 ルーレット選択
ルーレット選択は、適応度に比例した確率で個体を選ぶ方式である。成績の良い候補が選ばれやすいが、完全に独占するわけではないため、多様性を保ちやすい。
2.2.2 トーナメント選択
トーナメント選択は、複数の個体を無作為に抽出し、その中で最も評価の高いものを採用する方法である。実装が比較的単純で、選択圧の調整もしやすい。
2.3 交叉
交叉は、二つ以上の親個体から特徴を受け継いだ子個体を作る操作である。既存の良い部分を組み合わせ、新たな候補を生み出す役割を持つ。
2.3.1 一点交叉
一点交叉では、染色体を一か所で切り、前半と後半を入れ替えて子個体を作る。扱いやすい方式であり、離散表現との相性がよい。
2.3.2 多点交叉
多点交叉は、複数箇所で分割して部分列を交換する方法である。再結合の自由度が上がり、親の特徴をより複雑に混ぜ合わせられる。
2.4 突然変異
突然変異は、個体の一部を確率的に変更する操作である。交叉だけでは生まれにくい新しい構造を導入し、探索空間の取りこぼしを減らす。
2.4.1 変異率
変異率は、どの程度の頻度で変異を起こすかを決める設定値である。低すぎると探索が硬直しやすく、高すぎると有益な構造が壊れやすい。
2.4.2 多様性の維持
多様性の維持は、集団が似た個体ばかりになるのを防ぐ考え方である。新規性を保てば、探索が早期に狭い領域へ固定される事態を抑えられる。
3 アルゴリズムの流れ
典型的な処理は、初期集団の生成、評価、親の選択、交叉と突然変異による生成、世代交代、終了判定という順で進む。各段階は単純に見えるが、設定次第で性能は大きく変わる。
3.1 初期集団の生成
最初に、探索空間の中から複数の候補を作る。完全なランダム生成がよく使われるが、既知の良い解を一部混ぜて出発点を工夫する場合もある。
3.2 評価
各個体について評価関数を計算し、目的への適合度を求める。評価の質は探索全体の方向性を左右するため、問題設定に応じた定義が重要である。
3.3 世代交代
評価結果をもとに新しい集団へ更新する。古い個体をすべて捨てるとは限らず、一部を残して継続利用する方法も広く用いられる。
3.3.1 エリート保存
エリート保存は、上位の個体を次世代へ直接引き継ぐ仕組みである。優秀な解が失われにくくなる一方、使い方によっては集団の硬直化を招くことがある。
3.3.2 置換戦略
置換戦略は、どの個体を新しい世代に残すかを定める方針である。全置換、部分置換、定常型などがあり、探索速度と安定性のバランスに影響する。
3.4 終了条件
終了条件は、反復を打ち切る基準である。世代数の上限、改善量の停滞、目標値の達成などが用いられ、実運用では計算資源との兼ね合いも考慮される。
4 設計上の要素
遺伝的アルゴリズムの性能は、表現方法、評価関数、各種パラメータ、制約の扱い方に強く依存する。これらの設計が不適切だと、探索効率が低下しやすい。
4.1 染色体表現
染色体表現は、解をどのような形式で符号化するかを決める。問題構造に合った表現を選ぶことで、遺伝的操作の効果が高まりやすい。
4.1.1 ビット列表現
ビット列表現は、0と1の列で候補解を表す方式である。古典的で扱いやすく、離散的な組合せ問題に適用しやすい。
4.1.2 実数表現
実数表現は、連続値をそのまま遺伝子として保持する方法である。数値最適化では自然な表現になり、細かな調整を行いやすい。
4.1.3 順列表現
順列表現は、要素の並び順そのものを解として扱う。巡回や順序付けが本質となる問題、たとえば作業順序の決定などで利用される。
4.2 評価関数の設計
評価関数は、良し悪しを数値化する中心要素である。目的に対して敏感でありながら、極端に偏らない形に調整することが望ましい。
4.3 パラメータ設定
集団サイズ、交叉率、突然変異率などの設定は、探索の性質を大きく左右する。固定値で運用するほか、問題に応じて調整する方法もある。
4.3.1 集団サイズ
集団サイズは、同時に保持する個体数である。大きいほど多様性を確保しやすいが、計算量は増加する。
4.3.2 交叉率
交叉率は、親から子を作る際に交叉を適用する頻度である。高めにすると再結合が活発になり、低めだと親の構造をより保ちやすい。
4.3.3 突然変異率
突然変異率は、遺伝子を変更する確率である。探索の広がりと安定性の両方に関わるため、慎重な調整が必要である。
4.4 制約条件の扱い
現実の問題では、満たすべき条件がしばしば存在する。制約違反の個体に罰則を与える方法、修復処理を行う方法、制約を満たす範囲に探索を限定する方法などがある。
5 代表的な拡張
基本形を土台として、目的の複数化、連続空間への適応、他手法との統合など、多様な拡張が行われている。これにより、扱える問題領域が広がった。
5.1 多目的遺伝的アルゴリズム
多目的遺伝的アルゴリズムは、複数の評価基準を同時に考慮する方式である。相反する目標の間で、極端に偏らない解集合を得ることを目指す。
5.1.1 パレート最適性
パレート最適性は、ある目的を改善すると別の目的が悪化するような状態を表す概念である。多目的問題では、単一の最良解ではなく、複数の妥当な折衷案が重要になる。
5.1.2 解の多様性維持
多様性維持は、パレート前線上の解が一部に集中しないようにする工夫である。幅広い選択肢を残すことで、利用者が状況に合う解を選びやすくなる。
5.2 連続値最適化への応用
連続値最適化では、変数が実数で表されるため、実数表現と連続的な遺伝的操作が用いられる。関数の形が複雑でも、勾配に頼らず探索できる利点がある。
5.3 ハイブリッド化
ハイブリッド化は、遺伝的アルゴリズムに別の最適化技法を組み合わせる方針である。大域探索と局所改善を役割分担させ、性能を引き上げる狙いがある。
5.3.1 局所探索との併用
局所探索との併用では、遺伝的アルゴリズムで候補を広く探し、見つかった解を局所的に磨き上げる。探索の粗さと精密さを補完し合える。
5.3.2 他手法との組み合わせ
他手法との組み合わせには、焼きなまし法や粒子群最適化などとの統合が含まれる。問題の性質に応じて、探索の強みを分担できる。
6 長所と短所
遺伝的アルゴリズムは、適用範囲の広さと実装上の柔軟さを備える一方、計算負荷や設定依存性といった制約も持つ。長所と短所を理解することが、適切な利用につながる。
6.1 長所
一般性が高く、並列化しやすく、局所解に陥りにくい点が評価される。厳密性より実用性を重視する問題で特に有効である。
6.1.1 汎用性
汎用性が高く、離散問題から連続問題まで幅広く適用できる。評価関数さえ設計できれば、問題固有の詳細に合わせやすい。
6.1.2 並列計算への適性
個体ごとの評価は独立性が高いため、並列処理に向いている。大規模な集団でも、計算資源を分散して効率化しやすい。
6.1.3 局所解への強さ
複数の候補を同時に扱うため、一つの谷に閉じ込められにくい。突然変異による新規探索も、局所的な停滞から抜け出す助けになる。
6.2 短所
一方で、評価回数が多くなりやすく、最適化に時間を要することがある。また、設定が不適切だと十分な性能を発揮しにくい。
6.2.1 計算コスト
集団全体を反復的に評価するため、総計算量が増えやすい。特に評価関数が重い場合、実行時間が問題になる。
6.2.2 早期収束
集団内の多様性が失われると、探索が早い段階で似た解に集中する。結果として、より良い候補を見逃すことがある。
6.2.3 パラメータ依存性
性能は、集団サイズや変異率などの設定に大きく左右される。問題ごとに調整が必要であり、万能な定値は存在しない。
7 応用例
応用範囲は広く、設計、運用、分析、学習の各場面で活用されている。特に、探索空間が大きく、従来法だけでは扱いにくい課題で存在感を示す。
7.1 工学分野
工学では、機械構造、回路、工程配置、運転条件の調整など、複数条件の折り合いを要する課題に使われる。制約付き最適化との相性もよい。
7.1.1 設計最適化
設計最適化では、強度、重量、コスト、性能のバランスを探る。候補案を比較しながら、実用的な仕様へ近づけるのに役立つ。
7.1.2 スケジューリング
スケジューリングでは、作業順や割り当てを調整し、遅延や待ち時間を減らす。順列表現がよく使われる典型例である。
7.2 情報科学
情報科学では、学習モデルの調整、経路の探索、構造選択などに応用される。問題の定式化が複雑でも、探索型の枠組みで対応しやすい。
7.2.1 機械学習の探索
機械学習の探索では、ハイパーパラメータの調整やモデル構成の選択に利用される。勾配法だけでは扱いにくい設定空間でも探索しやすい。
7.2.2 経路探索
経路探索では、複数の経路候補から条件に合うものを選ぶ。最短距離だけでなく、混雑回避や制約回避を含む場合にも適用される。
7.3 研究用途
研究用途では、変数選択や構造推定、仮説比較などに使われる。探索の自由度が高いため、分析対象に合わせて柔軟に設計できる。
7.3.1 モデル選択
モデル選択は、複数の統計モデルや予測モデルの中から適切なものを選ぶ作業である。複雑さと説明力の均衡を図る場面で有効である。
7.3.2 特徴選択
特徴選択は、学習に使う変数の組合せを絞り込む方法である。不要な要素を減らし、精度や解釈性の改善を狙う。
8 関連概念
遺伝的アルゴリズムと近い領域には、進化に基づく他の最適化法や、確率的に探索を進める手法がある。いずれも、厳密解よりも有望解の発見を重視する点で共通する。
8.1 進化戦略
進化戦略は、主に実数値問題に向いた進化計算の一種である。突然変異の扱いを重視し、連続空間の探索でしばしば用いられる。
8.2 遺伝的プログラミング
遺伝的プログラミングは、解そのものをプログラムや式の形で進化させる手法である。構造の自動生成に強みがあり、表現の自由度が高い。
8.3 粒子群最適化
粒子群最適化は、群れの移動に着想を得た探索法である。個体間の情報共有を通じて解を改善し、比較的少ない設定で機能しやすい。
8.4 焼きなまし法
焼きなまし法は、確率的に悪化解も受け入れながら探索を進める方法である。局所解から抜け出す工夫を持ち、組合せ最適化で広く知られる。
</INTERNAL_LINK_CANDIDATES> 進化計算（生物進化に着想を得た最適化手法群） 最適化（より良い解を求める計算手法） メタヒューリスティクス（厳密解より実用的解を狙う探索枠組み） 適応度（個体の良さを表す評価指標） ルーレット選択（適応度に比例して選ぶ方式） トーナメント選択（少数候補の比較で選ぶ方式） 交叉（親の情報を組み合わせる操作） 突然変異（遺伝子を確率的に変える操作） エリート保存（優秀個体を次世代へ残す仕組み） 染色体表現（解を符号化する形式） 評価関数（解の良さを数値化する関数） 制約条件（満たすべき条件） 多目的最適化（複数目的を同時に扱う最適化） パレート最適性（ある目的改善が他目的悪化を伴う状態） 局所探索（近傍解を改善する手法） 焼きなまし法（確率的に悪化解も許容する探索法） 粒子群最適化（群れの挙動を模した最適化法） モデル選択（候補モデルから適切なものを選ぶこと） 特徴選択（学習に使う変数を絞ること） スケジューリング（作業や資源の割り当て計画）