遺伝的アルゴリズム

遺伝的アルゴリズム (genetic algorithm) †

進化を模倣した最適化アルゴリズム

遺伝的アルゴリズムは確率的多点探索アルゴリズムの一種である。遺伝的アルゴリズムでは、探索点を個体、探索点の集合を集団と呼ぶ。

• アルゴリズム
  1. 集団から親を選ぶ
  2. 親に対して交叉オペレーターを適用し、子個体を発生させる（交叉・突然変異）
  3. 子個体及び集団から、新たな集団を作る（世代交代）
  4. ステップ１へ

生命の進化を観察した結果、次の２つのことが経験的にわかっている。

1. 交叉では親(あるいは集団)と「似ている」子個体を発生させることがポイント。
2. 世代交代では良い個体を選択すると同時に「多様性」を維持することがポイント。

近年は数理的な観点から、これらの操作を確率モデルを用いて表現したestimation of distribution algorithm (EDA)が注目されている。EDAでは交叉が「（良い個体の）集団の背後にある確率分布の推定と、その分布からのサンプリング」と定義できる。

--あかほ

関連項目 †

• genetic algorithm
• GA
   
• 最適化
• EDA
• 逐次モンテカルロ法
• 遺伝的プログラミング
   
• 検索: 遺伝的アルゴリズム GA

リンク集 †

• Genetic Algorithms WAREHOUSE：資料やソフトウェアへのポータル
• 人工知能学会「私のブックマーク」進化的計算
• 遺伝的アルゴリズム (GA) @ 伊庭斉志研究室
• Genetic Algorithm & Genetic Programming @ AAAI AI topics
• Thomas Weise "Global Optimization Algorithms - Theory and Application"
   
• Scholarpedia:Evolutionary_algorithms
• Wikipedia:Genetic_algorithm
• MathWorld:GeneticAlgorithm

Freeware †

• mloss:genetic-algorithms
• CIlib：Swarm Intelligence, Evolutionary Computation
• Distributed Genetic Programming Framework
• EO Evolutionary Computation Framework (C++)
• Genetic Algorithms WAREHOUSE/Libraries：遺伝的アルゴリズムのライブラリへのリンク集
• IlliGAL (Illinois Genetic Algorithm Laboratory)：遺伝アルゴリズム （C++, matlab)
• JGAP：遺伝的アルゴリズムライブラリ (java)
• KEEL (Knowledge Extraction based Evolutionary Learning)
• Paradiseo：遺伝的アルゴリズムによる最適化と，局所検索などのメタヒューリスティックによる最適化 (C++)
• RjpWiki:RでGA(遺伝的アルゴリズム)
• SHARK：遺伝的アルゴリズム, 最急勾配法, ニューラルネットなどを含む機械学習ライブラリ (C++)
• Swarm：複雑系のシミュレーションツール (研究のツールボックス記事)

関連文献 †

• Book/人工知能学事典 6章
• 人工知能学会誌 特集「遺伝的アルゴリズムの発展」vol.18, no.5