Steiner樹優(yōu)化問題的算法研究綜述

王軍霞，王曉峰，2，彭慶媛，華盈盈，宋家歡

1.北方民族大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，銀川 750021

2.北方民族大學(xué)圖形圖像智能處理國(guó)家民委重點(diǎn)實(shí)驗(yàn)室，銀川 750021

Steiner樹問題是一個(gè)經(jīng)典的組合優(yōu)化問題，在計(jì)算機(jī)網(wǎng)絡(luò)布局、無線通信、生物網(wǎng)絡(luò)分析，以及對(duì)給定的一組種子基因或蛋白質(zhì)進(jìn)行子網(wǎng)絡(luò)的識(shí)別等領(lǐng)域都有重要的應(yīng)用[1-2]。最短網(wǎng)絡(luò)問題是求解最小生成樹問題的基礎(chǔ)，且最小Steiner樹問題（minimum Steiner tree problem，MSTP）與最小生成樹問題之間有許多相似之處[3]，最小生成樹是在給定的頂點(diǎn)集和邊中尋找最短網(wǎng)絡(luò)使得所有的點(diǎn)連通。MSTP 是使得指定的頂點(diǎn)集合中的所有點(diǎn)連通，且邊的權(quán)值總和最小的生成樹。換句話說，最小生成樹是MSTP 的一種特殊情況，因此用于解決MSTP 的啟發(fā)式算法可以通過延伸和推廣最短路徑算法和最小生成樹算法的思想而得到。STP 是圖論中研究較多的組合優(yōu)化問題[4]，目標(biāo)是在給定的無向圖中找到一棵最小的子圖（即Steiner樹），使得該子圖包含了給定的特定節(jié)點(diǎn)（稱為正則節(jié)點(diǎn)）以及其他節(jié)點(diǎn)（稱為Steiner 節(jié)點(diǎn)）之間的最小連接。該問題是一個(gè)NP 難問題[5]，其求解難點(diǎn)在于該類問題很難找到多項(xiàng)式時(shí)間內(nèi)的算法，且隨著問題規(guī)模的增加，通常具有指數(shù)級(jí)別的解空間。因此，對(duì)于這類問題，研究者通常致力于尋找高效的求解方法。

目前，求解該問題的算法主要分為三類：（1）啟發(fā)式算法，主要有禁忌搜索算法[6]、KMB（Kou Mrakousky Bermaa）算法[7]、MPH（minimum cost path heuristic）算法[8]、ADH（average distance heuristic）算法[9]、Physarum啟發(fā)式算法[10]等，該類算法在較短的時(shí)間內(nèi)可以找到問題的可行解或次優(yōu)解，適用于大規(guī)模問題，但利用該算法求解STP 時(shí)解的質(zhì)量無法保證。（2）信息傳播算法（belief propagation algorithm，BP）[11]，該算法可以作為STP 的消息傳遞求解器，允許并行計(jì)算，因此在處理大規(guī)模問題時(shí)有一定的效率。但是Steiner 樹實(shí)例中可能會(huì)存在回路，使得算法收斂性變得相對(duì)復(fù)雜。（3）智能優(yōu)化算法，如遺傳算法（genetic algorithm，GA）[12]、粒子群優(yōu)化算法（particle swarm optimizer，PSO）[13]、協(xié)同進(jìn)化算法（co-evolutionary algorithms）[14]均為著名的智能計(jì)算工具，被廣泛應(yīng)用于各種Steiner樹優(yōu)化問題中。但該類算法易陷入局部最優(yōu)，且基于樹的遺傳算法會(huì)產(chǎn)生非法的后代樹，為確保后代樹的連通性，必須采用全局鏈路信息，計(jì)算量大。

現(xiàn)有關(guān)于求解STP的算法對(duì)比分析較少，因此本文將分別從STP的研究發(fā)展、已有算法的概念、基本原理、改進(jìn)策略及改進(jìn)前后算法的優(yōu)缺點(diǎn)展開綜述。首先，對(duì)相關(guān)背景知識(shí)進(jìn)行介紹，梳理STP的發(fā)展；其次，對(duì)啟發(fā)式算法、信息傳播算法、智能優(yōu)化算法等經(jīng)典算法在Steiner 樹中的應(yīng)用進(jìn)行概述；最后，基于上述提出的算法，分析其研究趨勢(shì)，總結(jié)全文。

1 相關(guān)背景介紹

最優(yōu)Steiner樹問題已廣泛應(yīng)用于各種算法大賽，如在2014 年舉行的第11 屆DIMACS 挑戰(zhàn)賽和2018 年P(guān)ACE 挑戰(zhàn)賽中，加強(qiáng)了Steiner 樹的普遍適用性和相關(guān)性。STP仍然吸引著來自許多學(xué)科的研究人員，包括應(yīng)用數(shù)學(xué)、計(jì)算機(jī)科學(xué)、運(yùn)籌學(xué)和管理科學(xué)等。

1.1 Steiner樹問題的發(fā)展

Steiner樹問題是以Jakob Steiner名字命名的，通過引入一些輔助節(jié)點(diǎn)來生成一組具有最小權(quán)重的樹。該問題根據(jù)兩個(gè)節(jié)點(diǎn)之間權(quán)值的確定方式，存在多種變體問題。如歐式Steiner 樹問題、絕對(duì)距離Steiner 樹問題和圖的Steiner 樹問題等，其中圖的Steiner 樹問題是研究最多的組合優(yōu)化問題之一。這些變體增加了問題的復(fù)雜性，同時(shí)該類問題很難尋找合適的Steiner 節(jié)點(diǎn)組合，這導(dǎo)致了搜索空間呈指數(shù)級(jí)增長(zhǎng)?？傊甋TP具有高度的復(fù)雜性和計(jì)算難度，其求解涉及到圖論、組合優(yōu)化以及算法設(shè)計(jì)等多個(gè)領(lǐng)域。

