鞠成安,王妮婭,HANZALA,張書凡,毛劍琳

(昆明理工大學(xué) 信息工程與自動化學(xué)院,昆明 650500)

0 引 言

在交通、通信、電路芯片設(shè)計(jì)等領(lǐng)域[1-6],度約束最小生成樹(degree-constrained minimum spanning trees,DCMST)問題是一個重要的基本問題。實(shí)踐中往往將問題模型簡化為度約束最小生成樹問題,考慮結(jié)點(diǎn)的脆弱性、能源的有限性等問題,在每個結(jié)點(diǎn)上增加度的限制,以確保圖的暢通性、資源的合理分配。

對于度約束最小生成樹問題,通常采用啟發(fā)式算法[7-9]去搜尋其最優(yōu)解。遺傳算法作為一種啟發(fā)式搜索優(yōu)化算法,為求解DCMST問題提供了有效的途徑。應(yīng)用遺傳算法對樹進(jìn)行編碼一般分為點(diǎn)編碼和邊編碼。文獻(xiàn)[10]首次運(yùn)用Prüfer點(diǎn)編碼,利用遺傳算法求解度約束最小生成樹問題,國內(nèi)也有很多人采用Prüfer編碼對該問題進(jìn)行求解[11-12]。但是,Prüfer編碼在局部性與遺傳性方面有很大的劣勢,并且隨著問題規(guī)模的增大表現(xiàn)會更差[13]。文獻(xiàn)[14]提出一種邊集編碼方式,并證明了此種編碼方式在遺傳算法中有著很好的局部性與遺傳性,尤其在數(shù)據(jù)規(guī)模較大的實(shí)例中展現(xiàn)了很好的優(yōu)越性。文獻(xiàn)[15]采用邊集編碼提出一種混合穩(wěn)態(tài)遺傳算法,該算法設(shè)計(jì)了針對該問題的交叉算子,具有更好的遺傳性。在局部搜索方面,文獻(xiàn)[16]提出蟻群算法中應(yīng)用雙邊替換和單邊替換的局部搜索策略,文獻(xiàn)[15]中改進(jìn)了單邊替換的搜索策略,將其分為兩個階段,進(jìn)一步提高了算法局部搜索能力。近年來,文獻(xiàn)[17]針對大規(guī)模結(jié)點(diǎn)問題,提出一種嫁接和剪接的搜索策略,從正、反兩方面出發(fā)加速搜索過程;文獻(xiàn)[18]提出一種遺傳交叉算子,以解決產(chǎn)生不可行后代解的問題;文獻(xiàn)[16]對分支定界法進(jìn)行改進(jìn),使其能在動態(tài)的環(huán)境中得到較為理想的結(jié)果;文獻(xiàn)[19]提出一種新型智能搜索算法煙花算法,因其隨機(jī)性強(qiáng)、精度高,具有較好的全局收斂性。

然而,以上算法仍然在收斂速度和局部搜索能力上有不小的提升空間,為此,本文提出了一種融合禁忌搜索并增強(qiáng)局部搜索的穩(wěn)態(tài)遺傳算法(improved hybrid steady-state genetic algorithm with local search strategy,IHSGA)。初始種群的質(zhì)量直接影響算法的收斂速度和性能,生成高質(zhì)量的初始種群是遺傳算法成功的關(guān)鍵,為了能在生成初始解時形成較好的樹結(jié)構(gòu),本文提出了服從邊隸屬度值的度約束初始生成樹算法;在IHSGA算法后期,為了增強(qiáng)局部搜索能力,在局部搜索條件里設(shè)置了一個自適應(yīng)變量,并提出“邊替換+點(diǎn)替換”的局部搜索方法,進(jìn)一步提高解的質(zhì)量;為了防止對相同的子代進(jìn)行大量重復(fù)的搜索,在遺傳算法的基礎(chǔ)上引入禁忌搜索策略;通過將該算法用于對DCMST問題進(jìn)行求解,與混合穩(wěn)態(tài)遺傳算法[15]、ABA算法[8]得到的結(jié)果相比較,本文算法所得解的質(zhì)量和穩(wěn)定性都有較大的提高。

