路 遙，張 曉，江漢紅，吳 優(yōu)，許軼楠

(海軍工程大學(xué) 艦船綜合電力技術(shù)國(guó)防科技重點(diǎn)實(shí)驗(yàn)室， 湖北 武漢 430033)

因?yàn)槁窂絾?wèn)題，網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)優(yōu)化具有多約束和多目標(biāo)特點(diǎn)，是一個(gè)典型的NP難組合優(yōu)化問(wèn)題，難以在多項(xiàng)式時(shí)間內(nèi)實(shí)現(xiàn)求解。目前針對(duì)拓?fù)浣Y(jié)構(gòu)優(yōu)化的研究主要集中在算法求解上。文獻(xiàn)[1]利用插值法來(lái)對(duì)遺傳算法的輸入進(jìn)行初始化，對(duì)特定區(qū)域進(jìn)行搜索，從而更好地實(shí)現(xiàn)尋找拓?fù)渥钚?quán)值的目標(biāo)，該方法對(duì)于簡(jiǎn)單的網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化問(wèn)題效果較好，對(duì)于復(fù)雜網(wǎng)絡(luò)的拓?fù)鋬?yōu)化效果不佳；文獻(xiàn)[2]對(duì)局域網(wǎng)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的平均時(shí)延和網(wǎng)絡(luò)成本提出了具有雙重準(zhǔn)則設(shè)計(jì)問(wèn)題的算法，該算法搜索速度更快，但實(shí)現(xiàn)過(guò)程也較為復(fù)雜。

電磁發(fā)射系統(tǒng)是一套通過(guò)能量存儲(chǔ)、轉(zhuǎn)換、釋放，為目標(biāo)對(duì)象提供所需附加動(dòng)力的復(fù)雜系統(tǒng)。電磁發(fā)射系統(tǒng)以太網(wǎng)作為頂層閉環(huán)運(yùn)控分系統(tǒng)的二級(jí)網(wǎng)絡(luò)子系統(tǒng)，主要用于提供頂層分系統(tǒng)控制器下達(dá)指令數(shù)據(jù)與底層分系統(tǒng)控制器和IP部件上傳波形數(shù)據(jù)的暢通渠道，實(shí)現(xiàn)全系統(tǒng)控制器的協(xié)同管理、閉環(huán)控制、設(shè)備維護(hù)、故障診斷、數(shù)據(jù)采集匯總與備份等功能。通過(guò)工業(yè)以太網(wǎng)交換機(jī)將全系統(tǒng)的控制器互聯(lián)為一個(gè)復(fù)雜的網(wǎng)絡(luò)化控制系統(tǒng)，有助于提高電磁發(fā)射系統(tǒng)的網(wǎng)絡(luò)可靠性和易維護(hù)性，為將來(lái)電磁發(fā)射系統(tǒng)網(wǎng)絡(luò)結(jié)構(gòu)和功能的可拓展性提供可能，是實(shí)現(xiàn)電磁發(fā)射系統(tǒng)網(wǎng)絡(luò)化控制的基礎(chǔ)。

