２ 遺伝アルゴリズム(GA)の基礎

• 最適化問題とGA

決定変数があり、それらが分布しうる範囲は基本空間のうちの部分空間についてなる制約条件を満たすときに、目的関数を最小にするようなを求めることを最適化と呼び、その解を最適解と呼ぶ。最適化には、GA以外にもさまざまな手法があるが、それらの手法が不適切な場合があり、そのような場合にGAによる最適化が有効である。そのような場合とは、目的関数が多峰性であったり、が離散集合であったりする場合である

• 組み合わせ最適化問題

決定変数の制約条件が組み合わせ的であるような条件のときの最適化問題で、離散集合型である点で連続分布に対する解法が不適であるとともに、組み合わせ数が膨大になるという点でNP困難な問題に属する

組み合わせ最適化問題に対する解法は大きく２つに分けられる。１つは厳密解法、もうひとつは近似解法である

厳密解法はしらみつぶし法であるが、すべてをしらみつぶしに調べるのはあまりに膨大なので、動的計画法(Dynamic programming)、分枝限定法などによるしらみつぶす範囲の限定操作を行う方法も用いられる

近似解法にはランダムに広域をスキャンしつつ解に到達使用とする方法(モンテカルロ)と取得情報を用いてより解に近い方向へと進む逐次改善法・欲張り(Greedy)法に大別できる。GAは近似解法に属し、その中でも取得情報を用いて進みながら、ランダム性を持たせる解法である

• GAの『遺伝的』側面

遺伝子は交叉と変異により変化する。組み換えは親世代にて起き、子世代は２親から２対の遺伝子を受け取り、そこで生じた遺伝子のペアが次々世代への伝達時の交叉を起こすペアとなる。次世代への遺伝子の伝達は遺伝子型によって決まる表現型が決める適応度により選択圧がかかる。適応度は保有遺伝子の組み合わせにより基底される

もっとも単純なGAのパラメタは、個体数(M)・世代数(T)・交叉確率(Pc)・変異確率(Pm)の４つである