Skip to content
検索結果に戻る

確率的遺伝的アルゴリズム — 最適化のためのランダム化進化的探索

提唱者
Holland, J. H.
年
1975
種類
Stochastic evolutionary metaheuristic
系統
Simulation / optimization

この文章は機械翻訳で、まだ確認されていません。 英語の原文を読む

文字サイズ

何をする手法か?

確率的遺伝的アルゴリズム(SGA)は、生物学的進化(選択、交叉、突然変異)を模倣して、複雑、非線形、または組み合わせ空間における準最適解を探索する、集団ベースのメタヒューリスティックです。そのランダム化された演算子は、局所的最適解に対してロバストであり、工学、スケジューリング、機械学習、オペレーションズリサーチに広く適用可能です。

手法の背後にある直感

生存競争を行う候補解の集団を想像してください。より良い解が親として選択される可能性が高く、その子孫は良い特性を受け継ぎ再結合しますが、時折ランダムな突然変異が新規性を導入します。多くの世代を経て、このプロセスは勾配情報なしで探索空間の高品質な領域に収束します。「確率的」というラベルは、選択、交叉、突然変異がすべて確率的描画を伴うことを強調しており、これが標準的なGAをまれな決定論的変種と区別し、グローバル探索能力を与えるものです。

歴史学

ジョン・ホランドは1975年にミシガン大学で遺伝的アルゴリズムの理論的基盤を導入し、シミュレートされた遺伝システムに関するフレーザー(1957年)の初期の研究に依拠しました。デイビッド・ゴールドバーグの1989年の教科書は、工学最適化におけるGAを普及させました。選択の確率的性質はスキーマ定理によって形式化され、この方法は進化的計算と計算知能の礎となりました。

使うべき場面

SGAを使用するのは、(1)探索空間が大きく、多峰性または不連続であり、勾配ベースの方法が失敗または適用できない場合。(2)目的関数がブラックボックス、ノイズが多い、または評価コストが高いが、集団レベルのサンプリングでは処理可能な場合。(3)組み合わせ問題または混合整数問題に効率的な厳密ソルバーがない場合。(4)合理的な評価回数内で準最適解が見つかれば許容できる場合。SGAを使用しないのは、問題が凸であるか、勾配が利用可能で安価な場合(古典的最適化の方が高速に収束する)。関数評価が非常に高コスト(数十または数百)で、集団ベースの方法が予算を使い果たす可能性がある場合。または、証明可能な最適解が必要な場合(GAは最適性の保証を提供しない)。

限界と注意点

  • 大域的最適解を見つける保証がない。解の質は、集団サイズ、演算子の選択、世代数に依存します。
  • 滑らかで低次元の問題における勾配ベースの方法と比較して計算コストが高い — 多くの関数評価が必要です。
  • ハイパーパラメータチューニング(集団サイズ、交叉率、突然変異率)は問題依存であり、しばしば実験が必要です。
  • 選択圧が高すぎるか、突然変異率が低すぎると、早期収束が発生し、探索が準最適領域に閉じ込められる可能性があります。

出典に示された条件は、独立した科学的レビューや分析エンジンによる検証の代わりにはなりません。

強み

  • 勾配情報が不要 — ブラックボックス、不連続、または非微分可能な目的関数に適用可能。
  • 適切なエンコーディングにより、組み合わせ、混合整数、順列探索空間を自然に扱います。
  • 設計上並列化可能:集団の評価を並列化でき、実質的な実行時間を短縮します。
  • 集団の多様性と確率的探索により、局所的最適解に対してロバストです。
  • ドメイン固有の制約に合わせて演算子、エンコーディング、選択スキームをカスタマイズできるため、拡張性が高いです。

応用

  • 製造業および物流におけるジョブショップおよびフローショップスケジューリング
  • 機械学習パイプラインにおける特徴選択およびハイパーパラメータチューニング
  • 機械工学および土木工学における構造およびトポロジー最適化
  • オペレーションズリサーチにおける巡回セールスマン問題および車両ルーティング問題
  • バイオインフォマティクスにおけるタンパク質構造予測および創薬
  • ニューラルネットワークアーキテクチャ探索および重み最適化

使い方

使い方

1

ランダムまたはヒューリスティックシードによって、N個の候補解(染色体)の初期集団を生成します。各染色体は、選択された問題表現に応じて、二値文字列、実数ベクトル、順列、またはツリーとして、決定空間内の実行可能点をエンコードします。

2

目的関数(または代理モデル)を使用して、集団内のすべての個体の適合度f(x_i)を計算します。適合度は解の質を定量化し、適合度が高いほど良い解となります。最小化問題では、適合度はコスト関数の逆数または変換として定義されることがよくあります。