目前，關(guān)于Steiner樹問題的研究已取得一些重要進(jìn)展，如呂其誠(chéng)[15]使用快速算法求解圖的Steiner 樹問題，隨后又對(duì)其進(jìn)行改進(jìn)，降低了算法的復(fù)雜性。Biazzo等人[16]在2012 年提出解決圖中獲獎(jiǎng)Steiner 樹問題的空腔法，分析了Goemans-Williamson啟發(fā)式算法和DHEA求解器，這是一種基于分支和整數(shù)線性規(guī)劃的方法。比較結(jié)果表明，在大多數(shù)情況下，空腔法在運(yùn)行時(shí)間和解的質(zhì)量方面均優(yōu)于前兩種算法。Lai等人[17]在2017年對(duì)求解Steiner 樹問題的進(jìn)化算法（evolutionary algorithm，EA）進(jìn)行性能分析，該算法是一種通用且流行的隨機(jī)算法，并揭示了（1+1）EA在解決一類特殊準(zhǔn)二部圖的度量Steiner 問題時(shí)近似比為3/2，該算法可以有效地找到STP實(shí)例的全局最優(yōu)值。但在構(gòu)造Steiner樹實(shí)例時(shí)，該算法需要指數(shù)級(jí)的優(yōu)化運(yùn)行時(shí)間，意味著（1+1）EA在解決STP時(shí)效率低下。近些年關(guān)于STP的研究發(fā)展如圖1所示。

圖1 關(guān)于Steiner樹問題的研究發(fā)展Fig.1 Research and development of Steiner tree problem（STP）

1.2 問題描述及公式化

定義1最優(yōu)Steiner樹問題指：給定一個(gè)無向圖G=(V,E)和權(quán)值函數(shù)w:E→R+，其中V和E分別表示節(jié)點(diǎn)和邊的集合。設(shè)P(P?V)為終端集合（又稱正則節(jié)點(diǎn)），S?VP為非正則節(jié)點(diǎn)集合（又稱Steiner 節(jié)點(diǎn)）。STP的目標(biāo)是找到一個(gè)跨越終端集合P，且邊的權(quán)值之和最小的生成樹。若|P|=2，則將該問題簡(jiǎn)化為“最短路徑問題”；若|P|=|V|，則簡(jiǎn)化為“最小生成樹問題”。記|V|=n,|E|=l,|P|=m,r=m-n。如圖2 展示了STP 的一個(gè)實(shí)例，其中圖（a）為原始的無向加權(quán)圖G，圖中紅色節(jié)點(diǎn)為正則節(jié)點(diǎn)；圖（b）為最優(yōu)Steiner樹，其中藍(lán)色節(jié)點(diǎn)為Steiner節(jié)點(diǎn)。

圖2 STP實(shí)例Fig.2 STP instance

1.3 數(shù)學(xué)性質(zhì)

性質(zhì)1度為0 或1 的非正則節(jié)點(diǎn)一定不在最優(yōu)Steiner樹中。

性質(zhì)2與度為1 的正則節(jié)點(diǎn)相鄰的點(diǎn)一定在最優(yōu)Steiner樹中。

性質(zhì)3對(duì)于度為2的Steiner節(jié)點(diǎn)v，若其相鄰的兩個(gè)節(jié)點(diǎn)vi和vj間有邊，且w(v,vi)+w(v,vj)＞w(vi,vj)，則最優(yōu)Steiner樹中不包含節(jié)點(diǎn)v。

性質(zhì)4正則節(jié)點(diǎn)v的度為2時(shí)，若其相鄰的兩個(gè)節(jié)點(diǎn)vi和vj均為正則節(jié)點(diǎn)，則min{w(v,vi),w(v,vj)}對(duì)應(yīng)的邊一定在最優(yōu)Steiner樹中。

2 求解Steiner樹的啟發(fā)式算法

2.1 MPH算法

MPH算法借鑒了最短路徑和最小生成樹的算法思想[24]，其步驟如下：

步驟1任意選擇一個(gè)節(jié)點(diǎn)v1,且v1∈P。設(shè)置i=1,則Ti={v1},Vi={v1}。

步驟2查找節(jié)點(diǎn)vi∈S-Vi-1(i=2,3,…,m)，使得vi到Ti-1的權(quán)重之和最小，且vi通過最短路徑Path(vi-Ti-1)連接到Ti-1,Ti=Ti-1∪Path(vi-Ti-1),Vi為Ti的節(jié)點(diǎn)集，最終得到的樹為TMPH。

2.2 改進(jìn)的MPH算法

上述啟發(fā)式算法通過最短路徑來添加正則節(jié)點(diǎn)，但最短路徑的選擇不具有唯一性，使得形成的Steiner樹不一定最優(yōu)。因此，余燕平等人[25]提出基于關(guān)鍵節(jié)點(diǎn)的啟發(fā)式算法（KBMPH）。該算法是對(duì)MPH算法的改進(jìn)，把含有較多最短路徑經(jīng)過的節(jié)點(diǎn)稱為關(guān)鍵節(jié)點(diǎn)，通過對(duì)含較多關(guān)鍵節(jié)點(diǎn)的路徑費(fèi)用進(jìn)行修正，然后添加到Steiner樹中，其步驟如下：