電磁發(fā)射系統(tǒng)以太網(wǎng)的主要性能指標(biāo)為：鏈路為1000 Mbit/s單模光纖環(huán)網(wǎng)，光纖波長(zhǎng)1310 nm，最大衰減≤0.4 dB/km；節(jié)點(diǎn)為工業(yè)以太網(wǎng)交換機(jī)，一個(gè)環(huán)上允許最多160臺(tái)交換機(jī)，最大恢復(fù)時(shí)間5 ms/臺(tái)，丟包率為0。全系統(tǒng)以太網(wǎng)中有底層分系統(tǒng)控制器和IP部件共113個(gè)，通過(guò)事件數(shù)據(jù)和狀態(tài)數(shù)據(jù)兩種類型與頂層閉環(huán)運(yùn)控分系統(tǒng)進(jìn)行通信。不同數(shù)據(jù)對(duì)網(wǎng)絡(luò)的性能要求不同，事件數(shù)據(jù)對(duì)網(wǎng)絡(luò)鏈路有較高的實(shí)時(shí)性、可靠性要求；狀態(tài)數(shù)據(jù)對(duì)實(shí)時(shí)性的要求雖然沒(méi)有事件數(shù)據(jù)的高，但是數(shù)據(jù)量較大，對(duì)于系統(tǒng)的狀態(tài)分析和事后故障診斷具有重要作用，因此需要較高的帶寬保證數(shù)據(jù)的完整性。總體上，電磁發(fā)射系統(tǒng)的網(wǎng)絡(luò)流量兼具平穩(wěn)性、周期突發(fā)性及較弱的長(zhǎng)相關(guān)性等特點(diǎn)。目前網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)方面的研究對(duì)象以通用網(wǎng)絡(luò)及應(yīng)用網(wǎng)絡(luò)為主，電磁發(fā)射系統(tǒng)由于網(wǎng)絡(luò)流量的特殊性，以太網(wǎng)拓?fù)浣Y(jié)構(gòu)優(yōu)化直接采用上述方法存在著一定的局限性；另外，前人研究工作偏重基于硬件成本的物理拓?fù)浣Y(jié)構(gòu)優(yōu)化，很少考慮對(duì)網(wǎng)絡(luò)的邏輯拓?fù)溥M(jìn)行軟件優(yōu)化。因此，有必要針對(duì)電磁發(fā)射系統(tǒng)以太網(wǎng)的物理拓?fù)浣Y(jié)構(gòu)和流量特性，建立拓?fù)浣Y(jié)構(gòu)優(yōu)化的數(shù)學(xué)模型，提出有效的算法改進(jìn)以太網(wǎng)的性能，降低系統(tǒng)的軟成本。

1 生成樹協(xié)議在電磁發(fā)射系統(tǒng)網(wǎng)絡(luò)拓?fù)渲械木窒薹治?/h2>

電磁發(fā)射系統(tǒng)以太網(wǎng)是由工業(yè)以太網(wǎng)交換機(jī)采用環(huán)形拓?fù)浣Y(jié)構(gòu)組成的，交換機(jī)作為底層控制系統(tǒng)與頂層維護(hù)管理系統(tǒng)的中間層，具有存儲(chǔ)、轉(zhuǎn)發(fā)事件數(shù)據(jù)和狀態(tài)數(shù)據(jù)的功能。為了防止環(huán)形結(jié)構(gòu)導(dǎo)致的廣播風(fēng)暴的產(chǎn)生，交換機(jī)支持生成樹協(xié)議(Spanning Tree Protocol, STP),通過(guò)生成樹算法(Spanning Tree Algorithm, STA)生成一個(gè)無(wú)環(huán)的樹形拓?fù)洌员ＷC網(wǎng)絡(luò)的正常運(yùn)行。

STP由IEEE802.1D標(biāo)準(zhǔn)定義。當(dāng)一個(gè)局域網(wǎng)內(nèi)兩個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)之間存在一條以上的通信路徑時(shí)，STA會(huì)檢測(cè)到環(huán)路的存在，并根據(jù)網(wǎng)橋ID(Bridge ID，BID)、路徑開銷(Path Cost，PC)和端口ID(Port ID，PID)參數(shù)來(lái)自動(dòng)選擇開銷值最低的那條路徑作為可使用的最優(yōu)路徑(稱為主鏈路或活動(dòng)鏈路)，而阻斷其他的通信路徑，將它們作為備用鏈路。當(dāng)主鏈路正常工作時(shí)，備用鏈路處于邏輯阻斷狀態(tài)；當(dāng)交換機(jī)偵測(cè)到主鏈路中出現(xiàn)故障時(shí)，將通過(guò)STA自動(dòng)啟用備用鏈路重構(gòu)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)以保證網(wǎng)絡(luò)的正常運(yùn)行，提高網(wǎng)絡(luò)的可靠性。

