遺伝的アルゴリズム — 進化的最適化
- 提唱者
- John Henry Holland
- 年
- 1975
- 種類
- Population-based metaheuristic
この文章は機械翻訳で、まだ確認されていません。 英語の原文を読む
何をする手法か?
遺伝的アルゴリズム(GA)は、1975年にJohn Henry Hollandによって導入された、自然選択の原理を模倣した集団ベースのメタヒューリスティック最適化手法です。候補解の集団を維持し、選択、交叉、突然変異演算子を通じてそれらを反復的に改善します。これにより、古典的な勾配ベースの手法が失敗するような、不連続、非凸、多峰性の探索空間において特に強力になります。
手法の背後にある直感
難しい問題に対する数千の可能な解答があり、最良の解答を見つけるための公式がないと想像してください。遺伝的アルゴリズムは、各候補解答を個体群内の個体として扱います。各世代で、最も適した個体を維持し、それらを交配させて良い特性を混ぜ合わせ、時折子孫に突然変異を加えて新規性を注入します。多くの世代を経て、個体群は勾配をたどるのではなく、進化が時間とともに生物を形作る方法を模倣することによって、より良い解へと漂流します。
歴史学
遺伝的アルゴリズムは、John Henry Hollandが1975年の著書『Adaptation in Natural and Artificial Systems』で導入しました。この本はスキーマ(ビルディングブロック)の概念を形式化し、交叉と選択がどのようにしてより適合度の高い領域へと探索を駆動するかの基礎的な理論分析を提供しました。Hollandの学生、特にDavid Goldbergは、1980年代の工学応用を通じてGAを普及させました。Kalyanmoy Debは後に、多目的設定にフレームワークを拡張し、広く採用されているNSGA-IIアルゴリズム(2002年)に至りました。今日、GAは進化計算における標準的なツールであり続けており、進化探索と局所的洗練を組み合わせたハイブリッド手法に関する活発な研究が行われています。
使うべき場面
遺伝的アルゴリズムは、探索空間が広大、不連続、非微分可能、または多峰性である場合に適切です。これらの条件では、勾配ベースのソルバーは動作できないか、局所最適解にトラップされる可能性があります。連続変数、カテゴリ変数、バイナリ変数、順序変数のすべての型に適用でき、正規性や分布に関する仮定を課しません。唯一の要件は、計算可能な適合度関数です。解析的または凸的な定式化が存在する問題では、古典的な手法(線形計画法、勾配降下法)の方が高速であり、優先されるべきです。意味のある収束には十分な反復(通常は1,000世代をはるかに超える)が必要であり、世代数が少なすぎることが最も一般的な失敗モードです。
限界と注意点
- 大域的最適解への収束は保証されない;結果は実行ごとに異なる可能性がある。
- 計算コストが高い:各世代で個体群全体を評価する必要があり、適合度関数が遅い場合は実行不可能になる。
- パフォーマンスはハイパーパラメータの選択に敏感である — 個体群サイズ、交叉確率、突然変異率 — これらはしばしば問題固有の調整を必要とする。
- 滑らかで、凸状で、または構造化された問題に対しては、古典的な勾配ベースまたは線形手法の方が高速で信頼性が高い。
出典に示された条件は、独立した科学的レビューや分析エンジンによる検証の代わりにはなりません。
強み
- 不連続、非微分可能、多峰性の目的ランドスケープで動作し、勾配ベースの手法が破綻する。
- 分布に関する仮定を課さない — 唯一必要な入力は計算可能な適合度関数である。
- 広範囲の変数型を自然に処理する:連続型、バイナリ型、カテゴリ型、順序型。
- 個体群の多様性により、探索空間の複数の領域を同時に探索でき、早期の局所最適解トラッピングのリスクを低減する。
- 拡張性が高い:ドメイン固有の交叉および突然変異演算子、制約処理、多目的変種(例:NSGA-II)が文献で確立されている。
応用
- 工学設計最適化:構造、回路、または機械システムの最適なパラメータ構成を見つける。
- スケジューリングおよびルーティング問題:ジョブショップスケジューリング、車両ルーティング、および時間割作成。これらの問題では、組み合わせ探索空間が網羅的探索には大きすぎる。
- 機械学習:ハイパーパラメータチューニング、ニューラルアーキテクチャ探索、および特徴量選択。
- オペレーションズリサーチ:サプライチェーン最適化、ポートフォリオ割り当て、および複雑な制約下でのリソース割り当て。
- バイオインフォマティクス:配列アラインメント、タンパク質構造予測、および遺伝子制御ネットワーク推論。
使い方
使い方
通常、探索空間内でランダムに作成された候補解(個体)の集団です。各個体は、例えばバイナリ文字列、実数値ベクトル、または順列として、潜在的な解をエンコードします。個体群のサイズは、初期段階から探索空間をどの程度広くサンプリングするかを決定する重要なパラメータです。
個体群内のすべての個体は、その解が問題の目的と比較してどの程度優れているかを定量化する適合度関数によって採点されます。適合度関数は、ユーザーが提供する必要がある唯一のドメイン固有のコンポーネントです。シミュレーション出力、コスト式、またはモデル誤差メトリックなど、計算可能な任意の尺度にすることができます。
より高い適合度を持つ個体が、次世代の親となるために優先的に選択されます。一般的な選択メカニズムには、トーナメント選択、ルーレットホイール(適合度比例)選択、ランクベース選択などがあります。選択圧は、高品質な解の活用と個体群の多様性の維持との間のトレードオフを制御します。
選択された親は、2つの親のエンコーディングのセグメントを組み合わせて新しい個体を形成する交叉(組み換え)と、個々の遺伝子に小さなランダムな変更を加える突然変異を通じて子孫を生成します。交叉確率と突然変異率は重要な調整パラメータです。突然変異が少なすぎると早期収束を引き起こし、多すぎると探索がランダムウォークになります。
評価 → 選択 → 再生産のループは、指定された世代数まで、または収束基準が満たされるまで(例:一定期間の世代で改善が見られない)継続されます。すべての世代で見つかった最良の個体が解として返されます。大域的最適解への収束は保証されないため、重要な問題に対しては複数の独立した実行が推奨されます。
よくある落とし穴
- 世代数が少なすぎることが最も一般的なエラー:十分な世代数がないとアルゴリズムは収束しないため、反復予算が少ない場合は解析的または勾配ベースの手法を優先すべきである。
- 早期収束 — 個体群が早期に多様性を失う — は、局所最適であるが大域的には劣る結果を生む;これを相殺するために、十分な個体群サイズと突然変異率を維持する。
- 不適切に定義された、または誤って指定された適合度関数を使用すると、アルゴリズムの正しさに関係なく誤解を招く結果が生じる;GAを実行する前に適合度関数を独立に検証する。
- 勾配降下法や線形計画法で十分な滑らかで凸状の問題にGAを適用すると、計算リソースが無駄になり、不必要な確率的要素が導入される。
- 再現性を確認せずに単一の実行を解として報告すること;重要なアプリケーションでは、アルゴリズムを複数回実行し、結果の分布を報告する。
よくある質問
遺伝的アルゴリズムは勾配降下法とどう違うのですか?
勾配降下法は微分可能な目的関数を必要とし、局所的な勾配を下にたどります。遺伝的アルゴリズムは、候補解に対して適合度を計算できることだけを必要とします。勾配をたどるのではなく、個体群を進化させることによって探索するため、勾配降下法が失敗したり行き詰まったりする不連続、非微分可能、多峰性のランドスケープを処理できます。
いくつの世代とどのくらいの個体群が必要ですか?
普遍的な規則はありません;どちらも探索空間の複雑さに依存します。個体群が小さすぎたり、実行が短すぎたりすると、早期収束のリスクがあります。実用的な出発点として、個体群サイズ50〜200、世代数100〜1,000が文献で一般的ですが、難しい問題では通常それ以上が必要です。恣意的な停止基準を設定するのではなく、常に収束曲線を確認してください。
遺伝的アルゴリズムは、大域的最適解を見つけることを保証していますか?
いいえ。GAはヒューリスティックであり、有限時間で大域的最適解への収束を保証しません。決定論的な保証が必要な場合は、整数計画ソルバーなどの厳密な手法が必要です。重要な決定については、GAを複数回実行し、結果の分布を報告し、最良の解を既知の境界と比較してください。
シミュレーテッドアニーリングや粒子群最適化よりもGAを選択すべきなのはいつですか?
GAは、解が組み合わせ構造(順列、バイナリ文字列)として自然にエンコードされている場合、または多目的拡張が必要な場合に好まれる傾向があります。粒子群最適化は、連続的な単峰性問題ではより高速な場合が多いです。シミュレーテッドアニーリングは、明確に定義された近傍を持つ組み合わせ問題の実装がより簡単です。実際には、1つにコミットする前に、小規模な問題インスタンスで2つまたは3つの手法をベンチマークすることをお勧めします。
関連する手法
参考文献
Holland, J.H. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press.
出版物の文献を開くコピーしました。Deb, K. (2001). Multi-Objective Optimization using Evolutionary Algorithms. Wiley.
ISBN:9780471873396コピーしました。