王海紅，李 林，劉 莉

(青島科技大學(xué) 信息科學(xué)技術(shù)學(xué)院，山東 青島 266061)

0 引言

現(xiàn)實(shí)中大部分的網(wǎng)絡(luò)系統(tǒng)都可以用最小生成樹作為簡(jiǎn)化模型來(lái)分析。在特定情況下，為了確保圖的暢通性，通過(guò)在最小生成樹模型中添加節(jié)點(diǎn)度數(shù)的限制，從而生成了度約束的最小生成樹模型(DCMST)。如何求解該問(wèn)題是一個(gè)NP問(wèn)題，許多專家、學(xué)者對(duì)此進(jìn)行了大量的研究工作。在求解有約束的問(wèn)題時(shí)，智能控制方法往往具有操作簡(jiǎn)單，適用性強(qiáng)的優(yōu)點(diǎn)，因此受到廣泛關(guān)注。越來(lái)越多的智能控制方法在該問(wèn)題上得到很好的應(yīng)用，如禁忌搜索算法[1]、模擬退火算法[2]、灰狼算法[3]、布谷鳥算法[4]等。文獻(xiàn)[5]提出了一種能夠生成優(yōu)質(zhì)近似解的算法，并采用改進(jìn)的禁忌搜索算法和模擬退火算法對(duì)該近似解實(shí)施進(jìn)一步優(yōu)化。文獻(xiàn)[6]使用最小生成樹模型構(gòu)造網(wǎng)絡(luò)，采用人工蜂群算法來(lái)進(jìn)行節(jié)點(diǎn)尋優(yōu)。文獻(xiàn)[7]針對(duì)同時(shí)考慮多目標(biāo)和度約束情況下的最小生成樹求解問(wèn)題，對(duì)傳統(tǒng)的蟻群算法進(jìn)行優(yōu)化，設(shè)計(jì)了三種信息素?cái)?shù)量模型，并對(duì)信息素的持久度進(jìn)行設(shè)計(jì)更新，進(jìn)而影響蟻群尋優(yōu)軌跡，提高求解效率。從實(shí)驗(yàn)過(guò)程和數(shù)據(jù)來(lái)看，上面的提到的這些智能方法一定程度上存在操作過(guò)程相對(duì)復(fù)雜，改進(jìn)效果并不十分明顯等問(wèn)題。

遺傳算法由于其編碼方式簡(jiǎn)單，實(shí)現(xiàn)容易且效果較好，而在該問(wèn)題上有更廣泛的應(yīng)用和改進(jìn)[8]。文獻(xiàn)[9]對(duì)傳統(tǒng)遺傳算法進(jìn)行優(yōu)化，提出了一種帶有加速和調(diào)節(jié)算子作為激勵(lì)的遺傳算法，從正反兩方面出發(fā)來(lái)加速搜索最小生成樹過(guò)程。文獻(xiàn)[10]提出了一種以過(guò)程控制為基礎(chǔ)的生成樹編碼方法—PC編碼，進(jìn)而給出以PC-Prim算法作為譯碼器的求解DC-MST問(wèn)題的遺傳算法來(lái)求解最小生成樹。文獻(xiàn)[11]采用單親遺傳算法來(lái)求解該問(wèn)題，能提高個(gè)體的有效性，但仍存在變異產(chǎn)生不可行解以及解個(gè)體跳躍問(wèn)題，求解效率不高。

針對(duì)以上問(wèn)題，本文提出改進(jìn)單親遺傳算法的變異算子方法，并引入自適應(yīng)變異率，求解過(guò)程中可以避免不可行解的產(chǎn)生，并提高求解效率。同時(shí)融合模擬退火算法，來(lái)解決個(gè)體的跳躍問(wèn)題，提高獲得全局最優(yōu)解的可能性。最后，進(jìn)行實(shí)驗(yàn)驗(yàn)證，與標(biāo)準(zhǔn)單親遺傳算法的結(jié)果進(jìn)行比較，證明了所提算法的有效性和優(yōu)越性。

1 度約束的最小生成樹模型