在電磁發(fā)射系統(tǒng)以太網(wǎng)的物理拓?fù)浣Y(jié)構(gòu)已經(jīng)完全確定的情況下，通過(guò)交換機(jī)STP得到的最小生成樹(Minimum Spanning Tree, MST)是唯一的，且具有最優(yōu)性。然而這種生成樹的最優(yōu)性是交換機(jī)基于上述BID、PC、PID等幾個(gè)參數(shù)值進(jìn)行優(yōu)化的，并沒(méi)有結(jié)合系統(tǒng)中各個(gè)鏈路的實(shí)際流量狀況，因此這樣得到的MST拓?fù)渫ǔＧ闆r下只具有最小開銷，卻可能導(dǎo)致部分節(jié)點(diǎn)和鏈路的負(fù)載過(guò)大，一旦發(fā)生堵塞，將會(huì)影響網(wǎng)絡(luò)中關(guān)鍵鏈路的性能，無(wú)法使全系統(tǒng)運(yùn)行在最佳狀態(tài)，有必要結(jié)合各個(gè)鏈路的實(shí)際流量對(duì)拓?fù)浣Y(jié)構(gòu)進(jìn)行進(jìn)一步優(yōu)化[3]。

2 電磁發(fā)射系統(tǒng)多環(huán)拓?fù)涞亩嗄繕?biāo)優(yōu)化模型

以一個(gè)電磁發(fā)射系統(tǒng)以太網(wǎng)拓?fù)錇槔?，通過(guò)對(duì)該網(wǎng)絡(luò)的交換機(jī)和實(shí)際通信鏈路抽象化以后得到如圖1所示的拓?fù)浣Y(jié)構(gòu),圖中節(jié)點(diǎn)代表布置于各個(gè)設(shè)備內(nèi)的交換機(jī)，連線代表將交換機(jī)互連的光纖鏈路，底層控制器和IP部件反映為鏈路中流量的方向和大小。

圖1 電磁發(fā)射系統(tǒng)以太網(wǎng)的實(shí)際拓?fù)浣Y(jié)構(gòu)Fig.1 Ethernet topology of electromagnetic launch system

圖1中網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)可看作一個(gè)無(wú)向連通圖G=(V,E)。V={Va,Vb,…,Vw}為交換機(jī)節(jié)點(diǎn)的集合(未列出與交換機(jī)相連的底層控制器節(jié)點(diǎn))，并且所有交換機(jī)均支持STP；E={E1,E2,…,E26}為通信鏈路的集合，其中實(shí)線表示邏輯通路，虛線表示通過(guò)STP算法生成的備用鏈路，每條鏈路的權(quán)重記為wi(i=1,2,…,26)。

由于交換機(jī)環(huán)網(wǎng)鏈路均為單模1310 nm波長(zhǎng)的1000 Mbit/s的光纖連接，鏈路之間性能差異很小，所以在本系統(tǒng)中鏈路的權(quán)重完全由其流量決定，并且該系統(tǒng)中主要數(shù)據(jù)流量的大小和流向是確定的。通過(guò)在網(wǎng)絡(luò)多個(gè)關(guān)鍵節(jié)點(diǎn)上對(duì)數(shù)據(jù)包的流量和流向進(jìn)行抓包分析，可以得出所有兩個(gè)交換機(jī)之間的數(shù)據(jù)流量，如表1所示。

表1 交換機(jī)節(jié)點(diǎn)間數(shù)據(jù)流量統(tǒng)計(jì)

經(jīng)測(cè)得目前網(wǎng)絡(luò)所有鏈路上的廣播流量均小于1 kbit/s，所以表1中忽略了網(wǎng)絡(luò)上的廣播流量。對(duì)照?qǐng)D1和表1，優(yōu)化前的鏈路流量(單位：kbit/s)拓?fù)淙鐖D2所示。

1)使網(wǎng)絡(luò)鏈路的總流量(即平均流量)最小，使整個(gè)網(wǎng)絡(luò)系統(tǒng)在較低的負(fù)載下工作，使網(wǎng)絡(luò)工作更加安全穩(wěn)定；

