低自相關二進制序列（LABS）問題是一項極具挑戰性的組合優化難題，在通信、信號處理和衞星導航等領域有着重要的應用。該問題的目標是尋找具有最小自相關值的二進制序列，但搜索空間隨着序列長度呈指數增長，使得精確求解變得極為困難。近日，一支研究團隊提出了一種新穎的混合搜索框架，將湯普森採樣（Thompson sampling）與並行自迴避行走（parallel self-avoiding walks）相結合，旨在自適應地分配計算資源，從而更高效地探索LABS問題的解空間。
該方法的核心思想是將搜索空間劃分為多個分區（restriction classes），並將每個分區視為多臂老虎機問題中的一個“臂”。通過湯普森採樣，算法動態地根據各分區歷史上產生的品質因子（merit factor）來調整搜索資源的分配，優先投資於那些能夠帶來更高品質因子的分區，同時保留對較少探索區域的隨機性。這種在線、數據驅動的資源分配策略確保了探索與利用之間的平衡。
為了進一步提升算法效率，研究團隊採用了多項加速技術。首先，利用GPU並行執行搜索任務，同時對多個分區進行自迴避行走，大幅縮短了搜索時間。其次，通過共享後驗更新機制，各個並行進程能夠及時分享彼此的發現，加快收斂速度。此外，高效的鄰域評估方法減少了計算量，而布隆過濾器（Bloom filter）有效防止了搜索過程中的循環，避免了重複計算。
在優化策略上，該框架採用了兩階段方法：第一階段在受約束的偏斜對稱（skew-symmetric）空間中進行搜索，利用對稱性質縮減搜索範圍；第二階段則將第一階段得到的最佳候選序列放入無約束空間中進一步精煉，以獲得更優的解。這種兩階段設計充分利用了問題結構的特性，提高了搜索的針對性和效率。
實驗結果表明，該框架在多個長二進制序列上取得了突破性進展。在序列長度L從450到527的範圍內，以及L=573時，該方法共改進了35個長度下的已知最佳結果。特別值得一提的是，在L=451時，研究團隊發現了一條品質因子超過8.0的新最長序列，這是該領域的一個重要里程碑。這些結果充分驗證了湯普森採樣在LABS優化中有效識別高性能分區的潛力，也證明了在線數據驅動資源分配策略的價值。
總體而言，該混合搜索框架為LABS問題提供了一種可擴展且高效的最大化品質因子的策略。通過將經典的自迴避行走與現代機器學習方法（如湯普森採樣）相結合，該工作展示瞭如何將組合優化與自適應決策融為一體，有望推動相關應用領域的發展。