徐志翔 楊余旺 郭利強(qiáng) 牛曉春 肖高權(quán)

（1.南京理工大學(xué) 南京 210094）（2.兵器淮海工業(yè)集團(tuán)有限公司 長(zhǎng)治 046000）（3.兵裝云箭集團(tuán)有限公司 懷化 419503）

1 引言

A.Rhlswede等在2000年提出網(wǎng)絡(luò)編碼（Network Coding）的理論，其主要思想來源于圖論中著名的最大流最小割理論［1］。不同與傳統(tǒng)的網(wǎng)絡(luò)傳輸技術(shù)中中間節(jié)點(diǎn)僅負(fù)責(zé)轉(zhuǎn)發(fā)信息，網(wǎng)絡(luò)編碼賦予中間節(jié)點(diǎn)編碼和轉(zhuǎn)發(fā)的功能，即中間節(jié)點(diǎn)從各個(gè)輸入鏈路中獲取信息并進(jìn)行編碼，然后把編碼后的數(shù)據(jù)傳輸給所有輸出鏈路［2］，更好地利用網(wǎng)絡(luò)帶寬，增大網(wǎng)絡(luò)吞吐量。但網(wǎng)絡(luò)編碼同時(shí)也帶來了編解碼的開銷。因此，如何在保證網(wǎng)絡(luò)編碼帶來優(yōu)勢(shì)的同時(shí)，將隨之帶來的資源損耗將降低就成了一個(gè)研究的熱點(diǎn)問題。

網(wǎng)絡(luò)編碼優(yōu)化［3］是指在給定的網(wǎng)絡(luò)拓?fù)湎?，針?duì)優(yōu)化的目標(biāo)，在保證達(dá)到理論多播速率［4］的前提下，盡可能地降低網(wǎng)絡(luò)編碼的開銷。文獻(xiàn)［5］證明了網(wǎng)絡(luò)編碼優(yōu)化問題是NP難問題，并使用傳統(tǒng)遺傳算法優(yōu)化網(wǎng)絡(luò)編碼以求得最小編碼邊方案。但是隨著網(wǎng)絡(luò)拓?fù)涞膹?fù)雜度提升，算法運(yùn)行時(shí)間倍增，得到解的質(zhì)量下降。文獻(xiàn)［6］將模擬退火算法融合到網(wǎng)絡(luò)編碼優(yōu)化領(lǐng)域，提出基于模擬退火遺傳算法的網(wǎng)絡(luò)編碼優(yōu)化方案，該算法一方面采用了模擬退火的個(gè)體接收策略保證了種群多樣性，另一方面用網(wǎng)絡(luò)轉(zhuǎn)移矩陣指導(dǎo)遺傳操作，提高了收斂速度。文獻(xiàn)［7］將多目標(biāo)優(yōu)化理論和小生境遺傳算法融合到網(wǎng)絡(luò)編碼優(yōu)化領(lǐng)域，提出基于多目標(biāo)小生境遺傳算法的網(wǎng)絡(luò)編碼優(yōu)化方案，在設(shè)計(jì)適應(yīng)度函數(shù)的適合引入了多目標(biāo)優(yōu)化的概念，兼顧了最小化編碼邊數(shù)和帶寬利用率。雖然這些算法優(yōu)化了傳統(tǒng)的遺傳算法，但是遺傳算法局部搜索能力不足的問題還是沒有得到有效解決。

在上述的研究基礎(chǔ)上，本文提出一種求解網(wǎng)絡(luò)編碼優(yōu)化問題的混合啟發(fā)式算法，算法結(jié)合了遺傳算法并行的大規(guī)模搜索能力和局域搜索能力強(qiáng)的禁忌搜索算法。實(shí)驗(yàn)表明，相比傳統(tǒng)GA算法，能有效得出最少編碼節(jié)點(diǎn)方案，加快了收斂速度，降低網(wǎng)絡(luò)編碼的開銷。

2 網(wǎng)絡(luò)編碼優(yōu)化模型

2.1 網(wǎng)絡(luò)優(yōu)化模型

為了方便研究，我們做出如下約定：

1）G=（V，E）表示一個(gè)單源有向無(wú)環(huán)網(wǎng)絡(luò)，其中V節(jié)點(diǎn)集合，E是邊集合，Rj是網(wǎng)絡(luò)的宿點(diǎn)，|R|表示宿點(diǎn)的個(gè)數(shù)，h表示最大理論傳輸容量，Ni是編碼節(jié)點(diǎn)標(biāo)識(shí)。

