張賽男, 劉東亮

(1. 吉林財(cái)經(jīng)大學(xué) 新聞與傳播學(xué)院, 長(zhǎng)春 130117； 2. 東北師范大學(xué) 信息科學(xué)與技術(shù)學(xué)院, 長(zhǎng)春 130117)

作為互聯(lián)網(wǎng)的最基礎(chǔ)設(shè)施, 通信網(wǎng)絡(luò)的質(zhì)量和速度目前已嚴(yán)重影響人們的生活質(zhì)量[1]. 在網(wǎng)絡(luò)發(fā)展初期, 主要采用人工方式進(jìn)行網(wǎng)絡(luò)規(guī)劃, 這在現(xiàn)在龐大的網(wǎng)絡(luò)通信工程中是不可行的； 后來人們采用最小生成樹方法搜索問題的全局最優(yōu)解, 但隨著網(wǎng)絡(luò)通信越來越復(fù)雜, 規(guī)模越來越龐大, 該方法效果越來越不理想. 一方面最小生成樹方法未考慮到實(shí)際工程的限制, 無法找到最優(yōu)解, 甚至無法找到近似最優(yōu)解; 另一方面, 隨著網(wǎng)絡(luò)規(guī)模的逐漸增大, 最小生成樹法的耗時(shí)呈指數(shù)增長(zhǎng)[2].

在實(shí)際網(wǎng)絡(luò)優(yōu)化問題中, 最顯著的特點(diǎn)是網(wǎng)絡(luò)連接未知. 模擬退火算法基本始于一個(gè)已知狀態(tài), 繼而隨機(jī)進(jìn)行搜索, 這與網(wǎng)絡(luò)優(yōu)化問題不符[3-4]. 在進(jìn)化策略中, 由于選擇機(jī)制的制約, 易使算法過早收斂, 進(jìn)而導(dǎo)致在很多情況下無法使問題得到最優(yōu)解. 遺傳算法的特點(diǎn)是以隨機(jī)生成的初始種群開始, 不斷地迭代, 求解適應(yīng)度函數(shù), 最終得出最佳解, 符合通信網(wǎng)絡(luò)的優(yōu)化條件. 本文提出在遺傳算法迭代時(shí), 結(jié)合CW(Clarke Wright)節(jié)約算法, 使遺傳算法的收斂速度加快, 且不會(huì)影響遺傳算法的隨機(jī)性, 即能找到近似最優(yōu)解[5].

1 通信網(wǎng)絡(luò)優(yōu)化問題模型

假設(shè)有7個(gè)通信節(jié)點(diǎn)需要連接, 初始連接圖如圖1所示. 其中, 連接線的數(shù)字為設(shè)計(jì)距離, 現(xiàn)需要對(duì)該通信網(wǎng)絡(luò)圖進(jìn)行優(yōu)化, 以最小的成本代價(jià)實(shí)現(xiàn)對(duì)網(wǎng)絡(luò)的連通. 其中, 網(wǎng)絡(luò)規(guī)劃方案需要結(jié)合系統(tǒng)連通、 連接限制控制表和節(jié)點(diǎn)負(fù)載控制表等制約條件計(jì)算網(wǎng)絡(luò)投資的大小.

2 CW節(jié)約算法

CW節(jié)約算法的思想較簡(jiǎn)單且易實(shí)現(xiàn), 假設(shè)有一個(gè)中間連接節(jié)點(diǎn)A, 兩個(gè)通信節(jié)點(diǎn)B,C與其進(jìn)行連接, 如圖2(A)所示, 則此時(shí)的連接代價(jià)為

2×S(A,B)+2×S(B,C),

如果把連接方式改為如圖2(B)所示, 則此時(shí)的連接代價(jià)為

S(A,B)+S(A,C)+S(B,C),

減少的代價(jià)即為節(jié)約值, 表示為

S(A,B)+S(A,C)-S(B,C).

在所有這種通信節(jié)點(diǎn)中找出節(jié)約值最大的, 調(diào)整連接方式. 然后不斷循環(huán)上述操作, 直到滿足連通條件[6]為止.

圖1 通信網(wǎng)絡(luò)規(guī)劃設(shè)計(jì)初始連接圖Fig.1 Initial connection diagram of communication network planning and design

圖2 CW節(jié)約算法應(yīng)用通信連接前后比較Fig.2 Comparison of CW saving algorithm before and after application of communication connection

如果把CW節(jié)約算法直接應(yīng)用到通信網(wǎng)絡(luò)規(guī)劃中, 該算法只能考慮到距離成本問題, 無法考慮其他限制條件, 如負(fù)載限制、 連接數(shù)量限制等[7]. 所以本文把CW節(jié)約算法和遺傳算法相結(jié)合, 以加快遺傳算法的收斂速度, 而遺傳算法的特點(diǎn)是可以求適應(yīng)度函數(shù), 該適應(yīng)度函數(shù)可包含所有實(shí)際工程中的問題[8].