步驟1求G中所有節(jié)點(diǎn)對(duì)間的最短路徑，若最短路徑經(jīng)過某個(gè)節(jié)點(diǎn)，則該節(jié)點(diǎn)的權(quán)值加1，找出權(quán)值最大的k個(gè)節(jié)點(diǎn)，加入節(jié)點(diǎn)集M中。

步驟2從P中任選一個(gè)節(jié)點(diǎn)v1，設(shè)i=1，則初始生成樹Ti={v1},Vi={v1}。

步驟3對(duì)于vi∈S-Vi-1(i=2,3,…,m)，使得vi到Ti-1的修正費(fèi)用d′(vi,Ti-1)最小，若路徑經(jīng)過一個(gè)以上M中的節(jié)點(diǎn)，則將路徑費(fèi)用乘以系數(shù)λ后再做比較(0＜λ ＜1)。且vi通過修正費(fèi)用最短路徑Path(vi-Ti-1)連接到,Vi為Ti的節(jié)點(diǎn)集，最終得到的樹為TKBMPH。

KBMPH 算法實(shí)現(xiàn)了鏈路共享，在性能方面進(jìn)行了改進(jìn)，但該算法選擇的關(guān)鍵節(jié)點(diǎn)不一定是Steiner 節(jié)點(diǎn)，因此時(shí)間復(fù)雜度較高。在此基礎(chǔ)上，2015年王小龍[26]提出基于加權(quán)節(jié)點(diǎn)的啟發(fā)式算法（NWMPH），通過對(duì)所有Steiner節(jié)點(diǎn)構(gòu)造權(quán)值計(jì)算的加權(quán)公式，根據(jù)權(quán)值修正路徑費(fèi)用，用最短路徑連接所有正則節(jié)點(diǎn)，得到最優(yōu)Steiner樹，改進(jìn)后的算法在時(shí)間復(fù)雜度上優(yōu)于KBMPH 算法，其步驟如下：

步驟1對(duì)Steiner節(jié)點(diǎn)進(jìn)行權(quán)值計(jì)算，公式如下：

通常取0.1 ≤β≤2,0.4 ≤α≤0.8。f(i)為節(jié)點(diǎn)i在圖中的重要程度，F(xiàn)為f(i)的最大值。di表示節(jié)點(diǎn)i的度。gi表示正則節(jié)點(diǎn)間最短路徑經(jīng)過節(jié)點(diǎn)i的次數(shù)。li表示節(jié)點(diǎn)i與正則節(jié)點(diǎn)直接相連的次數(shù)。修正費(fèi)用d′(vi,Ti-1)=λ×d(vi,Ti-1)，其中λ是所有Steiner 節(jié)點(diǎn)權(quán)值的平均值。d(vi,Ti-1)是vi到Ti-1的最短距離。

步驟2初始化T1={v1},V1={v1}。

步驟3將vi通過修正費(fèi)用最短路徑Path(vi-Ti-1)連接到Ti-1,Ti=Ti-1∪Path(vi-Ti-1),最終得到的樹為TNWMPH。

2.3 Physarum啟發(fā)式及其改進(jìn)算法

Physarum啟發(fā)式算法（Physarum optimization algorithm，POA）是一種基于粘菌體行為的優(yōu)化算法，模擬了粘菌體在尋找食物的過程中所表現(xiàn)出的集體智能和自組織行為。其智能行為主要有[27]：尋找最短路徑、建立高質(zhì)量的網(wǎng)絡(luò)、適應(yīng)不斷變化的環(huán)境。Physarum是一種單細(xì)胞粘菌，能夠形成網(wǎng)絡(luò)并與其他Physarum 生物融合，并行搜索問題的解空間，每個(gè)個(gè)體收集信息形成問題的部分解，個(gè)體間相互融合并共享信息，以找到問題的全局最優(yōu)解。

近年來，基于Physarum 生物的啟發(fā)式算法發(fā)展迅速，并有研究證實(shí)了該類算法能夠解決旅行商、最短路徑、Steiner 樹等各種NP 難組合優(yōu)化問題[28]。如Liu 等人[29]在2013 年提出基于生物學(xué)的Physarum 優(yōu)化算法，用來求解Steiner 樹問題。利用Physarum 生物群體，找到終端集并相互融合，共享智能行為信息，以尋找最優(yōu)Steiner 樹，并將該算法與近似算法，禁忌搜索等經(jīng)典算法進(jìn)行對(duì)比，結(jié)果表明：在大多數(shù)情況下Physarum優(yōu)化算法都能達(dá)到與經(jīng)典算法相近的性能。此外，該算法具有低復(fù)雜度和高并行性，但無法保證問題解的質(zhì)量，在實(shí)際應(yīng)用中需要進(jìn)行多次迭代，收斂速度慢。在此基礎(chǔ)上，Sun等人[30]在2019年提出多源單匯Physarum優(yōu)化和分層多源單匯Physarum優(yōu)化兩種Physarum啟發(fā)式算法（Physarum-inspired algorithms，PAS）來解決圖的Steiner樹問題。用VLSI設(shè)計(jì)實(shí)例來評(píng)估PA的性能，對(duì)于具有數(shù)百個(gè)節(jié)點(diǎn)的實(shí)例，第一個(gè)PA 可以找到平均誤差為0.19%的可行解，并與遺傳算法、粒子群優(yōu)化算法進(jìn)行對(duì)比分析，結(jié)果表明：該算法在求解圖的Steiner 樹問題時(shí)可以取得較好的效果。對(duì)于多達(dá)數(shù)萬個(gè)節(jié)點(diǎn)的較大實(shí)例，GA、PSO 和第一個(gè)PA 太慢無法使用，而第二個(gè)PA可以找到平均誤差為3.69%的可行解。

