基于遺傳自適應(yīng)蟻群系統(tǒng)算法的中繼路由方法

陳可，胡曉光

(北京航空航天大學(xué) 自動(dòng)化科學(xué)與電氣工程學(xué)院，北京，100191)

近年來，采用低壓電力線作為通信介質(zhì)的傳輸技術(shù)具有充分利用現(xiàn)有資源、易施工、綜合成本低、不受環(huán)境條件限制等優(yōu)點(diǎn)，是電力部門實(shí)現(xiàn)遠(yuǎn)程自動(dòng)抄表的發(fā)展趨勢(shì)，具有廣闊的應(yīng)用前景。由于低壓電力線具有高噪聲、高衰減和高時(shí)變等特性[1-3]，使得集中器節(jié)點(diǎn)和目標(biāo)電表節(jié)點(diǎn)之間直接通信成功概率較低，這不僅制約了信號(hào)傳輸?shù)木嚯x，同時(shí)嚴(yán)重降低了電力線通信的可靠性，進(jìn)而影響抄表范圍和抄表成功率。因此在實(shí)際應(yīng)用中，需要通過中繼技術(shù)來彌補(bǔ)以上缺憾。許多學(xué)者在這一領(lǐng)域進(jìn)行了深入研究，提出了多種中繼路由方法，文獻(xiàn)[4]提出了具有中繼約束條件的自動(dòng)中繼路由算法；趙杰衛(wèi)等[5]采用蟻群算法及利用電氣距離作為約束條件候選集策略提高了中繼搜索的準(zhǔn)確度和效率；劉曉勝等提出了一種適用于未知建筑物電力線拓?fù)浣Y(jié)構(gòu)條件下的蟻群電力線組網(wǎng)方法[6]，并通過仿真驗(yàn)證了該組網(wǎng)算法的有效性和抗毀性；還提出了適用于低壓配電網(wǎng)電力線載波通信的類蟻群算法[7]，該方法可以有效延長(zhǎng)電力線載波通信距離。以上這些方法在一定程度上解決了抄表范圍與抄表成功率等問題，但均有一些缺點(diǎn)：文獻(xiàn)[4]中的方法與一般自動(dòng)中繼方法相比，雖然節(jié)約了抄表時(shí)間，提高了抄表成功率，但不具有動(dòng)態(tài)適應(yīng)電力線環(huán)境的變化能力；文獻(xiàn)[5-7]中的方法雖然能動(dòng)態(tài)適應(yīng)電力線環(huán)境的變化，但算法的收斂速度較慢，并且容易陷入局部極小值。針對(duì)以上問題，本文作者從提高抄表系統(tǒng)的時(shí)效性角度出發(fā)，將遺傳算法(Genetic algorithm，GA)和蟻群系統(tǒng)(Ant colony system，ACS)算法有機(jī)融合，提出了一種遺傳自適應(yīng)蟻群系統(tǒng)(Genetic adaptive ant colony system，GAACS)算法。該算法利用 GA 的隨機(jī)搜索、快速性及全局收斂性等特點(diǎn)，獲得集中器到目標(biāo)電表的初始中繼路由路徑并將其運(yùn)用到蟻群算法初期信息素分布中，再利用蟻群系統(tǒng)算法的并行性、正反饋機(jī)制以及求解效率高等特性求出最終解。在求解過程中，為了防止算法陷入局部最優(yōu)解，依據(jù)搜索情況對(duì)ACS算法中的狀態(tài)轉(zhuǎn)移概率因子、信息素?fù)]發(fā)因子以及信息素強(qiáng)度等參數(shù)采取自適應(yīng)調(diào)節(jié)策略。通過將本文算法、遺傳蟻群系統(tǒng)(Genetic ant colony system，GACS)算法、ACS和最大最小螞蟻系統(tǒng)(Max-min ant system，MMAS)算法進(jìn)行對(duì)比仿真實(shí)驗(yàn)，結(jié)果表明本文算法在收斂性、魯棒性、抗毀性及算法運(yùn)行時(shí)間等方面均優(yōu)于其他3種算法。

1 電力線載波抄表網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

在低壓電力線載波抄表系統(tǒng)中，下行線路主要由集中器和一定數(shù)量的電表組成，在邏輯拓?fù)浣Y(jié)構(gòu)中可以將集中器視作網(wǎng)關(guān)，每個(gè)用戶電表視為可通信的終端節(jié)點(diǎn)。由于低壓電力線的干擾、信號(hào)衰減和負(fù)載的接入與切出等因素，使信號(hào)在電力線上的傳輸并不能和理想狀態(tài)時(shí)的傳輸距離相比，某些電表節(jié)點(diǎn)將不能直接與集中器節(jié)點(diǎn)進(jìn)行通信。為了實(shí)現(xiàn)集中器對(duì)每一個(gè)目標(biāo)電表的抄收，必須先建立集中器到部分電表之間的路由路徑，再將這些節(jié)點(diǎn)作為中繼節(jié)點(diǎn)進(jìn)行數(shù)據(jù)的轉(zhuǎn)發(fā)，擴(kuò)展通信距離，才可能將所有的節(jié)點(diǎn)連入低壓電力線抄表系統(tǒng)中，達(dá)到自動(dòng)抄表的目的。抄表系統(tǒng)中，集中器與電表之間的樹形拓?fù)淠Ｐ腿鐖D1所示，集中器位于樹形拓?fù)浣Y(jié)構(gòu)的根部，即圖1中的0號(hào)節(jié)點(diǎn)，1～60號(hào)節(jié)點(diǎn)分別代表抄表系統(tǒng)中各電能表。

圖1 電力線載波抄表網(wǎng)絡(luò)樹形拓?fù)銯ig.1 Power line carrier meter reading network tree topology

2 算法原理

2.1 遺傳算法原理

遺傳算法是一類可用于復(fù)雜系統(tǒng)優(yōu)化的魯棒性搜索算法，它是模擬生物在自然環(huán)境中的遺傳和進(jìn)化過程而形成的一種自適應(yīng)全局概率搜索算法。遺傳算法是由可行解組成的群體逐代進(jìn)化過程，選擇、交叉、變異是遺傳算法的3個(gè)主要過程[8-10]。

