タグ: 最適化

昨日の問題を遺伝的アルゴリズムっぽく

昨日の問題[1][2][3]を、遺伝的アルゴリズムのようなもので解いてみた。解くのに使ったPerlコードは最後に添付。

一応、前々回のエントリで提示したサンプルデータに対しては、10個の実験枠と40人の参加希望者を全て使い切る最適解を一つ見つけることができた。パラメータ変えながら50回くらい繰り返した末にだが。

とはいえ、実験枠数と参加希望者数の関係が変わったりするとまだうまく最適解を推測できないようなので、もう少しチューニングしたほうがよさそう。

続きを読む

スポンサーサイト



前回と前々回のエントリーの問題を総当りで

前々回と前回のエントリで書いた問題を、Perlで総当りで解こうとしてみた。使ったコードは最後に添付。

実行開始から7時間半経過したけど未だに終わる気配がない。馬鹿正直に40人の参加希望者と10個の実験枠を組み合わせたら組み合わせは10^40通り。今回のコードでは、参加可能枠の配列を使って解空間を狭めたけれど、それでもやはり9 * 8 * 9 * 6 * 6 * 5 * 4 * 6 * 7 * 9 * 6 * 8 * 9 * 6 * 7 * 5 * 9 * 4 * 4 * 5 * 3 * 8 * 6 * 8 * 6 * 8 * 7 * 3 * 7 * 9 * 5 * 9 * 5 * 6 * 8 * 7 * 8 * 8 * 7 * 5 = 1.4271125147448316e+32通りの解がある。もっと解空間を狭めるアルゴリズムを考えるか、確率的なアルゴリズムを考えるしかないようだ。

ちなみに、7時間半走らせたところ、最適解は最大実験枠が4個で最大参加者数が12人になっている。明らかにまだまだ。

続きを読む

前回のエントリの問題を詳述

前回のエントリで、僕では解けない問題を書いてみたんだが、書き方が曖昧であまり伝っていないみたいなので、少し正確に書いてみることにした。ついでにサンプルデータも用意したから、サンプルデータでイメージしてもらえると助かる。

続きを読む

この問題はどう解けばいいんだ？

最近作ってるシステムで、どうしてもどう解いていいのかがわからなくて行き詰っていた問題があったのでpostしてみる。

作っているのは心理学実験の参加者募集システムで、問題は参加希望者を最適に実験枠に割り振るためのアルゴリズム。

問題の状況を簡単にまとめると図1のような感じ。

続きを読む