一種求解GSTP問題的新型黏菌優化算法

摘" 要： 針對圖的Steiner樹問題（GSTP）的NP難特性，提出一種融合多策略改進的黏菌優化算法。首先，定義種群初始化方法，由于STP是二進制解空間中的優化問題，而標準的黏菌優化算法迭代更新后每個維度的值是連續的。因此，為搜索個體確定最佳的S型傳遞函數，對連續的個體位置進行離散化處理。其次，為避免種群陷入局部最優，對二進制的黏菌優化算法引入新的位置更新策略。最后，將改進后的黏菌優化算法在OR?Library標準測試集上的計算結果與其他經典啟發式算法、近似算法以及深度強化學習算法進行實驗對比分析。結果表明，改進后的黏菌優化算法能夠有效避免陷入局部最優，收斂精度更高，在求解GSTP時有一定優越性。

關鍵詞： Steiner樹問題； 黏菌優化算法； 傳遞函數； 位置更新； 離散化處理； 種群初始化

中圖分類號： TN919?34； TP301.6" " " " " " " " " " 文獻標識碼： A" " " " " " " " " 文章編號： 1004?373X（2025）05?0162?07

Novel slime mould algorithm for solving GSTP problems

WANG Junxia1， WANG Xiaofeng1， 2， HUA Yingying1， HE Fei1， TANG Ao1， LIU Jianping1， 2

（1. School of Computer Science and Engineering， North Minzu University， Yinchuan 750021， China; 2. The Key Laboratory of Images and Graphics Intelligent Processing of State Ethnic Affairs Commission， North Minzu University， Yinchuan 750021， China）

Abstract： In view of the NP?hard property of the Steiner tree problem in Graphs （GSTP）， a slime mould algorithm （SMA） incorporating multi?strategy improvement is proposed. Firstly， the population initialization method is defined. Since the STP is an optimization problem in binary solution space， the value of each dimension is continuous after the iteration update of the standard SMA. Therefore， the optimal S?type transfer function is determined for individuals under search， and the continuous individual positions are discretized. Secondly， a new position update strategy is introduced to the binary SMA in order to avoid the population from falling into the local optimum. Finally， the computational results of the improved SMA on the OR?Library standard test set are compared with the classical heuristic algorithms， approximation algorithms， and deep reinforcement learning algorithms， and the comparative results are analyzed. The results show that the improved SMA can avoid falling into the local optimum effectively， with higher convergence accuracy， so it has a certain advantages in solving GSTP.

Keywords： STP; SMA; transfer function; position update; discretization processing; population initialization

0" 引" 言

圖的Steiner樹問題（The Steiner Tree Problem in Graph， GSTP）是圖論中經典的NP難組合優化問題[1]，其目標是在一個具有可區分頂點子集的任意加權圖中尋找一個跨越所有終端節點集合的最小代價子樹，為了減少生成樹的總權重，引入額外的中間節點集（Steiner節點）和邊集。許多現實問題都可以歸結為GSTP問題，如VLSI設計[2]、通信網絡設計[3]等。目前求解GSTP問題的算法主要集中于元啟發式算法，如文獻[4]提出一種能夠避免全局鏈路信息、編碼/解碼和修復操作的遺傳算法交叉機制。文獻[5]提出多源單匯絨泡菌優化和分層多源單匯絨泡菌優化兩種啟發式算法。文獻[6]利用在線遷移學習的多因子進化算法求解GSTP的變體問題。盡管該類算法在解決實際問題時表現良好，但仍存在收斂速度慢、參數調優困難、時間復雜度高、最優值誤差較大、易陷入局部最優等缺點。