2.1.1 適應(yīng)度函數(shù)及優(yōu)化目標(biāo)函數(shù)

適應(yīng)度函數(shù)應(yīng)該能夠反映出動(dòng)態(tài)路由問題中解的優(yōu)劣，通過群體的初始化，用式(1)計(jì)算每個(gè)個(gè)體的適應(yīng)度F(X)，集中器到目標(biāo)電表節(jié)點(diǎn)的路由路徑中，跳數(shù)相對(duì)越少，其適應(yīng)度值越高，適應(yīng)度函數(shù)定義為：

式中：F(X)為個(gè)體適應(yīng)度值；Cmax為一個(gè)適當(dāng)?shù)叵鄬?duì)比較大的數(shù)，本文所研究的抄表系統(tǒng)中，目標(biāo)電表節(jié)點(diǎn)共60個(gè)，因此，Cmax取值為100；f(X)為個(gè)體相應(yīng)的目標(biāo)函數(shù)值，即動(dòng)態(tài)路由路徑中源節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的跳數(shù)。

2.1.2 選擇運(yùn)算

為了加快遺傳算法的收斂速度，保留抄表過程中所獲得的較好路徑，本文采用精英選擇方法，該方法使適應(yīng)度函數(shù)值高的個(gè)體不受交叉和突然變異的影響，而是無條件的遺傳給后代，由于作為最優(yōu)個(gè)體的遺傳因子在群體中可能急劇地增多，算法能較快收斂到最優(yōu)解或局部最優(yōu)解。

2.1.3 交叉運(yùn)算

該運(yùn)算是交換2個(gè)染色體中的子路徑，其中用于交換的染色體必須擁有相同的源節(jié)點(diǎn)和目的節(jié)點(diǎn)。路徑交叉運(yùn)算的交叉位置限制在2個(gè)染色體中都含有的節(jié)點(diǎn)(不包含源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn))，從潛在的交叉位置中隨機(jī)選擇節(jié)點(diǎn)作為交叉位置，交換子路徑。圖2所示為將交叉運(yùn)算應(yīng)用于從集中器節(jié)點(diǎn)0到目標(biāo)電表節(jié)點(diǎn)15的一對(duì)父代A1和A2的情況，父代潛在的交叉位置是中繼節(jié)點(diǎn)6，9和12，選擇中繼節(jié)點(diǎn)6作為交叉位置，圖2通過交換子路徑產(chǎn)生新的子代B1和B2。

圖2 交叉運(yùn)算框圖Fig.2 Crossover operation figure

當(dāng)一對(duì)染色體中的公共點(diǎn)不存在時(shí)交叉位置就不能選擇，因此也就不可能實(shí)施交叉運(yùn)算。交叉概率pc取值過大會(huì)破壞群體中的優(yōu)良模式，對(duì)進(jìn)化運(yùn)算產(chǎn)生不利影響；若取值過小，產(chǎn)生新個(gè)體的速度較慢。本文為了加快遺傳算法的收斂速度，交叉概率pc取值為0.5。

2.1.4 變異運(yùn)算

該運(yùn)算是從一個(gè)染色體產(chǎn)生另一個(gè)染色體。為了實(shí)現(xiàn)變異，從染色體中隨機(jī)選擇節(jié)點(diǎn)，該節(jié)點(diǎn)稱為變異節(jié)點(diǎn)，在滿足最小通信距離的條件下從與變異點(diǎn)相鄰節(jié)點(diǎn)中隨機(jī)選擇另一個(gè)節(jié)點(diǎn)，最后利用基于最小跳計(jì)數(shù)準(zhǔn)則的Dijkstra算法分別產(chǎn)生從源節(jié)點(diǎn)到選擇點(diǎn)和從選擇點(diǎn)到目標(biāo)節(jié)點(diǎn)的可選路徑。路徑變異運(yùn)算如圖3所示，假設(shè)中繼節(jié)點(diǎn)6被選擇作為變異點(diǎn)，從變異節(jié)點(diǎn)的鄰點(diǎn)中選擇節(jié)點(diǎn)7，根據(jù)Dijkstra最小跳數(shù)算法產(chǎn)生源節(jié)點(diǎn)0到節(jié)點(diǎn)7的子路徑a及節(jié)點(diǎn)7到目標(biāo)節(jié)點(diǎn)15的子路徑b，連接a和b，完成變異操作。為了避免路徑中的任何環(huán)，如果子路徑a和b中存在重復(fù)節(jié)點(diǎn)，子代B就不能產(chǎn)生。變異概率pm取值較大時(shí)，雖然能夠產(chǎn)生較多的新個(gè)體，但可能破壞很多較好的路徑，使得算法性能近似于隨機(jī)搜索算法的性能；若取值過小，則變異操作產(chǎn)生新個(gè)體的能力和擬制早熟現(xiàn)象的能力就會(huì)較差。本文為了加快遺傳算法的收斂速度，變異概率pm取值為0.01。

圖3 變異運(yùn)算框圖Fig.3 Mutation operation figure

2.2 基本蟻群系統(tǒng)算法原理

蟻群系統(tǒng)算法是近年發(fā)展起來、受自然界螞蟻搜尋食物行為啟發(fā)得到的并行優(yōu)化算法[11-15]。該算法具有采用分布式并行計(jì)算機(jī)制、易于與其他方法結(jié)合、具有較強(qiáng)的魯棒性等優(yōu)點(diǎn)，但搜索時(shí)間長(zhǎng)、易陷入局部最優(yōu)解是其最為突出的缺點(diǎn)。

2.2.1 路徑構(gòu)建

在ACS算法中，位于城市i的螞蟻k，根據(jù)偽隨機(jī)比例規(guī)則選擇城市j作為下一個(gè)訪問的城市，路徑轉(zhuǎn)移規(guī)則如下：

式中：q0(0＜q0＜1)是狀態(tài)轉(zhuǎn)移因子；q為0到1之間的隨機(jī)數(shù)；ηil為啟發(fā)式信息；β為期望啟發(fā)式因子；若y=f(x)，則argmax[y]表示當(dāng)y取得最大值時(shí)x的值。當(dāng)q≤q0時(shí)，按照先驗(yàn)規(guī)律選擇路徑；當(dāng)q＞q0時(shí)，按照概率進(jìn)行路徑搜索。