針對(duì)啟發(fā)式及其改進(jìn)算法進(jìn)行對(duì)比，總結(jié)算法原理及優(yōu)缺點(diǎn)，具體分析如表1所示。

3 求解Steiner樹的信息傳播算法

近年來，BP算法發(fā)展迅速，該算法是基于傳統(tǒng)物理學(xué)的空腔法，也是一種基于因子圖的消息傳遞求解器[31]，用于給定圖形模型（graphical model，GM）表示的聯(lián)合分布中的最大后驗(yàn)概率分配（MAP）。單個(gè)實(shí)例的空腔法的優(yōu)化版本稱為Max-Sum 算法，過去已應(yīng)用于STP 及變體問題。Braunstein 等人[11]通過空腔法優(yōu)化STP，描述了Max-Sum 方程的兩個(gè)增強(qiáng)功能，以便能夠解決現(xiàn)實(shí)世界實(shí)例的優(yōu)化。第一個(gè)是開發(fā)一種替代“平面”的模型公式，允許減少相關(guān)配置空間，使該方法在實(shí)例上可行，特別是當(dāng)正則節(jié)點(diǎn)數(shù)量較少時(shí)。第二個(gè)是Max-Sum算法和貪婪啟發(fā)式算法間的集成，這種集成是將Max-Sum 轉(zhuǎn)換為一種極具競(jìng)爭(zhēng)力的自包含算法，其中在迭代過程的每一步都給出了可行解。

3.1 圖形模型

定義2n個(gè)（二進(jìn)制）隨機(jī)變量的聯(lián)合分布Z=[Zi]∈{0,1}n被稱為圖形模型：

其中，{?i,?α}為給定的非負(fù)函數(shù)，稱為因子。如圖3描述了因子Fi和變量zi之間的圖形關(guān)系，F(xiàn)i={α1,α2,α3},n=4,。

圖3 因子Fi 和變量zi 之間的圖形關(guān)系Fig.3 Graphical relationship between factor Fi and variable zi

對(duì)于給定的一組消息，BP邊際信念計(jì)算如下：

如果因子圖是樹且MAP 分配是唯一的，則zBP收斂于MAP分配。如果圖中存在循環(huán)，BP算法一般不能保證找到MAP賦值。BP算法的具體描述如下：

算法1BP算法

輸入：構(gòu)造初始化因子圖模型，最大迭代次數(shù)為tm。

輸出：算法收斂后得到不動(dòng)點(diǎn)。

3.2 Steiner樹的變體問題

最優(yōu)Steiner樹存在多種變體和推廣問題，本文主要區(qū)分了頂點(diǎn)不相交的Steiner樹問題（Steiner tree problem with disjoint vertices，V-DSTP）與邊緣不相交的Steiner樹問題（Steiner tree problem with disjoint edges，E-DSTP）。在V-DSTP中，不同的樹不能共享節(jié)點(diǎn)，因而也不能共享邊；在E-DSTP中，邊不能被樹共享，而節(jié)點(diǎn)可以由不同的樹共享。這些額外約束的引入，增加了算法設(shè)計(jì)的難度，使得問題更為復(fù)雜，且該問題均為NP難問題[32]。這兩個(gè)變體的應(yīng)用通常涉及到需要滿足特定約束條件的網(wǎng)絡(luò)或布局設(shè)計(jì)問題。如在實(shí)際應(yīng)用中，V-DSTP可以用于通信網(wǎng)絡(luò)設(shè)計(jì)，以提高網(wǎng)絡(luò)的可靠性；E-DSTP 可以用于流水線布局，以提高生產(chǎn)效率?；谠搯栴}的求解難度與廣泛實(shí)用性，研究人員進(jìn)一步探索深度學(xué)習(xí)和機(jī)器學(xué)習(xí)方法在Steiner 樹變體問題中的應(yīng)用，從而提高求解效率。

如圖4和圖5分別表示兩種變體問題使用分支模型的可行賦值。方形節(jié)點(diǎn)表示根節(jié)點(diǎn)，圓形節(jié)點(diǎn)表示終端節(jié)點(diǎn)，箭頭表示邊緣被使用，標(biāo)簽表示（正）深度分量的值。圖4 為V-DSTP 變量的可行賦值，包含兩個(gè)子圖；圖5為E-DSTP變量的可行賦值。

圖4 使用分支模型對(duì)V-DSTP的變量的可行賦值Fig.4 Feasible assignment of variables to V-DSTP using branching model

圖5 使用分支模型對(duì)E-DSTP的變量的可行賦值Fig.5 Feasible assignment of variables to E-DSTP using branching model

為了強(qiáng)調(diào)分支模型（branching model）和平面模型（flat model）的區(qū)別，如圖6和圖7分別描繪了分支模型和平面模型在網(wǎng)格圖上對(duì)V-DSTP相同解的情況。圖6根據(jù)分支形式，需要d=7 的最小深度，以允許“藍(lán)色”通信的所有終端到達(dá)根節(jié)點(diǎn)“1”；圖7根據(jù)平面形式，需要d=3 的最小深度。事實(shí)上，當(dāng)每次到達(dá)一個(gè)終端節(jié)點(diǎn)，或分支點(diǎn)時(shí)（如圖中節(jié)點(diǎn)“23”附近），深度變量增加一個(gè)單位。