2）G（V，E）中每條邊擁有單位傳輸速率，即單位時(shí)間內(nèi)可傳輸單位數(shù)據(jù)。

3）采用隨機(jī)線性網(wǎng)絡(luò)編碼［8］，編碼操作是基于有限域的線性操作。對(duì)于每個(gè)節(jié)點(diǎn)v，分配一個(gè)節(jié)點(diǎn)編碼向量，標(biāo)識(shí)該節(jié)點(diǎn)輸入鏈路的編碼情況。

4）將需要進(jìn)額外編碼操作的節(jié)點(diǎn)稱為編碼節(jié)點(diǎn)，不需要進(jìn)行編碼操作的節(jié)點(diǎn)稱為普通轉(zhuǎn)發(fā)節(jié)點(diǎn)。

5）輸出鏈路傳輸?shù)男畔⑹怯筛鬏斎腈溌飞蟼鬏斝畔⒌幕谟邢抻蜻\(yùn)算的線性組合，這種組合的系數(shù)所構(gòu)成的向量稱為該鏈路的局部編碼向量。輸出鏈路的信息相對(duì)于源節(jié)點(diǎn)的各信息分量的一個(gè)映射系數(shù)稱為該輸出鏈路的全局編碼向量。

則對(duì)于宿點(diǎn)Rj的h條輸入信息流，傳輸?shù)男畔⒘飨蛄靠杀硎緸楣剑?/p>

目標(biāo)函數(shù)：編碼節(jié)點(diǎn)的總數(shù)最小，即

約束條件：達(dá)到網(wǎng)絡(luò)的組播速率即

2.2 圖分解法

對(duì)一個(gè)網(wǎng)絡(luò)拓?fù)渲械闹虚g節(jié)點(diǎn)分為兩類，第一類為入度為1的中間節(jié)點(diǎn)，顯然這種節(jié)點(diǎn)是不需要編碼的。第二類為入度大于等于2的中間節(jié)點(diǎn)稱為匯點(diǎn)。針對(duì)匯點(diǎn)，當(dāng)出度大于1后，無(wú)法確實(shí)其是否需要執(zhí)行編碼操作以及需要編碼操作時(shí)如何編碼都是不可確定的，因此，我們參考文獻(xiàn)［9］提出的圖分解法。假設(shè)一個(gè)匯點(diǎn)有N個(gè)輸入，有M個(gè)輸出，其中N＞1，M＞1，則引入N個(gè)輸入輔助節(jié)點(diǎn)，M個(gè)輸出輔助節(jié)點(diǎn)，把匯點(diǎn)的N個(gè)輸入連接在對(duì)應(yīng)的輸入輔助節(jié)點(diǎn)上，M個(gè)輸出流連接到對(duì)于的輸出輔助節(jié)點(diǎn)上，同時(shí)，每個(gè)輸入輔助節(jié)點(diǎn)連接所有的輸出輔助節(jié)點(diǎn)。具體如圖1所示。

圖1 圖分解法

2.3 節(jié)點(diǎn)的編碼

在有向圖G（V，E）中，針對(duì)所有匯點(diǎn)，我們?yōu)閰R點(diǎn)的輸入鏈路分配二進(jìn)制編碼向量，用來標(biāo)識(shí)該輸入鏈路是否參與編碼運(yùn)算。

如圖2，匯點(diǎn)v1入度為3，分別是i1，i2，i3，出度為1，所以該匯點(diǎn)的編碼向量用三位的二進(jìn)制向量表示。當(dāng)匯點(diǎn)v1的編碼向量為（1，0，0）時(shí)，表示只有鏈路i1參與編碼運(yùn)算。若編碼向量為（1，1，1）時(shí)，則表示三條鏈路上的信息全部參與編碼運(yùn)算。當(dāng)整個(gè)網(wǎng)絡(luò)中的所有匯點(diǎn)的二進(jìn)制編碼分配完畢后，整個(gè)網(wǎng)絡(luò)的信息流進(jìn)而得以確定。

圖2 編碼向量為（1，0，0）的節(jié)點(diǎn)

3 遺傳算法

