全くの初心者が遺伝的アルゴリズムについて考えてみた
色々あって勉強する機会があったので忘備録代わりに
そもそも遺伝的アルゴリズムとは
解の候補となる個体を複数用意し、それらを組み合わせ、適合度が高いものを残しながら解を探索するアルゴリズム
今回は巡回セールスマン問題（TSP)を解くことが目的であったため、交叉方法に部分一致交叉、変異には2点の位置をランダムで交換した。
親世代の中で巡回路長が短いもの上位10%をエリートとし、変異や交叉を行わずに次世代へ受け継がせた。
部分一致交叉
- 親となる巡回路を2つランダムに選択する
- ランダムで交叉開始箇所と終了箇所を選択する
- 交叉範囲内にて親の同位置の遺伝子をペアとする
- 同一個体内のペアとなってる遺伝子の位置を交換する
巡回路の評価方法は単純に巡回路長を用いた。
選択・淘汰はトーナメント選択を適用。
ランダムに集団から4個体選出し、最も巡回路長が短い物を選択する。
これを個体数分繰り返し、子世代の比率はエリート10%、交叉、淘汰を行ったもの90%としてみた。
値の決め方は基本適当。
結果
案の定うまく行きませんでした。知ってた。
交叉する範囲が広い場合、部分一致交叉を用い、点の排他性を保とうと試みると親の遺伝子情報が大きく破壊され、ランダム探索に近いものとなってしまう。
サブツアー交叉を用いることができればなんとかなったのかもしれないけど実装力がない。つらい。
アルゴリズム自体は比較的単純なのに実装力がなさすぎてしんだ。
現状だと精度は最近傍法で初期順回路を生成して、2-opt、or-opt改善を用いた方が速度的にもはやい。
勿論、遺伝的アルゴリズム自体がダメってわけでなくて、純粋にわたしのコーディング力が無い現実に直面させられた。
つらい。