圖6 使用分支模型時(shí)V-DSTP的解Fig.6 Solution for V-DSTP using branching model

圖7 使用平面模型時(shí)V-DSTP的解Fig.7 Solution for V-DSTP using flat model

3.3 信息傳播方程

對(duì)于圖G其頂點(diǎn)與邊分別具有非負(fù)獎(jiǎng)勵(lì)和正權(quán)重,STP的目標(biāo)是尋找M個(gè)連通子圖，該子圖Gμ=(Vμ,Eμ)跨越不相交的終端集{Pμ?Vμ,μ=1,2,…,M}，使以下成本函數(shù)最?。?/p>

為了解決上述兩個(gè)組合優(yōu)化問題，在與圖G相關(guān)的因子圖上定義一組適當(dāng)?shù)南嗷プ饔米兞?。因子圖是因子和變量的二部圖。若函數(shù)依賴于變量，則因子和變量之間存在邊。對(duì)每個(gè)節(jié)點(diǎn)i∈V和每條邊(i,j)∈E，分別關(guān)聯(lián)一個(gè)因子節(jié)點(diǎn)?i和一個(gè)二分量變量{(dij,μij)∈{-D,…,0,…,D}×{0,…,M}}，其中dij為深度，μij為通信變量，用來標(biāo)記形成不同樹的邊緣。將Steiner 樹的每個(gè)解映射到相關(guān)因子圖的變量d={dij:(i,j)∈E} 和μ={μij:(i,j)∈E}的某個(gè)賦值上。則式（8）可以用新變量表示為：

BP方程為：

其中，Zij是歸一化常數(shù)；δij是Kronecker Delta 函數(shù)；mij為消息，表明一些信息在因子圖的邊(i,j)上從節(jié)點(diǎn)i向j流動(dòng)。上式也可以看作是可迭代求解的不動(dòng)點(diǎn)方程組，從t=0 時(shí)的一組初始消息開始迭代公式的右邊，直到數(shù)值收斂到一個(gè)不動(dòng)點(diǎn)。

3.4 BP算法的收斂性與正確性

關(guān)于BP算法的收斂性與正確性已經(jīng)取得了一些顯著的研究成果，但當(dāng)問題規(guī)模增大時(shí)，樹狀因子圖的結(jié)構(gòu)復(fù)雜，使得算法的收斂速度變慢。文獻(xiàn)[33]給出BP算法的收斂性和正確性準(zhǔn)則，GM的最大后驗(yàn)概率分配對(duì)應(yīng)于LP的最優(yōu)解。此外，如果LP的解是唯一的，則GM上的最大乘積BP 具有唯一不動(dòng)點(diǎn)。文獻(xiàn)[34]中為了分析BP算法的收斂性，通過對(duì)消息更新方程取雙曲正切，將消息取值從[0，1]擴(kuò)展為(-∞,+∞)，利用壓縮映射原理證明了BP算法收斂的充分條件。

4 求解Steiner樹的智能優(yōu)化算法

智能優(yōu)化算法是一類基于自然界的生物進(jìn)化、群體行為等思想，通過模擬和引入這些思想來解決問題的計(jì)算方法。近年來也用于求解Steiner 樹及變體問題，如Dehouche[35]描述了遺傳算法在最小標(biāo)記Steiner 樹問題中的應(yīng)用，引入了一類新的有效不等式，評(píng)估其在解決該問題時(shí)的性能，給出最小標(biāo)記Steiner樹問題的整數(shù)線性規(guī)劃公式，以及用于加速分解過程的有效約束條件，并將新的方法與進(jìn)化算法進(jìn)行比較。Camacho-Vallejo等人[14]提出求解電信網(wǎng)絡(luò)中分層Steiner 樹問題的協(xié)同進(jìn)化算法，在該網(wǎng)絡(luò)中將集線器之間的連接視為Steiner樹，并把Steiner 樹問題建模為雙層數(shù)學(xué)規(guī)劃模型，以降低網(wǎng)絡(luò)連接成本。此外，開發(fā)了兩種協(xié)同進(jìn)化方法來解決該雙層模型，總結(jié)出上述方法的優(yōu)缺點(diǎn)，并證明其有效性。

4.1 粒子群優(yōu)化算法

粒子群優(yōu)化（particle swarm optimizer，PSO）算法是模擬鳥群或魚群等群體行為的智能優(yōu)化算法。種群中的每個(gè)粒子表示解空間中的一個(gè)潛在解，通過不斷更新粒子的位置和速度來搜索最優(yōu)解。劉耿耿等人[36]提出基于混合離散粒子群優(yōu)化的Slew 約束下X 結(jié)構(gòu)Steiner最小樹算法。使用預(yù)處理方法，節(jié)省電壓轉(zhuǎn)換速率的計(jì)算，設(shè)計(jì)了一種高效的混合修正策略，使得Steiner最小樹能夠完全滿足Slew約束。該算法與同類算法相比，實(shí)現(xiàn)了最佳的布線結(jié)果。劉慶等人[37]提出求解最優(yōu)Steiner 樹的前驅(qū)編碼粒子群優(yōu)化算法，避免了環(huán)的產(chǎn)生。分別基于鄰接矩陣和剔除相同適應(yīng)度值粒子策略，設(shè)計(jì)了“開發(fā)”算子和“勘探”算子，進(jìn)一步提高了算法的全局搜索能力。