遺傳算法［10］是一種模擬自然界生物演化過程的計(jì)算模型，最先由美國(guó)的Holland教授提出。遺傳算法具有很好全局搜索能力，不會(huì)陷入類似梯度下降算法致使快速下降引發(fā)的局部收斂陷阱，是一種運(yùn)算簡(jiǎn)單、能有效解決問題的普適方法。但是，傳統(tǒng)的遺傳算法同樣存在不少缺點(diǎn)，例如局部搜索能力差，容易早熟，無(wú)法收斂于全局最優(yōu)解。其主要起影響作用的遺傳操作主要有選擇算子、交叉算子、變異算子，下面我們對(duì)主要傳統(tǒng)的遺傳算法的主要算子和適應(yīng)度函數(shù)進(jìn)行說明并進(jìn)行初步的優(yōu)化。

圖3 傳統(tǒng)遺傳算法

3.1 選擇算子

本文算法中選擇算子采用輪盤賭選擇方法（Roulette Whell Selection）。輪盤賭選擇方法屬于一種回放式的隨機(jī)的采樣方法，它的基本思想就是個(gè)體適應(yīng)度值在整個(gè)種群中適應(yīng)度值總和的占比決定該個(gè)體進(jìn)入到子代種群的概率。即產(chǎn)生一隨機(jī)數(shù)p，p∈（0，1），若

則個(gè)體i被選中，其中fitnessj為個(gè)體j的適應(yīng)度值，N是種群的大小。

3.2 交叉算子

遺傳算法中，交叉率選擇對(duì)于遺傳算法的性能有著重要的影響。當(dāng)交叉率過大時(shí)，不利于精英種群基因的傳承而當(dāng)交叉率過小時(shí)，又不利于產(chǎn)生新解。因此，不同于傳統(tǒng)遺傳算法采用常數(shù)交叉率，本文算法采用自適應(yīng)交叉率，每個(gè)個(gè)體都以一定的交叉率進(jìn)行交叉運(yùn)算，第i條個(gè)體的交叉率Pc的計(jì)算公式如下：

其中c1、c2是大于1的常系數(shù)，fitnessmax，是種群中最大的適應(yīng)值，fitnessavg是最種群中平均適應(yīng)度值。

針對(duì)網(wǎng)絡(luò)編碼的場(chǎng)景，交叉運(yùn)算采用單元交叉，以節(jié)點(diǎn)的編碼系數(shù)為單元，即隨機(jī)地找出一個(gè)節(jié)點(diǎn)，交換兩個(gè)相互配對(duì)染色體的該節(jié)點(diǎn)的編碼系數(shù)。這種方法實(shí)現(xiàn)簡(jiǎn)單且也能使得子代保留父代基本特征。

3.3 變異算子

同交叉算子，當(dāng)變異算子的變異率過小時(shí)，不利于新解的產(chǎn)生，過大時(shí)，效果則趨向于隨機(jī)算法，失去原有的意義。因此，采用自適應(yīng)變異率，每個(gè)個(gè)體都以一定的變異率進(jìn)行變異運(yùn)算，第i條個(gè)體的變異率Pc的計(jì)算公式如下

其中m1、m2是大于1的常系數(shù)。

變異是指對(duì)每個(gè)個(gè)體編碼串隨機(jī)地指定一位或者幾位基因位以一定的變異概率進(jìn)行變異的運(yùn)算。本文的變異運(yùn)算采用取反運(yùn)算代。變異運(yùn)算對(duì)于改進(jìn)遺傳算法的局部搜索的能力及維持種群多樣性，并防止早熟現(xiàn)象的出現(xiàn)都有比較好的效果。

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

在遺傳算法中，適應(yīng)度函數(shù)用于評(píng)價(jià)染色體性能優(yōu)劣的指標(biāo)，需要結(jié)合具體求解問題來進(jìn)行設(shè)計(jì)，是整個(gè)遺傳算法的核心。本算法除對(duì)滿足約束條件的解進(jìn)行區(qū)分外，針對(duì)不滿足約束條件的解，根據(jù)能解碼的目標(biāo)節(jié)點(diǎn)個(gè)數(shù)進(jìn)行區(qū)分，對(duì)染色體i，其適應(yīng)度函數(shù)設(shè)計(jì)如下：

其中G（i）是在i滿足約束條件下，能解碼的目的節(jié)點(diǎn)數(shù)，N是網(wǎng)絡(luò)總結(jié)點(diǎn)數(shù)，T（i）是指需要編碼的網(wǎng)絡(luò)節(jié)點(diǎn)，C1、C2為常數(shù)。

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

