基于遺傳算法的光傳送網絡規劃

劉小鈺，李士心，張 海

（天津職業技術師范大學電子工程學院，天津 300222）

光傳送網絡（optical transport network，OTN）可以在光域中實現業務信號的傳輸、復用、路由和監控，且性能和生存能力仍可以得到保障[1-2]。在確定城市連接數和資源限制的情況下，如何連接足夠多的區域則是迫切需要研究的課題，這是一種組合尋優的問題，容易描述但難于處理。本文通過對全國12 個城市群間所構筑的傳送網絡連接與網絡價值進行建模仿真與分析，尋找出網絡價值最大化的連接方式。

1 光傳送網絡的網絡價值及模型數據的選取

1.1 光傳送網絡的網絡價值

不同傳輸格式下的傳輸距離如表1 所示。3 種典型光傳輸設備參數在優化升級后均發生了變化。

表1 不同傳輸格式下的傳輸距離

優化通信網絡的目的是在資源一定的情況下，把更多的人口更充分地連接到一起，網絡價值定義如下。

（1）給出連接的定義 直接連接2 個區域的鏈路。

（2）根據要求給出單個連接的價值定義 連接區域人口數乘積的開方與傳輸容量的乘積。

網絡的價值則是所有連接價值的加權和，即

網絡價值=∑權重×容量×人口

下面舉例說明網絡價值的計算方法。選取北京、上海、南京3 座城市，3 個節點網絡示意圖如圖1 所示。

圖1 3 個節點網絡示意圖

首先要求3 座城市之間互有連接，然后根據城市之間的距離可以得到傳輸容量，進而由傳輸容量配合人口數算出網絡價值（network value，NV）為（假定每條傳輸鏈路的權重為1）

式中：m 為百萬人（million）。

該網絡的連接數為3，但是現實生產中，不可能讓每2 個城市之間均互有連接，這樣對資源是極大的浪費。實際上要想將這3 個地區的人口實現互聯，并不需兩兩城市之間建立連接，可通過使用中間轉節點的方式連接起來[3]。從如圖1（b）可知，北京和南京之間需通過上海中轉，這種情況下只需要建立2 個連接，即北京-上海，上海-南京。可進行如下安排：先保留一半容量（100 GB/s）給北京-上海之間的傳輸，而剩下的另一半容量用于南京-北京的信號傳輸（100 GB/s），同時南京-上海之間的直接傳輸容量也會降低至300 GB/s，此時網絡的價值[4]為

根據需要2 個節點之間也可以有多個連接。

1.2 模型數據的選取

在全國范圍內選取典型的12 個城市構筑一個城市群，包括哈爾濱、北京&天津、上海、鄭州、武漢、西安、重慶、成都、拉薩、烏魯木齊、廣州&深圳、昆明。

（1）由表1 及城市間距構建傳輸總容量，為了直觀顯示，還需將各城市的坐標位置（經度和緯度）顯示在圖上[5]。

（2）由傳輸連接數的要求計算出總容量，而后由總容量及城市人口數建立起網絡價值的函數，本研究所使用的人口數為各城市在某年的人口數據統計。共有12 個城市，故要實現兩兩互聯總連接數需有（12×11）/2=66 條。可知當連接數為66 條（即每2 個城市之間均互有連接）時，網絡總價值以及傳輸總容量是一個確定的算術問題，不需要借助該算法來尋優，且此時的網絡價值最大，資源耗費也最大；而此處需要權衡連接數與網絡價值的關系，基于資源等因素的限制，本研究只求解連接數為33 條、17 條以及49 條時的總容量以及網絡價值來進行對比，以分析在限定連接數即限定資源配置的情況下，如何連接更多人口，達到網絡價值最大化[6]；也可分析如何平衡東西部的連接。

2 遺傳算法機理及優化模型建立

2.1 遺傳算法機理

在遺傳算法中，對于要優化解決的問題可將其編碼為一個簡單的字符串，將其稱為染色體[7]。本研究中采用實數編碼，將2 個城市之間的連接進行編碼且不用解碼，這樣既符合合理化需要又能簡化程序。在算法的開端先隨機生成1 個種群（即1 個染色體群組）。對于每個個體計算其適應度值并排序，然后進行選擇、交叉、變異等一系列遺傳操作，再根據適應度來排序，選擇出新的種群，周而復始，直到終止條件出現[8]。

