一種求解GSTP問題的新型黏菌優(yōu)化算法

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

關(guān)鍵詞： Steiner樹問題； 黏菌優(yōu)化算法； 傳遞函數(shù)； 位置更新； 離散化處理； 種群初始化

中圖分類號(hào)： TN919?34； TP301.6" " " " " " " " " " 文獻(xiàn)標(biāo)識(shí)碼： A" " " " " " " " " 文章編號(hào)： 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）是圖論中經(jīng)典的NP難組合優(yōu)化問題[1]，其目標(biāo)是在一個(gè)具有可區(qū)分頂點(diǎn)子集的任意加權(quán)圖中尋找一個(gè)跨越所有終端節(jié)點(diǎn)集合的最小代價(jià)子樹，為了減少生成樹的總權(quán)重，引入額外的中間節(jié)點(diǎn)集（Steiner節(jié)點(diǎn)）和邊集。許多現(xiàn)實(shí)問題都可以歸結(jié)為GSTP問題，如VLSI設(shè)計(jì)[2]、通信網(wǎng)絡(luò)設(shè)計(jì)[3]等。目前求解GSTP問題的算法主要集中于元啟發(fā)式算法，如文獻(xiàn)[4]提出一種能夠避免全局鏈路信息、編碼/解碼和修復(fù)操作的遺傳算法交叉機(jī)制。文獻(xiàn)[5]提出多源單匯絨泡菌優(yōu)化和分層多源單匯絨泡菌優(yōu)化兩種啟發(fā)式算法。文獻(xiàn)[6]利用在線遷移學(xué)習(xí)的多因子進(jìn)化算法求解GSTP的變體問題。盡管該類算法在解決實(shí)際問題時(shí)表現(xiàn)良好，但仍存在收斂速度慢、參數(shù)調(diào)優(yōu)困難、時(shí)間復(fù)雜度高、最優(yōu)值誤差較大、易陷入局部最優(yōu)等缺點(diǎn)。

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

基于GSTP問題的特點(diǎn)，本文提出一種融合多策略改進(jìn)的黏菌優(yōu)化算法（Improved Binary Slime Mould Optimization Algorithm， IBSMA）。在OR?Library標(biāo)準(zhǔn)測(cè)試集上進(jìn)行實(shí)驗(yàn)驗(yàn)證，與啟發(fā)式算法、近似算法和深度強(qiáng)化學(xué)習(xí)算法進(jìn)行比較，分析IBSMA的算法性能。

1" 理論知識(shí)

1.1" 圖的Steiner樹問題

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

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

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

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

圖1展示了GSTP的一個(gè)實(shí)例。其中，圖1a）為[G]，灰色節(jié)點(diǎn)為終端節(jié)點(diǎn)，白色節(jié)點(diǎn)為Steiner節(jié)點(diǎn)。圖1b）～圖1d）為生成的三個(gè)解，權(quán)重分別為10、12、6。圖1d）所示的子樹覆蓋了所有的終端節(jié)點(diǎn)集合，且權(quán)重之和最小，即為最優(yōu)Steiner樹。

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

1） 當(dāng)[A=2]時(shí)，其中[?]為元素個(gè)數(shù)，該問題等價(jià)于最短路徑問題；

2） 當(dāng)[A=V]時(shí)，等價(jià)于最小生成樹問題；

3） 當(dāng)[2lt;Alt;V]時(shí)，該問題具有NP難特性。

1.2" 數(shù)學(xué)性質(zhì)分析

以下為GSTP的數(shù)學(xué)性質(zhì)，通過這些性質(zhì)可以對(duì)網(wǎng)絡(luò)進(jìn)行簡化，降低網(wǎng)絡(luò)規(guī)模，加快求解速度。

1） 度為0或1的Steiner節(jié)點(diǎn)一定不在最優(yōu)Steiner樹中。

2） 與度為1的終端節(jié)點(diǎn)相鄰的點(diǎn)一定在最優(yōu)Steiner樹中。