針對(duì)遺傳算法長(zhǎng)于全局搜索短于局部搜索的特點(diǎn)，我們引進(jìn)了禁忌搜索算法。禁忌搜索（Taboo Search TS）由Glover于1989年提出的一種基于局部搜索的算法［11～12］，是一種高效的逐步優(yōu)化算法。相對(duì)于一般的局部搜索來說，為避免無(wú)效的重復(fù)搜索，禁忌算法模擬人類大腦中的記憶功能，引入了禁忌表的概念，通過禁忌表記錄近期訪問過的解，在一定時(shí)間內(nèi)禁止訪問該解，進(jìn)而更快地搜索更大范圍的解空間。禁忌搜索的偽代碼如表1所示。

表1 禁忌搜索算法偽代碼

禁忌搜索雖然搜索能力比較快且易于實(shí)現(xiàn)，但是它的性能優(yōu)劣很大程度上依賴初始解的質(zhì)量，如果初始解質(zhì)量較差，也會(huì)容易陷入局部最優(yōu)解。同時(shí)，禁忌算法作為一種串行算法，即它的運(yùn)算過程是一個(gè)解向另外一個(gè)解轉(zhuǎn)化的過程，相對(duì)遺傳操作來說迭代次數(shù)多，計(jì)算時(shí)間長(zhǎng)。而遺傳算法在初期迭代時(shí)，群體在解空間的分布還不是很穩(wěn)定，如果在初期就是用禁忌局部搜索，會(huì)導(dǎo)致計(jì)算量過大，花費(fèi)較大的時(shí)間成本，而且得到的解的質(zhì)量也不高。

因此，本文提出了一種基于改進(jìn)遺傳算法的網(wǎng)絡(luò)編碼節(jié)點(diǎn)最小化算法。該算法主要引入了禁忌搜索，將長(zhǎng)于全局搜索的遺傳算法和長(zhǎng)于局部搜索的禁忌搜索算法結(jié)合，即首先利用遺傳算法進(jìn)行全局搜索，使群體中的個(gè)體相對(duì)穩(wěn)定的分布在解空間的大部分區(qū)域，然后用禁忌搜索算法進(jìn)行局部搜索以優(yōu)化解的質(zhì)量。該算法有效整合了傳統(tǒng)遺傳算法并行大范圍搜索能力和禁忌搜索優(yōu)秀的局部搜索能力，大大降低了局部收斂的可能性，提高了全局收斂性能。其算法流程下所示。該混合策略的計(jì)算過程如下。

步驟1：設(shè)置相關(guān)參數(shù)，種群population，最大迭代次數(shù)T，禁忌搜索觸發(fā)持續(xù)代數(shù)S，當(dāng)前迭代代數(shù)t=0，最大適應(yīng)值持續(xù)代數(shù)BestfitConAlg=0；

步驟2：確定編碼方式，產(chǎn)生初始種群；

步驟3：計(jì)算每個(gè)個(gè)體的適應(yīng)值，保存最大適應(yīng)值的個(gè)體進(jìn)入新的種群；

步驟4：t++；如果滿足觸發(fā)禁忌遺傳算法的條件，執(zhí)行步驟9，否則執(zhí)行步驟5；

步驟5：采用輪盤賭選擇進(jìn)行選擇操作；

步驟6：采用自適應(yīng)交叉概率選擇個(gè)體執(zhí)行單元交叉操作；

步驟7：采用自適應(yīng)變異概率選擇個(gè)體執(zhí)行變異操作；

步驟8：如果滿足終止條件，停止運(yùn)算，否則，轉(zhuǎn)而執(zhí)行步驟4；

步驟9：t++；調(diào)用禁忌搜索算法，對(duì)種群的每個(gè)個(gè)體進(jìn)行局部搜索；執(zhí)行步驟4；

步驟10：如果滿足終止條件，停止運(yùn)算，否則，轉(zhuǎn)而執(zhí)行步驟8。

其中，觸發(fā)禁忌遺傳算法的條件：

當(dāng)BestfitConAlg==S時(shí)，觸發(fā)一次禁忌搜索，每觸發(fā)一次S值降低一半，BestfitConAlg=0s；當(dāng)最大適應(yīng)值改變時(shí)，S恢復(fù)初始值，如圖4所示，假設(shè)初始S值為20。

圖4 S值變化圖

在0～10次中，最大適應(yīng)值不變時(shí)，每執(zhí)行一次禁忌算子，S值將為一半，當(dāng)降至0時(shí)，即一直執(zhí)行禁忌算子。當(dāng)最大適應(yīng)值改變時(shí)，S值恢復(fù)初始設(shè)定值。