2)使網(wǎng)絡(luò)中流量最大的鏈路流量最小，因?yàn)榫W(wǎng)絡(luò)沖突率和網(wǎng)絡(luò)帶寬占用率呈指數(shù)關(guān)系，降低鏈路的最大流量對(duì)降低網(wǎng)絡(luò)沖突率有顯著效果。

設(shè)xi(i=1,2,…,26)是0-1型決策變量，xi=1表示邊Ei為邏輯通路，xi=0表示邊Ei為物理斷路或邏輯斷路，則該規(guī)劃問(wèn)題的數(shù)學(xué)模型可以表示為：

(1)

(2)

xi∈{0,1},i=1,2,…,26

(3)

圖2 優(yōu)化前的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和鏈路流量Fig.2 Network topology and link traffic before optimization

其中：wi為鏈路xi上的總流量，作為該鏈路在目標(biāo)函數(shù)中的權(quán)重；wmax為系統(tǒng)中所有鏈路的最大流量；k為最大流量wmax在目標(biāo)函數(shù)中所占的額外權(quán)重，是對(duì)網(wǎng)絡(luò)所有鏈路總流量最小和沖突率最小這兩個(gè)優(yōu)化目標(biāo)的一個(gè)主觀綜合考量，取值范圍0.2

從形式上來(lái)看，這個(gè)組合優(yōu)化問(wèn)題與最小生成樹問(wèn)題類似，是一個(gè)NP完全問(wèn)題[4-6]，然而從優(yōu)化目標(biāo)和約束條件來(lái)看，其又與傳統(tǒng)的最小生成樹問(wèn)題有所區(qū)別：其中每條鏈路上的流量權(quán)重是動(dòng)態(tài)變化的，不同的解所對(duì)應(yīng)的拓?fù)浣Y(jié)構(gòu)不同。當(dāng)一條鏈路由通路變?yōu)閭溆面溌窌r(shí)，原本流經(jīng)該鏈路的數(shù)據(jù)流會(huì)選擇其他鏈路到達(dá)接收節(jié)點(diǎn)，從而影響到該鏈路及相關(guān)的鏈路流量。而按照?qǐng)D論中經(jīng)典的Prim算法或Kruskal算法對(duì)最小生成樹問(wèn)題進(jìn)行求解時(shí)，需要固定每條邊的權(quán)重，因此本文的最小生成樹問(wèn)題無(wú)法使用這些方法，需要考慮其他的算法。

3 基于遺傳算法的電磁發(fā)射網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)優(yōu)化

遺傳算法源自對(duì)生物種群系統(tǒng)對(duì)自然環(huán)境適應(yīng)性進(jìn)化過(guò)程的觀察，通過(guò)模擬生物種群中個(gè)體的適者生存、交配繁殖、進(jìn)化變異等自然行為對(duì)NP難問(wèn)題進(jìn)行求解。作為一種具有普適性的全局尋優(yōu)隨機(jī)搜索算法，遺傳算法可以在較大的搜索區(qū)域內(nèi)有效地獲得比傳統(tǒng)方法更優(yōu)的最優(yōu)解或次優(yōu)解[7]。遺傳算法可以定義為一個(gè)8元組：GA=(C,E,P0,M,Φ,Γ,Ψ,T)，其中C為基因編碼規(guī)則，E為個(gè)體適應(yīng)度評(píng)價(jià)函數(shù)，P0為初始種群，M為種群規(guī)模，Φ為選擇算子，Γ為交叉算子，Ψ為變異算子，T為算法終止條件。

3.1 基于基因環(huán)的編碼規(guī)則和個(gè)體適應(yīng)度評(píng)價(jià)

個(gè)體中的每一個(gè)元素稱為一個(gè)基因。為了將每一個(gè)網(wǎng)絡(luò)狀態(tài)以基因編碼形式表示，同時(shí)滿足編碼規(guī)則的基本條件，將網(wǎng)絡(luò)鏈路狀態(tài)的基因編碼采用決策變量xi來(lái)表示：C(x)=(x1x2…x26)，其中xi=1表示活動(dòng)鏈路，xi=0表示備用鏈路或故障鏈路，這樣第2節(jié)的數(shù)學(xué)模型仍可用來(lái)判斷個(gè)體的合法性。

