このエントリーは tech.kayac.com Advent Calendar 2015 の22日目のエントリーです。
こんにちは。技術部のバックエンドを担当しているあっつーです。
今回はあの大女優から学んだアルゴリズムについて書いていきます。
はじめに
人工知能といえばこの分野を大きく進歩させた深層学習が注目を集め、 Alpaca,Google,Facebookはすでにこの技術をサービスに利用し始めています。
一方、ネガティブなイメージとして２０４５年問題や職業の消滅など 人とテクノロジーの付き合い方を含めて今後も目が離せません
さて、今回は人工知能分野でも少し毛色の違う遺伝的アルゴリズムについて紹介していきます。
なぜ遺伝的アルゴリズム(GA)なのか?
- あの大女優の菊川怜の卒論テーマがGA
- シンプルなアルゴリズムで応用し易い
実は菊川怜さん以外にも使用例はあるすごいやつです
1998年に発売されたプレイステ ーション用のゲ ーム 、『アストロノーカ』のモンスタ ーの進化には 、
人工知能の一つである 「遺伝的アルゴリズム 」が使われていて 、
プレイヤ ーとのバトルを通して 、自分の力で進化していくようになっていました 。
引用:マッチ箱の脳
解説
ここでは遺伝的アルゴリズムというものをざっくりと簡単に紹介します。
遺伝的アルゴリズムはダーウィンの進化論に基いて作られたアルゴリズムです。
遺伝的アルゴリズムはデータ（解の候補）を遺伝子で表現した「個体」を複数用意し、適応度の高い個体を優先的に選択して交叉（組み換え）・突然変異などの操作を繰り返しながら解を探索する。適応度は適応度関数によって与えられる。
この手法の利点は、評価関数の可微分性や単峰性などの知識がない場合であっても適用可能なことである。 必要とされる条件は評価関数の全順序性と、探索空間が位相（トポロジー）を持っていることである。
また、遺伝子の表現の仕方によっては組合せ最適化問題やNP困難な問題などのさまざまな問題に適用可能である。 引用:wiki
とのことです。
分かりやすく、菊川怜さんを例に見ていきましょう
ここで菊川怜さんのデビュー時を第１世代として、取り巻く環境が変わり、
どう適応していったのか経歴の流れに沿ってみていきます
第1世代：
1997年、大学2年生の時に東京・新宿でスカウトされる。 1998年（平成10年）にモデルデビュー。グラビアモデル、女性ファッション誌 『Ray』の専属モデルとして活躍。 1999年、フジテレビ系ドラマ 『危険な関係』にて女優デビュー。 引用: wiki
ここが世代のスタートとします。
第2世代:
2006年 「クイズバラエティー」に出演、インテリキャラとして活躍
ここで第2世代に交代です。 世間のお笑いブームによりバラエティ番組が増え、需要と供給のバランスが崩れます。 そこでインテリタレントとしての、ポジションへ変化していきます
第3世代:
2012年7月、初の帯番組レギュラーとなる『情報プレゼンター とくダネ!』の女性司会者に就任。
ここで3世代目に交代です。 「優木まおみ」「麻木久仁子」等の登場で女性のインテリタレントの競争率が激しくなり、 このままでは淘汰されてしまいます。 そこで、独身女性のいじられキャラという新しいポジションへ移ることで芸能界に適応していきます
こういったように競争率の激しい芸能界では、 あの菊川怜さんでもわずかデビューしてから15年間の間に第3世代まで進化していることがわかります
応用例
では、遺伝的アルゴリズムをつかって「KikukawaRei」を生成してみましょう
KikuwaRei Generator
https://github.com/kawasakiatsushi/KikukawaReiGenerator
下記にアルゴリズムのポイントを解説していきます。
(a) 適応度の評価
アルファベットをHash化し、KikukawaReiという文字列と遺伝的アルゴリズムで得られた文字列の差分を絶対値で取得し評価
(b) 選択
スコアの高い遺伝子を上から２つ選択し子を作成
(c) 交叉
つくられた遺伝子の交叉を行う
(d) 突然変異
一定の確率で突然変異を起こし、遺伝子を操作
この流れを繰り返し、評価の結果、差分が0になるまで続けます
実行
それではコードを実行してみましょう
ruby kikukawa_rei_generator.rb
実行時に一世代ごとの遺伝子の数と突然変異の起こる確率を設定
遺伝子の数: 20 突然変異率: 15
ここから遺伝子の交叉がスタートし世代ごとの結果が出力されます
第1世代はまだ、バラバラな文字列のみが並んでいます
generation : 1 RmkumeaOKfk score : 67 MveUoZyoRqb score : 99 JkzwXBvUfHj score : 133 aelYgfTcimh score : 133 DiPkVMReObf score : 135 juwZvlghcYX score : 173 ZkrMZGtSwWe score : 179 MeEQyJmlkax score : 182
進化を続け、82世代目になると少しKikukawaReiに少し近づいてきました
generation : 82 OikulawjRej score : 15 OikulawjRek score : 16 OikulawjRek score : 16 OikulawjRek score : 16 OikulawjRek score : 16 OikulawjRek score : 16 OikulawjRek score : 16 OikulawjRek score : 16 OikulawjRek score : 16 OikulawjRek score : 16 OikulawjRek score : 16 OikulawjRek score : 16 OikulawjRek score : 16 OikulawjRek score : 16 OikulawjRek score : 16 OikulawjRek score : 16
115世代目になるとKikukawaReiまであともうあと一息
generation : 115 KikukawhRek score : 9 KikukawiRek score : 10 KikukawiRek score : 10 KikukawiRek score : 10 KikukawiRek score : 10 KikukawiRek score : 10 KikukawiRek score : 10 KikukawiRek score : 10 KikukawiRek score : 10 KikukawiRek score : 10 KikukawiRek score : 10 KikukawiRek score : 10 KikukawiRek score : 10
179世代目でついにKikukawaReiにたどり着くことができました
generation : 179 KikukawaRei score : 0 KikukawaRej score : 1 KikukawaRej score : 1 KikukawaRej score : 1 KikukawaRej score : 1 KikukawaRej score : 1 KikukawaRej score : 1 KikukawaRej score : 1 KikukawaRej score : 1 KikukawaRej score : 1 ******************************* "Answer: KikukawaRei"
まとめ
いかがだったでしょうか？
(a) 適応度の評価
(b) 選択
(c) 交叉
(d) 突然変異
という流れで評価方法やパラメータを変えることで色んなことへ応用ができます
- 例
マリオをある意味スーパープレイな遺伝的アルゴリズムとニューラルネットワーク学習のみで全自動クリアしてしまう「MarI/O」
簡単ではありましたが、菊川怜さんを通じてアルゴリズムを学ぶことができました
自分で作ったプログラムが育っていく体験は楽しいですね！
参考
芸能人の卒業論文タイトルまとめ
http://matome.naver.jp/odai/2128996142357642601
最後に
明日の担当はyuma_nishizakiさんです
お楽しみに！
