遺伝的アルゴリズムでディズニーシーの効率的な回り方を調べる①説明編

Home / Python / 遺伝的アルゴリズムでディズニーシーの効率的な回り方を調べる①説明編

先日、ディズニーシーに行ってきました。

ディズニーキャラクターとのグリーティングの待ち時間が長いのが目につきましたが、Instagramの影響なんですかね?

とはいえ、個人的には、やっぱりディズニーに行くならたくさんアトラクションに乗りたい!

ということで、”ディズニーシーの効率の良い回り方”を調べてみたいと思います。

プログラミングがわからない人でも、ある程度まではなんとなく理解できるように書く予定です。

技術的な部分にのみ興味のある方は実践編へどうぞ。

遺伝的アルゴリズムでディズニーシーの効率的な回り方を調べる②実践編

ー なぜ遺伝的アルゴリズムなのか?

今回は、最適ルートを計算するのに ”遺伝的アルゴリズム” という手法を選びました。その理由は、

ただただ面白そうだったから

これだけです。

 

遺伝的アルゴリズムとは、簡単に言うと、

1.問題の答えの候補をたくさん作り

2.より優秀な答え同士に子孫を作らせ

3.その子孫の中で、さらに優秀な答え同士に子孫を作らせ

4.稀に突然変異を起こしながら

5.より優秀な答えを選択していく

という、まさに現実世界の生物の進化を模倣したような計算手法のことです。

最近流行りの機械学習は複雑すぎて理解が難しいですが、遺伝的アルゴリズムは生物の進化を模倣しているという点で非常に直感的で、誰にでもなんとなく仕組みを想像することができると思います。

 

こんな動画がありました。

今回の ”ディズニーシーの効率的な回り方を調べる” という問題の場合、例えば

[ 3 7 4 6 2 1 8 9 2 11 3 3 15 2 5]

というような数字の羅列が答えの候補になります。

そしてこれを、便宜的に生物の”遺伝子”と捉えます。この遺伝子は左から順に読み取られ、

“1” であればトイストーリーマニアに乗る。

“2” であればトイストーリーマニアのファストパスを取る。

“3” であればタワーオブテラーに乗る。

というふうに解釈されます。そしてその順番通りに行動し、効率良く回れば回るほど、高く評価されます。

これらが交配(正確には交叉と呼ばれる)や突然変異を繰り返して、より効率よくディズニーシーを回れる遺伝子のみが選ばれて行くのです。

なんだかコンピュータ上で新たな生物が進化していくようですね。

 

少し話は逸れますが、僕が遺伝的アルゴリズムという言葉に出会ったのは、

『ガイドツアー 複雑系の世界: サンタフェ研究所講義ノートから』

という本を読んだときでした。

2009年には科学書部門においてAmazonでベスト10に入り、2010年には英国王立協会推薦科学図書に選ばれ、既に良書であることは証明されているのですが、

この本、面白いです。

最初から最後まで、ひたすら知的好奇心を刺激されます。

現実世界には、人々のあらゆる行動や自然現象など、まったく秩序のないように見える現象が多々ありますが、それらは皆 ”複雑系” です。

ダーウィンの進化論や遺伝的アルゴリズムが例に挙げられ、 ”複雑系” と呼ばれる現実世界の様々な現象を、コンピュータのプログラムという人間の理解できる形に落とし込むような、コンピュータの世界を現実世界に置き換えて理解するような、そんな内容でした。

一見秩序の無いように見える ”複雑系” ですが、この本を読んでいると、そんな ”複雑系” にも秩序があって、自分にも理解することができる、と思えてきてしまうのです。

『ガイドツアー』というタイトルの通り、知識のない一般人をいつの間にか科学の世界に誘ってしまう、素晴らしい1冊。

最近流行りのディープラーニングなどにも通じる話ですので、興味があれば皆さんも是非読んでみてください。

ー アルゴリズムを実装してみる

アルゴリズムの実装にあたって、以下のサイトを参考にしました。

【初心者向け】Re:ゼロから始める遺伝的アルゴリズム【人工知能】

遺伝的アルゴリズム(Genetic Algorithm)を始めよう!

すごくわかりやすいので、これらを読めばプログラミングができる人はすぐに実践できます。

少し長くなりそうなので今回はここまでにします。

遺伝的アルゴリズムでディズニーシーの効率的な回り方を調べる②実践編

Comments(0)

Leave a Comment

CAPTCHA