圖1中所對(duì)應(yīng)的個(gè)體用這種編碼規(guī)則表示為(11011011011011111111111111)。除了表示正常的網(wǎng)絡(luò)狀態(tài)(個(gè)體)外，這種編碼規(guī)則，對(duì)個(gè)體x=(11011011011011111111111111)，則表示與交換機(jī)Vj相連的兩條鏈路均不連通，是一種網(wǎng)絡(luò)故障狀態(tài)，故可以用于網(wǎng)絡(luò)鏈路狀態(tài)監(jiān)測(cè)。

個(gè)體適應(yīng)度評(píng)價(jià)函數(shù)用來(lái)評(píng)價(jià)一個(gè)個(gè)體對(duì)目標(biāo)函數(shù)的適應(yīng)度，適應(yīng)度高的個(gè)體在優(yōu)勝劣汰選擇中容易存活并產(chǎn)生下一代個(gè)體，適應(yīng)度低的個(gè)體則容易被從種群中淘汰[8]。遺傳算法中通常根據(jù)個(gè)體的適應(yīng)度值來(lái)確定其在遺傳操作中的存活概率，因此適應(yīng)度函數(shù)要滿足單值、連續(xù)、非負(fù)、最大化等性質(zhì)要求。由于本模型是多目標(biāo)最小值優(yōu)化問(wèn)題，需要對(duì)多個(gè)目標(biāo)進(jìn)行加權(quán)調(diào)整轉(zhuǎn)換為最大值優(yōu)化問(wèn)題，將目標(biāo)函數(shù)進(jìn)行如下改造得到個(gè)體x的適應(yīng)度函數(shù)：

(4)

式中，A為f(x)的一個(gè)保守估計(jì)值。

3.2 基于基因環(huán)的初始種群和種群規(guī)模

初始種群是遺傳算法搜索過(guò)程的起始點(diǎn)，是一個(gè)由多個(gè)個(gè)體構(gòu)成的集合，不同的初始群體的收斂速度可能有著較大的差別。遺傳算法通過(guò)選擇算子、交叉算子和變異算子只能保證低階、短定義矩以及平均適應(yīng)度高于種群平均適應(yīng)度的模式在子代中呈指數(shù)級(jí)增長(zhǎng)，但并不能確保算法收斂到最優(yōu)個(gè)體。對(duì)于本文的算法要從理論上保證能夠收斂到最優(yōu)解，則必須保證種群中所有個(gè)體的基因集合(即基因池)等價(jià)于整個(gè)解空間的基因集合，即遺傳算法的搜索空間能夠覆蓋整個(gè)解空間。

常規(guī)的二進(jìn)制基因編碼規(guī)則通過(guò)隨機(jī)方法生成初始種群，非常容易實(shí)現(xiàn)完備的基因池[9]。然而本文的情況較為特殊，如果產(chǎn)生初始種群的方法不當(dāng)，可能需要較大的種群數(shù)量才能實(shí)現(xiàn)完備的基因池；而且遺傳算法的三個(gè)算子中，選擇算子和交叉算子都不會(huì)產(chǎn)生新的基因，而變異算子發(fā)生的概率通常比較低，如果初始種群的基因池不完備，很難通過(guò)變異使得搜索過(guò)程完全覆蓋解空間的基因池。因此考慮用基因環(huán)解決電磁發(fā)射系統(tǒng)以太網(wǎng)拓?fù)浣Y(jié)構(gòu)優(yōu)化問(wèn)題?；颦h(huán)是由圖1中若干構(gòu)成環(huán)(單環(huán)或復(fù)環(huán))的鏈路所代表的基因組構(gòu)成。在遺傳算法中，一個(gè)基因環(huán)作為一個(gè)整體進(jìn)行交叉和變異操作，以避免非法解的產(chǎn)生。