轉(zhuǎn)移概率計(jì)算公式如下：

式中：τij為路徑(i，j)上的信息素大?。沪莍j為路徑(i，j)上的啟發(fā)式信息大??；α為信息啟發(fā)式因子；β為期望啟發(fā)式因子。

2.2.2 局部信息素更新

在路徑構(gòu)建過程中，螞蟻每經(jīng)過一條邊(i，j)，都將立刻調(diào)用局部信息素規(guī)則更新該邊上的信息素，規(guī)則如下：

式中：τij為路徑(i，j)上的信息素含量；ξ為局部更新?lián)]發(fā)因子；τ0為信息素初始值。ξ的引入使被選擇過的路徑上的信息素減少。局部更新規(guī)則使螞蟻傾向于選擇沒有走過的路徑，避免搜索過于集中到同一條線路上，使得算法不會(huì)陷入停滯狀態(tài)，這種更新規(guī)則有利于新路徑的發(fā)現(xiàn)。

2.2.3 全局信息素更新

在ACS算法中，只有一只螞蟻(至今最優(yōu)螞蟻)被允許在每一次迭代之后釋放信息素，全局信息素更新規(guī)則如下：

式中：τij為路徑(i，j)上的信息素含量；Δτij為路徑(i，j)上的信息素增量；ρ為信息素?fù)]發(fā)因子；Q為信息素強(qiáng)度；Lbs為至今最優(yōu)路徑長(zhǎng)度。對(duì)至今最優(yōu)線路進(jìn)行信息素增加，可使搜索過程具有指導(dǎo)性，搜索范圍集中在至今最優(yōu)線路。

2.3 自適應(yīng)蟻群系統(tǒng)算法原理

基本蟻群系統(tǒng)算法在搜索初期，各條路徑上的信息素分布比較分散，在經(jīng)過一定的迭代步數(shù)后，信息素會(huì)逐漸集中到少數(shù)路徑上，搜索的大致方向也就隨之確定，由于ACS算法的正反饋機(jī)制旨在強(qiáng)化性能較好的解，因此，在搜索后期，當(dāng)某些路徑上的信息素強(qiáng)度明顯高于其余路徑時(shí)，繼續(xù)搜索將會(huì)總在少數(shù)路徑上進(jìn)行，這樣會(huì)使解的結(jié)構(gòu)過于相似，搜索過程也會(huì)停頓下來，算法容易陷入局部最優(yōu)解。

本文采用遺傳算法得到集中器到某目標(biāo)電表的初始路徑，并將其運(yùn)用到蟻群系統(tǒng)算法初期信息素分布中，這將導(dǎo)致在算法初期，少數(shù)路徑上的信息素強(qiáng)度會(huì)明顯高于其余路徑，算法極易出現(xiàn)停滯現(xiàn)象并陷入局部最優(yōu)解而無法跳出。為了解決這個(gè)問題，本文在ACS算法的基礎(chǔ)上，提出了根據(jù)解的搜索情況，動(dòng)態(tài)自適應(yīng)調(diào)整狀態(tài)轉(zhuǎn)移概率因子、信息素?fù)]發(fā)因子、信息量強(qiáng)度等因素，可在一定程度上有效地克服 ACS算法的一些不足。

2.3.1 轉(zhuǎn)移概率因子的改進(jìn)

在式(2)中，狀態(tài)轉(zhuǎn)移因子q0是一個(gè)非常重要的參數(shù)。當(dāng)q≤q0時(shí)，螞蟻依據(jù)信息素的積累量和啟發(fā)式信息值確定要移動(dòng)的下一節(jié)點(diǎn)；當(dāng)q＞q0時(shí)，螞蟻依據(jù)概率有偏向性地探索各條邊。在基本蟻群算法中，q0是區(qū)間[0，1]上的固定常數(shù)，缺乏自適應(yīng)性。本文通過自適應(yīng)調(diào)整參數(shù)q0來調(diào)節(jié)算法對(duì)新路徑的探索度，從而決定算法是應(yīng)該集中搜索至今最優(yōu)路徑附近的區(qū)域，還是應(yīng)該搜索其他區(qū)域，q0按下式進(jìn)行選擇：

由于抄表系統(tǒng)中，終端電表的數(shù)量較多，因此，在算法執(zhí)行初期，選擇相對(duì)較大的q0能加快算法的收斂速度，降低算法的隨機(jī)性，利于局部搜索；在算法執(zhí)行中期，選擇相對(duì)較小的q0能提高算法隨機(jī)性，利于全局搜索；在算法執(zhí)行后期，重新恢復(fù)q0的初始值，進(jìn)一步提升收斂速度并最終找到全局最優(yōu)解。

2.3.2 信息素?fù)]發(fā)因子的改進(jìn)

蟻群系統(tǒng)算法中信息素?fù)]發(fā)因子ρ的大小直接關(guān)系到ACS算法的全局搜索能力及其收斂速度。在自動(dòng)抄表系統(tǒng)中，如果終端電表數(shù)量比較多，由于ρ的存在，會(huì)使那些從來未被搜索到的路徑上的信息量減小到接近于 0，因而降低了算法的全局搜索能力，而且當(dāng)ρ過大時(shí)，以前搜索過的路徑被再次選擇的可能性過大，也會(huì)影響到算法的隨機(jī)性能和全局搜索能力；反之，通過減小ρ雖然可以提高算法的隨機(jī)性能和全局搜索能力，但又會(huì)使算法的收斂速度降低?；谝陨戏治?，本文采取自適應(yīng)調(diào)整信息素?fù)]發(fā)因子ρ的方法，在提高收斂速度的同時(shí)避免陷入局部最優(yōu)解，當(dāng)算法在連續(xù)N次循環(huán)迭代過程中，最優(yōu)解都沒有變化，表明搜索過程可能陷入了局部最優(yōu)解，此時(shí)ρ按照下式作自適應(yīng)調(diào)整：