具體說來，設(shè)種群規(guī)模為N，其中每個(gè)粒子都是一個(gè)d維向量，其在目標(biāo)搜索空間中的位置可以表示為xi={xi1,xi2,…,xid},i=1,2,…,N,速度可以表示為vi={vi1,vi2,…,vid},i=1,2,…,N。記pbest表示當(dāng)前粒子的歷史最優(yōu)值，gbest表示全局最優(yōu)值。當(dāng)前粒子根據(jù)以下速度更新公式和位置更新公式進(jìn)行狀態(tài)更新：

其中，下標(biāo)ij表示粒子i的第j維；t為迭代次數(shù)；ω為慣性權(quán)重；c1,c2為加速常量；r1,r2為隨機(jī)數(shù)，通常在[0，1]范圍內(nèi)取值。對(duì)于給定的無向圖G=(V,E)，利用PSO算法求解最優(yōu)Steiner樹的基本步驟如下：

4.2 遺傳算法

遺傳算法是一種模擬自然界生物繁殖和進(jìn)化過程的全局搜索算法。由四個(gè)主要元素組成，即染色體編碼/解碼、個(gè)體適應(yīng)度評(píng)估、遺傳算子和操作參數(shù)。Haouari等人[38]提出一種用于獎(jiǎng)品收集Steiner 樹問題的混合拉格朗日遺傳算法。下界是基于問題的最小生成樹公式的拉格朗日分解，體積算法用于求解拉格朗日對(duì)偶。遺傳算法結(jié)合了多項(xiàng)增強(qiáng)功能，充分利用了拉格朗日分解產(chǎn)生的原始和對(duì)偶信息。但是，現(xiàn)有用于求解STP的遺傳算法由于不連通、存在循環(huán)和正則節(jié)點(diǎn)缺失，可能導(dǎo)致產(chǎn)生非法解。因此，Diveev[39]提出了一種避免組合優(yōu)化問題非法解的有吸引力的方法：在有限范圍內(nèi)通過迭代搜索一個(gè)基本解的微小變化，以找到更好的解。

Steiner 樹優(yōu)化問題中的遺傳算法交叉機(jī)制已廣泛應(yīng)用于經(jīng)驗(yàn)建模、決策樹、多項(xiàng)式符號(hào)回歸、數(shù)據(jù)分類、語法樹等領(lǐng)域[40]?，F(xiàn)有Steiner樹優(yōu)化問題的GA根據(jù)染色體的表示可以分為以下兩類[41]：

（1）直接編碼樹的遺傳算法交叉機(jī)制（DT）。樹作為染色體，在交叉過程中，隨機(jī)選擇兩條父染色體，將相同的鏈路和正則節(jié)點(diǎn)復(fù)制到子代。這些節(jié)點(diǎn)和鏈路通常是一系列分離的子樹，采用Prim、Dijkstra[42]等最短路徑算法迭代連接兩個(gè)隨機(jī)選擇的子樹，直到所有子樹全部連通。

（2）間接編碼的遺傳算法交叉機(jī)制。在Steiner樹優(yōu)化問題中，該機(jī)制分為兩種[43]：第一種是Prüfer 編碼，字符串交叉操作采用兩點(diǎn)交叉，父字符串在兩個(gè)隨機(jī)選擇的位置上交換基因片段，通過解碼生成的新字符串得到后代樹；第二種是序列和拓?fù)渚幋a（ST），先將樹轉(zhuǎn)化為位置索引樹，再進(jìn)行編碼。但這類遺傳算法可能會(huì)產(chǎn)生非法后代樹，因此，需要一個(gè)檢測(cè)程序和帶有貪婪算法的修復(fù)函數(shù)來保證后代樹的合法性，降低了算法的有效性。

4.3 改進(jìn)的遺傳算法

Huy 等人[44]提出求解圖中Steiner 樹問題的并行遺傳算法，基于二進(jìn)制編碼，利用啟發(fā)式算法來評(píng)估個(gè)體的適應(yīng)度，并與其他元啟發(fā)式算法進(jìn)行對(duì)比。王小龍[26]通過結(jié)合模擬退火算法與遺傳算法提出求解STP 的混合遺傳算法，通過對(duì)每一代的最優(yōu)個(gè)體進(jìn)行模擬退火操作，增強(qiáng)算法的局部搜索能力。Zhang 等人[45]給出一種新的Steiner 樹優(yōu)化遺傳算法交叉機(jī)制，稱為L(zhǎng)C 機(jī)制。該交叉機(jī)制不需要全局鏈路信息，編碼/解碼以及修復(fù)操作，只需交換部分父染色體就可以產(chǎn)生合法的后代樹。在不同規(guī)模的網(wǎng)絡(luò)中，使用葉交叉機(jī)制的遺傳算法不僅能產(chǎn)生更好的解，而且收斂速度更快，優(yōu)于現(xiàn)有交叉機(jī)制的遺傳算法。

4.3.1 LC機(jī)制的兩個(gè)過程

定義3在無向圖G中，源節(jié)點(diǎn)集為D，正則點(diǎn)集為R,link(u,v)∈E表示連接節(jié)點(diǎn)u和v的直接鏈路，則{D}∪R?V。設(shè)Π={T1,T2,…,Tj,…,Tn}表示問題的解空間，其中Tj={Vj,Ej}?G,Vj?V,Ej?E,對(duì)于?Tj?Π，設(shè)：

