□遺伝的アルゴリズムとは?
複数の組み合わせのうち,最も適したものを求めたい場合,通常は全ての組み合わせを調べ,その上で最適なものを選ぶといったことを行います．しかし,世の中には組み合わせの数が莫大なものもあり,それら問題では全組み合わせの調査は実際には不可能となります．このような場合,調査する組み合わせを絞り込まなければなりません．その絞り込みにダーウィンの自然淘汰説を適用したものが遺伝的アルゴリズム（GA）です．
□ダーウィンの自然淘汰説とは?
キリンを例にとってみましょう．キリン同士を比べると,当然,大まかに首が長いキリングループと,首が短いキリングループに分けることができます．そしてある時,キリンの世界で食糧不足が起こったとします．一番最初に消費する食料は,どのキリンも届くような場所に生えている草です．そして残るのが,高いところに生えている草で,この草は首の短いキリングループメンバーは届くことができず,食べることができません．これにより首の短いキリンメンバーに含まれるキリンは,首の長いキリングループのメンバーより死亡率が高いことが予想されます．そして生き残る確率が高いのは背の高いキリングループメンバーということになります．生き残る確率が高いので,キリン種全体として,首の長いキリンが多くを占めるようになります．そしてそれらが交配し,子供を産みます．子供は両親から形質を受け継ぐので,子供も首が長いものが生まれる率が高くなります．よって,さらにキリン種として全体的に首が長くなることになります．
GAではこのような性質を利用し,解に近いと思われる候補解を選択し（生き残り）,それらの中の2つ（両親）から,解に近いという形質を受け継いだ新たな候補解（子）を合成する,といったことを繰り返すことで,なるべく正解に近い組み合わせのものを求めます．
□GAの流れ
GAの流れは次のようになります．
1．遺伝子生成
最初はランダムに遺伝子文字列生成
2．遺伝子評価
遺伝子型→表現型→適合度
3．遺伝子淘汰
適合度の低い遺伝子は削除
4．優良両親から子供の遺伝子生成
適合度の高い2つの遺伝子（両親）から子供の遺伝子生成
5．子供の遺伝子追加
2に戻る
□GAは何に応用されているか
GAは基本的に組み合わせ最適化問題に用いられます．しかし巡回セールスマン問題，ナップサック問題などの学術的なものだけではなく，カーナビゲーションシステム，TVゲームなどにも用いられるようになりました．またCGアート，似顔絵，楽曲生成など，クリエイティブな用途にも用いられるようになっています．その中でも面白いものとして仮想日本庭園設計（筑波大）が例に挙げられます．
|
