Hatena::ブログ(Diary)

小人さんの妄想 このページをアンテナに追加 RSSフィード Twitter

2011-07-11

海辺の美女の問題を遺伝的アルゴリズムで解く

急いては事を仕損じる。

あわてて物事を取り決めてしまうと、後からもっと良いものが出てくることがある。

かといって、いつまでも慎重に見送っていたのでは、みすみすチャンスを逃してしまうこともある。

いったいどのタイミングで決断を下せば、最大の期待値を引き当てられるのか?

この問題は、秘書問題、あるいは、最良選択問題、海辺の美女の問題などと呼ばれていて、

幾つかのケースでは数学的に最適な答が知られています。 >> wikipedia:秘書問題


たとえば、海辺に20人の美女がいたとして、順番に出会ってゆくものとします。

これぞと思った美女をデートに誘いたいのですが、

あまり早いうちに誘ってしまうと、後からもっといい女が出現するかもしれません。

かといって誘いを出さずに見送っていると、いい女を逃してしまいます。

誘いを出すのは1回だけで、もちろん後戻りはできません。

美女は必ず誘いに乗ってくれるものとしましょう(この点が現実的ではない?!)

これが「海辺の美女の問題」です。


美女が20人の場合の最適解は、次の通りです。

  1〜5人目: 見るだけで誘わない。

 5〜10人目: それまで出会った中の1番だったら誘う。

11〜13人目: それまで出会った中の2番以内だったら誘う。

14〜15人目: それまで出会った中の3番以内だったら誘う。

   16人目: それまで出会った中の4番以内だったら誘う。

   17人目: それまで出会った中の5番以内だったら誘う。

   18人目: それまで出会った中の7番以内だったら誘う。

   19人目: それまで出会った中の10番以内だったら誘う。

   20人目: それまで出会った中の20番以内だったら誘う。

この最適解を1列20個の数字で表すと、こんな風になるでしょう。

 ( 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 3, 3, 4, 5, 7, 10, 20 )

左から順番に1人目、2人目、3人目・・・が、

それぞれ、そこに書かれている数字以内の順位だったら誘う、という意味です。


この最適解をどうやって計算したかについては、ウィキペディアなり他のサイトを見てもらうことにして、

ここではあまり頭を使わずに、コンピューターを使って力技で答を出すことを考えましょう。

最も単純なのは、乱数を使って何度も何度もシミュレーションを繰り返し、

偶然結果が良かったものを答に採用する、という方法でしょう(ランダム探索)

しかし、まったくの乱数まかせで偶然に期待するのでは、あまりにも芸が無い。

果たして答にたどり着けるかどうかも不安です。

そこで、同じ乱数を使うにしても、もう少し効率的に探索する方法を試してみることにしました。

いま調べたい答は、一列に並んだ20個の数字の並びの中にあります。

この一列に並んだ数字の並びを、あたかも生物の遺伝子のように見立て、

生物の進化をマネして答を探るという方法があります。

遺伝的アルゴリズム」と呼ばれる方法です。

ネットで「遺伝的アルゴリズム」を検索すると、たくさんのページがヒットします。

この辺がわかりやすい。

* 愛媛大学 村上・泉田研究室 >> http://ipr20.cs.ehime-u.ac.jp/column/ga/index.html

* 甲南大学 田中研究室 Web教材 >> http://carnation.is.konan-u.ac.jp/xoops/CJcontents/


遺伝的アルゴリズムを応用して、こんな方法で「海辺の美女の問題」を解いてみました。

1.最初に20個の数字の並びをランダムにたくさん(60個)作る。

2.数字の並び同士を組み合わせたり(交差)、乱数で書き換えたり(突然変異)して、

  バラエティに富んだ数字の並びをたくさん(120個)作る。

3.個々の数字の並びに点数を付ける。

  20人の美女(実はただの数字)との出会いのシミュレーションを8回繰り返し、平均点を採る。

4.点数がトップだった数字の並びは「エリート」として、

  1個だけコピーして、どこか適当な数字の並びの上に上書きする(エリート保存)

5.取得した平均点に比例する確率で、120個の数字の並びの中から60個を選び出す(淘汰)

6.以上の処理を、2.に戻って何回も繰り返す。(1回の繰り返しで1世代)