設(shè)G=(V,E,C)是一個(gè)連通賦權(quán)網(wǎng)絡(luò)圖。其中V={v1,v2,...,vn}是圖G的節(jié)點(diǎn)集合，代表一個(gè)個(gè)節(jié)點(diǎn)。E={e1,e2,...,en}是圖G的邊集合，代表節(jié)點(diǎn)之間相互連接的邊。C={c1,c2,...,cn}是每條邊上的正實(shí)數(shù)權(quán)重，用來(lái)表示相鄰節(jié)點(diǎn)間的距離。G的生成樹規(guī)定為一棵能含有G中所有節(jié)點(diǎn)的無(wú)向樹G′=(V,T)，T∈E，T中沒(méi)有回路并且能將圖中全部節(jié)點(diǎn)都連接起來(lái)。因此，構(gòu)建G的最小生成樹需要找到各邊權(quán)重之和最小的生成樹。若圖T是圖G的最小生成樹，D={d1,d2,...,dn}是每個(gè)節(jié)點(diǎn)的度約束，且對(duì)于任意的節(jié)點(diǎn)vi∈V(i=1,2,...,n)都有dvi

度約束最小生成樹目標(biāo)函數(shù)如下：

(1)

約束函數(shù)如下：

(2)

(3)

(4)

xij∈{0,1}?vi∈V,vj∈V,i,j=1,2,......n

(5)

約束條件(2)能夠確保最終得到的生成樹有n-1條邊。約束條件(3)限定了在一步步得到最小生成樹的操作期間任何一個(gè)節(jié)點(diǎn)都始終不包含通向自身的回路。

2 基于單親遺傳算法和模擬退火算法的改進(jìn)SAPGA算法

2.1 初始化

本節(jié)研究算法的染色體采用Prufer數(shù)列[14]編碼。根據(jù)度約束的最小生成樹對(duì)節(jié)點(diǎn)的連接邊都是有數(shù)量限制的原則，使用生成的Prufer數(shù)列作為初始種群時(shí)，需要考慮到度數(shù)限制，避免產(chǎn)生不可行解[15]，使求解更加高效。

假設(shè)這個(gè)問(wèn)題的度約束序列是b=(b1,b2,..,bn)，那么根據(jù)每個(gè)節(jié)點(diǎn)的度約束可以得到一個(gè)數(shù)列S={1，1，…1，2，2，…2，…i，i，…，i，…n，n，…，n}，該數(shù)列中數(shù)字i的個(gè)數(shù)為bi-1個(gè)。獲得初始種群的Prufer數(shù)的具體操作為：從數(shù)列S中隨機(jī)地取出n-2個(gè)數(shù)組成一個(gè)新的數(shù)列。從上述數(shù)列中得到的任何一個(gè)包含n-2個(gè)數(shù)的隨機(jī)排列組合，都能夠作為一棵生成樹對(duì)應(yīng)的Prufer數(shù)，并且符合每一個(gè)節(jié)點(diǎn)的度約束要求。重復(fù)地進(jìn)行從數(shù)列S中隨機(jī)取n-2個(gè)數(shù)的操作，直至達(dá)到初始化種群所要求的最大個(gè)體數(shù)目N。這樣就得到了初始種群 ，既充分滿足每個(gè)結(jié)點(diǎn)的度約束，又不會(huì)出現(xiàn)不可行解。

設(shè)置初始較高溫度為T0，最低溫度Tmin，全局最優(yōu)解Pg，及全局最優(yōu)解對(duì)應(yīng)的適應(yīng)度Fg。

2.2 適應(yīng)度函數(shù)

本文使用適應(yīng)度函數(shù)來(lái)衡量遺傳操作過(guò)程中每個(gè)個(gè)體的適應(yīng)度，并以此來(lái)得出優(yōu)勝劣汰的標(biāo)準(zhǔn)。根據(jù)前面描述的度約束最小生成樹問(wèn)題的模型，適應(yīng)值函數(shù)F(x)設(shè)置如下。

(6)

2.3 選擇過(guò)程

遺傳算法的選擇過(guò)程通常采取相對(duì)公平的輪盤賭策略[16]。輪盤賭選擇的基本思想是每個(gè)個(gè)體被選中的概率與其適應(yīng)度大小成正比。對(duì)于上一代種群中適應(yīng)度非常好的個(gè)體，如果采取傳統(tǒng)的輪盤賭選擇策略可能會(huì)將其丟棄，所以本文采用輪盤賭策略加保留最優(yōu)個(gè)體的選擇方法。即先將最優(yōu)個(gè)體保留下來(lái)，然后將父代和子代中按輪盤賭選出N-1個(gè)個(gè)體。

2.4 優(yōu)化變異操作

變異的本質(zhì)是將個(gè)體的遺傳基因發(fā)生改變，但如果采用一般的變異方式會(huì)導(dǎo)致很多不可行解的產(chǎn)生，從而導(dǎo)致求解效率大大降低，根據(jù)種群生成可知，如果不產(chǎn)生新的數(shù)，只是改變數(shù)列中數(shù)字的排列順序，則該數(shù)列解的可行性不會(huì)由此改變。據(jù)此，本文摒棄遺傳算法中的交叉操作，只進(jìn)行變異操作，并引入自適應(yīng)變異率，提出兩種新的變異算子來(lái)避免產(chǎn)生不可行解，這樣在很大程度上簡(jiǎn)化了求解的復(fù)雜度。

