遺伝的アルゴリズム
遺伝的アルゴリズムとは
ビット列として表現された染色体に対して、交叉、突然変異、選択などの遺伝的操作を加えることで、よりよい染色体を作り出す仕組みを与える。
遺伝座
ビット列のそれぞれのビットを保持する部分のこと
遺伝的アルゴリズムの流れ
初期化
染色体集団を初期化する
乱数などで初期化
染色体の個数は大きすぎても小さすぎてもいけない
大きすぎると、計算時間や記憶容量がたくさんいる
小さすぎると、遺伝情報を保持しきれず進化が進まない
進化
染色体集団に遺伝的操作を加える
交叉
1点交叉
2点交叉
多点交叉
一様交叉
突然変異
ランダムに遺伝情報を書き換える
突然変異を生じさせる確率値
数%程度の低い値を指定するべき
大きすぎると、獲得した形態がすぐに壊され、進化が進まない
小さすぎると、遺伝情報の探索範囲が広がらず、進化が進まない
選択
次世代に残すべき染色体を選択する
基本的には、適応度が高い染色体を選択すべき
単に適応度が高い染色体を選ぶだけでは、遺伝情報の多様性が失われて進化が停滞する
多様性を考慮して、適応度が高いものばかりでなく、低いものも選ぶべき
様々な手法
ルーレット選択
トーナメント選択
ランク選択
遺伝的アルゴリズムの特徴
確率的な探索方法なので、最適解が見つかるとは限らない
終了条件は自分で設定する必要がある
エリート保存戦略
うえで紹介した単純GAに工夫を加えたもの
適応度の最も高い染色体を無条件で次の世代に伝える
必ず最良の染色体を次の世代に伝えることができる
参考文献
基礎から学ぶ人工知能の教科書
著者 : 小高知宏
発行所 : オーム社
ページ : 145-151