概要
機械学習の一つに遺伝的アルゴリズムというものがある。原理は単純で「良いものと良いものを組み合わせれば、さらに良いものが生まれるはず」というものだ。今回は簡単な問題を例にあげて実際に最適解を得る事を確認する。
コードはgitHubにおいておく。今回使用したコードを活用して別の記事を書く予定のため、より使いやすいように改良をしていくつもりだ。
遺伝的アルゴリズムの簡単な説明
この章で遺伝的アルゴリズムの簡単な説明を行う。
遺伝情報の表現方法
遺伝的アルゴリズムはそれぞれの個体が遺伝子として0と1で構成された配列を持つ。
遺伝子の長ながさは個体ごとに変わることはない。
子孫を残す
個体は他の個体と子孫を残す
親はそれぞれの遺伝子を組み合わせたものを子孫として生成する。
基本的に獲得形質は遺伝させないが本によってはそのようなアプローチを紹介するものもある。
また子孫を残す際、一定の確立で遺伝子の一部を反転させる。これを突然変異という。
優れたものが子孫を残す。
より良い個体を生成するために良い個体が子孫をより多く残す必要がある。
そのため個体ごとに評価するひつようがある。
遺伝的アルゴリズムのフロー
今回示したフローは遺伝的アルゴリズムを実装する上で最低限必要な処理を示したものである。
問題設定
今回は遺伝的アルゴリズムの問題でよく例にあげられる、遺伝情報内の1の数をできるだけ多くする問題を解く。
これは単純に遺伝情報が1のみで構成されたものが最も良い個体、0のみで構成された個体を最も悪い個体である。
評価値
遺伝情報内の1の数を評価値とする。
問題を解く
本来はパラメータの設定や子孫を残す際の両親の選択方法など、多くのことを決定、説明するべきである。しかし今回は次の記事への布石としての面が大きいため省く。
今回は0世代目と15世代目の結果を見る。
左の少数が個体の評価値、右の0と1の羅列はその個体の遺伝情報である。
0世代目
-----------------ソート済み--------------------
評価値: 遺伝情報
3.0 : 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0
3.0 : 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0
2.0 : 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0
2.0 : 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0
2.0 : 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0
1.0 : 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0
1.0 : 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0
1.0 : 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0
1.0 : 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0
1.0 : 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
1.0 : 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0
1.0 : 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0
0.0 : 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0.0 : 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0.0 : 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0.0 : 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0.0 : 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0.0 : 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0.0 : 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0.0 : 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
15世代目
-----------------ソート済み--------------------
評価値: 遺伝情報
14.0 : 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1
14.0 : 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1
14.0 : 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1
14.0 : 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1
14.0 : 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1
14.0 : 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1
14.0 : 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1
13.0 : 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1
13.0 : 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0
13.0 : 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1
13.0 : 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1
13.0 : 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0
13.0 : 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0
13.0 : 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0
13.0 : 1 0 1 1 1 1 1 1 1 1 1 1 1 1 0
13.0 : 1 0 1 1 1 0 1 1 1 1 1 1 1 1 1
12.0 : 1 0 1 1 1 1 1 1 1 1 1 1 1 0 0
12.0 : 1 0 1 1 1 1 0 1 1 1 1 1 1 1 0
11.0 : 1 0 1 1 0 1 0 1 1 1 1 1 1 0 1
10.0 : 1 0 1 1 0 1 1 1 1 1 0 0 1 1 0
評価値の平均 :
0.95, 1.5, 2.25, 3.0, 4.65, 6.25, 7.75, 8.15, 9.45, 10.35, 11.0, 11.45, 11.75, 12.3, 12.6,
最大値 :
3.0, 3.0, 4.0, 5.0, 7.0, 9.0, 9.0, 11.0, 12.0, 12.0, 13.0, 13.0, 13.0, 13.0, 14.0,
15世代目でも最適解を見つける事は出来なかったが0世代目と比べるとだいぶ良い結果が得られた事が分かる。
これをより現実の問題(時間割など新幹線の設計など)にあてはめることで現実世界でも活用できる結果をえる事ができる。