3） 與度為2的Steiner點(diǎn)[v]相鄰的終端節(jié)點(diǎn)[v1]、[v2]，若[w（v，v1）+w（v，v2）gt;w（v1，v2）]，則最優(yōu)Steiner樹中不包含節(jié)點(diǎn)[v]。

4） 對(duì)于Steiner點(diǎn)[v]，若刪除節(jié)點(diǎn)[v]后，剩余圖中所有節(jié)點(diǎn)不能構(gòu)成連通圖，且每個(gè)連通量中都包含終端節(jié)點(diǎn)，則[v]一定在最優(yōu)Steiner樹中。

5） 與度為2的終端節(jié)點(diǎn)[v]相鄰的兩個(gè)節(jié)點(diǎn)[v1]、[v2]均為終端節(jié)點(diǎn)，則相應(yīng)的邊在最優(yōu)Steiner樹中。

6） 對(duì)于度為2的終端節(jié)點(diǎn)[v0]，其相鄰的兩個(gè)節(jié)點(diǎn)[v1]和[v2]均為Steiner點(diǎn)，且[v1]和[v2]之間存在邊[e12]，若[w01+w12lt;w02]，則邊[e01]和節(jié)點(diǎn)[v1]一定在最優(yōu)Steiner樹中。

7） 若最優(yōu)Steiner樹存在，則Steiner節(jié)點(diǎn)的數(shù)目最多不超過終端節(jié)點(diǎn)的數(shù)目減2。

2" 黏菌優(yōu)化算法

該算法通過模擬黏菌在自然界中的覓食過程來實(shí)現(xiàn)優(yōu)化目的，與其他優(yōu)化算法相比，SMA在單峰和多峰函數(shù)的探索和開發(fā)性能良好，且具有參數(shù)少、尋優(yōu)能力強(qiáng)的特點(diǎn)。黏菌覓食過程包括接近食物、包圍食物和獲取食物三個(gè)階段。

2.1" 接近食物

黏菌根據(jù)空氣中的氣味來接近食物，用以下數(shù)學(xué)模型表示接近行為：

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

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

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

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

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

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

[a=arctanh1-tmaxt]" （5）

式中[maxt]為最大迭代次數(shù)。

黏菌主要依靠生物振蕩器產(chǎn)生的傳播波來改變細(xì)胞質(zhì)的流動(dòng)，靜脈接觸的食物濃度越高，生物振蕩器產(chǎn)生的波越強(qiáng)，細(xì)胞質(zhì)流動(dòng)越快，靜脈越厚，這一特點(diǎn)確保了黏菌在該區(qū)域可以獲得足夠的營養(yǎng)。對(duì)搜索時(shí)黏菌靜脈組織結(jié)構(gòu)的收縮模式進(jìn)行數(shù)學(xué)模擬，反映黏菌脈寬與所探索的食物濃度之間的正負(fù)反饋關(guān)系。黏菌個(gè)體權(quán)重因子[W]（又稱黏菌的重量）模擬了黏菌的生物振蕩器，采用log函數(shù)緩解數(shù)值的變化率，使收縮頻率的值變化不大。[W]的更新規(guī)則如下：

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

式中：[bF]為當(dāng)前迭代過程中獲得的最優(yōu)適應(yīng)度值；[wF]為當(dāng)前迭代過程中獲得的最差適應(yīng)度值；[r]模擬了自然環(huán)境中黏菌靜脈收縮模式的不確定性；[SmellIndex]表示對(duì)黏菌種群的適應(yīng)度值進(jìn)行排序；condition表示在SmellIndex中排序前半部分的個(gè)體。黏菌種群根據(jù)食物的質(zhì)量來調(diào)整自身搜索模式，當(dāng)食物濃度較高時(shí)，該區(qū)域附近的權(quán)重[W]越大；當(dāng)食物濃度較低時(shí)，區(qū)域的權(quán)重會(huì)降低，從而轉(zhuǎn)向其他區(qū)域的探索。

2.2" 包圍食物

模擬黏菌靜脈結(jié)構(gòu)在搜索過程中的收縮模式，基于上述原理，黏菌位置更新規(guī)則如下：

