一種融合模擬退火和單親遺傳的優化求解算法

王海紅，李 林，劉 莉

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

0 引言

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

遺傳算法由于其編碼方式簡單，實現容易且效果較好，而在該問題上有更廣泛的應用和改進[8]。文獻[9]對傳統遺傳算法進行優化，提出了一種帶有加速和調節算子作為激勵的遺傳算法，從正反兩方面出發來加速搜索最小生成樹過程。文獻[10]提出了一種以過程控制為基礎的生成樹編碼方法—PC編碼，進而給出以PC-Prim算法作為譯碼器的求解DC-MST問題的遺傳算法來求解最小生成樹。文獻[11]采用單親遺傳算法來求解該問題，能提高個體的有效性，但仍存在變異產生不可行解以及解個體跳躍問題，求解效率不高。

針對以上問題，本文提出改進單親遺傳算法的變異算子方法，并引入自適應變異率，求解過程中可以避免不可行解的產生，并提高求解效率。同時融合模擬退火算法，來解決個體的跳躍問題，提高獲得全局最優解的可能性。最后，進行實驗驗證，與標準單親遺傳算法的結果進行比較，證明了所提算法的有效性和優越性。

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

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

度約束最小生成樹目標函數如下：

(1)

約束函數如下：

(2)

(3)

(4)

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

(5)

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

2 基于單親遺傳算法和模擬退火算法的改進SAPGA算法

2.1 初始化

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

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

設置初始較高溫度為T0，最低溫度Tmin，全局最優解Pg，及全局最優解對應的適應度Fg。

2.2 適應度函數

本文使用適應度函數來衡量遺傳操作過程中每個個體的適應度，并以此來得出優勝劣汰的標準。根據前面描述的度約束最小生成樹問題的模型，適應值函數F(x)設置如下。

(6)

2.3 選擇過程

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

2.4 優化變異操作

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

2.4.1 優化變異算子生成方式

本文設計兩種不會產生不可行解的變異算子，具體生成方法如下。

1)隨機插入變異：首先要隨機生成一個位置i(i不大于基因總數)，將它記為即將插入的位置。再從代表父輩個體的Prufer數列中隨機地取出一個子數列，將取出的子數列插入剛剛標記的位置，這樣就得到了新的子代個體。這個操作僅僅是移動原數列中的某些數字，因此不會導致不可行解的出現。

操作舉例：隨機選擇的子串為4、5、6，隨機產生的位置為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)后移變異：首先生成一個隨機數j(j小于基因總數)，將父代個體的Prufer數列依次后移j個位置，該操作簡單易行，并且很明顯在這個過程中可以保證解的可行性。操作舉例如下：

假設生成隨機數為1，則每個數都后移一位。

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 改進變異率

為加快算法的求解速度，設計自適應變異率。訓練前期較大的變異率能夠保證較高的個體多樣性，而后期應該采取較小的變異率，能加快收斂。因此，設計自適應更新學習因子如下：

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

(7)

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

2.5 判斷是否接受新解

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

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

(8)

2.6 改進算法流程

本文所提算法的基本步驟總結如下。

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

步驟2：判斷是否達到最低溫度，如果T≤Tmin，算法終止，輸出最優解及其適應度；否則繼續向下執行。

步驟3：令迭代次數k=1，開始T溫度下的內循環。

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

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

步驟6：根據兩種變異方法來對上面選出的個體上實行變異。

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

步驟8：判斷是否繼續循環，如果k達到最大迭代次數kmax，比較全局最優適應度Fg和局部最優適應度Fl，如果Fl

改進算法的具體流程圖如圖1所示。

圖1 改進SAPGA算法流程圖

3 實驗結果與分析

為了驗證所提出算法的有效性，與單親遺傳算法[17]進行實驗對比。本文實驗環境是Core(TM) i7-8550U CPU @1.80 GHz 1.99 GHz，內存8.00 GB，開發工具是Matlab 2016a。

給定九個節點的圖G的權值矩陣W(數據取自文獻[17])如下，各節點的度約束都為3。

實驗1:設置種群規模為100，最大迭代次數為100，初始變異率為0.1。使用所提算法和標準的單親遺傳算法分別求其最小生成樹代價值，結果如圖2所示。

圖2 最優值對比

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

實驗2:設置最大迭代次數為100，初始變異率為0.1，在種群規模為10到100的情況下，對比兩種算法的運行時間，結果如圖3所示。從圖3中可以看出，本文所提SAPGA算法用時始終比PGA算法少，并且隨著種群規模的擴大，差距會越來越明顯。因為變異算子的改進，能避免不可行解個體的產生，且自適應變異率能加速收斂，所以SAPGA算法的運行時間能得到有效的改善。

圖3 運行時間對比

實驗3:在種群大小為50和100的情況下，使用所提算法與單親遺傳算法的求解方法進行對比，驗證所提算法得到最優解的概率。本文提出的算法SAPGA進行求解，得到度約束下兩種算法在兩種群規模下各運行100次結果對比見表1。

表1 運行結果對比

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

4 結束語

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