1 問題描述

給定一個無向連通加權(quán)圖G(V,E,w),其中V是結(jié)點(diǎn)或頂點(diǎn)的集合,E是邊的集合,wij是端點(diǎn)i和端點(diǎn)j之間連接的邊eij∈E相關(guān)聯(lián)的正權(quán)重,則度約束最小生成樹問題旨在找到圖G的最小生成樹T,并且其每個結(jié)點(diǎn)要么是葉子結(jié)點(diǎn),要么在T中最多連接d條邊,即度不超過d,d是一個給定的正整數(shù)。

(1)

(2)

1≤di≤dc,i=1,2,…,n

(3)

(4)

(5)

xij∈{0,1},i,j=1,2,…,n

(6)

(1)—(6)式所述數(shù)學(xué)模型由DCMST問題的優(yōu)化目標(biāo)函數(shù)及約束構(gòu)成,其中:(1)式為DCMST問題的優(yōu)化目標(biāo);(2)式為生成樹包含不同結(jié)點(diǎn)的n-1條邊;(3)式為每個結(jié)點(diǎn)應(yīng)滿足的度約束條件,dc為給定的度約束值;(4)式表示生成樹無為環(huán)路;(5)式為所有結(jié)點(diǎn)的度值和;(6)式表示當(dāng)xij=1時,由結(jié)點(diǎn)〈vi,vj〉構(gòu)成的邊是生成樹的一條邊。

2 融合局部搜索策略的改進(jìn)穩(wěn)態(tài)遺傳算法

2.1 初始解的生成

2.1.1 編碼和解碼

為了表示度約束生成樹的一個可能的解決方案,即遺傳算法中的染色體, IHSGA使用了邊集編碼[12]。按照這種編碼方式,每個解包含一組邊,數(shù)量為|V|-1。選擇這種編碼的原因是它不僅提供了較高的局部性和遺傳性,而且對于特定問題的遺傳算子有很強(qiáng)的適應(yīng)性。

F(Ti)作為生成樹可行解的適應(yīng)度值,被計(jì)算為與其生成樹相關(guān)聯(lián)的邊的成本之和。如果Ti的適應(yīng)度值小于Tk,那么Ti會被認(rèn)為是比Tk更優(yōu)的解決方案。

2.1.2 服從邊隸屬度值的度約束初始生成樹算法

目前的初始解生成方式都采用隨機(jī)生成方法,生成的初始解的質(zhì)量較差。通過采用服從邊隸屬度值的生成樹算法來引導(dǎo)初始解的生成,可以提高初始種群的質(zhì)量。該算法將每個點(diǎn)都視為一個中心,其余各點(diǎn)對于這個中心點(diǎn)都有一個隸屬度,距離越近的點(diǎn)隸屬度越大,反之越小。隸屬度的大小由邊的權(quán)重來確定,將一個中心點(diǎn)周圍的邊的權(quán)重取倒數(shù),然后進(jìn)行歸一化操作,得到周圍點(diǎn)的隸屬度的和總等于1,即

(7)

(7)式中:uij為隸屬度值,介于0～1之間;ωij為邊eij的權(quán)值。

滿足度約束初始解的生成過程如圖1所示。

圖1 初始解的生成Fig.1 Initial solution generation

圖1a給出了一個賦予權(quán)值的完全圖,在生成初始解前將每一個點(diǎn)都作為中心點(diǎn),根據(jù)(7)式計(jì)算其余各點(diǎn)到中心點(diǎn)的隸屬度,結(jié)果如表1所示。

表1 隸屬度值Tab.1 Membership value