式中：ρmin為ρ的最小值，為了防止ρ過小降低算法的收斂速度；λ為預(yù)先設(shè)定的衰減系數(shù)，根據(jù)抄表規(guī)模調(diào)整。式(8)使得信息素?fù)]發(fā)因子ρ從最大值逐漸降低，但又不至于太低而影響算法的收斂速度。與式(5)對(duì)比可以看出：改進(jìn)前的ρ是一個(gè)固定值，而改進(jìn)之后，在算法運(yùn)行初期，ρ取相對(duì)較大值，提高算法的收斂速度，快速找到局部最優(yōu)解；在算法運(yùn)行后期，ρ取相對(duì)較小值，可以進(jìn)一步提高隨機(jī)性能和全局搜索能力。

2.3.3 信息素強(qiáng)度的改進(jìn)

信息素強(qiáng)度Q為螞蟻循環(huán)一周時(shí)釋放在所經(jīng)過路徑上的信息素總量，其作用是為了充分利用路徑上的全局信息反饋量，使得算法在正反饋機(jī)制作用下以合理的演化速度搜索到所求問題的全局最優(yōu)解。Q越大，則在螞蟻已遍歷路徑上信息素的累積加快，可以加強(qiáng)蟻群搜索時(shí)的正反饋性能，有助于算法的快速收斂，但此時(shí)算法的全局搜索能力變差，極易陷入局部最優(yōu)解，計(jì)算性能也變得很不穩(wěn)定；Q過小又會(huì)影響算法的收斂速度。針對(duì)以上問題，本文提出了一種根據(jù)蟻群算法搜索情況來自適應(yīng)動(dòng)態(tài)修改信息素強(qiáng)度的方法，可在一定程度上有效地解決擴(kuò)大搜索空間和尋找最優(yōu)解之間的矛盾，從而使得算法跳離局部最優(yōu)解。當(dāng)算法在連續(xù)N次循環(huán)迭代過程中，最優(yōu)解都沒有變化，表明搜索過程可能陷入了局部最優(yōu)解，則采用強(qiáng)制機(jī)制，減小要添加的信息素，使算法從局部極小值中逃脫出來。此時(shí)Q按照下式作自適應(yīng)調(diào)整：

式中：ζ為正參數(shù)，控制Q(t)的下降速度；Q(0)為信息素強(qiáng)度的初始值；Qmin為Q(t)的最小值。采用時(shí)變遞減函數(shù)代替常數(shù)項(xiàng)Q，可以保證在路徑上的信息素隨搜索過程逐漸增多的情況下，繼續(xù)保持隨機(jī)搜索和路徑信息的啟發(fā)作用間的平衡，使算法能跳出局部最優(yōu)，繼續(xù)尋找全局最優(yōu)解。

3 基于 GAACS路由算法的特點(diǎn)及步驟

3.1 路由算法特點(diǎn)

電力線載波抄表系統(tǒng)中，集中器與各用戶電表的連接關(guān)系通常未知，通信網(wǎng)絡(luò)邏輯拓?fù)浣Y(jié)構(gòu)處于盲態(tài)，路由算法須具有如下特點(diǎn)：

(1) 算法能適應(yīng)盲網(wǎng)絡(luò)狀態(tài)要求。在盲網(wǎng)絡(luò)狀態(tài)下，指定中繼方式已經(jīng)不能滿足路由要求，路由算法須具有對(duì)抄表系統(tǒng)網(wǎng)絡(luò)探索和辨識(shí)的能力，找到集中器節(jié)點(diǎn)和目標(biāo)電表節(jié)點(diǎn)之間路由線路，同時(shí)算法應(yīng)具有路由優(yōu)化能力，搜索并收斂于優(yōu)良的路由線路。

(2) 路由算法能夠適應(yīng)抄表系統(tǒng)中網(wǎng)絡(luò)邏輯拓?fù)涞淖兓３硐到y(tǒng)中不斷有新的用戶接入網(wǎng)絡(luò)，導(dǎo)致系統(tǒng)的邏輯拓?fù)洳粩嘧兓?，路由算法要能夠適應(yīng)該變化，對(duì)變化前后的邏輯拓?fù)浣Y(jié)構(gòu)，算法的路由能力不變。

(3) 路由算法有較強(qiáng)的抗毀性。低壓電力線具有負(fù)載多、噪聲強(qiáng)、衰減大、時(shí)延長(zhǎng)等特征，抄表通信路徑易失效，網(wǎng)絡(luò)中電表節(jié)點(diǎn)本身也存在硬件故障等異常情況。要求路由算法能夠在抄表通信線路被破壞時(shí)迅速重構(gòu)，提高抄表系統(tǒng)的抗毀性。

3.2 基于GAACS路由算法實(shí)現(xiàn)步驟

在闡述利用GAACS算法實(shí)現(xiàn)抄表系統(tǒng)動(dòng)態(tài)路由過程之前，對(duì)本文常用的名詞進(jìn)行定義。

定義1 搜索螞蟻壽命：是指搜索螞蟻數(shù)據(jù)幀能夠被中繼電表節(jié)點(diǎn)轉(zhuǎn)發(fā)次數(shù)的上限。在實(shí)際抄表系統(tǒng)中，數(shù)據(jù)幀不能被無限次轉(zhuǎn)發(fā)，尤其是對(duì)于窄帶電力線載波通信，通信速率較低，數(shù)據(jù)幀轉(zhuǎn)發(fā)次數(shù)受到較大限制，否則占用信道時(shí)間過長(zhǎng)，同時(shí)也容易產(chǎn)生錯(cuò)誤?？紤]該約束條件，算法中定義螞蟻壽命變量為 7，表示每只搜索螞蟻?zhàn)疃嗄軌蚪?jīng)歷7個(gè)不同的中繼節(jié)點(diǎn)，每轉(zhuǎn)發(fā)一次該值減1。如果在經(jīng)歷了7個(gè)電表節(jié)點(diǎn)之后，該搜索螞蟻沒有找到目標(biāo)電表節(jié)點(diǎn)，則設(shè)定該螞蟻死亡，不再繼續(xù)尋找，工程應(yīng)用中表現(xiàn)為舍棄該數(shù)據(jù)幀不再轉(zhuǎn)發(fā)。