Steiner樹優(yōu)化問題表示如下：

（1）若邊上無約束，有min{w(T):T∈Π}，質(zhì)量函數(shù)F′(T)=w0-w(T)，w0為足夠大的常數(shù)，使F′(T)為正。

（2）若邊上有約束，Ci(u,v),i=1,2,…,k,k≥1 表示約束的量化指標(biāo)。設(shè)

優(yōu)化問題表示為：min{w(T):T∈Π} ，約束為：Ci(T)≤ci0,i=1,2,…,k，其中ci0是約束Ci的閾值。

對(duì)于給定的樹T1、T2，LC機(jī)制主要有兩個(gè)過程：

過程1LC機(jī)制為D添加鏈接(D,-1)，并將相同鏈接復(fù)制到后代樹中：newT={V(E1∩E2),E1∩E2} 。這一過程類似于DT 遺傳算法，避免了編碼、解碼操作，并以葉節(jié)點(diǎn)作為切入點(diǎn)，從剩余鏈路中選擇關(guān)鍵的高質(zhì)量鏈路。

過程2首先在newT中添加高質(zhì)量的路徑，再刪除父樹中的冗余鏈接。從leaf1∩leaf2中隨機(jī)選擇一個(gè)節(jié)點(diǎn)v，并分別在T1、T2中找到從v返回D的路徑P1、P2。選擇連接點(diǎn)u將路徑連接到newT。定義Child(ET)={v|link(v,u),link(v,u)∈ET}，其中VP表示P中的節(jié)點(diǎn)，u滿足：μ∈Child(EnewT)∩VP。若Child(EnewT)∩VP有多個(gè)節(jié)點(diǎn)，則選擇距離葉節(jié)點(diǎn)最近的節(jié)點(diǎn)作為u，并切割路徑僅保留葉節(jié)點(diǎn)到u之間的鏈路。最后，比較P1,P2的質(zhì)量，將較好的路徑添加到newT，再從父樹中刪除P1,P2。綜上，一次完整的LC 過程迭代結(jié)束，LC的下一次運(yùn)算只需選擇一個(gè)相同的葉節(jié)點(diǎn)v∈leaf1∩leaf2，重復(fù)上述操作。

4.3.2 基于LC遺傳算法的實(shí)現(xiàn)

該算法以樹作為染色體，避免了編碼/解碼操作。與現(xiàn)有交叉機(jī)制不同，LC 通過交換部分父染色體來產(chǎn)生后代樹。以父樹中的葉節(jié)點(diǎn)作為切入點(diǎn)，將父染色體分解成若干條路徑，比較具有相同葉節(jié)點(diǎn)對(duì)應(yīng)的兩條路徑，將較好的路徑添加到后代樹中。并從合法后代樹和時(shí)間復(fù)雜度兩個(gè)方面說明了該算法的有效性，證明了LC機(jī)制可以生成合法子樹，且不需要最短路徑算法、檢測(cè)過程、修復(fù)函數(shù)、全局鏈路信息和編碼/解碼等操作。具有適應(yīng)性廣、計(jì)算量小、實(shí)現(xiàn)收斂所需的平均適應(yīng)度評(píng)估次數(shù)少的特點(diǎn)，表明了LC 比其他交叉機(jī)制更有效。其算法原理如下：

（1）適應(yīng)度函數(shù)：若邊上無約束，則取函數(shù)F′(T)作為適應(yīng)度函數(shù)。若邊上有約束，約束Steiner樹優(yōu)化問題的一種常用方法是在適應(yīng)度函數(shù)中使用懲罰技術(shù)。樹T的適應(yīng)度函數(shù)表示如下：

其中，α是懲罰因子，通常限制在區(qū)間（0，0.5]內(nèi)。

（2）選擇：目前廣泛使用的選擇方案有比例選擇。

（3）交叉和變異：文獻(xiàn)[46]給出一種新的遺傳算法變異方案。根據(jù)變異概率Pm隨機(jī)選擇一個(gè)節(jié)點(diǎn)子集，通過刪除與所選節(jié)點(diǎn)相關(guān)的所有鏈路，將樹分解成若干個(gè)獨(dú)立的子樹。然后，隨機(jī)選擇一條權(quán)重最小的路徑，將這些分離的子樹連接成一棵新的樹。

4.3.3 各種交叉機(jī)制的性能分析

分析文獻(xiàn)[45]，并總結(jié)各類交叉機(jī)制的算法性能。取G1=（50，63，13）、G2=（50，63，25）、G3=（50，100，13）、G4=（100，125，17）、G5=（100，200，17）、G6=（100，200，50）、G7=（500，1 000，83）、G8=（500，2 500，83）8組實(shí)例數(shù)據(jù)，分別表示節(jié)點(diǎn)數(shù)、連接數(shù)和正則節(jié)點(diǎn)數(shù)。交叉概率與變異概率分別為Pc=0.6 和Pm=0.05。如表2 統(tǒng)計(jì)分析了各類交叉機(jī)制的GA 在小規(guī)模圖上隨機(jī)生成1 000個(gè)后代樹的性能，種群規(guī)模M=100。

表2 小規(guī)模圖上的性能對(duì)比分析Table 2 Performance comparison analysis on small-scale graphs