隨機(jī)選擇一個點(diǎn)v1(如圖1b),根據(jù)計(jì)算好的隸屬度,以隸屬度值選擇下一個點(diǎn)v2(如圖1c),將v1、v2兩點(diǎn)放入集合U中并將其度值加1,代表這兩個點(diǎn)都已經(jīng)連接了一條邊,同時把邊ev1v2添加到集合Ti中;此時以v1、v2作為中心點(diǎn),根據(jù)表1選擇出兩條以v1、v2為端點(diǎn)的邊,如圖1c中的邊ev1v2、ev2v3,再根據(jù)表1的隸屬度值選擇邊,若選擇到了邊ev1v3,那么就將v3放入集合U中并將點(diǎn)v1、v3的度值加1。在每次加邊的過程中都會判斷與其相關(guān)的點(diǎn)是否超過了度的約束且生成的子樹不會成環(huán)。在初始解生成過程中,如果出現(xiàn)了滿度的點(diǎn)(如圖1f的點(diǎn)v1),那么在下一次尋邊時就不會考慮該點(diǎn)周圍的邊。此后,該算法每次迭代都會搜索到一條邊,直到集合U中包含了圖中所有的點(diǎn),此時已經(jīng)構(gòu)造了一個可行的度約束生成樹Ti(如圖1f)。每生成一個初始解都要對照目前種群里的每個解檢查解Ti的唯一性。如果當(dāng)前生成的新解是唯一的,則將其包含在群體中,否則將其丟棄。

一般的遺傳算法隨機(jī)產(chǎn)生的初始種群質(zhì)量較低,但初始種群的質(zhì)量往往影響著算法的收斂速度,本文采用一種服從邊隸屬度值的度約束生成樹算法和隨機(jī)方式的種群生成方法,在保證種群多樣性前提下,使部分子樹有更好的結(jié)構(gòu)。

2.2 基于二元競爭選擇法與最大邊距法的交叉算子

文獻(xiàn)[15]提出的交叉算子是一種針對特定問題的算子,它試圖在新生成的子代中盡可能多地繼承父代個體的好邊,同時保持子代的所有非葉子結(jié)點(diǎn)的度約束。但是在算法后期種群的適應(yīng)度值相差不大,該交叉算子并不能很好地讓子代繼承到父代優(yōu)秀的結(jié)構(gòu),所以本文在交叉算子的父代選擇策略上采用二元競爭選擇法與最大邊距法相結(jié)合的方法(BST-maxdis)表示為

(8)

(8)式中:p1,2代表交叉算子選擇出來的父代;BST為二元競標(biāo)賽選擇算法;max{dis(T1,T2,T3,T4)}是在候選解中選出邊的距離最遠(yuǎn)的兩個父代,Niter為迭代的代數(shù);n為設(shè)置的總迭代次數(shù)。

在算法迭代前期使用二元競爭選擇法對父代進(jìn)行選擇,能夠盡量讓子代繼承適應(yīng)度值小的父代的邊,讓種群向好的方向發(fā)展,但在算法后期種群的適應(yīng)度值相差不大,所以選擇邊距較大的兩個父代進(jìn)行交叉,使子代繼承不同的樹結(jié)構(gòu),提升種群的多樣性,防止算法陷入局部最優(yōu)。

2.3 改進(jìn)的局部搜索策略

2.3.1 局部搜索條件的改進(jìn)

因?yàn)橛卸燃s束的要求,滿度的點(diǎn)可能會有更多、更好邊的組合。因此,要對此類點(diǎn)進(jìn)行局部搜索。為了進(jìn)一步提高當(dāng)前生成的子代Tc的質(zhì)量,在文獻(xiàn)[15]的基礎(chǔ)上,考慮到算法后期局部搜索能力較弱的問題,本文給出局部搜索的應(yīng)用條件為

(9)

(9)式中:Tgb是當(dāng)前種群中最佳的解決方案;Tc是當(dāng)前生成的子代;F(Tgb),F(Tc)分別表示Tgb,Tc的適應(yīng)度值;α×ek/kmax是根據(jù)經(jīng)驗(yàn)確定的自適應(yīng)變量,會隨著迭代次數(shù)k值的增加而增大;dis(Tgb,Tc)表示Tgb和Tc之間的距離,以Tgb與Tc相異的邊來表示,neq表示Tgb與Tc共同邊的數(shù)量。

