基于遺傳算法的光傳送網(wǎng)絡(luò)規(guī)劃

劉小鈺，李士心，張 海

（天津職業(yè)技術(shù)師范大學(xué)電子工程學(xué)院，天津 300222）

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

1 光傳送網(wǎng)絡(luò)的網(wǎng)絡(luò)價(jià)值及模型數(shù)據(jù)的選取

1.1 光傳送網(wǎng)絡(luò)的網(wǎng)絡(luò)價(jià)值

不同傳輸格式下的傳輸距離如表1 所示。3 種典型光傳輸設(shè)備參數(shù)在優(yōu)化升級后均發(fā)生了變化。

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

優(yōu)化通信網(wǎng)絡(luò)的目的是在資源一定的情況下，把更多的人口更充分地連接到一起，網(wǎng)絡(luò)價(jià)值定義如下。

（1）給出連接的定義 直接連接2 個(gè)區(qū)域的鏈路。

（2）根據(jù)要求給出單個(gè)連接的價(jià)值定義 連接區(qū)域人口數(shù)乘積的開方與傳輸容量的乘積。

網(wǎng)絡(luò)的價(jià)值則是所有連接價(jià)值的加權(quán)和，即

網(wǎng)絡(luò)價(jià)值=∑權(quán)重×容量×人口

下面舉例說明網(wǎng)絡(luò)價(jià)值的計(jì)算方法。選取北京、上海、南京3 座城市，3 個(gè)節(jié)點(diǎn)網(wǎng)絡(luò)示意圖如圖1 所示。

圖1 3 個(gè)節(jié)點(diǎn)網(wǎng)絡(luò)示意圖

首先要求3 座城市之間互有連接，然后根據(jù)城市之間的距離可以得到傳輸容量，進(jìn)而由傳輸容量配合人口數(shù)算出網(wǎng)絡(luò)價(jià)值（network value，NV）為（假定每條傳輸鏈路的權(quán)重為1）

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

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

根據(jù)需要2 個(gè)節(jié)點(diǎn)之間也可以有多個(gè)連接。

1.2 模型數(shù)據(jù)的選取

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

（1）由表1 及城市間距構(gòu)建傳輸總?cè)萘?，為了直觀顯示，還需將各城市的坐標(biāo)位置（經(jīng)度和緯度）顯示在圖上[5]。

（2）由傳輸連接數(shù)的要求計(jì)算出總?cè)萘?，而后由總?cè)萘考俺鞘腥丝跀?shù)建立起網(wǎng)絡(luò)價(jià)值的函數(shù)，本研究所使用的人口數(shù)為各城市在某年的人口數(shù)據(jù)統(tǒng)計(jì)。共有12 個(gè)城市，故要實(shí)現(xiàn)兩兩互聯(lián)總連接數(shù)需有（12×11）/2=66 條。可知當(dāng)連接數(shù)為66 條（即每2 個(gè)城市之間均互有連接）時(shí)，網(wǎng)絡(luò)總價(jià)值以及傳輸總?cè)萘渴且粋€(gè)確定的算術(shù)問題，不需要借助該算法來尋優(yōu)，且此時(shí)的網(wǎng)絡(luò)價(jià)值最大，資源耗費(fèi)也最大；而此處需要權(quán)衡連接數(shù)與網(wǎng)絡(luò)價(jià)值的關(guān)系，基于資源等因素的限制，本研究只求解連接數(shù)為33 條、17 條以及49 條時(shí)的總?cè)萘恳约熬W(wǎng)絡(luò)價(jià)值來進(jìn)行對比，以分析在限定連接數(shù)即限定資源配置的情況下，如何連接更多人口，達(dá)到網(wǎng)絡(luò)價(jià)值最大化[6]；也可分析如何平衡東西部的連接。

2 遺傳算法機(jī)理及優(yōu)化模型建立

2.1 遺傳算法機(jī)理

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

2.2 遺傳算法實(shí)現(xiàn)以及優(yōu)化模型建立

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

（2）適應(yīng)度函數(shù)。由于此發(fā)明是在給定區(qū)域連接數(shù)的情況下去求解網(wǎng)絡(luò)價(jià)值最大化的連接方式，故適應(yīng)度函數(shù)采用整個(gè)光傳送網(wǎng)絡(luò)的網(wǎng)絡(luò)價(jià)值來表示。

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

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

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

對新產(chǎn)生的群體返回第（2）步，再進(jìn)行一輪運(yùn)算，對個(gè)體適應(yīng)度值再進(jìn)行優(yōu)化，多次循環(huán)，直至終止循環(huán)的條件出現(xiàn)[12]。

3 模型訓(xùn)練及仿真結(jié)果分析

對于整個(gè)城市群的傳輸鏈路而言，先將各城市坐標(biāo)顯示在圖上，連接數(shù)為33、17、49 條時(shí)的最大傳輸容量、連接情況及網(wǎng)絡(luò)價(jià)值分別如圖2、圖3 和圖4 所示。

圖2 連接數(shù)為33 條時(shí)的最大傳輸容量、連接情況及網(wǎng)絡(luò)價(jià)值

圖3 連接數(shù)為17 條時(shí)的最大傳輸容量、連接情況及網(wǎng)絡(luò)價(jià)值

圖4 連接數(shù)為49 條時(shí)的最大傳輸容量、連接情況及網(wǎng)絡(luò)價(jià)值

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

4 結(jié) 語

遺傳算法相對于一些傳統(tǒng)的尋優(yōu)方法收斂性有所增強(qiáng)，耗時(shí)少，精度高。本研究在城市群之間建立連接的過程中，可通過遺傳算法逐步迭代尋得最優(yōu)的連接方式以及最大的網(wǎng)絡(luò)價(jià)值和傳輸總?cè)萘?，這時(shí)便可在傳輸容量一定的情況下，根據(jù)優(yōu)化結(jié)果減少不必要的連接，精簡資源配置。本研究也可修改網(wǎng)絡(luò)價(jià)值的權(quán)重，有針對性地使傳輸連接偏向某一地區(qū)，更有利于合理規(guī)劃統(tǒng)籌。