とにかく上のようなプログラムを作って試したところ・・・

・・・なんか、ダメそうです。

5000世代くらい繰り返し計算しても、望むような答が出てきません。


そこで、もう少しやり方を見直すことにしました。

考えたのは、数字の並び(遺伝子)の作り方についてです。

上で試したのは「N人目の美女が、X番目以内だったら」という数字の並びだったのですが、

これだと明らかに無意味な並びも含まれることになります。

例えば、( 20, 5, 3, 2 ・・・ という数字の並びは

「1人目の美女が20番以内だったら」誘うという意味なので、最初の20以外の数字は無意味です。

同様に、( 1, 3, 10, 2, 6 ・・・ という数字の並びがあったとき、

10 より後に 2 があったとしても意味がありません。

つまり順位の数字の並びは、後に行くほどだんだん大きくなってゆくものについてだけ探索すれば十分なのです。

この考えを取り入れて、遺伝子の作り方を次のように変えてみました。

* 遺伝子の作り方(コーディング方法)

・「N人目の美女が、X番目以内だったら」という数字の並びあったとする。

 ( 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 3, 3, 4, 5, 7, 10, 20 )

・先頭から何番目で数字が変わったのか、その場所を記録する。

 たとえば上の数字の並びでは、先頭から5番目の場所で、数字が0->1に、1つだけ増えている。

 これを「5が1つ」と記録する。

・この記録方法を続けてゆくと、

 (5が1つ、10が1つ、13が1つ、15が1つ、16が1つ、17が2つ、18が3つ、19が10個)

 となる。

・こうして記録した数字を、遺伝子と見なすことにする。

 ( 5, 10, 13, 15, 16, 17, 17, 18, 18, 18, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19 )

・この遺伝子は、数字の並び順を変えても同じ意味を持つことになる。たとえば、

 ( 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 5, 10, 13, 15, 16, 17, 17, 18, 18, 18 )

 であっても、意味は同じになる。

このような遺伝子の作り方であれば、遺伝子同士を適当に組み合わせたり、

数字をランダムに書き換えたりしても、それなりに意味が通るわけです(致死遺伝子にはならない)


以上の方法で、実際に海辺の美女の問題をコンピュータに解かせてみました。

* 海辺の美女の問題を遺伝的アルゴリズムで解く(要 Silverlight 4)

>> http://brownian.motion.ne.jp/memo/GA_SeaShore/

* ソース主要部分(C#

>> http://brownian.motion.ne.jp/memo/GA_SeaShore/GA_SeaShore.cs

>> http://brownian.motion.ne.jp/memo/GA_SeaShore/Gene.cs

* ソース一式(Visual WebDeveloper 2010 Express のプロジェクト・ディレクトリ丸ごと, 約1.6M)

>> http://brownian.motion.ne.jp/memo/GA_SeaShore/SilverlightApplication14.zip

リンク先 Silverlightの[実行]ボタンを押すと、次のようなテキストが100行ずつ表示されます。

100 : 4.1875 : 0, 0, 0, 0, 1, 1, 3, 3, 4, 6, 8, 10, 14, 15, 16, 16, 16, 16, 19, 20,

この出力の1行は、ある1世代のエリート(最も点数の高い遺伝子)の状態です。

 (世代数) : (平均順位、小さいほど良い) : (N人目の美女が、X番目以内だったら、という数字の並び)

例えば上の1行は、

 100回目の試行で、平均順位4.1875位、最初の4人は見るだけで、次の2人は1位以内だったら誘う、、、

という意味です。


このプログラムをひたすら動かしてみたところ、こんな結果になりました。

* 1回目のトライアル

1 : 6.1 : 0, 0, 1, 2, 2, 2, 4, 4, 5, 6, 7, 10, 10, 13, 14, 14, 16, 16, 18, 20,

30 : 4.1 : 0, 0, 0, 1, 1, 2, 4, 4, 4, 5, 5, 7, 7, 11, 12, 13, 14, 14, 18, 20,

293 : 3.86875 : 0, 0, 0, 0, 1, 1, 1, 2, 3, 3, 4, 7, 7, 10, 11, 13, 14, 15, 17, 20,

294 : 3.39375 : 0, 0, 0, 0, 1, 1, 1, 2, 3, 3, 4, 7, 7, 10, 11, 13, 14, 15, 17, 20,

922 : 3.3875 : 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 3, 6, 6, 12, 13, 14, 14, 17, 20, 20,

1102 : 3.3625 : 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 3, 6, 6, 11, 12, 14, 14, 17, 19, 20,

1178 : 3.34375 : 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 3, 6, 6, 11, 12, 14, 14, 17, 19, 20,

1191 : 3.13125 : 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 3, 5, 5, 7, 8, 10, 11, 14, 18, 20,

1488 : 2.86875 : 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 3, 5, 5, 7, 8, 10, 11, 14, 18, 20,

・・・10000世代まで実施してみた・・・

10000 : 2.86875 : 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 3, 5, 5, 7, 8, 10, 11, 14, 18, 20,

* 2回目のトライアル

1 : 5.50625 : 0, 0, 1, 1, 1, 4, 4, 5, 7, 8, 9, 10, 10, 11, 12, 13, 14, 16, 17, 20,

17 : 5.20625 : 0, 1, 1, 1, 3, 3, 3, 7, 8, 9, 9, 10, 10, 12, 12, 12, 13, 16, 17, 20,

190 : 5.19375 : 0, 0, 1, 1, 2, 2, 3, 4, 5, 5, 6, 8, 9, 12, 13, 15, 15, 17, 19, 20,

200 : 5.0125 : 0, 0, 1, 1, 2, 3, 3, 5, 5, 6, 6, 6, 7, 8, 8, 13, 14, 15, 18, 20,

209 : 4.98125 : 0, 0, 0, 0, 2, 3, 3, 3, 4, 4, 5, 6, 6, 7, 7, 11, 13, 15, 18, 20,

216 : 4.75 : 0, 0, 1, 1, 2, 2, 2, 4, 5, 5, 6, 8, 8, 8, 8, 11, 12, 14, 18, 20,

295 : 4.68125 : 0, 0, 1, 1, 2, 2, 2, 4, 5, 5, 6, 8, 8, 8, 8, 11, 12, 14, 18, 20,

361 : 4.6375 : 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 5, 6, 8, 10, 11, 12, 15, 16, 19, 20,

365 : 4.3 : 0, 0, 1, 1, 1, 2, 2, 2, 3, 3, 5, 6, 8, 10, 11, 12, 15, 16, 19, 20,

366 : 4.15 : 0, 0, 1, 1, 1, 1, 2, 3, 5, 5, 5, 6, 6, 7, 8, 9, 11, 12, 17, 20,

369 : 4.03125 : 0, 0, 1, 1, 1, 1, 2, 3, 5, 5, 5, 6, 6, 7, 8, 9, 11, 12, 17, 20,

551 : 3.5875 : 0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 4, 4, 5, 7, 8, 10, 11, 17, 20,

553 : 3.25625 : 0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 4, 4, 5, 7, 8, 10, 11, 17, 20,

563 : 2.91875 : 0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 3, 4, 4, 5, 7, 7, 9, 11, 17, 20,

2038 : 2.83125 : 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 3, 7, 7, 8, 10, 19, 20,

4638 : 2.80625 : 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 2, 3, 3, 4, 6, 6, 7, 9, 19, 20,

・・・6000世代まで実施してみた・・・

6000 : 2.80625 : 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 2, 3, 3, 4, 6, 6, 7, 9, 19, 20,

* 3回目のトライアル

1 : 5.48125 : 0, 0, 0, 0, 0, 1, 1, 3, 6, 6, 8, 8, 8, 9, 9, 10, 10, 11, 14, 20,

14 : 5.275 : 0, 0, 0, 1, 1, 2, 2, 4, 8, 8, 10, 11, 12, 12, 12, 13, 13, 13, 16, 20,

42 : 5.1 : 0, 0, 0, 1, 1, 2, 2, 4, 10, 10, 11, 11, 11, 11, 11, 12, 12, 12, 16, 20,

44 : 4.50625 : 0, 0, 0, 1, 1, 2, 2, 4, 6, 6, 6, 6, 8, 9, 9, 11, 12, 13, 17, 20,

49 : 4.4375 : 0, 0, 1, 1, 1, 3, 3, 3, 8, 9, 9, 9, 10, 12, 12, 12, 13, 15, 17, 20,

485 : 4.38125 : 0, 0, 0, 0, 1, 2, 2, 2, 3, 6, 7, 8, 11, 12, 14, 14, 15, 17, 19, 20,

486 : 4.00625 : 0, 0, 0, 0, 1, 2, 2, 2, 3, 6, 7, 8, 11, 12, 14, 14, 15, 17, 19, 20,

633 : 3.9125 : 0, 0, 0, 0, 1, 1, 1, 3, 3, 6, 7, 8, 10, 12, 15, 15, 15, 18, 19, 20,

756 : 3.86875 : 0, 0, 0, 0, 1, 1, 2, 3, 3, 6, 8, 8, 10, 12, 15, 15, 15, 18, 19, 20,

825 : 3.83125 : 0, 0, 0, 1, 1, 1, 2, 2, 3, 5, 7, 8, 11, 12, 15, 16, 16, 17, 19, 20,

935 : 3.76875 : 0, 0, 0, 1, 1, 1, 2, 2, 2, 4, 7, 8, 11, 12, 15, 16, 16, 17, 19, 20,

1092 : 3.64375 : 0, 0, 0, 1, 1, 1, 1, 1, 1, 4, 6, 7, 10, 11, 14, 15, 15, 17, 19, 20,

1685 : 3.45625 : 0, 0, 0, 0, 0, 0, 1, 1, 1, 2, 4, 4, 5, 8, 11, 12, 13, 16, 18, 20,

1696 : 3.4125 : 0, 0, 0, 0, 0, 0, 1, 1, 1, 2, 4, 4, 5, 8, 11, 12, 13, 16, 18, 20,

1802 : 3.35625 : 0, 0, 0, 0, 0, 0, 1, 1, 1, 2, 4, 4, 5, 7, 10, 11, 13, 16, 18, 20,

1848 : 3.31875 : 0, 0, 0, 0, 0, 0, 1, 1, 1, 2, 4, 4, 5, 7, 10, 11, 13, 15, 17, 20,

2563 : 3.2625 : 0, 0, 0, 1, 1, 1, 1, 1, 1, 2, 4, 4, 6, 8, 10, 11, 13, 14, 17, 20,

2958 : 3.1125 : 0, 0, 0, 1, 1, 1, 1, 1, 1, 2, 3, 3, 6, 7, 9, 10, 13, 15, 18, 20,

5165 : 3.10625 : 0, 0, 0, 0, 0, 0, 1, 1, 1, 2, 3, 3, 6, 6, 8, 10, 13, 15, 18, 20,

5454 : 3.06875 : 0, 0, 0, 0, 0, 0, 1, 1, 1, 2, 3, 3, 6, 6, 8, 10, 13, 15, 18, 20,

5992 : 3.04375 : 0, 0, 0, 0, 0, 0, 1, 1, 1, 2, 3, 3, 8, 8, 10, 11, 13, 15, 18, 20,

・・・10000世代まで実施してみた・・・

10000 : 3.04375 : 0, 0, 0, 0, 0, 0, 1, 1, 1, 2, 3, 3, 8, 8, 10, 11, 13, 15, 18, 20,

だんだん答に近づいて「進化」してゆく様子が見てとれると思います。

この結果を、最初に掲げた“正解”と比較してみてください。

まあまあ、いい線いっていると思いませんか?

ちなみに、このプログラムに最初から“正解”を入れてみたらどうなるかというと・・・

1 : 2.61875 : 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 3, 3, 4, 5, 7, 10, 20,

こうなった。

今回試した中で最も良かったのが、2回目のトライアル 2.80625 ですから、“正解”はそれを見事に上回っています。

乱数で力技の探索であっても、この程度までは正解に近付ける。

しかしながら、力技では真の正解に達するのは難しい。

・・・えっ、正解が分かっている問題を、わざわざ乱数で探るのに何の意味があるかって?

それは、途中の過程に意味があるというか、手段のために目的を選んだというか・・・


※ 今回作成したプログラムは、この本に載っていたC言語のソースコードを元にしています。

人工知能システムの構成―基礎からエージェントまで

人工知能システムの構成―基礎からエージェントまで

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証

トラックバック - http://d.hatena.ne.jp/rikunora/20110711/p1