定義2 跳數(shù)：是指集中器節(jié)點(diǎn)與任意一個(gè)目標(biāo)電表節(jié)點(diǎn)通信時(shí)，搜索螞蟻數(shù)據(jù)幀到達(dá)目標(biāo)電表節(jié)點(diǎn)所需被轉(zhuǎn)發(fā)的次數(shù)?？梢灾苯油ㄐ诺墓?jié)點(diǎn)，跳數(shù)為 0；需要通過1個(gè)中間電表節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)幀，跳數(shù)為1，以此類推。

定義3 通信距離：是指抄表系統(tǒng)中可以相互通信的兩個(gè)節(jié)點(diǎn)所跨過的節(jié)點(diǎn)個(gè)數(shù)加 1。該距離會(huì)隨著電力線信道質(zhì)量而變化。本文規(guī)定任意一個(gè)節(jié)點(diǎn)最小可通信距離可以跨過2個(gè)節(jié)點(diǎn)，即通信距離為3，實(shí)際抄表系統(tǒng)中，各個(gè)電表節(jié)點(diǎn)的通信距離會(huì)遠(yuǎn)大于3。

GAACS算法設(shè)計(jì)了合理有效地適應(yīng)度函數(shù)和優(yōu)化目標(biāo)函數(shù)，并且采用通信距離、螞蟻壽命作為約束條件，力求在保證抄表正確和可靠的前提下盡量提高路由效率。在該算法中，約定如下：①在集中器節(jié)點(diǎn)控制范圍內(nèi)每個(gè)電表節(jié)點(diǎn)有一個(gè)唯一的地址編號(hào)；②抄表系統(tǒng)邏輯拓?fù)鋱D為無向圖；③任意相鄰的兩個(gè)電表節(jié)點(diǎn)都能夠保證可靠通信。GAACS算法流程如下，其中，步驟1～8利用遺傳算法的快速全局搜索能力生成路徑初始信息素分布，步驟 9～15利用蟻群算法的正反饋收斂機(jī)制完成最終集中器到目標(biāo)電表之間最優(yōu)路徑的建立。

步驟1 參數(shù)初始化。主要包括以下幾方面：① 群體規(guī)模M、交叉概率pc、變異概率pm、信息啟發(fā)式因子α、期望啟發(fā)式因子β、信息素常量τC、等效信息素τG、信息素強(qiáng)度初始值Q(0)、信息素強(qiáng)度最小值Qmin、信息素?fù)]發(fā)因子最小值ρmin、轉(zhuǎn)移概率因子最小值qmin、局部更新?lián)]發(fā)因子ξ、系數(shù)σ，λ和ζ；② 集中器及各電表節(jié)點(diǎn)通信信息表、轉(zhuǎn)移概率表、啟發(fā)信息表、禁忌表初始化；③ 遺傳迭代次數(shù)NG、蟻群迭代次數(shù)NA、迭代螞蟻數(shù)m初始化；

步驟2 編碼。利用序列編碼方法，編碼位串的首個(gè)字符代表集中器編號(hào)，設(shè)定為 0，編碼位串最后一個(gè)字符代表目標(biāo)電表節(jié)點(diǎn)編號(hào)，中間字符按照抄表路由路徑順序依次排列。如果路徑不符合最小通信距離的約束條件，則不能被編譯成一個(gè)染色體，這意味著路徑中的每一步都必須經(jīng)過抄表系統(tǒng)中實(shí)質(zhì)上的連接；

步驟3 初始化群體。針對(duì)某一目標(biāo)電表節(jié)點(diǎn)，利用基于最小跳計(jì)數(shù)準(zhǔn)則的 Dijkstra算法產(chǎn)生從集中器節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的路徑作為初始路徑。為了提高遺傳算法的運(yùn)行效率，避免搜索中繼路由路徑的時(shí)間過長(zhǎng)，初始群體規(guī)模不宜太大；

步驟4 根據(jù)式(1)計(jì)算種群內(nèi)個(gè)體適應(yīng)度值、判斷迭代次數(shù)nG，若nG＞NG，獲得優(yōu)化抄表路由路徑并轉(zhuǎn)向步驟9，否則轉(zhuǎn)向步驟5；

步驟5 記錄父代的精英個(gè)體，將父代中的精英個(gè)體直接復(fù)制到子代種群中；

步驟6 以概率pc對(duì)種群進(jìn)行路徑雜交運(yùn)算；

步驟7 以概率pm對(duì)種群進(jìn)行路徑變異運(yùn)算；

步驟8 由精英復(fù)制個(gè)體、交叉、變異后的個(gè)體構(gòu)成下一代種群個(gè)體，轉(zhuǎn)入步驟4；

步驟9 經(jīng)過遺傳算法得到集中器到目標(biāo)電表的優(yōu)化抄表路徑，并運(yùn)用到蟻群算法初期信息素分布中，用下式更新各條路徑上的初始信息素分布：

式中：τC是給定的一個(gè)信息素常數(shù)；τG則是根據(jù)遺傳算法求得的初始抄表路徑所對(duì)應(yīng)的等效信息素。

步驟10 集中器節(jié)點(diǎn)發(fā)起探索螞蟻數(shù)據(jù)幀。該數(shù)據(jù)幀包括集中器地址、目標(biāo)電表地址、路由區(qū)及搜索螞蟻壽命。路由區(qū)在數(shù)據(jù)幀到達(dá)目標(biāo)電表節(jié)點(diǎn)之前不斷填充其所經(jīng)歷路由節(jié)點(diǎn)地址信息。依據(jù)算法運(yùn)行時(shí)間，按式(7)自適應(yīng)調(diào)整狀態(tài)轉(zhuǎn)移概率因子q0(t)，螞蟻按式(2)選擇下一個(gè)訪問的節(jié)點(diǎn)，并立即按式(4)更新局部信息素濃度；

步驟11 判斷是否為目標(biāo)節(jié)點(diǎn)，如果是目標(biāo)節(jié)點(diǎn)轉(zhuǎn)入步驟12，否則轉(zhuǎn)入步驟10；

步驟12 對(duì)每一只螞蟻執(zhí)行步驟10和11，直到所有的螞蟻均迭代完成；

步驟13 找出至今最優(yōu)螞蟻，并按式(5)和(6)進(jìn)行至今最優(yōu)路徑的全局信息素濃度更新；