從表2可以看出LC機(jī)制的執(zhí)行時(shí)間遠(yuǎn)遠(yuǎn)小于其他交叉算子，同時(shí)計(jì)算了4種交叉機(jī)制在G4～G6上實(shí)現(xiàn)收斂所需的平均適應(yīng)度評(píng)估次數(shù)。Prüfer達(dá)到收斂時(shí)所需的適應(yīng)度評(píng)估次數(shù)最多，ST次之，而LC和DT以相同的速度收斂，適應(yīng)度評(píng)估的次數(shù)最少。與其他交叉機(jī)制不同的是，DT 的執(zhí)行時(shí)間不會(huì)隨著網(wǎng)絡(luò)圖的復(fù)雜程度而增加，這是因?yàn)镈T 算法以最短路徑算法為主要操作。因此，正則節(jié)點(diǎn)的相對(duì)位置對(duì)執(zhí)行時(shí)間有很大影響，當(dāng)正則節(jié)點(diǎn)之間距離較近時(shí)，執(zhí)行速度較快；當(dāng)正則節(jié)點(diǎn)之間距離較遠(yuǎn)時(shí)，執(zhí)行速度較慢。最后統(tǒng)計(jì)了四種交叉機(jī)制在G6上，M=200 時(shí)的平均權(quán)重和最小權(quán)重?？梢钥闯觯琇C和ST的平均權(quán)重幾乎相同，而DT和Prüfer的平均權(quán)重較大，同時(shí)LC在最小權(quán)重方面性能更好。

表3 記錄了在G3～G5的規(guī)模圖上，RW+0.6+0.1、RW+0.8+0.05、RW+0.8+0.1不同參數(shù)組合下GA的執(zhí)行時(shí)間。從表中可以看出，LC 機(jī)制比其他交叉機(jī)制需要更少的執(zhí)行時(shí)間，性能優(yōu)于其他交叉機(jī)制。

表3 不同參數(shù)組合下遺傳算法的執(zhí)行時(shí)間Table 3 Execution time of genetic algorithm under different parameter combinations

如圖8是在G1～G3上采用典型參數(shù)的GA取得的最佳權(quán)重，從圖中可以看出，LC機(jī)制的遺傳算法在G1～G3上的權(quán)值均小于其他交叉機(jī)制，表明在此規(guī)模上LC 機(jī)制的性能最好。

圖8 GA在典型參數(shù)下的權(quán)重Fig.8 Weight of GA under typical parameters

如圖9（a）、（b）分別記錄了GA 在G7、G8規(guī)模上生成前30代獲得的最佳權(quán)重。從圖中可以看出，DT算法收斂速度最快，ST 次之，而LC 收斂速度最慢。這是由于LC 的時(shí)間復(fù)雜度與父樹的長(zhǎng)度成正相關(guān)，而與圖的大小無關(guān)。所以使用LC 機(jī)制的GA 可以達(dá)到30 代，而其他機(jī)制的遺傳算法只能達(dá)到1～2 代。這個(gè)特點(diǎn)使得LC 很容易采取額外的措施，如擴(kuò)大種群規(guī)?；蛱岣咦儺惛怕?，以獲得更好的解。

圖9 大規(guī)模圖上GA的最佳權(quán)重Fig.9 Optimal weight of GA on large-scale graphs

關(guān)于遺傳算法不同交叉機(jī)制的分析如表4所示。

表4 不同交叉機(jī)制的對(duì)比分析Table 4 Comparative analysis of different crossover mechanisms

4.4 智能優(yōu)化算法的性能對(duì)比

針對(duì)智能優(yōu)化算法及其改進(jìn)算法進(jìn)行對(duì)比，總結(jié)各算法的原理及優(yōu)缺點(diǎn)，具體的算法性能分析對(duì)比如表5所示。

表5 智能優(yōu)化算法及其改進(jìn)算法的對(duì)比分析Table 5 Comparative analysis of intelligent optimization algorithms and their improved algorithms

5 結(jié)束語

本文詳細(xì)介紹了啟發(fā)式算法、信息傳播算法、智能優(yōu)化算法的相關(guān)知識(shí)，對(duì)Steiner樹優(yōu)化實(shí)例的求解進(jìn)行概括，從交叉機(jī)制、收斂速度、有效性等方面進(jìn)行綜述，給出求解最優(yōu)Steiner 樹問題的算法研究趨勢(shì)和發(fā)展方向。Steiner 樹及其變體問題具有高度復(fù)雜性，且為NP難問題。在實(shí)際應(yīng)用中，往往存在多個(gè)沖突的優(yōu)化目標(biāo)，如最小化成本、最小化延遲等。針對(duì)大規(guī)模問題，傳統(tǒng)的求解方法可能會(huì)變得非常耗時(shí)，甚至不切實(shí)際。盡管對(duì)于Steiner樹優(yōu)化問題的研究已取得了一些進(jìn)展，但仍存在許多挑戰(zhàn)和待解決的問題，如在考慮實(shí)際約束的同時(shí)，如何設(shè)計(jì)快速有效的算法以在合理的時(shí)間內(nèi)找到全局最優(yōu)解；針對(duì)大規(guī)模問題時(shí)，如何提高算法的可伸縮性。由于LC是基于Steiner樹的GA中第一個(gè)未使用貪婪算法的交叉機(jī)制，大大減少了計(jì)算時(shí)間。因此，未來的工作應(yīng)聚焦于探索結(jié)合不同算法和技術(shù)的新方法，以進(jìn)一步提高解的質(zhì)量和求解能力，并研究GAS和LC在其他實(shí)際中的應(yīng)用，如SMT、組播通信和傳輸路由設(shè)計(jì)等。