2.4.1 優(yōu)化變異算子生成方式

本文設(shè)計(jì)兩種不會(huì)產(chǎn)生不可行解的變異算子，具體生成方法如下。

1)隨機(jī)插入變異：首先要隨機(jī)生成一個(gè)位置i(i不大于基因總數(shù))，將它記為即將插入的位置。再?gòu)拇砀篙厒€(gè)體的Prufer數(shù)列中隨機(jī)地取出一個(gè)子數(shù)列，將取出的子數(shù)列插入剛剛標(biāo)記的位置，這樣就得到了新的子代個(gè)體。這個(gè)操作僅僅是移動(dòng)原數(shù)列中的某些數(shù)字，因此不會(huì)導(dǎo)致不可行解的出現(xiàn)。

操作舉例：隨機(jī)選擇的子串為4、5、6，隨機(jī)產(chǎn)生的位置為10，則位移變異操作前后的子串情況如下：

P：1 2 3 [4 5 6] 7 8 9 10 11 12 13 ?P’：1 2 3 7 8 9 [4 5 6] 10 11 12 13

2)后移變異：首先生成一個(gè)隨機(jī)數(shù)j(j小于基因總數(shù))，將父代個(gè)體的Prufer數(shù)列依次后移j個(gè)位置，該操作簡(jiǎn)單易行，并且很明顯在這個(gè)過(guò)程中可以保證解的可行性。操作舉例如下：

假設(shè)生成隨機(jī)數(shù)為1，則每個(gè)數(shù)都后移一位。

P：1 2 3 4 5 6 7 8 9 10 11 12 13 ?P’：13 1 2 3 4 5 6 7 8 9 10 11 12

2.4.2 改進(jìn)變異率

為加快算法的求解速度，設(shè)計(jì)自適應(yīng)變異率。訓(xùn)練前期較大的變異率能夠保證較高的個(gè)體多樣性，而后期應(yīng)該采取較小的變異率，能加快收斂。因此，設(shè)計(jì)自適應(yīng)更新學(xué)習(xí)因子如下：

pv=pv·e(1-k/kmax)

(7)

其中:k表示目前迭代次數(shù)，kmax表示最大迭代次數(shù)。隨著求解的進(jìn)行，變異率隨迭代次數(shù)的增加而變小，最終趨近于0。使得迭代后期逐漸減小變異操作的變化率，以加快算法的收斂速度。

2.5 判斷是否接受新解

模擬退火算法的思想是以一定概率接受一個(gè)較差的解[6]，對(duì)于每一個(gè)溫度Tk，執(zhí)行如下操作：

計(jì)算新生成染色體的適應(yīng)度函數(shù)值F(x)，以概率p接受這個(gè)新解，在0到1中生成一個(gè)隨機(jī)數(shù)q，若p>q，則更新解個(gè)體；否則，保持原來(lái)的解個(gè)體。

(8)

2.6 改進(jìn)算法流程

本文所提算法的基本步驟總結(jié)如下。

步驟1：按照前面的方法生成一個(gè)含有N個(gè)個(gè)體的初始群體P0，將初始溫度設(shè)為100 ℃，最低溫度設(shè)為0 ℃。設(shè)置固定溫度下的最大迭代次數(shù)kmax，記錄初始種群中適應(yīng)度最小的Pg為全局最優(yōu)解，以及全局最優(yōu)解對(duì)應(yīng)的適應(yīng)度Fg。

步驟2：判斷是否達(dá)到最低溫度，如果T≤Tmin，算法終止，輸出最優(yōu)解及其適應(yīng)度；否則繼續(xù)向下執(zhí)行。

步驟3：令迭代次數(shù)k=1，開(kāi)始T溫度下的內(nèi)循環(huán)。

步驟4：計(jì)算種群Pk里面含有的每一個(gè)染色體的F(x)。

步驟5：使用最優(yōu)個(gè)體保留方法和輪盤賭方法從父子兩代種群中選出N個(gè)個(gè)體。

步驟6：根據(jù)兩種變異方法來(lái)對(duì)上面選出的個(gè)體上實(shí)行變異。

步驟7：根據(jù)概率p判斷是否接受新解。

步驟8：判斷是否繼續(xù)循環(huán)，如果k達(dá)到最大迭代次數(shù)kmax，比較全局最優(yōu)適應(yīng)度Fg和局部最優(yōu)適應(yīng)度Fl，如果Fl

