Stein Variational Black-Box Combinatorial Optimization
全新發表的 SVGD-EDA 演算法結合史坦排斥力，在 256 維黑盒最佳化中擊敗 83 款模型。
- 首度將史坦變分梯度下降引入離散最佳化，有效避免群體提早收斂。
- 採用秩轉換計分機制，確保演算法不受目標函數極端數值波動影響。
- 在 256 維度的崎嶇地形中，具備核函數排斥力的架構效能提升達 15%。
在處理高維度的離散黑盒最佳化難題時，傳統演算法常因過早收斂而陷入次優的死胡同。法國昂熱大學團隊發表的全新架構 SVGD-EDA，首度將連續空間專用的史坦變分梯度下降演算法導入離散最佳化領域。在具備 256 個變數的高維度測試環境中，該演算法擊敗了包含 Nevergrad 函式庫在內的 83 種主流模型，於 24 種複雜地形配置中奪得 17 項冠軍，平均綜合排名達到 5.375。憑藉純張量運算的硬體加速，批次運算時間更從傳統 CPU 的 300 秒大幅縮減至 RTX 3060 上的 20 秒。
突破 EDAs 模型的單一收斂理論瓶頸
黑盒最佳化（BBO，在不清楚目標函數內部結構的情況下尋找最佳解）的目標在於優化未知系統。在多數實際場景中，例如執行高擬真模擬或實體實驗，每次查詢的運算成本都相當高昂，因此樣本效率成為演算法設計的核心指標。為解決這類單目標最佳化問題，分佈估計演算法（EDAs，透過機率模型學習並採樣潛在解的族群演算法）逐漸成為主流。傳統的 EDAs 不使用基因演算法中的交配或突變算子，而是透過參數化的機率模型迭代演化出一組分佈，藉此找出潛在的極值。
然而，EDAs 具備一個極為常見的缺陷，即搜尋分佈極易發生過早崩潰（premature collapse）。由於機率模型是根據當下群體的表現進行迭代更新，演算法往往會迅速將機率質量集中於單一的高適應度區域，使得族群多樣性銳減，進而錯失多模態適應度地形（multimodal landscapes）中的其他最佳解。從資訊理論的角度來看，當控制目標分佈尖銳程度的溫度參數趨近於零時，傳統演算法會完全坍縮在單一最佳解上。
為解決這個困境，研究團隊主張將溫度參數維持在大於零的狀態，並利用變分推論（Variational Inference）對搜尋分佈的熵（entropy）進行正則化。為此，團隊引入了史坦變分梯度下降（SVGD）框架。SVGD 的特點在於其結合了函數梯度更新與由核函數（Kernel）引發的排斥力，這種機制能在引導粒子前往高價值區域的同時，利用數學上具備理論保證的排斥項維持族群的廣泛分佈。
具備秩轉換不變性的 SVGD-EDA 架構設計
由於離散的組合最佳化無法直接計算梯度，研究團隊建立了一個多代理人（multi-agent）框架來實踐 SVGD-EDA 演算法。在這個設定下，每個代理人代表 SVGD 模型中的一個參數粒子，各自維持一組生成解的機率策略。具體而言，在處理偽布林（pseudo-Boolean）問題時，演算法為代理人配備單變數白努利分佈模型，以對數勝率（log-odds）作為參數；面對分類變數問題時，則採用 Softmax 函數將數值轉換為分類分佈，並利用對數導數技巧估算出梯度的替代值。
單純引入 SVGD 並不足以應付所有實務問題，因為更新規則對目標函數的極端數值過於敏感。為了提升模型在各類異質最佳化任務中的強健性，團隊借鑒了資訊幾何最佳化（Information-Geometric Optimization）的概念，捨棄原始的適應度數值，改採基於分位數的單調轉換目標。團隊設計了一種單純基於排名（rank-based）的實用計分機制：每一代取樣出的個體會根據表現排序，表現最優者獲得排名零與 +1 的絕對最高分，最差者則得到 -1 分。
這個設計確保了 SVGD-EDA 演算法行為對於適應度尺度的任何單調變換具備完全的不變性。透過上述機制，代理人群體不僅能相互比較尋求進步，還能免受異常極端分數的干擾，維持穩健且單調遞增的改善軌跡。
在 NKD 複雜地形迎戰 83 款基準演算法
為驗證 SVGD-EDA 的實戰效能，團隊將其投入 NKD 模型測試。NKD 是一個可高度參數化調整規模與崎嶇度的適應度地形框架，本研究涵蓋了偽布林變數的 NK 模型與具備三個分類值的 NK3 模型。測試設定中，變數規模區分為 64、128 與 256，控制局部變數互動範圍（崎嶇度）的參數 K 則設為 1、2、4、8。所有實驗皆受限於嚴格的 50,000 次目標函數評估預算，並導入 Nevergrad 函式庫中的演算法以及經典的 PBIL、MIMIC 與 BOA，形成多達 83 款模型的龐大競爭池。
實驗數據證實，SVGD-EDA 在大規模與高崎嶇度的環境中展現了壓倒性優勢。在變數達 128 與 256 的 NK 模型中，它在所有不同 K 值的配置下皆奪得全場第一。深入觀察搜尋初期的演進曲線可以發現，部分採用菁英策略與動態突變範圍的基準演算法（例如 DiscreteLengler3OnePlusOne），在初期能透過組合基本移動快速攀升；但隨著突變範圍縮小，這類演算法會退化為單步隨機爬山演算法，並在局部最佳解處提早停滯。
相較之下，SVGD-EDA 在整個 50,000 次評估週期內展現出持續且穩定的改善軌跡。在 100 次獨立執行中，該模型繳出極窄的四分位距（Interquartile range），證明其最終生成的最佳解具備高度的品質一致性與可靠性。
探究 7 個代理人的資源配置與史坦排斥效應
為了確認 SVGD-EDA 的優異表現並非單純來自平行運算的隨機紅利，研究團隊執行了代理人數量敏感度分析與消融實驗（Ablation study）。在預算固定的前提下，代理人數量決定了探索廣度與挖掘深度的資源權衡。數據顯示，在較為單純的測試中，較大的代理人數（10 至 14 個）能獲取最佳探索效益；但當維度上升至 256 或地形變得高度崎嶇時，最適代理人數會一致性地收斂至 7 個。若代理人數過多，會導致嚴重的「預算稀釋」，使個別代理人缺乏足夠的演化世代來精煉模型。
核心的消融實驗進一步移除了 SVGD 架構中的徑向基底函數（RBF）互動機制，強制切斷史坦排斥力，將演算法降級為多個獨立平行的分佈估計代理人。結果顯示，當面臨最嚴苛的 256 維度與 K=8 的高度崎嶇地形時，具備排斥力的架構領先幅度高達 15%，在分類空間 NK3 模型中也穩定超出 10%。
詳細的行為軌跡分析顯示，在進行至 20,000 次評估時，獨立平行模型會無可避免地永遠陷在次優區域。而 SVGD-EDA 則能藉由核函數排斥力所維持的族群多樣性，成功脫離欺騙性的局部最佳解陷阱。未來，團隊計畫將歐幾里得核函數進階為定義在統計流形上的 Fisher-Rao 資訊幾何核函數，並導入非同步更新機制，進一步提升探索大型組合空間的極限潛能。
透過在參數空間中引入核函數排斥力，SVGD-EDA 成功打破了分佈估計演算法在離散最佳化容易陷入局部極值的限制，為黑盒尋優機制建立了全新標準。