はじめに
今回のお話はGA(遺伝的アルゴリズム)というのを先生に聞いて、実装してみたくなったから挑戦してみた話です。
見様見真似で実装したので至らない点もあるかと思いますが、見ていただけますと幸いです。
とても内容が多いため
GW中に取り組んだ#1 と
GW明けに取り組んだ#2で記事を分けます。
#1
- GAの内容と実装内容
- GW中にやってみたこと
- GW中に実装できなかったこと
#2
- 前回の内容とその解決法の話
- 完成形
という感じで記事を進めていきます。
ほんとは5月中盤くらいには投稿したかった...
内容自体は5月中盤くらいにはできてたんだけど忙しすぎて記事が書けなかった...
GitHubリンク
GAの内容と実装内容
まず遺伝的アルゴリズムの基本的な内容として
- 乱数値で生成したもの内容同士を交配していき、最適解に近いものを導き出す。
というものです。
内容が遺伝していくから「遺伝的アルゴリズム」と覚えています。
遺伝的アルゴリズムの詳しい内容についてはここでは説明しないので気になった人は調べてみてください。
遺伝的アルゴリズムの流れとして
1.初期集団の作成
親となる複数のデータをランダムに作成する
2.適応度の評価
各データがどれくらい優れているか評価する
3.選択
評価の高いデータが生き残るようにする
4.交叉
選択されたデータの特徴を持つ子供データを作成する
5.突然変異
子のデータに変化をあたえ、より良い評価のデータが作成される可能性を作る
5終了時、継続条件を満たしているなら2に戻る
といったようになっています。
今回はこれを用いて 10×10のマスに10個ランダムにアイテムを作成し、最適に近い形で取り切る ことを目指しました。
GW中にやってみたこと
まずは形から ということで
1.初期要素作成(乱数値10個 × 4つ)
2.適応度評価(アイテムを取得するたびスコア+1、取り切った際に残り歩数分の点数を加算)
3.選択(上位2つを次世代とし、インデックスを保存する)
4.交叉(乱数値2つを生成し、親要素2つから2点交叉を行う)
5.突然変異(5で割り切れるときに値をランダムに入れ替える)
と実装してみました。
どんな実装になったのかを詳しく知りたい方はこちらをご覧ください。
実際にログを出してみると、変わっていく様子を見ていくことができて楽しかったです。
ランダムで突然変異しているわけではないのですが、そこ以外はほぼその通りに実装しました。
基本的なところまでは実装できたのですが、何点か問題があり、とても完成といえるものではありませんでした。
GW中に実装できなかったこと
大きな失敗点として
- 2点交叉を採用していたが、似た個体のみが生成され良い個体がほぼ生まれない
- この突然変異の状態では、ほぼ変化が生まれず親を超えうる個体を生成しづらい
といったことが挙げられます。
この様な問題点があることまでは突き止められたのですが、それを解決する良い方法が浮かばず、GW明けに先生に相談してみることにしました。
そうして相談をしてみたところ
- もっと交叉数を増やしてみてはどうか
- 突然変異の数or発生数を増やすべきではないか
- 要素を分割し、それぞれを遺伝的アルゴリズムで実装したらいいのでは
といったことを聞くことができました。
この後は実際にそれを取り入れた結果を記述していきます。
#2→