因此在本文算法中，基因環(huán)是遺傳操作中最小的基因單位。要滿足種群基因池的完備性條件，需要先產(chǎn)生部分初始種群以覆蓋整個(gè)解空間的個(gè)體集合，再隨機(jī)產(chǎn)生其他個(gè)體直到滿足預(yù)設(shè)的種群規(guī)模，這樣產(chǎn)生的初始種群P0才能較好地符合多樣性和完備性要求?？紤]本文問(wèn)題中解空間的規(guī)模并不大，種群規(guī)模M設(shè)為固定值51。

3.3 基于基因環(huán)的遺傳操作

遺傳操作是模擬生物基因的遺傳過(guò)程，對(duì)群體的個(gè)體按照其適應(yīng)度值進(jìn)行交叉、變異、選擇等操作[10]。遺傳操作對(duì)于算法的收斂性和搜索速度等有著重要影響。相比于傳統(tǒng)搜索算法的無(wú)向搜索，遺傳操作的搜索是向最優(yōu)解方向的隨機(jī)擾動(dòng)，效率相對(duì)較高。由于本文編碼規(guī)則比較嚴(yán)格，遺傳算子設(shè)計(jì)不當(dāng)很容易產(chǎn)生非法個(gè)體，如何設(shè)計(jì)遺傳算子十分重要。

3.3.1 交叉算子

交叉算子在遺傳算法中起到核心作用，是一種把兩個(gè)父代個(gè)體的部分結(jié)構(gòu)加以替換重組而生成新個(gè)體的操作，但該操作不會(huì)產(chǎn)生新的基因。常用的二進(jìn)制交叉算子有單點(diǎn)交叉、多點(diǎn)交叉、均勻交叉、匹配交叉、洗牌交叉等?？紤]到本文中的基因編碼方式，采用以一個(gè)基因環(huán)為單位的整環(huán)交叉，這樣可以確保交叉后得到的都是合法的個(gè)體，而用其他交叉方法則容易產(chǎn)生非法個(gè)體?；颦h(huán)交叉方法如下(以圖1中Va,Vb,Vc,Vd,Ve組成的環(huán)為例)：

(110110)11011011111111111111+

(011110)11011011111111111111

↓

(011110)11011011111111111111+

(110110)11011011111111111111

交叉算子是影響遺傳算法收斂性的主要因素。在不變異僅交叉的情況下，遺傳算法可等效為有限吸收的馬爾科夫過(guò)程，在適當(dāng)?shù)倪x擇策略下，通過(guò)交叉可實(shí)現(xiàn)向最優(yōu)解收斂。交叉概率pc是影響遺傳算法行為和性能的關(guān)鍵參數(shù)，pc越大，新個(gè)體產(chǎn)生的速度就越快，但也會(huì)導(dǎo)致具有高適應(yīng)度的個(gè)體結(jié)構(gòu)很快就會(huì)被破壞；pc過(guò)小會(huì)使搜索過(guò)程減緩，降低搜索速度。為保證遺傳算法的性能，可以采用如式(5)所示自適應(yīng)交叉概率：

(5)

交叉算子步驟：

步驟1：對(duì)種群Pt-1內(nèi)除歷代最優(yōu)個(gè)體外所有個(gè)體進(jìn)行兩兩配對(duì)。

步驟2：遍歷所有配對(duì)個(gè)體，按交叉概率確定配對(duì)個(gè)體是否進(jìn)行交叉操作。

步驟3：若交叉則隨機(jī)選擇一個(gè)基因環(huán)進(jìn)行交叉操作，否則轉(zhuǎn)步驟4。

步驟4：遍歷未結(jié)束則轉(zhuǎn)步驟2，否則結(jié)束交叉操作，生成種群Pt1。

3.3.2 變異算子