(9)式在算法前期對適應(yīng)度值要略低于Tgb,但沒有距離Tgb足夠遠(yuǎn)的子代進(jìn)行局部搜索,這樣不僅增強(qiáng)了前期的全局搜索能力,也節(jié)省了計(jì)算時間;在算法的后期,因?yàn)棣痢羍k/kmax是一個隨著迭代次數(shù)k增加而增大的自適應(yīng)變量,所以能夠針對dis(Tgb,Tc)較小時的Tc,對其進(jìn)行局部搜索,進(jìn)一步提高當(dāng)前解的質(zhì)量。

2.3.2 局部搜索方法的改進(jìn)

文獻(xiàn)[15]運(yùn)用了“邊替換”進(jìn)行局部搜索,先隨機(jī)選取一條邊,然后在該邊的所有候選非相鄰邊中選取一條邊替換它,使得當(dāng)前解得到一定提升。IHSGA在該方法的基礎(chǔ)上提出“點(diǎn)替換”的局部搜索策略,進(jìn)一步增強(qiáng)算法的局部搜索能力?！包c(diǎn)替換”的中心思想是將一個子樹的葉子結(jié)點(diǎn)進(jìn)行兩兩替換,在替換的過程中找到更優(yōu)的組合,使整個樹的結(jié)構(gòu)更加緊湊,從而達(dá)到減小總權(quán)重的目的。定義一個針對葉子結(jié)點(diǎn)交換的增益函數(shù)定義為

gain(i,j,u,v)=F(T1)-F(T2)=

ωij+ωuv-(ωiv+ωuj)

(10)

(10)式中:結(jié)點(diǎn)j、v為葉子結(jié)點(diǎn);結(jié)點(diǎn)i、u為樹的固定結(jié)點(diǎn);T1為葉子結(jié)點(diǎn)交換前的樹;T2為葉子結(jié)點(diǎn)交換后的樹。

在點(diǎn)替換的每次迭代過程中,當(dāng)葉子結(jié)點(diǎn)交換后的增益函數(shù)為正值時,就允許本次結(jié)點(diǎn)交換,否則就放棄交換。

2.4 禁忌搜索策略

穩(wěn)態(tài)遺傳算法在后期產(chǎn)生了大量結(jié)構(gòu)相似的子代,為了減少對大量結(jié)構(gòu)相似的解進(jìn)行搜索的工作量,引入禁忌搜索。禁忌搜索算法是一種全局逐步尋優(yōu)的搜索算法,模擬人的思維模式,用長期記憶或短期記憶來誘導(dǎo)算法跳出局部最優(yōu)解,避免重復(fù)低效搜索。借助禁忌搜索的記憶功能,可以將已經(jīng)進(jìn)行過局部搜索的子樹放入禁忌表中。

禁忌表中的解并非完全被隔絕,也可以通過特赦準(zhǔn)則對優(yōu)秀的解進(jìn)行釋放,保留當(dāng)前種群最優(yōu)個體的結(jié)構(gòu),引導(dǎo)種群向更好的方向發(fā)展。其它禁忌表中的解需要度過預(yù)設(shè)的禁忌周期,才可解除禁忌。禁忌表中元素的鄰域結(jié)構(gòu)的條件定義為

dis(TTS,Tc)

(11)

(11)式中:TTS為禁忌表中的解。

加入禁忌搜索后,可以防止算法相同或相似的解進(jìn)行大量重復(fù)的搜索,提高了算法的運(yùn)行效率。

2.5 融合局部搜索策略的改進(jìn)混合穩(wěn)態(tài)遺傳算法流程