黏菌優化算法（Slime Mould Algorithm， SMA）是文獻[7]提出的一種新型元啟發式算法，廣泛應用于各類工程問題。如文獻[8]將SMA與鯨魚優化算法相結合，提取X射線圖像中含有COVID?19特征的區域。文獻[9]提出一種名為HG?SMA的增強黏菌算法來求解基于Said?Ball曲線的新型平滑路徑規劃模型。通過添加分層引導策略構建增強算法，將黏菌種群分為兩個等級，并將相應的策略應用于不同的層次結構以提高解的質量。目前該類算法在許多方面都取得了較大的成功，但現有文獻還未有利用SMA算法來求解GSTP問題。

基于GSTP問題的特點，本文提出一種融合多策略改進的黏菌優化算法（Improved Binary Slime Mould Optimization Algorithm， IBSMA）。在OR?Library標準測試集上進行實驗驗證，與啟發式算法、近似算法和深度強化學習算法進行比較，分析IBSMA的算法性能。

1" 理論知識

1.1" 圖的Steiner樹問題

給定一個無向加權圖[G=（V，E）]，其中，[V]表示節點集，存在一組終端節點集[A?V]和Steiner節點集[V ＼ A]。[E]表示邊的集合，在邊集[E]上定義權值非負實數函數[w：E→R+]。GSTP的目標是在圖[G]上尋找一棵跨越所有終端節點集合[A]的樹[T=（VT，ET）]，且使邊的權值之和最小，表達式如下：

[F（T）=e∈ETw（e）?（e）]" （1）

式中，[?（e）]為決策變量，取值為1表示邊[e]在樹[T]中，取值為0表示邊[e]不在樹[T]中，描述如下：

[z（e）=1，" " " e∈ET?E0，" " " others]" （2）

圖1展示了GSTP的一個實例。其中，圖1a）為[G]，灰色節點為終端節點，白色節點為Steiner節點。圖1b）～圖1d）為生成的三個解，權重分別為10、12、6。圖1d）所示的子樹覆蓋了所有的終端節點集合，且權重之和最小，即為最優Steiner樹。

對于GSTP問題，存在以下三種特殊情形：

1） 當[A=2]時，其中[?]為元素個數，該問題等價于最短路徑問題；

2） 當[A=V]時，等價于最小生成樹問題；

3） 當[2lt;Alt;V]時，該問題具有NP難特性。

1.2" 數學性質分析

以下為GSTP的數學性質，通過這些性質可以對網絡進行簡化，降低網絡規模，加快求解速度。

1） 度為0或1的Steiner節點一定不在最優Steiner樹中。

2） 與度為1的終端節點相鄰的點一定在最優Steiner樹中。

3） 與度為2的Steiner點[v]相鄰的終端節點[v1]、[v2]，若[w（v，v1）+w（v，v2）gt;w（v1，v2）]，則最優Steiner樹中不包含節點[v]。

4） 對于Steiner點[v]，若刪除節點[v]后，剩余圖中所有節點不能構成連通圖，且每個連通量中都包含終端節點，則[v]一定在最優Steiner樹中。

5） 與度為2的終端節點[v]相鄰的兩個節點[v1]、[v2]均為終端節點，則相應的邊在最優Steiner樹中。

6） 對于度為2的終端節點[v0]，其相鄰的兩個節點[v1]和[v2]均為Steiner點，且[v1]和[v2]之間存在邊[e12]，若[w01+w12lt;w02]，則邊[e01]和節點[v1]一定在最優Steiner樹中。

7） 若最優Steiner樹存在，則Steiner節點的數目最多不超過終端節點的數目減2。

2" 黏菌優化算法

該算法通過模擬黏菌在自然界中的覓食過程來實現優化目的，與其他優化算法相比，SMA在單峰和多峰函數的探索和開發性能良好，且具有參數少、尋優能力強的特點。黏菌覓食過程包括接近食物、包圍食物和獲取食物三個階段。

2.1" 接近食物

黏菌根據空氣中的氣味來接近食物，用以下數學模型表示接近行為：

[X（t+1）=Xb（t）+vb?（W?XA（t）-XB（t）），" " rlt;pvc?X（t），" " r≥p] （3）