5 仿真

為驗(yàn)證改進(jìn)算法的有效性，本文設(shè)計(jì)了仿真實(shí)驗(yàn)，通過不同網(wǎng)絡(luò)拓?fù)浜筒煌惴ǖ膶?shí)驗(yàn)結(jié)果對(duì)比，驗(yàn)證了本算法的有性能。

5.1 實(shí)驗(yàn)環(huán)境與實(shí)驗(yàn)數(shù)據(jù)集

本文仿真環(huán)境為Dell PC機(jī)，處理器為Intel（R）Core（TM）i5-3210M CPU@2.50GHz，內(nèi)存為4.00GB，操作系統(tǒng)為64位Win7系統(tǒng)，對(duì)2～4層蝶形圖擴(kuò)展網(wǎng)絡(luò)從算法有效性、運(yùn)行時(shí)間及收斂性方面與傳統(tǒng)遺傳算法進(jìn)行仿真比較分析。3層蝶形圖擴(kuò)展網(wǎng)絡(luò)如圖5所示。

圖5 三層蝴蝶網(wǎng)絡(luò)模型

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

表2給出了本文算法和傳統(tǒng)的遺傳算法在3組網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)下多次實(shí)驗(yàn)得到的平均值，即在保證最大組播速率的前提下，所需編碼的最小節(jié)點(diǎn)數(shù)。從表中我們看出相對(duì)與傳統(tǒng)GA算法，本文算法能有效地得出最小編碼節(jié)點(diǎn)數(shù)。

表2 本文算法與傳統(tǒng)遺傳算法有效性驗(yàn)證結(jié)果比較

為了分析和比較算法的收斂性能，實(shí)驗(yàn)中記錄了三層蝴蝶模型的網(wǎng)絡(luò)拓?fù)湎?，群體最佳適應(yīng)度的變化情況。從圖6我們看出，傳統(tǒng)的遺傳算法適應(yīng)度增長(zhǎng)速度比較緩慢，40代的時(shí)候發(fā)生突變，表明搜索到符合約束的解。80代的時(shí)候傳統(tǒng)的遺傳算法收斂于局部最優(yōu)解。改進(jìn)后的遺傳算法適應(yīng)度增長(zhǎng)速度明顯較快，但是在70代左右時(shí)仍然收斂于局部最優(yōu)解。本文提出的混合禁忌改進(jìn)遺傳算法適應(yīng)值穩(wěn)步上升，并在140代后達(dá)到最優(yōu)解。這是因?yàn)楸疚乃惴ㄒ肓私伤惴?，彌補(bǔ)了遺傳算法局部搜索能力不足的缺點(diǎn)，有效結(jié)合了遺傳算法出色的并行大范圍搜索和禁忌搜索出色的局部搜索能力，提高了解的質(zhì)量。

圖6 收斂性能比較

6 結(jié)語(yǔ)

本文在代數(shù)網(wǎng)絡(luò)編碼的框架下提出了網(wǎng)絡(luò)編碼優(yōu)化模型，在此模型基礎(chǔ)上給出了一種求解網(wǎng)絡(luò)編碼優(yōu)化問題的混合啟發(fā)式算法。本文算法是在傳統(tǒng)遺傳算法的基本之上，針對(duì)遺傳算法的不足引入了一些新的解決措施，減少無(wú)效的遺傳操作，提高了遺傳多樣性；設(shè)計(jì)了新的適應(yīng)度函數(shù)，將沒有達(dá)到約束條件的解根據(jù)能解碼的目的節(jié)點(diǎn)的個(gè)數(shù)進(jìn)行區(qū)分，提高了種群的多樣性。最后，引入了禁忌算法，改進(jìn)了遺傳算法局部搜索能力不足的缺點(diǎn)，有效避免了算法的局部收斂。實(shí)驗(yàn)結(jié)果表明，本文算法在達(dá)到理論多播速率的基礎(chǔ)上，能有效得出最小編碼節(jié)點(diǎn)數(shù)，降低網(wǎng)絡(luò)編碼的編解碼開銷，同時(shí)提高了收斂速度，解決了遺傳算法在網(wǎng)絡(luò)編碼應(yīng)用中的陷入局部最優(yōu)的問題，展現(xiàn)出的性能明顯優(yōu)于傳統(tǒng)遺傳算法。