[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]]范圍內(nèi)兩個(gè)不同的隨機(jī)值；LB、UB分別表示搜索空間的下界和上界；[z]的值與維持探索和開發(fā)的平衡有關(guān)，相關(guān)實(shí)驗(yàn)證明[z=0.03]時(shí)[7]，算法性能更好。

2.3" 獲取食物

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

3" 離散型SMA求解GSTP

3.1" 問題轉(zhuǎn)化及初始化

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

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

3.2" 離散化處理

通常V型和S型函數(shù)簇的各種傳遞函數(shù)都可以將連續(xù)值映射到[0，1]范圍內(nèi)，根據(jù)概率將其轉(zhuǎn)換為0或1。常見的傳遞函數(shù)如表1所示，文獻(xiàn)[10]對(duì)以下函數(shù)進(jìn)行了詳細(xì)比較。

在求解GSTP問題時(shí)，傳遞函數(shù)從標(biāo)準(zhǔn)的SMA算法中接收實(shí)值作為輸入，然后使用S型函數(shù)在0～1對(duì)該值進(jìn)行歸一化，本文使用一種新的傳遞函數(shù)[11]對(duì)個(gè)體位置進(jìn)行離散化處理，具體方法為：

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

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

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

S型函數(shù)曲線如圖3所示。

3.3" 位置更新策略

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

[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（?）]表示傳遞函數(shù)。

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

算法1：IBSMA

Input：加權(quán)無向圖[G]、終端節(jié)點(diǎn)集[A]、參數(shù)[z，r]

Output：最優(yōu)Steiner樹

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

While [t≤maxt] do

使用傳遞函數(shù)將每個(gè)[Xi]轉(zhuǎn)換為二進(jìn)制

計(jì)算所有黏菌[Xi]的適應(yīng)度值

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

通過式（6）計(jì)算[W]

for [i=1：pop] do

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

根據(jù)式（10）～式（13）更新黏菌位置

end for

[t=t+1]

end while

return最優(yōu)Steiner樹

4" 實(shí)" 驗(yàn)

4.1" 實(shí)驗(yàn)環(huán)境

實(shí)驗(yàn)數(shù)據(jù)選用OR?Library中關(guān)于圖的Steiner樹的標(biāo)準(zhǔn)測(cè)試集[12]。采用Matlab 2016b編程實(shí)現(xiàn)本文算法，在處理器為13th Gen Intel[?] CoreTM i5?13500H@2.60 GHz，內(nèi)存為16.0 GB的計(jì)算機(jī)上進(jìn)行實(shí)驗(yàn)。

4.2" 實(shí)驗(yàn)設(shè)計(jì)

設(shè)種群規(guī)模pop=50，[maxt=500]，鄰域半徑[R]=2，[z=0.03]。[V]表示節(jié)點(diǎn)總數(shù)，[E]表示邊集總數(shù)，[A]表示終端節(jié)點(diǎn)的個(gè)數(shù)。每個(gè)實(shí)例重復(fù)進(jìn)行20次，以確保實(shí)驗(yàn)結(jié)果的穩(wěn)定性和可靠性。OPT是OR?Library中公開的最優(yōu)解值，運(yùn)算結(jié)果達(dá)到最優(yōu)則加粗表示，存在誤差且趨近最優(yōu)值，加粗帶星表示，NF為未在相關(guān)實(shí)例上進(jìn)行測(cè)試，Best為相應(yīng)算法的最優(yōu)解。

4.3" 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)1：選用深度強(qiáng)化學(xué)習(xí)算法[13]：圖卷積網(wǎng)絡(luò)（GCN）、Vulcan、圖注意力（GAT）、S2V、MLP、Classic近似算法，以及DNH和MPH啟發(fā)式算法[14]與IBSMA算法進(jìn)行對(duì)比實(shí)驗(yàn)。表2記錄了在實(shí)例B上的測(cè)試結(jié)果，用最優(yōu)解值和運(yùn)行時(shí)間來評(píng)估算法性能。