在文獻(xiàn)[15]給出的穩(wěn)態(tài)遺傳算法中,還應(yīng)用了一個附加的擾動策略,以便在整個搜索過程中保持種群的多樣性。本文在該算法的基礎(chǔ)上改進(jìn)初始解的生成方式,引入了禁忌搜索并改進(jìn)了局部搜索策略。通過服從邊隸屬度值的度約束初始生成樹算法來引導(dǎo)初始種群的生成,有效提高初始種群的質(zhì)量;在種群中選取適當(dāng)?shù)母复M(jìn)行交叉操作或變異操作,再通過禁忌搜索和改進(jìn)的自適應(yīng)質(zhì)量-距離特征公式和改進(jìn)的搜索策略進(jìn)行局部搜索,以進(jìn)一步提高當(dāng)前子代的質(zhì)量。具體流程如算法1所示。

算法1融合局部搜索策略的改進(jìn)混合穩(wěn)態(tài)遺傳算法(IHSGA)

輸入:一個連通帶有權(quán)值的無向完全圖G(V,E,w),正整數(shù)常量d

輸出:帶有度約束的最小生成樹Tgb

1.生成初始解種群

2.Tgb→ 當(dāng)前種群中的最優(yōu)解

3.while未達(dá)到終止條件 do

4.BST-maxdis (T1,T2,…,Tpop) →p1,p2

5.交叉、變異 →Tc

6.ifTc不在禁忌表里 then

8.Tc進(jìn)行局部搜索//局部搜索

9.end if

10.end if

11.ifTc是唯一解 then

12.ifTc適應(yīng)度值優(yōu)于Tgbthen

13.Tc→Tgb;

14.end if

15.end if

16.end while

3 仿真測試與分析

3.1 仿真設(shè)置

仿真采用歐幾里得(CRD)和非歐幾里得(SHRD)兩個典型的標(biāo)準(zhǔn)算例[20]。其中,前者由大小從50到100個頂點(diǎn)不等的圖形組成。這種圖中的頂點(diǎn)是在二維平面中均勻隨機(jī)生成的,邊權(quán)重是兩個頂點(diǎn)之間的歐幾里得距離。由于歐式距離形成的圖復(fù)雜度較低,因而文獻(xiàn)[17]構(gòu)建一個較難的人工算例。該數(shù)據(jù)集由大小從15到30個頂點(diǎn)不等的圖形組成。第一個結(jié)點(diǎn)通過長度為ll的邊連接到所有其他結(jié)點(diǎn),第二個結(jié)點(diǎn)通過長度為2l的邊連接到除第一個結(jié)點(diǎn)之外的所有結(jié)點(diǎn),以此類推構(gòu)造點(diǎn)之間的非歐幾里得距離。通過在1和18之間增加均勻分布的擾動來稍微隨機(jī)化這個參數(shù)。這降低了存在大量最佳解決方案的可能性,但不會改變問題的潛在復(fù)雜性。實(shí)驗(yàn)中參數(shù)設(shè)置如表2所示。

表2 實(shí)驗(yàn)參數(shù)表Tab.2 Experimental parameter

3.2 算法測試結(jié)果與分析

為了驗(yàn)證所提出算法的有效性,本文與混合穩(wěn)態(tài)遺傳算法(Hssga)[15]和改進(jìn)蟻群算法(ABA)[8]在標(biāo)準(zhǔn)算例上進(jìn)行實(shí)驗(yàn)比對。每個算例在3種算法上單獨(dú)運(yùn)行50次,將度約束分別設(shè)置為2、3、4,對運(yùn)行結(jié)果的最優(yōu)值、均值和標(biāo)準(zhǔn)差進(jìn)行比對。本文實(shí)驗(yàn)環(huán)境是Core(TM)i7-8700K CPU@3.70GHz,內(nèi)存32GB,開發(fā)工具是python3.7。

