基于CW節約算法和遺傳算法的網絡優化

張賽男, 劉東亮

(1. 吉林財經大學 新聞與傳播學院, 長春 130117； 2. 東北師范大學 信息科學與技術學院, 長春 130117)

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

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

1 通信網絡優化問題模型

假設有7個通信節點需要連接, 初始連接圖如圖1所示. 其中, 連接線的數字為設計距離, 現需要對該通信網絡圖進行優化, 以最小的成本代價實現對網絡的連通. 其中, 網絡規劃方案需要結合系統連通、 連接限制控制表和節點負載控制表等制約條件計算網絡投資的大小.

2 CW節約算法

CW節約算法的思想較簡單且易實現, 假設有一個中間連接節點A, 兩個通信節點B,C與其進行連接, 如圖2(A)所示, 則此時的連接代價為

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

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

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

減少的代價即為節約值, 表示為

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

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

圖1 通信網絡規劃設計初始連接圖Fig.1 Initial connection diagram of communication network planning and design

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

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

3 遺傳算法

遺傳算法廣泛應用于組合優化問題中, 尤其在規模龐大的組合優化問題中, 遺傳算法相對于其他算法表現出更好的結果和更高的效率[9]. 遺傳算法基本思想： 提出適應度函數, 作為整個種群要優化的衡量標準, 個體適應環境的能力越強, 其適應度函數值越大, 反之越小. 每個個體都是待優化的向量, 從初始種群開始, 在相應的概率下進行選擇、 交叉和變異操作, 產生新的個體, 形成下一代種群, 重復迭代過程, 直到符合預期的標準. 最后, 在種群中適應度函數值最大的即為最優解[10].

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

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

表1 種群個體編碼

2) 生成初始種群. 在實際運算過程中, 對由個體組成的種群進行運算, 所以首先要產生初始種群, 一般采用隨機策略產生. 本文初始種群為4個個體, 結果列于表2.

3) 計算個體適應度. 產生初始種群后, 首先要對初始種群計算適應度函數值, 用于評判每個個體適應環境的好壞, 實際的適應度函數根據具體的應用場景設計, 本文適應度函數即為給出的待求最大值的函數, 結果列于表2.

表2 初始種群及適應度

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

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

圖3 交叉運算示意圖Fig.3 Schematic diagram of cross-operation

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

7) 循環運算. 循環計算即計算上述步驟1)～6), 不斷產生新一代種群, 并且記錄每代種群的最佳個體, 用于判斷是否滿足停止條件.

8) 停止. 當在新一代種群中找到符合條件的個體, 或達到設定的最大迭代次數時, 即可停止算法. 當前找到的最佳個體即為算法最優解.

4 加入CW算子的遺傳算法

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

(1)

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

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

改進算法的基本步驟如下：

1) 對通信網絡問題進行編碼;

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

3) 循環：

① 判斷是否有滿足條件的個體, 如果有, 則退出循環, 輸出最優解, 如果沒有則繼續;

② 應用交叉算子、 突變算子、 CW算子到種群個體中;

③ 計算種群中個體xi的適應度值F(xi);

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

⑤t=t+1.

5 實驗結果與討論

實驗對比傳統最小生成樹法、 傳統遺傳算法以及結合CW算子的遺傳算法的效果, 并且對比不同節點個數的通信網絡規劃結果. 隨著通信節點數目的增加, 不同算法的成本費用和計算速度比較分別如圖5和圖6所示.

圖5 不同算法的計算結果成本比較Fig.5 Comparison of costs of calculaiton results of different algorithms

圖6 不同算法的計算耗時成本比較Fig.6 Comparison of costs of computational time of different algorithms

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