低自己相関バイナリシーケンス（LABS）問題は、通信、信号処理、衛星航法などで重要な応用を持つ難解な組合せ最適化問題です。この問題では、自己相関が最小となるバイナリシーケンスを探索する必要がありますが、シーケンス長が増加するにつれて探索空間が指数的に拡大するため、厳密な解法は困難です。最近、研究者らは、トンプソンサンプリングと並列自己回避歩行を組み合わせた新しいハイブリッド探索フレームワークを提案しました。このフレームワークは、LABS問題の探索空間を制約クラスに分割し、各クラスをマルチアームバンディットの「腕」としてモデル化します。トンプソンサンプリングを用いて、各クラスで観測されたメリットファクターに基づき計算資源を動的に配分し、有望な領域を優先的に探索しながら、未探索領域の探索も維持します。
アルゴリズムの効率を高めるため、複数の高速化手法が採用されています。GPUによる並列実行により、複数の自己回避歩行を同時に進め、後方確率更新を共有することで収束を促進します。また、近傍評価を効率化し、ブルームフィルタを用いてサイクルを防止することで無駄な計算を削減します。さらに、二段階最適化戦略を採用し、まず制約付きの歪対称空間で探索を行い、その後、最良候補を制約なし空間で洗練させます。
実験の結果、提案手法は長いバイナリシーケンスにおいて優れた性能を示しました。シーケンス長Lが450から527の範囲の35個の長さ、およびL=573において、従来の最良結果を更新しました。特に、L=451においてメリットファクターが8.0を超える新たな最長シーケンスを発見しました。この成果は、トンプソンサンプリングがLABS最適化において有望なパーティションを効果的に特定できることを示し、オンラインでデータ駆動型の資源配分が有効であることを実証しています。
本フレームワークは、高性能メリットファクター最大化のためのスケーラブルで効果的な戦略を提供します。自己回避歩行のような古典的な手法と、トンプソンサンプリングのような最新の機械学習手法を融合させることで、組合せ最適化と適応的資源配分を統合し、関連分野の発展に貢献することが期待されます。