變異算子是對(duì)群體中某些個(gè)體串的基因座上的基因值作變動(dòng)的操作，一般作為遺傳算法的輔助算子，該操作會(huì)改變當(dāng)前群體內(nèi)基因環(huán)的數(shù)量。常用的二進(jìn)制變異算子有基本位變異、均勻變異、自適應(yīng)概率變異等。相對(duì)于具有全局搜索能力的交叉算子，變異算子本身是一種局部隨機(jī)搜索，使遺傳算法具備兼顧全局和局部的均衡搜索能力，有利于保持種群多樣性，防止出現(xiàn)非成熟收斂。一個(gè)有效的遺傳算法設(shè)計(jì)應(yīng)考慮變異算子和交叉算子的有效配合。

開始時(shí)增加變異率，結(jié)束時(shí)減少變異率可以改善搜索速度。當(dāng)變異概率pm>0.5時(shí)，遺傳算法就退化為隨機(jī)搜索，失去了遺傳算法一些重要的數(shù)學(xué)特性和搜索能力。本文選取pm=0.02，并使用如下謹(jǐn)慎變異算子以確保算法的有效性：

步驟1：遍歷種群Pt1內(nèi)除歷代最優(yōu)個(gè)體外的每個(gè)個(gè)體的每個(gè)非唯一的基因環(huán)，對(duì)選定的基因環(huán)以變異率與基因環(huán)長(zhǎng)度相乘后的數(shù)值作為概率來(lái)確定是否進(jìn)行變異操作。

步驟2：若滿足概率則重新隨機(jī)變異生成新的合法基因環(huán)，否則轉(zhuǎn)步驟3。

步驟3：遍歷未結(jié)束則轉(zhuǎn)步驟1，否則結(jié)束變異操作，生成種群Pt2。

3.3.3 選擇算子

選擇算子也稱為復(fù)制算子或再生算子，是一種從群體中選擇優(yōu)勢(shì)個(gè)體、淘汰劣勢(shì)個(gè)體的操作，該操作不會(huì)產(chǎn)生新的個(gè)體。常用的選擇算子有輪賭盤選擇算子、錦標(biāo)賽選擇算子、隨機(jī)遍歷抽樣選擇算子、局部選擇算子等。

常用的選擇算子由于選擇的隨機(jī)性，某些適應(yīng)度高的個(gè)體可能被多次復(fù)制，在群體數(shù)目小的情況下容易產(chǎn)生早熟和欺騙現(xiàn)象。本文采用跨世代選擇算子，即在迭代過(guò)程中將上世代種群和通過(guò)交叉產(chǎn)生的種群混合起來(lái)，按照式(6)的概率選擇較優(yōu)的個(gè)體，并使新種群中的個(gè)體均不重復(fù)，以保持種群中基因模式的多樣性，能有效地改善遺傳算法的行為，但相對(duì)的計(jì)算量也較大。

(6)

式中，fi為待選擇個(gè)體的適應(yīng)度值。

同時(shí)，在進(jìn)化的每一代種群中指定一個(gè)個(gè)體用于記錄歷史最優(yōu)個(gè)體(有多個(gè)最優(yōu)個(gè)體時(shí)保存編號(hào)最小的)，該個(gè)體不參與遺傳操作，這樣可防止歷史最優(yōu)個(gè)體在最終代被小概率漏選，這也是本文中選擇種群大小為奇數(shù)的原因。由于這種選擇操作需在其他遺傳操作之后，所以使用這種選擇算子的遺傳算法的流程也有所不同，需要在進(jìn)行選擇操作前重新計(jì)算新個(gè)體的適應(yīng)度值。

選擇算子步驟：

步驟1：將種群Pt2和Pt-1進(jìn)行混合，并剔除其中相同的個(gè)體，生成輪賭盤種群PR。

步驟2：設(shè)xP∈PR為PR中最優(yōu)個(gè)體，新種群Pt={xP}，PR=PR-{xP}。

步驟3：按輪賭盤方式從PR中隨機(jī)選擇個(gè)體xi，Pt=Pt+{xi}，PR=PR-{xi}。

步驟4：若Pt未達(dá)到預(yù)設(shè)種群大小則轉(zhuǎn)步驟3，否則選擇操作結(jié)束，生成種群Pt。

3.3.4 算法終止條件和算法流程

