🎅
Santa2024上位解法MEMO
※随時更新していきます
コンペの概要
Santa 2024 - The Perplexity Permutation Puzzle
1st place solution
-
Iterated Local Search(ILS|反復局所探索法)ベース(以下を繰り返す)
- 現在の解 (単語列) を局所的に探索して貪欲に改善を図る
- 改善できなくなったら kick (perturbation) によって局所解から抜け出す
- kickでの操作:2単語のswap、連続した区間の抜き出し&挿入など行う
- 近傍探索での操作:少数の単語抜き出し&挿入
- 高速化:軽量なNNで有望な近傍を絞りこんで、その後正確なスコアを計算 (NNは強化学習のようにオンラインで最適化)
2nd Place Solution
- Iterated Local Search(ILS)をベースに、制約付きk-optとカスタムキック(Kick) を組み合わせた手法
-
制約付き K-opt
- 局所探索アルゴリズムの一種
- 並びを反転する操作をは以上
- 移動する単語の数を制限
-
Custom Kick
- 特定の隣接単語のグループをランダムに選び、並びをシャッフル
- id5では、ブロック間で単語を移動、交換するCustom Kickを実装
4th Place Solution
- ビームサーチ
- 先頭行におくと、valid_length が上がる単語があった
- id3の場合はmagiを先頭に置いた
- id3はstopword + Contetnt wordsに分けて最適化
- id5もstopword + alphabetical block + alphabetical blockに分けて最適化
- 最後にand and andをstop wordから外す
10th Place Solution
- シミュレーテッド・アニーリング
- 以下を初期会にして最適化
[stop words("and" を除く)] + [alphabetical block1] + [and and and] + [alphabetical block2]
- メインの操作は、2単語のswap, 1単語の挿入
- stop wordのみにも同様の操作を適用
11th Place Solution
- シミュレーテッド・アニーリング
- 近傍解の生成手法を色々工夫
- ランダム挿入
- 距離ベースの確率的挿入:元の単語位置と近いところに挿入
- 可変長のランダム挿入:1~4単語をまとめて移動
- アルファベット順挿入:同じ頭文字の前後に挿入
- 部分的な並び替え(shuffle):1~4単語のブロックをシャッフル
関連書籍
- Kaggleで勝つデータ分析の技術
- Kaggleに挑む深層学習プログラミングの極意 (KS情報科学専門書)
- 実践Data Scienceシリーズ PythonではじめるKaggleスタートブック (KS情報科学専門書)
以上
Discussion