式中：[Xb]為適應度最優的個體位置；[W]為黏菌個體的權重因子；[t]為當前迭代次數；[X]為黏菌位置；[XA]和[XB]表示從黏菌中隨機選擇的兩個個體；[p]為條件參數，表示個體與當前最優適應度值間的差距，用于確定位置更新策略；[r]為[0，1]范圍內的隨機數。當[rlt;p]時，處于全局搜索狀態，并逐漸向當前最優位置靠近；當[r≥p]時，處于局部搜索狀態。[p]的定義如下：

[p=tanhS（i）-DF]" （4）

式中：[S（i）]，[i∈1，2，…，n]表示黏菌個體[X]的適應度值；DF表示所有迭代過程中獲得的最優適應度值。

圖2顯示了式（3）的效果，也說明搜索個體在三維空間中的位置變化，個體可以在任意方向搜索解空間，從而使算法具有找到最優解的可能性，模擬了黏菌接近食物時的扇形結構。

振蕩參數vc和vb用來改變個體的位置，vc從1～0呈線性遞減，模擬黏菌對自身的保留。vb的取值范圍為[[-a，a]]，模擬黏菌個體信息的交互過程。[a]隨著迭代次數的增加而逐漸減小，計算公式如下：

[a=arctanh1-tmaxt]" （5）

式中[maxt]為最大迭代次數。

黏菌主要依靠生物振蕩器產生的傳播波來改變細胞質的流動，靜脈接觸的食物濃度越高，生物振蕩器產生的波越強，細胞質流動越快，靜脈越厚，這一特點確保了黏菌在該區域可以獲得足夠的營養。對搜索時黏菌靜脈組織結構的收縮模式進行數學模擬，反映黏菌脈寬與所探索的食物濃度之間的正負反饋關系。黏菌個體權重因子[W]（又稱黏菌的重量）模擬了黏菌的生物振蕩器，采用log函數緩解數值的變化率，使收縮頻率的值變化不大。[W]的更新規則如下：

[W（SmellIndex（i））=1+r?logbF-S（i）bF-wF+1，" "condition1-r?logbF-S（i）bF-wF+1，" "othersSmellIndex=sort（S）] （6）

式中：[bF]為當前迭代過程中獲得的最優適應度值；[wF]為當前迭代過程中獲得的最差適應度值；[r]模擬了自然環境中黏菌靜脈收縮模式的不確定性；[SmellIndex]表示對黏菌種群的適應度值進行排序；condition表示在SmellIndex中排序前半部分的個體。黏菌種群根據食物的質量來調整自身搜索模式，當食物濃度較高時，該區域附近的權重[W]越大；當食物濃度較低時，區域的權重會降低，從而轉向其他區域的探索。

2.2" 包圍食物

模擬黏菌靜脈結構在搜索過程中的收縮模式，基于上述原理，黏菌位置更新規則如下：