3 遺傳算法

遺傳算法廣泛應(yīng)用于組合優(yōu)化問題中, 尤其在規(guī)模龐大的組合優(yōu)化問題中, 遺傳算法相對(duì)于其他算法表現(xiàn)出更好的結(jié)果和更高的效率[9]. 遺傳算法基本思想： 提出適應(yīng)度函數(shù), 作為整個(gè)種群要優(yōu)化的衡量標(biāo)準(zhǔn), 個(gè)體適應(yīng)環(huán)境的能力越強(qiáng), 其適應(yīng)度函數(shù)值越大, 反之越小. 每個(gè)個(gè)體都是待優(yōu)化的向量, 從初始種群開始, 在相應(yīng)的概率下進(jìn)行選擇、 交叉和變異操作, 產(chǎn)生新的個(gè)體, 形成下一代種群, 重復(fù)迭代過程, 直到符合預(yù)期的標(biāo)準(zhǔn). 最后, 在種群中適應(yīng)度函數(shù)值最大的即為最優(yōu)解[10].

下面舉例描述遺傳算法的過程. 給出一個(gè)函數(shù), 求出該函數(shù)的最大值：

1) 種群個(gè)體的編碼. 類似于生物的染色體帶有多個(gè)基因, 遺傳算法中的個(gè)體是帶有多個(gè)信息段的信息串, 或者在有些應(yīng)用中為多維向量. 本文采用兩個(gè)三位二進(jìn)制分別表示x1和x2, 將二者的組合作為種群中的個(gè)體, 且個(gè)體的取值范圍為8個(gè)值, 種群個(gè)體編碼列于表1.

表1 種群個(gè)體編碼

2) 生成初始種群. 在實(shí)際運(yùn)算過程中, 對(duì)由個(gè)體組成的種群進(jìn)行運(yùn)算, 所以首先要產(chǎn)生初始種群, 一般采用隨機(jī)策略產(chǎn)生. 本文初始種群為4個(gè)個(gè)體, 結(jié)果列于表2.

3) 計(jì)算個(gè)體適應(yīng)度. 產(chǎn)生初始種群后, 首先要對(duì)初始種群計(jì)算適應(yīng)度函數(shù)值, 用于評(píng)判每個(gè)個(gè)體適應(yīng)環(huán)境的好壞, 實(shí)際的適應(yīng)度函數(shù)根據(jù)具體的應(yīng)用場(chǎng)景設(shè)計(jì), 本文適應(yīng)度函數(shù)即為給出的待求最大值的函數(shù), 結(jié)果列于表2.

表2 初始種群及適應(yīng)度

4) 選擇運(yùn)算. 選擇運(yùn)算的過程即為遺傳算法的優(yōu)勝劣汰過程. 選擇過程就是依據(jù)適應(yīng)度大小對(duì)種群進(jìn)行篩選, 較高的適應(yīng)度會(huì)有較高的幾率被選中. 本文采用的選擇方法為函數(shù)值較大的則以一定的概率確定其被復(fù)制到下一代的個(gè)體數(shù)量. 編號(hào)為2的個(gè)體由于適應(yīng)度函數(shù)值較大被選擇了兩次, 而其余個(gè)體則只被選擇一次.

5) 交叉運(yùn)算. 交叉運(yùn)算是為了把整體解中較好的特征傳入下一代種群. 交叉運(yùn)算主要采用以一定的概率在染色體中選擇交叉點(diǎn), 把每個(gè)母染色體分為兩部分, 然后兩個(gè)染色體互換這兩部分. 本文的交叉過程即為隨機(jī)進(jìn)行配對(duì), 然后隨機(jī)選擇交叉點(diǎn), 把染色體串互換即可. 交換過程如圖3所示.

圖3 交叉運(yùn)算示意圖Fig.3 Schematic diagram of cross-operation

6) 變異運(yùn)算. 變異運(yùn)算與交叉運(yùn)算相同, 是產(chǎn)生下一代個(gè)體的方法, 但其模擬基因突變的過程, 主要是染色體中某段基因以極小的概率發(fā)生突變. 本文發(fā)生突變的過程是隨機(jī)選擇一個(gè)突變點(diǎn), 然后按某個(gè)指定的突變概率, 對(duì)參數(shù)串中突變點(diǎn)的二進(jìn)制取反即可.

7) 循環(huán)運(yùn)算. 循環(huán)計(jì)算即計(jì)算上述步驟1)～6), 不斷產(chǎn)生新一代種群, 并且記錄每代種群的最佳個(gè)體, 用于判斷是否滿足停止條件.