步驟14 當(dāng)算法在連續(xù)N次循環(huán)迭代過程中，最優(yōu)解都沒有變化，表明搜索過程可能陷入了局部最優(yōu)解，根據(jù)式(8)和(9)自適應(yīng)調(diào)整信息素?fù)]發(fā)因子ρ(t)及信息素強(qiáng)度Q(t)；

步驟15 判定算法是否達(dá)到設(shè)定的迭代次數(shù)NA，達(dá)到則記錄集中器節(jié)點(diǎn)到目標(biāo)電表節(jié)點(diǎn)的最優(yōu)路徑，并把最優(yōu)路徑存到集中器節(jié)點(diǎn)的路由表中，否則轉(zhuǎn)向步驟10。

4 仿真結(jié)果

本文仿真實(shí)驗(yàn)中各參數(shù)選擇為：種群規(guī)模M=20，交叉概率Pc=0.5，變異概率等效信息素τG=2，每次迭代螞蟻數(shù)m=15，螞蟻壽命N=4，NA=42。說明，在4.2和4.3中遺傳算法迭代次數(shù)NG取值為4；蟻群算法迭代次數(shù)NA取值為26；參數(shù)自適應(yīng)調(diào)整時(shí)最大迭代次數(shù)N取值為3。

4.1 算法收斂性分析

算法的收斂性是衡量算法性能優(yōu)劣的重要指標(biāo)之一，本文采用MATLAB7.01為仿真平臺(tái)，對(duì)GAACS，GACS，ACS和MMAS 4種算法下，集中器節(jié)點(diǎn)0到目標(biāo)電表節(jié)點(diǎn)60的抄表路由路徑尋優(yōu)進(jìn)行驗(yàn)證，仿真采用的物理拓?fù)浣Y(jié)構(gòu)如圖 1所示，仿真結(jié)果如圖 4所示。

圖4 搜索電表節(jié)點(diǎn)60的仿真結(jié)果Fig.4 Result of simulation about searching meter node 60

從圖4可以看出：4種算法經(jīng)過不同次數(shù)的迭代運(yùn)算后均能收斂到最優(yōu)路由路徑：0→19→51→60或者 0→19→50→60，從搜尋到最佳路由路徑的效率方面比較，顯然GAACS算法搜尋到最優(yōu)解的效率最高，僅僅經(jīng)過 22次迭代運(yùn)算就收斂到最優(yōu)解；其次是GACS算法，經(jīng)過27次迭代運(yùn)算收斂到最優(yōu)解；再是ACS算法，經(jīng)過32次迭代運(yùn)算收斂到最優(yōu)解；搜索效率最低的是MMAS算法，經(jīng)過42次迭代運(yùn)算才最終找到最優(yōu)解。因此，相比其他 3種算法，GAACS算法能更好地適用于電力線載波抄表系統(tǒng)中繼路由問題，該算法具有較高的動(dòng)態(tài)路由尋優(yōu)效率，能夠確保抄表路由路徑的質(zhì)量。

4.2 算法魯棒性分析

算法魯棒性是指算法適應(yīng)不同網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的能力，在實(shí)際抄表系統(tǒng)中，集中器與各電表之間的物理拓?fù)浣Y(jié)構(gòu)非常復(fù)雜，由于低壓電力線信道質(zhì)量的變化引起電表節(jié)點(diǎn)通信距離的變化，導(dǎo)致抄表系統(tǒng)的物理拓?fù)浣Y(jié)構(gòu)隨之變化；此外，隨著電表節(jié)點(diǎn)的加入與退出也會(huì)導(dǎo)致物理拓?fù)浣Y(jié)構(gòu)的變化。GAACS算法能否適應(yīng)這種復(fù)雜性，是該算法能否運(yùn)用到實(shí)際電力線載波抄表系統(tǒng)的重要評(píng)判標(biāo)準(zhǔn)。

為了更好地反映電力線載波抄表系統(tǒng)中通信網(wǎng)絡(luò)邏輯拓?fù)涞臅r(shí)變性，設(shè)某時(shí)刻各電表節(jié)點(diǎn)通信距離是在一定范圍內(nèi)的隨機(jī)值，仿真分析這種情況下GAACS算法搜索最佳路由路徑的能力。仿真中仍然采用圖 1所示的拓?fù)浣Y(jié)構(gòu)，但每個(gè)電表節(jié)點(diǎn)的通信距離為 1～5之間的一個(gè)隨機(jī)值。表1所示為仿真實(shí)驗(yàn)中各電表節(jié)點(diǎn)隨機(jī)產(chǎn)生的通信距離表，其中N表示電表節(jié)點(diǎn)號(hào)，D表示該電表節(jié)點(diǎn)通信距離。

圖5所示為采用表1中的電表節(jié)點(diǎn)隨機(jī)通信距離(集中器節(jié)點(diǎn)的通信距離設(shè)定為 2)，運(yùn)用 GAACS，GACS，ACS和MMAS等算法求取集中器節(jié)點(diǎn)0到目標(biāo)電表節(jié)點(diǎn)60的抄表路由路徑尋優(yōu)仿真結(jié)果。

表1 各電表節(jié)點(diǎn)通信距離隨機(jī)值Table 1 Random value of meter node communication distance

圖5 隨機(jī)通信距離仿真結(jié)果Fig.5 Result of simulation about random communication distance

從圖5可以看出：在實(shí)際低壓電力線載波抄表系統(tǒng)各電表節(jié)點(diǎn)通信距離隨機(jī)的情況下，只有 GAACS算法能夠最終搜索到最優(yōu)路由路徑，即：0→8→41→60或0→2→41→60，算法收斂到最少路由跳數(shù)2跳時(shí)所需的迭代數(shù)僅為 13次。而 GACS，ACS和 MMAS 3種算法對(duì)于節(jié)點(diǎn)通信距離隨機(jī)的抄表系統(tǒng)，均未能收斂到最優(yōu)路由路徑并全部陷入局部最優(yōu)解。原因是GAACS算法能夠依據(jù)當(dāng)前的搜索情況自適應(yīng)地改變狀態(tài)轉(zhuǎn)移因子、信息素?fù)]發(fā)因子、信息素強(qiáng)度等參數(shù)，使得在算法陷入局部最優(yōu)解后，仍然能夠跳出局部最優(yōu)解，繼續(xù)尋找全局最優(yōu)解，在保證收斂速度的條件下提高了解的全局性。因此，可以得出以下結(jié)論：GAACS算法的魯棒性能最好，GACS，ACS和MMAS 3種算法的魯棒性能大致相當(dāng)。