表3報告了3種算法在CRD和SHRD實(shí)例上的運(yùn)行結(jié)果。表3中,實(shí)例名稱數(shù)字的前兩位代表數(shù)據(jù)的頂點(diǎn)數(shù),最后一位代表數(shù)據(jù)集的編號;|V|列表示與其實(shí)例對應(yīng)的頂點(diǎn)數(shù);列d表示對其對應(yīng)實(shí)例的度約束。

表3 仿真實(shí)驗(yàn)對比Tab.3 Simulation experiment comparison

從表3可見,CRD數(shù)據(jù)集上的表現(xiàn),IHSGA算法能夠得到更優(yōu)的最優(yōu)值,且平均值和標(biāo)準(zhǔn)差有明顯的改善,說明IHSGA算法輸出的結(jié)果有更好的穩(wěn)定性。對于SHRD數(shù)據(jù)集,IHSGA算法在最優(yōu)值上略優(yōu)于其他兩種算法,且3種算法得到的標(biāo)準(zhǔn)差都比較小,可見IHSGA算法在穩(wěn)定性方面也有一定程度的優(yōu)化。在SHRD200、SHRD259、SHRD300數(shù)據(jù)集中IHSGA算法的標(biāo)準(zhǔn)差要大于Hssga算法,導(dǎo)致這種情況的原因是:IHSGA算法雖然整體結(jié)果要優(yōu)于Hssga算法,但是在數(shù)據(jù)離散程度大于Hssga算法。

為了進(jìn)一步展示IHSGA算法相較于Hssga算法的優(yōu)越性,圖2—圖3分別展示了算法在迭代中種群的平均適應(yīng)度值、種群最優(yōu)值的變化情況。本次實(shí)驗(yàn)隨機(jī)選擇了兩個標(biāo)準(zhǔn)算例(SHRD258、SHRD300),且d取值為3。圖2表明,IHSGA算法得到的初始種群要優(yōu)于Hssga算法,且收斂得更快。圖3表明,IHSGA算法在1 000代左右就找到了當(dāng)前最優(yōu)解的發(fā)展方向,且在3 000代之前找到最優(yōu)解,而Hssga算法需要在更多的迭代次數(shù)后找到最優(yōu)解,說明IHSGA算法有更好的局部搜索能力。由以上分析可得,IHSGA算法能夠得到更優(yōu)的解,并且具有很好的穩(wěn)定性,能夠在度約束最小生成樹問題中得到很好的應(yīng)用。

圖2 平均適應(yīng)度值變化曲線Fig.2 Variation curves of the average fitness value

圖3 最優(yōu)值適應(yīng)度值變化曲線Fig.3 Variation curves of the best fitness value

4 結(jié) 論

針對混合遺傳算法存在求解質(zhì)量不穩(wěn)定、局部搜索不徹底等問題,本文以初始解和局部搜索為優(yōu)化目標(biāo),提出一種服從邊隸屬度值的度約束初始生成樹算法,在生成初始解時進(jìn)行優(yōu)化。首先,設(shè)置自適應(yīng)變量對局部搜索的條件進(jìn)行改進(jìn)并提出點(diǎn)替換的搜索策略,克服原算法對部分解不能深入搜索的缺點(diǎn);然后,在交叉算子的父代選擇中,提出二元競爭選擇法與最大邊距法相結(jié)合的方法,使產(chǎn)生的子代具有更好的結(jié)構(gòu);最后,加入禁忌搜索,防止算法對相同或相似的解進(jìn)行大量重復(fù)的搜索。實(shí)驗(yàn)證明本文算法在迭代次數(shù)相同的前提下,種群平均適應(yīng)度要明顯優(yōu)于對比算法,并且標(biāo)準(zhǔn)差也較小,得到的結(jié)果是比較穩(wěn)定的。實(shí)驗(yàn)結(jié)果說明融合禁忌搜索并改進(jìn)局部搜索的混合穩(wěn)態(tài)遺傳算法是一種有效可行的改進(jìn)方法。未來將結(jié)合移動機(jī)器人網(wǎng)絡(luò)問題做進(jìn)一步探索。