2.2 遺傳算法實現以及優化模型建立

（1）種群初始化。應用實數編碼進行染色體的編碼，個體包含了城市群及兩兩互聯時所需連接數，由于共有12 個城市，要實現兩兩互聯可知總連接數有（12×11）/2=66 條；由此可知每個個體編碼長度為66，另外根據算法要求和實驗效果可設置種群規模為100，進化次數為600。

（2）適應度函數。由于此發明是在給定區域連接數的情況下去求解網絡價值最大化的連接方式，故適應度函數采用整個光傳送網絡的網絡價值來表示。

（3）遺傳操作—選擇。采用“輪盤賭”選擇法從第t代群體中選擇出一些適應度值高的優秀個體遺傳到下一代群體中[9]。該方法簡單實用又不失精確性。這種選擇基于比例來進行：若個體i 個適應度為fi，種群大小為NP，則個體i 被選擇的概率為

（4）遺傳操作—交叉。交叉是指將個體進行兩兩配對并交換部分染色體片段，其作用較為關鍵，可以使得優秀個體的優秀基因傳遞到下一代。采用“君主方案”進行交叉操作，首先選擇適應度值最高的染色體作為君主染色體，放在整個種群的奇數位，與其靠后一位的偶數位構成一對，接著根據交叉概率Pc確定交叉點的個數（Pc= 0.8），確定規則為：n = round（D × Pc），其中D 為染色體的維數，然后按交叉點個數，根據隨機生成的交叉位將每對染色體進行交換片段，得到新種群[10-11]。

（5）遺傳操作—變異。變異保證了種群基因的多樣性，變異概率此處不應太大，可設Pm=0.2，否則基因突變的可能性較大。從交叉后得到的種群中按變異概率Pm隨機選一些進行變異的個體，確定變異位后將該位的二進制取反，生成一個新個體。

對新產生的群體返回第（2）步，再進行一輪運算，對個體適應度值再進行優化，多次循環，直至終止循環的條件出現[12]。

3 模型訓練及仿真結果分析

對于整個城市群的傳輸鏈路而言，先將各城市坐標顯示在圖上，連接數為33、17、49 條時的最大傳輸容量、連接情況及網絡價值分別如圖2、圖3 和圖4 所示。

圖2 連接數為33 條時的最大傳輸容量、連接情況及網絡價值

圖3 連接數為17 條時的最大傳輸容量、連接情況及網絡價值

圖4 連接數為49 條時的最大傳輸容量、連接情況及網絡價值

圖2（b）、圖3（b）、圖4（b）為最大傳輸網絡價值迭代出最優結果的過程，由圖可知，隨著迭代次數的遞增，網絡價值逐漸增大最后趨于穩定。這3 次迭代所選擇的連接數是總連接數的三等劃分點，由實驗結果可得：連接條數在17 及以下，雖連接條數精簡了，資源也節省了，但傳輸容量以及網絡價值太小，這樣的網絡連接不利于生產生活；連接條數在49 條及以上時，傳輸容量和網絡價值均達到了很高的值，極大便利了區域間的信息互通，但與此同時帶來的損耗卻是連接數和資源配置的增加，這種連接情況適用于發達國家或區域的配置。而對于發展中國家或地區，聯通一片區域，既要考慮實現互聯互通的最大化，也要考慮經濟基礎和資源配置損耗，因此33 條連接較為合適[13-15]。

4 結 語

遺傳算法相對于一些傳統的尋優方法收斂性有所增強，耗時少，精度高。本研究在城市群之間建立連接的過程中，可通過遺傳算法逐步迭代尋得最優的連接方式以及最大的網絡價值和傳輸總容量，這時便可在傳輸容量一定的情況下，根據優化結果減少不必要的連接，精簡資源配置。本研究也可修改網絡價值的權重，有針對性地使傳輸連接偏向某一地區，更有利于合理規劃統籌。