遺傳算法的終止條件一般設(shè)為固定的終止代數(shù)，如果優(yōu)化問(wèn)題較為復(fù)雜，也可將終止條件設(shè)為最優(yōu)個(gè)體的適應(yīng)度超過(guò)某一閾值(達(dá)到預(yù)期目標(biāo)就終止搜索過(guò)程)，或連續(xù)幾代平均適應(yīng)度增長(zhǎng)低于某一閾值(算法已經(jīng)收斂)等。本文算法中終止代數(shù)T設(shè)為50，算法流程如圖3所示。

圖3 算法流程圖Fig.3 Flow chart of the algorithm

4 仿真測(cè)試與實(shí)際電磁發(fā)射系統(tǒng)驗(yàn)證

按照前文中所仿真參數(shù)選取種群規(guī)模為51，遺傳代數(shù)為50，用MATLAB編寫該遺傳算法程序，通過(guò)仿真得到最優(yōu)個(gè)體的趨勢(shì)如圖4所示。

圖4 遺傳算法趨勢(shì)圖Fig.4 Trend graph of the genetic algorithm

圖4中最優(yōu)個(gè)體為(10111011011111111110111111)，該網(wǎng)絡(luò)結(jié)構(gòu)的鏈路平均數(shù)據(jù)流量為4539 kbit/s，最大數(shù)據(jù)流量位于鏈路12處的17 914 kbit/s，其拓?fù)浣Y(jié)構(gòu)和鏈路流量(單位：kbit/s)如圖5所示。

優(yōu)化前后數(shù)據(jù)對(duì)比如表2所示，平均流量和最大流量有明顯下降。優(yōu)化后，系統(tǒng)的平均流量下降70.0%，最大流量下降10.0%。

根據(jù)仿真結(jié)果，對(duì)相應(yīng)交換機(jī)的參數(shù)進(jìn)行配置，將交換機(jī)Va與交換機(jī)Vc、交換機(jī)Vd與交換機(jī)Ve、交換機(jī)Vo與交換機(jī)Vp六處交換機(jī)相應(yīng)端口的PC值配置為100，大于其他端口的默認(rèn)PC值(1000 Mbit/s端口默認(rèn)PC值為4，100 Mbit/s端口PC值為19，10 Mbit/s端口PC值為100；全系統(tǒng)交換機(jī)的端口只有1000 Mbit/s和100 Mbit/s兩種，交換機(jī)間互連的端口是1000 Mbit/s，交換機(jī)與底層控制器連接的端口是100 Mbit/s)，這樣通過(guò)交換機(jī)的生成樹算法將使得全系統(tǒng)以太網(wǎng)的拓?fù)浣Y(jié)構(gòu)與圖5一致。修改網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)后，經(jīng)過(guò)多次實(shí)驗(yàn)檢驗(yàn)，網(wǎng)絡(luò)狀態(tài)運(yùn)行良好，網(wǎng)絡(luò)負(fù)載與模型的理論值相差不大。

5 結(jié)論

將電磁發(fā)射系統(tǒng)以太網(wǎng)拓?fù)浣Y(jié)構(gòu)抽象成無(wú)向連通圖，建立了網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)優(yōu)化的多目標(biāo)規(guī)劃模型，提出基于基因環(huán)操作的遺傳算法對(duì)模型進(jìn)行求解，并用窮舉法驗(yàn)證了仿真的有效性。優(yōu)化后，系統(tǒng)的平均流量下降70.0%，最大流量下降10.0%。這種優(yōu)化只需要對(duì)以太網(wǎng)交換機(jī)進(jìn)行相關(guān)配置，不需要改變以太網(wǎng)系統(tǒng)的物理鏈路，不會(huì)

圖5 優(yōu)化后的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和鏈路流量Fig.5 Network topology and link traffic after optimization

表2 拓?fù)浣Y(jié)構(gòu)優(yōu)化前后流量對(duì)比

增加額外成本，優(yōu)化后的網(wǎng)絡(luò)有效地降低了鏈路負(fù)載和沖突率，對(duì)電磁發(fā)射類系統(tǒng)具有普適性的意義。