4.3 算法抗毀性分析

低壓電力線具有噪聲強(qiáng)、衰減大、負(fù)載多、時(shí)延長(zhǎng)等特征，通信路徑易失效，抄表系統(tǒng)中，電表節(jié)點(diǎn)本身也存在硬件故障等異常情況。要求路徑尋優(yōu)算法能夠在系統(tǒng)中部分通信線路被破壞時(shí)迅速重構(gòu)，提高抄表系統(tǒng)的抗毀性。

仿真中仍然采用圖1所示的拓?fù)浣Y(jié)構(gòu)，假設(shè)某個(gè)時(shí)刻19號(hào)電表節(jié)點(diǎn)發(fā)生故障，喪失通信功能，則此電表節(jié)點(diǎn)在系統(tǒng)網(wǎng)絡(luò)邏輯拓?fù)渲邢В藭r(shí)含有19號(hào)電表節(jié)點(diǎn)的路由線路將不再適用，某些集中器到目標(biāo)電表節(jié)點(diǎn)的抄表路徑需要重新組建。對(duì)該情況進(jìn)行仿真實(shí)驗(yàn)，假設(shè)節(jié)點(diǎn)的通信距離為3，以60號(hào)電表節(jié)點(diǎn)作為目標(biāo)節(jié)點(diǎn)，分別采用GAACS，GACS，ACS和MMAS算法，仿真結(jié)果如圖6所示。

圖6 節(jié)點(diǎn)失效仿真結(jié)果Fig.6 Result of simulation about node failure

從圖6可以看出：在19號(hào)節(jié)點(diǎn)發(fā)生故障的情況下，GAACS，GACS，ACS和MMAS算法再次搜索到最優(yōu)路由路徑所需的迭代數(shù)分別為9，14，17和23次，顯然GAACS算法具有更高的搜索效率。GAACS算法僅僅需要9次迭代搜索，路由跳數(shù)就最終收斂到2跳，多次仿真實(shí)驗(yàn)輸出的路由線路均為以下7條線路中的1 條，即 0→8→41→60，0→8→50→60，0→8→51→60，0→30→41→60，0→30→50→60，0→30→51→60 和0→30→57→60。這些路徑均為最優(yōu)路由路徑。因此，在實(shí)際低壓電力線載波抄表系統(tǒng)中，因某電表節(jié)點(diǎn)自身發(fā)生故障或線路故障引起整個(gè)抄表系統(tǒng)拓?fù)浣Y(jié)構(gòu)發(fā)生變化時(shí)，GAACS算法不僅能夠針對(duì)新的拓?fù)浣Y(jié)構(gòu)迅速找到最優(yōu)路由路徑，提高抄表系統(tǒng)的抗毀性，而且與其他3種算法相比，GAACS算法能夠以相對(duì)較少的迭代次數(shù)收斂到最優(yōu)路徑，從而縮減集中器到目標(biāo)電表的中繼路由路徑尋優(yōu)時(shí)間，提升整個(gè)抄表系統(tǒng)的時(shí)效性。

4.4 算法性能指標(biāo)比較

為了綜合比較GAACS，GACS，ACS和MMAS 4種算法的性能，本文依然采用圖1所示的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，分別選取31～60號(hào)節(jié)點(diǎn)作為目標(biāo)節(jié)點(diǎn)，采用上面 4種算法對(duì)每一個(gè)目標(biāo)節(jié)點(diǎn)進(jìn)行一次路徑尋優(yōu)實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如表2所示。

表2 實(shí)驗(yàn)結(jié)果Table 2 Experimental results

從表2可以看出：對(duì)30個(gè)目標(biāo)電表節(jié)點(diǎn)路由路徑尋優(yōu)實(shí)驗(yàn)中，在收斂到最優(yōu)解節(jié)點(diǎn)數(shù)量方面，如果采用GAACS算法，集中器節(jié)點(diǎn)對(duì)其中25個(gè)目標(biāo)電表節(jié)點(diǎn)能搜索到最優(yōu)路由路徑，僅對(duì)5個(gè)目標(biāo)電表的尋優(yōu)陷入了局部最優(yōu)解，而采用 GACS，ACS和 MMAS 3種算法，收斂到最優(yōu)解的節(jié)點(diǎn)個(gè)數(shù)分別為23，20和19，收斂到次優(yōu)解的節(jié)點(diǎn)個(gè)數(shù)分別為7，10和10；對(duì)于所有節(jié)點(diǎn)收斂時(shí)迭代次數(shù)平均值方面，GAACS算法所需的迭代數(shù)平均值最少，僅為12.16次，遠(yuǎn)低于MMAS算法的36.28次；對(duì)于收斂到最優(yōu)解所需平均運(yùn)算時(shí)間方面，GAACS算法的平均運(yùn)算時(shí)間也明顯優(yōu)于其他3種算法。這是因?yàn)镚AACS算法利用了遺傳算法的快速全局搜索能力，并在迭代過程中依據(jù)搜索情況對(duì)蟻群系統(tǒng)算法的相關(guān)參數(shù)作自適應(yīng)調(diào)整，有效地克服了蟻群算法搜索時(shí)間長(zhǎng)、易陷入局部最優(yōu)解等缺點(diǎn)。

5 結(jié)論

(1) 針對(duì)實(shí)際電力線載波抄表系統(tǒng)中現(xiàn)有中繼路由算法的不足，提出了一種基于遺傳自適應(yīng)蟻群系統(tǒng)算法的動(dòng)態(tài)中繼路由方法，利用遺傳算法的快速全局搜索能力獲得路徑信息素的初始分布，再結(jié)合蟻群算法的正反饋收斂機(jī)制，同時(shí)依據(jù)搜索情況對(duì)狀態(tài)轉(zhuǎn)移概率因子、信息素?fù)]發(fā)因子、信息素強(qiáng)度等參數(shù)進(jìn)行自適應(yīng)調(diào)整，最終獲得最優(yōu)路由線路。