改進(jìn)算法的具體流程圖如圖1所示。

圖1 改進(jìn)SAPGA算法流程圖

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

為了驗(yàn)證所提出算法的有效性，與單親遺傳算法[17]進(jìn)行實(shí)驗(yàn)對(duì)比。本文實(shí)驗(yàn)環(huán)境是Core(TM) i7-8550U CPU @1.80 GHz 1.99 GHz，內(nèi)存8.00 GB，開(kāi)發(fā)工具是Matlab 2016a。

給定九個(gè)節(jié)點(diǎn)的圖G的權(quán)值矩陣W(數(shù)據(jù)取自文獻(xiàn)[17])如下，各節(jié)點(diǎn)的度約束都為3。

實(shí)驗(yàn)1:設(shè)置種群規(guī)模為100，最大迭代次數(shù)為100，初始變異率為0.1。使用所提算法和標(biāo)準(zhǔn)的單親遺傳算法分別求其最小生成樹代價(jià)值，結(jié)果如圖2所示。

圖2 最優(yōu)值對(duì)比

從圖2中可以看出，兩種算法均隨迭代次數(shù)的增加，不斷趨近最優(yōu)值，但明顯SAPGA算法的趨近速度更快。說(shuō)明自適應(yīng)變異率的加入確實(shí)能使算法加速收斂，自適應(yīng)變異率前期較大，能增加種群的多樣性，加快解的優(yōu)化；后期減小，能加快收斂效率。

實(shí)驗(yàn)2:設(shè)置最大迭代次數(shù)為100，初始變異率為0.1，在種群規(guī)模為10到100的情況下，對(duì)比兩種算法的運(yùn)行時(shí)間，結(jié)果如圖3所示。從圖3中可以看出，本文所提SAPGA算法用時(shí)始終比PGA算法少，并且隨著種群規(guī)模的擴(kuò)大，差距會(huì)越來(lái)越明顯。因?yàn)樽儺愃阕拥母倪M(jìn)，能避免不可行解個(gè)體的產(chǎn)生，且自適應(yīng)變異率能加速收斂，所以SAPGA算法的運(yùn)行時(shí)間能得到有效的改善。

圖3 運(yùn)行時(shí)間對(duì)比

實(shí)驗(yàn)3:在種群大小為50和100的情況下，使用所提算法與單親遺傳算法的求解方法進(jìn)行對(duì)比，驗(yàn)證所提算法得到最優(yōu)解的概率。本文提出的算法SAPGA進(jìn)行求解，得到度約束下兩種算法在兩種群規(guī)模下各運(yùn)行100次結(jié)果對(duì)比見(jiàn)表1。

表1 運(yùn)行結(jié)果對(duì)比

從表1可知，兩種算法均能得到最優(yōu)的最小生成樹代價(jià)2 256。在種群規(guī)模為50時(shí)，運(yùn)行100次中，SAPGA算法有67次得到了最優(yōu)解，比單親遺傳算法PGA的結(jié)果提高了12%左右。在種群規(guī)模為100時(shí)，運(yùn)行100次中，SAPGA有83次得到了最優(yōu)解，比單親遺傳算法PGA提高了15%左右。從解的平均值也可以看出，SAPGA算法的效果在兩種規(guī)模下都比PGA算法好。從實(shí)驗(yàn)結(jié)果可以看出，本文所提算法因?yàn)橛辛四M退火思想的加入，能解決解個(gè)體的跳躍問(wèn)題，提高獲得全局最優(yōu)解的可能性，所以在求解DCMSTP時(shí)能得到較好的結(jié)果，最優(yōu)解出現(xiàn)的次數(shù)有一定的增加。

4 結(jié)束語(yǔ)

本文針對(duì)度約束的最小生成樹模型求解問(wèn)題，提出了改進(jìn)SAPGA算法。改進(jìn)后的算法融合并改進(jìn)了單親遺傳算法和模擬退火算法。單親遺傳算法中變異算子改進(jìn)的兩種方法都不會(huì)出現(xiàn)不可行解，省去了解是否可行的檢測(cè)，并且自適應(yīng)的變異率能加速收斂，因此大大加快了求解速度。同時(shí)，算法中模擬退火的思想能增加解的多樣性，保證種群跳出局部最優(yōu)，收斂到全局最優(yōu)，改善單親遺傳算法的解的跳躍問(wèn)題，提高得到全局最優(yōu)解的可能性。該模型的求解方法可以在網(wǎng)絡(luò)通信架構(gòu)等多個(gè)問(wèn)題中得到很好的應(yīng)用。