8) 停止. 當(dāng)在新一代種群中找到符合條件的個(gè)體, 或達(dá)到設(shè)定的最大迭代次數(shù)時(shí), 即可停止算法. 當(dāng)前找到的最佳個(gè)體即為算法最優(yōu)解.

4 加入CW算子的遺傳算法

在遺傳算法中, 產(chǎn)生下一代的步驟主要是選擇、 復(fù)制交叉、 突變等方式, 但其缺點(diǎn)是相對(duì)耗時(shí)較大, 本文提出加入CW節(jié)約算子, 作為遺傳算法產(chǎn)生下一代的算子, 加快算法的收斂速度.

(1)

其中:x=(x1,x2,…,xn)T為目標(biāo)函數(shù)的向量; f(x)為目標(biāo)函數(shù). 式(1)為約束條件, 滿足該條件的解稱為可行解. 遺傳算法中, 將n維決策變量x=(x1,x2,…,xn)T用n個(gè)xi(i=1,2,…,n)所組成的符號(hào)串X=x1x2…xn表示. 每個(gè)xi即為一個(gè)遺傳基因, 其全部可能的取值稱為等位基因. X是由n個(gè)遺傳基因組成的一個(gè)染色體. 染色體的長(zhǎng)度一般為定長(zhǎng), 少數(shù)情況可以是變長(zhǎng)的. 這里的等位基因可以是一組整數(shù), 或是可行解范圍內(nèi)的實(shí)數(shù),也可以是一種記號(hào). 然后染色體進(jìn)行選擇、 交叉、 突變, 都在向量上操作, 其中突變是隨機(jī)的選擇向量的某一維參數(shù)做運(yùn)算. 遺傳算法由于交叉點(diǎn)和突變點(diǎn)都是隨機(jī)選擇的, 所以種群向較好的趨勢(shì)發(fā)展, 導(dǎo)致算法的速度較慢. 本文提出在產(chǎn)生下一代時(shí), 加入CW節(jié)約算子, 從而加快遺傳算法的收斂速度. 改進(jìn)后的遺傳算法流程如圖4所示.

圖4 結(jié)合CW算子的遺傳算法流程Fig.4 Flow chart of genetic algorithm combined with CW operator

改進(jìn)算法的基本步驟如下：

1) 對(duì)通信網(wǎng)絡(luò)問題進(jìn)行編碼;

2) 隨機(jī)的初始化種群個(gè)體x0=(x1,x2,…,xn);

3) 循環(huán)：

① 判斷是否有滿足條件的個(gè)體, 如果有, 則退出循環(huán), 輸出最優(yōu)解, 如果沒有則繼續(xù);

② 應(yīng)用交叉算子、 突變算子、 CW算子到種群個(gè)體中;

③ 計(jì)算種群中個(gè)體xi的適應(yīng)度值F(xi);

④ 淘汰適應(yīng)度較差的個(gè)體, 其余部分即為下一代種群X(t+1);

⑤t=t+1.

5 實(shí)驗(yàn)結(jié)果與討論

實(shí)驗(yàn)對(duì)比傳統(tǒng)最小生成樹法、 傳統(tǒng)遺傳算法以及結(jié)合CW算子的遺傳算法的效果, 并且對(duì)比不同節(jié)點(diǎn)個(gè)數(shù)的通信網(wǎng)絡(luò)規(guī)劃結(jié)果. 隨著通信節(jié)點(diǎn)數(shù)目的增加, 不同算法的成本費(fèi)用和計(jì)算速度比較分別如圖5和圖6所示.

圖5 不同算法的計(jì)算結(jié)果成本比較Fig.5 Comparison of costs of calculaiton results of different algorithms

圖6 不同算法的計(jì)算耗時(shí)成本比較Fig.6 Comparison of costs of computational time of different algorithms

由圖5和圖6可見, 最小生成樹方法生成的最佳可行解由于只考慮了距離的成本, 所以找到的可行解較差, 基本無法使用, 且隨著通信節(jié)點(diǎn)數(shù)量的增長(zhǎng), 計(jì)算時(shí)間呈指數(shù)增長(zhǎng). 而結(jié)合CW算子的遺傳算法與傳統(tǒng)遺傳算法的可行解結(jié)果接近, 但由于CW算子的快速收斂效果, 使改進(jìn)遺傳算法的計(jì)算時(shí)間降低了約40%, 且隨著通信節(jié)點(diǎn)的增長(zhǎng), 效率會(huì)更高. 因此, 結(jié)合CW算子的遺傳算法在解決通信網(wǎng)絡(luò)規(guī)劃問題上效果顯著, 運(yùn)算效率更快.