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

急いては事を仕損じる。
あわてて物事を取り決めてしまうと、後からもっと良いものが出てくることがある。
かといって、いつまでも慎重に見送っていたのでは、みすみすチャンスを逃してしまうこともある。
いったいどのタイミングで決断を下せば、最大の期待値を引き当てられるのか？
この問題は、秘書問題、あるいは、最良選択問題、海辺の美女の問題などと呼ばれていて、
幾つかのケースでは数学的に最適な答が知られています。 >> wikipedia:秘書問題

たとえば、海辺に２０人の美女がいたとして、順番に出会ってゆくものとします。
これぞと思った美女をデートに誘いたいのですが、
あまり早いうちに誘ってしまうと、後からもっといい女が出現するかもしれません。
かといって誘いを出さずに見送っていると、いい女を逃してしまいます。
誘いを出すのは１回だけで、もちろん後戻りはできません。
美女は必ず誘いに乗ってくれるものとしましょう（この点が現実的ではない?!）
これが「海辺の美女の問題」です。

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

　　１〜５人目：　見るだけで誘わない。
　５〜１０人目：　それまで出会った中の１番だったら誘う。
１１〜１３人目：　それまで出会った中の２番以内だったら誘う。
１４〜１５人目：　それまで出会った中の３番以内だったら誘う。
　　　１６人目：　それまで出会った中の４番以内だったら誘う。
　　　１７人目：　それまで出会った中の５番以内だったら誘う。
　　　１８人目：　それまで出会った中の７番以内だったら誘う。
　　　１９人目：　それまで出会った中の１０番以内だったら誘う。
　　　２０人目：　それまで出会った中の２０番以内だったら誘う。

この最適解を１列２０個の数字で表すと、こんな風になるでしょう。
　( 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 3, 3, 4, 5, 7, 10, 20 )
左から順番に１人目、２人目、３人目・・・が、
それぞれ、そこに書かれている数字以内の順位だったら誘う、という意味です。

この最適解をどうやって計算したかについては、ウィキペディアなり他のサイトを見てもらうことにして、
ここではあまり頭を使わずに、コンピューターを使って力技で答を出すことを考えましょう。
最も単純なのは、乱数を使って何度も何度もシミュレーションを繰り返し、
偶然結果が良かったものを答に採用する、という方法でしょう（ランダム探索）
しかし、まったくの乱数まかせで偶然に期待するのでは、あまりにも芸が無い。
果たして答にたどり着けるかどうかも不安です。
そこで、同じ乱数を使うにしても、もう少し効率的に探索する方法を試してみることにしました。
いま調べたい答は、一列に並んだ２０個の数字の並びの中にあります。
この一列に並んだ数字の並びを、あたかも生物の遺伝子のように見立て、
生物の進化をマネして答を探るという方法があります。
「遺伝的アルゴリズム」と呼ばれる方法です。
ネットで「遺伝的アルゴリズム」を検索すると、たくさんのページがヒットします。
この辺がわかりやすい。
* 愛媛大学 村上・泉田研究室 >> http://ipr20.cs.ehime-u.ac.jp/column/ga/index.html
* 甲南大学 田中研究室 Web教材 >> http://carnation.is.konan-u.ac.jp/xoops/CJcontents/

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

１．最初に２０個の数字の並びをランダムにたくさん（６０個）作る。
２．数字の並び同士を組み合わせたり（交差）、乱数で書き換えたり（突然変異）して、
　　バラエティに富んだ数字の並びをたくさん（１２０個）作る。
３．個々の数字の並びに点数を付ける。
　　２０人の美女（実はただの数字）との出会いのシミュレーションを８回繰り返し、平均点を採る。
４．点数がトップだった数字の並びは「エリート」として、
　　１個だけコピーして、どこか適当な数字の並びの上に上書きする（エリート保存）
５．取得した平均点に比例する確率で、１２０個の数字の並びの中から６０個を選び出す（淘汰）
６．以上の処理を、２．に戻って何回も繰り返す。（１回の繰り返しで１世代）

とにかく上のようなプログラムを作って試したところ・・・
・・・なんか、ダメそうです。
５０００世代くらい繰り返し計算しても、望むような答が出てきません。

そこで、もう少しやり方を見直すことにしました。
考えたのは、数字の並び（遺伝子）の作り方についてです。
上で試したのは「Ｎ人目の美女が、Ｘ番目以内だったら」という数字の並びだったのですが、
これだと明らかに無意味な並びも含まれることになります。
例えば、( 20, 5, 3, 2 ・・・ という数字の並びは
「１人目の美女が２０番以内だったら」誘うという意味なので、最初の２０以外の数字は無意味です。
同様に、( 1, 3, 10, 2, 6 ・・・ という数字の並びがあったとき、
10 より後に 2 があったとしても意味がありません。
つまり順位の数字の並びは、後に行くほどだんだん大きくなってゆくものについてだけ探索すれば十分なのです。
この考えを取り入れて、遺伝子の作り方を次のように変えてみました。

* 遺伝子の作り方（コーディング方法）
・「Ｎ人目の美女が、Ｘ番目以内だったら」という数字の並びあったとする。
　( 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 3, 3, 4, 5, 7, 10, 20 )
・先頭から何番目で数字が変わったのか、その場所を記録する。
　たとえば上の数字の並びでは、先頭から５番目の場所で、数字が0->1に、１つだけ増えている。
　これを「５が１つ」と記録する。
・この記録方法を続けてゆくと、
　(５が１つ、１０が１つ、１３が１つ、１５が１つ、１６が１つ、１７が２つ、１８が３つ、１９が１０個)
　となる。
・こうして記録した数字を、遺伝子と見なすことにする。
　( 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 : 4.1875 : 0, 0, 0, 0, 1, 1, 3, 3, 4, 6, 8, 10, 14, 15, 16, 16, 16, 16, 19, 20,

この出力の１行は、ある１世代のエリート（最も点数の高い遺伝子）の状態です。
　(世代数) : (平均順位、小さいほど良い) : (Ｎ人目の美女が、Ｘ番目以内だったら、という数字の並び)
例えば上の１行は、
　１００回目の試行で、平均順位4.1875位、最初の４人は見るだけで、次の２人は１位以内だったら誘う、、、
という意味です。

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

* １回目のトライアル
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,

* ２回目のトライアル
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,

* ３回目のトライアル
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.80625 ですから、“正解”はそれを見事に上回っています。
乱数で力技の探索であっても、この程度までは正解に近付ける。
しかしながら、力技では真の正解に達するのは難しい。
・・・えっ、正解が分かっている問題を、わざわざ乱数で探るのに何の意味があるかって？
それは、途中の過程に意味があるというか、手段のために目的を選んだというか・・・

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

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