可以看出：深度強(qiáng)化學(xué)習(xí)算法在B13實(shí)例上的最優(yōu)值優(yōu)于OPT，但在其他實(shí)例上均無法取得最優(yōu)值。Classic算法、MPH算法和DNH算法分別在2個(gè)、9個(gè)、7個(gè)實(shí)例上取得最優(yōu)值。而本文的IBSMA算法在所有實(shí)例上均能取得最優(yōu)值，且最優(yōu)解值精度均優(yōu)于其他算法。最后統(tǒng)計(jì)了DNH、IBSMA算法在B01～B18數(shù)據(jù)集上的運(yùn)行時(shí)間，在時(shí)間性能方面，IBSMA算法所需的時(shí)間更短。

由此可知：IBSMA算法在求解GSTP問題時(shí)，求解精度更高、運(yùn)行時(shí)間更短、算法性能更優(yōu)。

圖4為IBSMA算法分別在總節(jié)點(diǎn)數(shù)為75和100的數(shù)據(jù)集B11與B17上的適應(yīng)度曲線圖。由圖4可知：算法在[maxt]=200時(shí)均能達(dá)到收斂值，后續(xù)趨于穩(wěn)定，表明算法在早期迭代階段具有很強(qiáng)的收斂能力，能夠迅速找到最優(yōu)解，并在迭代過程中保持較高的穩(wěn)定性，全面地評(píng)估了算法的穩(wěn)健性和適應(yīng)性。

實(shí)驗(yàn)2：將啟發(fā)式算法[15]：最短路徑（SPATH）、最小生成樹和剪枝（MST+P）、OURS、DNH、MPH算法與IBSMA算法進(jìn)行對(duì)比。分別在總節(jié)點(diǎn)數(shù)為500的大規(guī)模數(shù)據(jù)C01～C20上設(shè)計(jì)實(shí)驗(yàn)，表3記錄了IBSMA算法的最優(yōu)解值和誤差率。

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

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

5" 結(jié)" 語

在標(biāo)準(zhǔn)的SMA算法基礎(chǔ)上，本文提出了融合多策略改進(jìn)的黏菌優(yōu)化算法來解決圖的Steiner樹問題，在OR?Library標(biāo)準(zhǔn)測(cè)試集中的38個(gè)算例上設(shè)計(jì)仿真實(shí)驗(yàn)，并與其他深度強(qiáng)化學(xué)習(xí)算法、近似算法、啟發(fā)式算法進(jìn)行比較，證明了IBSMA方法在求解精度方面明顯優(yōu)于其他算法，且能很好地跳出局部最優(yōu)。但該算法還存在收斂速度慢、時(shí)間復(fù)雜度大等缺點(diǎn)，未來可以進(jìn)一步優(yōu)化以提高算法性能，也可以將其拓展至更大規(guī)模的Steiner樹問題，或應(yīng)用于其他重要領(lǐng)域的組合優(yōu)化問題，使算法具有更強(qiáng)的適用性。

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

參考文獻(xiàn)

[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最小樹構(gòu)建及其布線應(yīng)用[D].上海：復(fù)旦大學(xué)，2014.

基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目（62062001）；寧夏青年拔尖人才項(xiàng)目（2021）；北方民族大學(xué)重點(diǎn)科研項(xiàng)目（2023ZRLG12）

作者簡介：王軍霞（2000—），女，甘肅白銀人，在讀碩士研究生，研究方向?yàn)樗惴ǚ治雠c設(shè)計(jì)。

王曉峰（1980—），男，回族，甘肅會(huì)寧人，博士研究生，副教授，研究方向?yàn)闄C(jī)器學(xué)習(xí)、人工智能等。

華盈盈（2000—），女，河南南陽人，在讀碩士研究生，研究方向?yàn)樗惴ǚ治雠c設(shè)計(jì)。

何" 飛（1999—），男，湖南永州人，在讀碩士研究生，研究方向?yàn)樗惴ǚ治雠c設(shè)計(jì)。

唐" 傲（2002—），男，湖南邵陽人，在讀碩士研究生，研究方向?yàn)樗惴ǚ治雠c設(shè)計(jì)。

劉建平（1989—），男，回族，寧夏固原人，博士研究生，講師，研究方向?yàn)橹悄苄畔z索與推薦。