数式
f(x_i), \quad i = 1, \ldots, N
3

確率的選択演算子を適用して親を選択します。ルーレットホイール(適合度比例)選択は、各個体にその適合度に比例した確率を割り当てます。トーナメント選択、ランク選択、エリート主義は、選択圧を制御する一般的な変種です。

数式
P(\text{select } x_i) = \frac{f(x_i)}{\sum_{j=1}^{N} f(x_j)}
4

確率p_c(通常0.6〜0.9)で、選択された親のペアを再結合して子孫を生成します。単一点、二点、または一様交叉は、親染色体間で遺伝物質を交換し、両方の親の特性を受け継ぐ子を作成します。この演算子は、良いビルディングブロックの活用を促進します。

5

各子孫染色体の個々の遺伝子を、低い確率p_m(通常、遺伝子あたり0.001〜0.05)でランダムに変更します。突然変異は遺伝的多様性を維持し、早期収束を防ぎ、アルゴリズムが局所的最適解から脱出できるようにします。突然変異率は、問題に合わせて調整される重要なパラメータです。

6

子孫で現在の集団を置き換える(世代交代)か、定常状態更新を使用します。適合度を再度評価し、停止基準(最大世代数、適合度閾値、または一定世代数での改善なし)が満たされるまで、選択ステップから繰り返します。

よくある落とし穴

  • 突然変異率が高すぎると、アルゴリズムが実質的にランダム探索になり、蓄積された適合度の向上を破壊します。
  • 置き換え戦略でエリート主義を無視すると、世代間で発見された最良の解が失われる可能性があります。
  • 二値エンコード問題に実数値交叉演算子を適用する(またはその逆)と、エンコーディングが壊れ、実行不可能な子孫が生成されます。
  • 早期停止 — 不十分な世代数 — は、実際には解の質が低い最も一般的な理由です。
  • 制約処理の無視:制約のない交叉と突然変異は頻繁に問題制約に違反します。ペナルティ関数または修復演算子を明示的に組み込む必要があります。

よくある質問

確率的遺伝的アルゴリズムは、標準的な遺伝的アルゴリズムとどのように異なりますか?

「確率的」というラベルは、すべてのコア演算子(選択、交叉、突然変異)が確率的描画を伴うことを強調しています。ホランドによって導入された標準的なGAは、本質的に確率的です。このラベルは、シミュレーション/最適化の文献で、まれな決定論的変種(例:決定論的クラウディング)と区別し、アルゴリズムの動作がランダム性により実行ごとに変化することを明確にするために使用されます。

集団サイズはどのくらいにすべきですか?

一般的な出発点は、中程度の次元の問題では50〜200個の個体です。集団が大きいほど多様性が向上し、早期収束が減少しますが、世代あたりの計算コストが増加します。染色体長に基づく経験則(例:遺伝子数の10倍)は存在しますが、経験的な調整またはメタ最適化が必要になることがよくあります。

遺伝的アルゴリズムよりも粒子群最適化または焼きなまし法を好むのはいつですか?

粒子群最適化(PSO)は、速度情報を活用するため、連続実数値問題ではしばしば高速です。焼きなまし法(SA)は実装が簡単で、単一解の軌跡探索に効果的です。GAは、探索空間が組み合わせ的である場合、交叉が解構造を意味のある形で再結合する場合、または集団の多様性が多峰性ランドスケープにとって価値がある場合に好まれます。

確率的遺伝的アルゴリズムは、高次元問題にスケールしますか?

集団が空間を適切にサンプリングするのに十分な大きさである必要があるため、非常に高次元(数百から数千の変数)ではパフォーマンスが低下します。リンク学習GA、分布推定アルゴリズム、または移行を伴うアイランドモデルなどの特殊な変種は、スケーラビリティに対処しますが、複雑さが増します。

遺伝的アルゴリズムで制約をどのように扱いますか?

3つの主要な戦略が使用されます。(1)制約違反に対する適合度を下げるペナルティ関数。(2)実行不可能な子孫を実行可能領域に投影する修復演算子。(3)構成によって実行可能な解のみを生成する特殊なエンコーディングと演算子。ペナルティベースの方法は実装が最も簡単ですが、ペナルティ係数の慎重な調整が必要です。

関連する手法

参考文献

  1. Holland, J. H. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor.

    ISBN:978-0262581110
    コピーしました。
  2. Goldberg, D. E. (1989). Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, Reading, MA.

    ISBN:978-0201157673
    コピーしました。