ビンゴ行列の行列式の最大値
この記事は、以下の記事に対する第三者によるさらに深い考察です。
私は、ビンゴ行列の行列式の最大値を、遺伝的アルゴリズムで求めてみました。
条件は以下のようにしました。
・世代数: 100
・個体数: 500
・次世代の選択方法: 上位20個体(*)はキープ、残り180個体は全世代からキープされた20個体から変異させて作る
・変異方法: 各成分に対し、20%の確率で別の値に置き換える(このとき、置き換える前と同じ値に置き換わることはないようにした)
・初期個体: ランダム
(*): なぜか上位が同じ個体で固まるため、10世代ごとにキープする個体数を1ずつ増やした。それに伴い、変異により作られる個体の数は減少する。
また、プログラミング言語にはRubyを使用しました。何回かプログラムを実行した結果、次のような行列が得られました(私のPCでは1回の実行当たり10秒程度かかりました)。
Matrix[[14, 28, 43, 59, 0], [0, 29, 42, 58, 75], [15, 30, 0, 54, 72], [12, 27, 45, 0, 73], [13, 0, 44, 60, 74]](行列式は28645603)
Matrix[[13, 0, 41, 58, 75], [14, 30, 44, 0, 72], [12, 28, 0, 60, 74], [0, 29, 45, 59, 73], [15, 27, 43, 57, 0]](行列式は287684196)
Matrix[[0, 29, 43, 59, 72], [13, 27, 42, 0, 73], [12, 28, 0, 60, 74], [15, 30, 45, 57, 0], [14, 0, 44, 58, 75]](行列式は287780688)
Matrix[[14, 28, 43, 60, 0], [12, 0, 42, 59, 73], [15, 30, 0, 58, 74], [0, 29, 45, 57, 72], [13, 27, 44, 0, 75]](行列式は287905806)
Matrix[[15, 0, 43, 58, 75], [13, 29, 45, 0, 74], [12, 30, 0, 59, 73], [0, 28, 44, 60, 72], [14, 27, 42, 57, 0]](行列式は289713264)
結果をよく見ると、各列の数字が「0と各列で可能な数が大きい方から4個」の並べ替え(1列目は0,12,13,14,15, 2列目は0,27,28,29,30, etc.)となっていることが多いことに気が付きます。そこで、このような行列を全探索することにしました。
しかし、このままでは120^5=24,883,200,000通りあって、全探索するには多すぎます。せめて1億通り以下には減らしたいものです。
そこで、改めて行列をよく見ると、0は各行、各列に2度現れないように位置していることがわかります。この場合、0の位置を最初に決めてから残りの数字の位置を決めることで、探索する行列は24*24^5=191,102,976個(∵3列目の0は必ず3行目)にまで減らせます。まだ少し多い気がしますが、これで全探索してしまいましょう。
...といってもこれが結構長いので、最初の20分ほど探索して得られた結果を示します。
Matrix[[0, 30, 42, 60, 72], [12, 0, 45, 57, 75], [15, 27, 0, 59, 73], [13, 29, 43, 0, 74], [14, 28, 44, 58, 0]](行列式は291970008)