(2) 將GAACS與GACS，ACS和MMAS算法在算法收斂性、魯棒性、抗毀性以及運(yùn)算時(shí)間方面進(jìn)行了比較。結(jié)果表明GAACS算法不僅具有動(dòng)態(tài)路由路徑尋優(yōu)功能，而且有效地克服了基本蟻群系統(tǒng)算法收斂速度慢、易陷入局部極小值等問題，提高了整個(gè)抄表系統(tǒng)的時(shí)效性。隨著抄表系統(tǒng)中目標(biāo)電表節(jié)點(diǎn)的規(guī)模增大，改進(jìn)的效果越明顯。

[1]趙陽, 董穎華, 陸婋泉, 等.EMI噪聲分離網(wǎng)絡(luò)在電力線噪聲分析中的應(yīng)用[J].中國(guó)電機(jī)工程學(xué)報(bào), 2010, 30(21)∶ 114-120.ZHAO Yang, DONG Yinghua, LU Xiaoquan, et al.EMI noise discrimination network applied to power-line EMI noise analysis[J].Proceedings of the CSEE, 2010, 30(21)∶ 114-120.

[2]羅文亮, 柯熙政, 馬鳴.基于低壓電力線通信信道的自適應(yīng)估計(jì)研究[J].儀器儀表學(xué)報(bào), 2009, 30(8)∶ 1623-1629.LUO Wenliang, KE Xizheng, MA Ming.Study of adaptive estimation based on low-voltage power-line communication channel[J].Chinese Journal of Scientific Instrument, 2009, 30(8)∶1623-1629.

[3]徐志強(qiáng), 翟明岳, 趙宇明.基于電力線信道作用的能量時(shí)頻分布及其能量分配[J].電力系統(tǒng)自動(dòng)化, 2009, 33(1)∶ 75-80.XU Zhiqiang, ZHAI Mingyue, ZHAO Yuming.Energy time frequency distribution based on power line channel effect and its application in energy assignment[J].Automation of Electric Power Systems, 2009, 33(1)∶ 75-80.

[4]陳可, 胡曉光.基于電力線寬帶載波集中器設(shè)計(jì)與中繼算法[J].電力自動(dòng)化設(shè)備, 2011, 31(9)∶ 115-120.CHEN Ke, HU Xiaoguang.Design of concentrator based on electric line broadband carrier and relay routing algorithm[J].Electric Power Automation Equipment, 2011, 31(9)∶ 115-120.

[5]趙杰衛(wèi), 盧文冰, 李賢亮.電力線載波自動(dòng)抄表動(dòng)態(tài)路由技術(shù)研究[J].電力系統(tǒng)通信, 2007, 28(11)∶ 1-5.ZHAO Jiewei, LU Wenbing, LI Xianliang.Research of dynamic routing technology in automatic meter reading system based on power line carrier[J].Telecommunications for Electric Power System, 2007, 28(11)∶ 1-5.

[6]劉曉勝, 戚佳金, 宋其濤, 等.基于蟻群算法的低壓配電網(wǎng)電力線通信組網(wǎng)方法[J].中國(guó)電機(jī)工程學(xué)報(bào), 2008, 28(1)∶ 71-76.LIU Xiaosheng, QI Jiajin, SONG Qitao, et al.Method of constructing power line communication networks over low-voltage distribution networks based on ant colony optimization[J].Proceedings of the CSEE, 2008, 28(1)∶ 71-76.

[7]劉曉勝, 周巖, 戚佳金.電力線載波通信的自動(dòng)路由方法研究[J].中國(guó)電機(jī)工程學(xué)報(bào), 2006, 26(21)∶ 76-81.LIU Xiaosheng, ZHOU Yan, QI Jiajin.Method study of automatic routing for power line communication[J].Proceedings of the CSEE, 2006, 26(21)∶ 76-81.

[8]Murat A, Novruz A.Development a new mutation operator to solve the traveling salesman problem by aid of genetic algorithm[J].Expert Systems with Applications, 2011, 38(3)∶1313-1320.

[9]Semya E, Jacques T, Taicir L.Multiple crossover genetic algorithm for the multiobjective traveling salesman problem[J].Electronic Notes in Discrete Mathematics, 2010, 36(1)∶939-946.

[10]雷友誠(chéng), 涂祖耀, 桂衛(wèi)華, 等.基于遺傳蟻群算法的樹枝型鐵路取送車問題優(yōu)化[J].中南大學(xué)學(xué)報(bào)∶ 自然科學(xué)版, 2011,42(8)∶ 2356-2362.LEI Youcheng, TU Zuyao, GUI Weihua, et al.Optimization of placing-in and taking-out wagons on branch-shaped railway lines based on genetic and ant colony algorithm[J].Journal of Central South University∶ Science and Technology, 2011, 42(8)∶2356-2362.

[11]YANG Jingan, ZHUANG Yanbin.An improved ant colony optimization algorithm for solving a complex combinatorial optimization problem[J].Applied Soft Computing, 2010, 10(2)∶653-660.

[12]ZHAO Dongming, LUO Liang, ZHANG Kai.An improved ant colony optimization for the communication network routing problem[J].Mathematical and Computer Modelling, 2010,52(11)∶ 1976-1981.

[13]WANG Hua, XU Dong, YI Shanwen, et al.A tree-growth based ant colony algorithm for QoS multicast routing problem[J].Expert Systems with Applications, 2011, 38(9)∶ 11787-11795.

[14]焦亞萌, 黃建國(guó), 侯云山.基于蟻群算法的最大似然方位估計(jì)快速算法[J].系統(tǒng)工程與電子技術(shù), 2011, 33(8)∶ 1718-1721.JIAO Yameng, HUANG Jianguo, HOU Yunshan.Fast maximum likelihood direction-of-arrival estimation based on ant colony optimization[J].Systems Engineering and Electronics,2011, 33(8)∶ 1718-1721.

[15]張煜東, 吳樂南, 韋耿, 等.基于自適應(yīng)蟻群算法的軟硬件劃分[J].控制與決策, 2009, 24(9)∶ 1385-1389.ZHANG Yudong, WU Lenan, WEI Geng, et al.Hardware/software partition using adaptive ant colony algorithm[J].Control and Decision, 2009, 24(9)∶ 1385-1389.