進化を模倣した最適化アルゴリズム
遺伝的アルゴリズムは確率的多点探索アルゴリズムの一種である。遺伝的アルゴリズムでは、探索点を個体、探索点の集合を集団と呼ぶ。
- アルゴリズム
- 集団から親を選ぶ
- 親に対して交叉オペレーターを適用し、子個体を発生させる(交叉・突然変異)
- 子個体及び集団から、新たな集団を作る(世代交代)
- ステップ1へ
生命の進化を観察した結果、次の2つのことが経験的にわかっている。
- 交叉では親(あるいは集団)と「似ている」子個体を発生させることがポイント。
- 世代交代では良い個体を選択すると同時に「多様性」を維持することがポイント。
近年は数理的な観点から、これらの操作を確率モデルを用いて表現したestimation of distribution algorithm (EDA)が注目されている。EDAでは交叉が「(良い個体の)集団の背後にある確率分布の推定と、その分布からのサンプリング」と定義できる。
--あかほ
関連項目 †
リンク集 †
関連文献 †