低自相關二進位制序列（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問題提供了一種可擴充套件且高效的最大化品質因子的策略。透過將經典的自迴避行走與現代機器學習方法（如湯普森取樣）相結合，該工作展示瞭如何將組合最佳化與自適應決策融為一體，有望推動相關應用領域的發展。