[X（t+1）=rand?（UB-LB）+LB，" " " " " "randlt;zXb（t）+vb?（W?XA（t）-XB（t）），" " rlt;pvc?X（t），" " " " "r≥p] （7）

式中：[rand]和[r]為[[0，1]]范圍內兩個不同的隨機值；LB、UB分別表示搜索空間的下界和上界；[z]的值與維持探索和開發的平衡有關，相關實驗證明[z=0.03]時[7]，算法性能更好。

2.3" 獲取食物

食物源會引起黏菌自身的振蕩，進而改變靜脈網絡中細胞質的流動，使得黏菌不斷靠近食物源，用振蕩參數vb和vc來模擬黏菌的選擇行為，[vb∈[-a，a]]有助于避免局部最優。為了尋找更好的食物來源，即使黏菌找到了食物濃度較高的目標，它也會分離出部分生物體去探索其他區域，試圖找到更高質量的食物來源。SMA算法的核心更新機制為：式（3）確保了算法一定的隨機性，式（6）、式（7）隨著振蕩幅度的變化讓算法分別進行全局和局部的搜索。

3" 離散型SMA求解GSTP

3.1" 問題轉化及初始化

由于圖的Steiner樹問題是二進制空間中的優化問題，因此針對標準的SMA算法，存在收斂精度較低，每個維度的解值是連續的，且在一定程度上易陷入局部最優等問題，故本文提出IBSMA算法。問題轉化過程首先將圖[G=（V，E）]轉化為網絡模型，其中節點對應食物源，邊對應黏菌的管道，每條管道的流量取決于邊的權重和當前的網絡結構。通過黏菌的行為模擬流體在網絡中的流動，管道的粗細（即邊的權重之和）隨著流量的變化而調整。流量越大則邊被選中的概率越大，而流量較小的路徑可能會被削弱或淘汰。

所有的元啟發式算法都從初始化步驟開始，在優化問題的搜索空間內擴展解，從而逐步逼近問題的最優解。GSTP要求覆蓋所有的終端節點，基于這一屬性需要選擇合適的Steiner節點，在算法的初始化階段，對[N]個節點進行隨機初始化，每個解對應于一個黏菌個體。其次，引入傳遞函數進行離散化處理，用二進制向量表示解，當節點被選中作為Steiner點時，向量的對應位置表示為1，否則表示為0。根據選擇的Steiner點和連接路徑，計算當前解的總權重，并用適應度函數來評估解的質量。

3.2" 離散化處理

通常V型和S型函數簇的各種傳遞函數都可以將連續值映射到[0，1]范圍內，根據概率將其轉換為0或1。常見的傳遞函數如表1所示，文獻[10]對以下函數進行了詳細比較。

在求解GSTP問題時，傳遞函數從標準的SMA算法中接收實值作為輸入，然后使用S型函數在0～1對該值進行歸一化，本文使用一種新的傳遞函數[11]對個體位置進行離散化處理，具體方法為：

[SXi（t）=11+e-10（Xi（t）-0.5）] （8）

[Y=1，" " "randlt;SXi（t）0，" " "others]" （9）

式中[Xi（t）]表示在第[t]次迭代中第[i]個粒子在第[d]維度上的位置。

S型函數曲線如圖3所示。

3.3" 位置更新策略

當使用式（7）進行位置更新時，無論是使用S型還是V型傳遞函數，[XA]和[XB]在二進制搜索空間中只有（0，0）、（0，1）、（1，0）和（1，1）四種可能，且[Xb=1]時，[Xi]大概率取1，這使得算法在一定程度上容易陷入局部最優。因此，本文給出一種新的位置更新策略：

[X（t+1）=x1，" " randlt;zx2，" " rlt;px3，" " r≥p]" （10）

式中，[x1]、[x2]、[x3]的表示由式（11）～式（13）給出：

[x1=1，" " randgt;0.50，" " rand≤0.5] （11）

[x2=1-Xb，" " " Svb?W（i）?XA-XB≥randXb，" " " others] （12）

[x3=1-Xi，" " "S（vc?Xi）gt;randXi，" " " others]" （13）

式中：[W（i）]由式（6）給出；[S（?）]表示傳遞函數。

3.4" IBSMA求解GSTP問題的算法步驟

算法1：IBSMA

Input：加權無向圖[G]、終端節點集[A]、參數[z，r]

Output：最優Steiner樹

初始化：種群pop，最大迭代次數[maxt]，黏菌位置[Xi（i=1，2，…，n ;d=1，2，…，D）∈{0，1}]

While [t≤maxt] do

使用傳遞函數將每個[Xi]轉換為二進制

計算所有黏菌[Xi]的適應度值

更新DF、[Xb]、[bF]和[wF]

通過式（6）計算[W]

for [i=1：pop] do

更新[vb]、[vc]和[p]

根據式（10）～式（13）更新黏菌位置

end for

[t=t+1]

end while

return最優Steiner樹

4" 實" 驗

4.1" 實驗環境

實驗數據選用OR?Library中關于圖的Steiner樹的標準測試集[12]。采用Matlab 2016b編程實現本文算法，在處理器為13th Gen Intel[?] CoreTM i5?13500H@2.60 GHz，內存為16.0 GB的計算機上進行實驗。

4.2" 實驗設計

設種群規模pop=50，[maxt=500]，鄰域半徑[R]=2，[z=0.03]。[V]表示節點總數，[E]表示邊集總數，[A]表示終端節點的個數。每個實例重復進行20次，以確保實驗結果的穩定性和可靠性。OPT是OR?Library中公開的最優解值，運算結果達到最優則加粗表示，存在誤差且趨近最優值，加粗帶星表示，NF為未在相關實例上進行測試，Best為相應算法的最優解。

4.3" 實驗結果與分析

實驗1：選用深度強化學習算法[13]：圖卷積網絡（GCN）、Vulcan、圖注意力（GAT）、S2V、MLP、Classic近似算法，以及DNH和MPH啟發式算法[14]與IBSMA算法進行對比實驗。表2記錄了在實例B上的測試結果，用最優解值和運行時間來評估算法性能。

可以看出：深度強化學習算法在B13實例上的最優值優于OPT，但在其他實例上均無法取得最優值。Classic算法、MPH算法和DNH算法分別在2個、9個、7個實例上取得最優值。而本文的IBSMA算法在所有實例上均能取得最優值，且最優解值精度均優于其他算法。最后統計了DNH、IBSMA算法在B01～B18數據集上的運行時間，在時間性能方面，IBSMA算法所需的時間更短。

由此可知：IBSMA算法在求解GSTP問題時，求解精度更高、運行時間更短、算法性能更優。

圖4為IBSMA算法分別在總節點數為75和100的數據集B11與B17上的適應度曲線圖。由圖4可知：算法在[maxt]=200時均能達到收斂值，后續趨于穩定，表明算法在早期迭代階段具有很強的收斂能力，能夠迅速找到最優解，并在迭代過程中保持較高的穩定性，全面地評估了算法的穩健性和適應性。

實驗2：將啟發式算法[15]：最短路徑（SPATH）、最小生成樹和剪枝（MST+P）、OURS、DNH、MPH算法與IBSMA算法進行對比。分別在總節點數為500的大規模數據C01～C20上設計實驗，表3記錄了IBSMA算法的最優解值和誤差率。

表3結果表明：SPATH和MST+P算法在20個實例上均未達到OPT。DNH、OURS、MPH算法分別在1個、6個和4個實例上取得最優值；而本文IBSMA算法在14個實例上均取得最優值，達到已知最優解占比高達70%，且最優解值的誤差率不超過0.1，可知，IBSMA算法求解GSTP問題時，求解精度均明顯優于其他算法。

圖5為IBSMA算法分別在邊集總數為625和12 500的數據集C05與C20上的適應度曲線圖。由圖5可以看出，即使在較高的初始適應度值下，IBSMA算法也能穩定地收斂到最優解，表明該算法在求解GSTP問題時的高效性。

5" 結" 語

在標準的SMA算法基礎上，本文提出了融合多策略改進的黏菌優化算法來解決圖的Steiner樹問題，在OR?Library標準測試集中的38個算例上設計仿真實驗，并與其他深度強化學習算法、近似算法、啟發式算法進行比較，證明了IBSMA方法在求解精度方面明顯優于其他算法，且能很好地跳出局部最優。但該算法還存在收斂速度慢、時間復雜度大等缺點，未來可以進一步優化以提高算法性能，也可以將其拓展至更大規模的Steiner樹問題，或應用于其他重要領域的組合優化問題，使算法具有更強的適用性。

注：本文通訊作者為王曉峰。

參考文獻

[1] KARP R M. Reducibility among combinatorial problems [C]// Proceedings of a Symposium on the Complexity of Computer Computations. New York： Plenum Press， 1972： 85?103.

[2] DE LAERE M， PHAM S T， DE CAUSMAECKER P. Solving the Steiner tree problem in graphs with variable neighborhood descent [EB/OL]. [2018?08?13]. http：//arxiv.org/abs/1806.06685.

[3] SUN Y H， BRAZIL M， THOMAS D A， et al. The fast heuristic algorithms and post?processing techniques to design large and low?cost communication networks [J]. IEEE/ACM transactions on networking， 2019， 27（1）： 375?388.

[4] ZHANG Q B， YANG S X， LIU M， et al. A new crossover mechanism for genetic algorithms for Steiner tree optimization [J]. IEEE transactions on cybernetics， 2020， 52（5）： 3147?3158.

[5] SUN Y H. Solving the Steiner tree problem in graphs using physarum?inspired algorithms [EB/OL]. [2022?10?20]. http：//arxiv.org/abs/1903.08926.

[6] LONG N B， BAN H B， BINH H T T. An online transfer learning based multifactorial evolutionary algorithm for solving the clustered Steiner tree problem [J]. Knowledge?based systems， 2024， 296： 111870.

[7] LI S M， CHEN H L， WANG M J， et al. Slime mould algorithm： A new method for stochastic optimization [J]. Future generation computer systems， 2020， 111： 300?323.

[8] ABDEL?BASSET M， CHANG V， MOHAMED R. HSMA_WOA： A hybrid novel Slime mould algorithm with whale optimization algorithm for tackling the image segmentation problem of chest X?ray images [J]. Applied soft computing journal， 2020， 95： 106642.

[9] HU G， DU B， WEI G. HG?SMA： Hierarchical guided Slime mould algorithm for smooth path planning [J]. Artificial intelligence review， 2023， 56（9）： 9267?9327.

[10] ABDEL?BASSET M， MOHAMED R， CHAKRABORTTY R K， et al. An efficient binary slime mould algorithm integrated with a novel attacking?feeding strategy for feature selection [J]. Computers amp; industrial engineering， 2021， 153： 107078.

[11] LI L， PAN T S， SUN X X， et al. A novel binary slime mould algorithm with AU strategy for cognitive radio spectrum allocation [J]. International journal of computational intelligence systems， 2021， 14（1）： 161.

[12] BEASLEY J E. OR?library Steiner problem in graphs [EB/OL]. [2018?02?26]. http：//people.brunel.ac.uk/～mastjjb/jeb/info.html.

[13] DU H Z， YAN Z， XIANG Q， et al. Vulcan： Solving the Steiner tree problem with graph neural networks and deep reinforcement learning [EB/OL]. [2021?11?26]. https：//arxiv.org/abs/2111.10810.

[14] YANG B Y， ZHENG W G. Near?optimal Steiner tree computation powered by node embeddings [J]. Knowledge and information systems， 2023， 65（11）： 4563?4583.

[15] 董君.圖的Steiner最小樹構建及其布線應用[D].上海：復旦大學，2014.

基金項目：國家自然科學基金資助項目（62062001）；寧夏青年拔尖人才項目（2021）；北方民族大學重點科研項目（2023ZRLG12）

作者簡介：王軍霞（2000—），女，甘肅白銀人，在讀碩士研究生，研究方向為算法分析與設計。

王曉峰（1980—），男，回族，甘肅會寧人，博士研究生，副教授，研究方向為機器學習、人工智能等。

華盈盈（2000—），女，河南南陽人，在讀碩士研究生，研究方向為算法分析與設計。

何" 飛（1999—），男，湖南永州人，在讀碩士研究生，研究方向為算法分析與設計。

唐" 傲（2002—），男，湖南邵陽人，在讀碩士研究生，研究方向為算法分析與設計。

劉建平（1989—），男，回族，寧夏固原人，博士研究生，講師，研究方向為智能信息檢索與推薦。