趙昶宇

（天津津航計(jì)算技術(shù)研究所，天津 300308）

基于混合遺傳算法的1553B消息傳輸優(yōu)化

趙昶宇

（天津津航計(jì)算技術(shù)研究所，天津 300308）

為了提高1553B總線消息傳輸?shù)膶?shí)時性，降低總線的通信延遲率，提出了一種改進(jìn)遺傳算法的1553B總線消息傳輸優(yōu)化算法。該算法先通過排隊(duì)論建立1553B總線消息調(diào)度數(shù)學(xué)模型，接著引入遺傳算法快速找到1553B總線消息調(diào)度可行解，然后將遺傳算法找到的可行解轉(zhuǎn)換成蟻群優(yōu)化算法初始信息素，最后利用蟻群算法的局部尋優(yōu)和正反饋機(jī)制得到1553B總線消息調(diào)度最優(yōu)解。仿真實(shí)驗(yàn)結(jié)果表明，利用改進(jìn)后的遺傳算法優(yōu)化1553B總線消息傳輸，能夠在滿足每條消息最大延遲時間要求和通訊實(shí)時性的前提下，提高總線利用率，有效緩解總線消息擁塞和飽和的情況，解決了總線負(fù)載均衡的難題，具有較好的處理異步消息的能力。

遺傳算法；蟻群算法；總線消息傳輸；數(shù)學(xué)模型

由于武器裝備系統(tǒng)對實(shí)時性和可靠性的要求很高，所以必須保證1553B總線上消息傳輸?shù)膶?shí)時性。當(dāng)1553B總線上需要處理不同長度、不同周期的多種消息時，并且存在異步消息需要處理時，系統(tǒng)的實(shí)時性一般很難保證。目前，比較常見的1553B總線消息優(yōu)化算法有基于計(jì)算量向量算法、RMS調(diào)度算法、長釋放時間間隔優(yōu)先算法和HTSF算法等。在這些方法中，基于計(jì)算量向量算法和RMS調(diào)度算法都是基于靜態(tài)負(fù)載均衡的，沒有解決消息的動態(tài)負(fù)載均衡問題，當(dāng)總線上有很多非周期性消息時，易導(dǎo)致總線堵塞或飽和；長釋放時間間隔優(yōu)先算法不能保證釋放間隔比較小的消息或者突發(fā)消息能在截止期前完成調(diào)度；HTSF算法沒有考慮同一時刻可能有多條消息同時到達(dá)的情況，而且算法執(zhí)行效率比較低。為了避免出現(xiàn)1553B總線堵塞和飽和的情況，提高1553B總線的利用率，降低總線的平均延遲時間，均衡總線負(fù)載，本文提出了一種優(yōu)化1553B總線消息傳輸?shù)乃惴ā?/p>

1 基于排隊(duì)論建立1553B總線消息傳輸?shù)臄?shù)學(xué)模型

圖1 M|M|1模型發(fā)生率圖

1553B總線上消息的傳輸過程可以看作是一種單服務(wù)員單隊(duì)列的排隊(duì)系統(tǒng)。該模型為一個M|M|1排隊(duì)模型，排隊(duì)系統(tǒng)的模型發(fā)生率如圖1所示，其中，圓圈中的數(shù)字代表系統(tǒng)的狀態(tài)。在圖1中，λ為消息的平均到達(dá)率，μ為總線的平均服務(wù)率，m為消息個數(shù)，因此，1/λ為消息的平均時間間隔，1/μ為消息的平均傳輸時間。

設(shè)Ek為排隊(duì)系統(tǒng)在狀態(tài)k處的概率，ρ為總線利用率，建立生滅過程的狀態(tài)平衡方程，即：

如果系統(tǒng)內(nèi)有k條消息，其中，k-1條消息在排隊(duì)等候，則排隊(duì)等候的消息平均數(shù)為：

消息傳輸花費(fèi)的時間為：

消息排隊(duì)等候所花費(fèi)時間的平均值為：

1553B總線傳輸系統(tǒng)的平均延遲時間為消息傳輸時間和消息排隊(duì)等候時間之和。對總線上非周期消息傳輸進(jìn)行優(yōu)化的目標(biāo)是使平均延遲時間最小，并確定達(dá)到最優(yōu)目標(biāo)值的最優(yōu)總線平均服務(wù)率μ*。

取目標(biāo)函數(shù)z為消息傳輸時間與消息在系統(tǒng)中排隊(duì)等候時間之和的期望值，即：

式（1）中：cs為當(dāng)μ＝1時總線消息傳輸所耗費(fèi)的時間；cw為每條消息在總線中排隊(duì)等候所耗費(fèi)的時間。

式（2）為1553B總線消息傳輸?shù)臄?shù)學(xué)模型。

2 基于遺傳算法得到1553B總線消息調(diào)度可行解

2.1 染色體編碼

設(shè)定消息個數(shù)為m，消息小周期個數(shù)為n，個體染色體上的每個基因位置編號代表消息編號，每個基因位用0～（m-1）之間的整數(shù)表示，代表某條消息所在的小周期編號。比如，m＝6，n＝4，染色體編碼為（0，1，2，3，3，2），表示第1條消息分配到小周期1上，第2條消息分配到小周期2上，第3條和第6條消息分配到小周期3上，第4條和第5條消息分配到小周期4上。

2.2 確定初始種群

種群的初始化是遺傳算法的關(guān)鍵，傳統(tǒng)的遺傳算法確定初始種群多半采取隨機(jī)生成法形成染色體方案，以至于迭代開始就可能形成許多不可行的方案，要進(jìn)行大量的計(jì)算后才能得到優(yōu)化方案。這在很大程度上降低了算法的運(yùn)算效率。本文改進(jìn)經(jīng)典遺傳算法，改進(jìn)后的初始種群的選擇算法能有效抑制“早熟”現(xiàn)象，其全局搜索能力和搜索效果都有了明顯的提高。改進(jìn)后的初始種群的產(chǎn)生方式是：隨機(jī)產(chǎn)生N個體，個體長度為Length，設(shè)x和y為2個個體，u是中群內(nèi)的第1個個體，ν是與u進(jìn)行相似度比較的個體，它們之間的相似度定義為sim（u，ν）＝1-dist（u，ν），dist（u，ν）是標(biāo)準(zhǔn)的海明距離函數(shù)。

通過比較個體相似度，要求規(guī)定能夠入選初始個體相似度必須滿足以下條件，即：

式（3）中：d為調(diào)節(jié)常數(shù)，用于控制期望的相似度。

2.3 適應(yīng)度函數(shù)

適應(yīng)度函數(shù)用于評價染色體的優(yōu)劣，其函數(shù)值越大，表示染色體生存能力越強(qiáng)，對應(yīng)的解最優(yōu)。式（2）給出了1553B總線傳輸系統(tǒng)的平均延遲時間函數(shù)，因此，本文采用的適應(yīng)度函數(shù)為：

2.4 交叉操作

常用的交叉方式有一點(diǎn)交叉、兩點(diǎn)交叉、多點(diǎn)交叉和一致交叉等。

本文改進(jìn)了遺傳算法，采用多點(diǎn)位單基因交叉的方式，用父代最優(yōu)解Tmax與子代染色體池交叉操作，該方法能避免算法過早地喪失進(jìn)化能力，具體步驟如下：①在染色體池T中選擇進(jìn)行交叉操作的染色體Ti和最優(yōu)染色體Tmax；②隨機(jī)生成交叉片段和交叉區(qū)域；③將Ti的交叉區(qū)域加到Tmax前面，將Tmax的交叉區(qū)域加到Ti前面；④刪除與交叉區(qū)域相同的基因，得到2個新的子代。

2.5 變異操作

在變異運(yùn)算中，變異率通常取0.1，在單個染色體Ti＝（ti1，ti2…tim）上隨機(jī)選擇連續(xù)多個基因（m表示消息個數(shù)），對多個基因進(jìn)行重新排列，實(shí)現(xiàn)染色體的變異。由于采用了最優(yōu)個體Tmax保留的策略，所以，在變異運(yùn)算中，可以加大在當(dāng)前最優(yōu)個體附近搜索的概率，不用擔(dān)心破壞已經(jīng)存在的優(yōu)良染色體。

2.6 復(fù)制操作

基于適應(yīng)度函數(shù)對染色體個體進(jìn)行評價，將適應(yīng)度較高的染色體直接復(fù)制到下一代染色體中。

2.7 選擇操作

經(jīng)過上述操作，得到新一代的染色體種群?；谀繕?biāo)函數(shù)評估得到的染色體種群，如果對當(dāng)前調(diào)度方案不滿意，則重復(fù)上述遺傳操作過程。當(dāng)染色體種群進(jìn)化速率比較小時，終止遺傳算法。

3 基于蟻群算法得到1553B總線消息調(diào)度最優(yōu)解

4 結(jié)束語

本文利用混合遺傳算法合理組織傳輸?shù)?553B消息塊，降低了總線的平均延遲率，使得總線負(fù)載達(dá)到均衡，并得到了最優(yōu)的通信效率。

實(shí)驗(yàn)證明，在周期消息和非周期消息混合傳輸?shù)那闆r下，文中所述算法具有實(shí)時性好、可靠性高、異步事件處理能力強(qiáng)等特點(diǎn)。

［1］劉桂山，胡軍程.1553B總線信息流設(shè)計(jì)［J］.北京理工大學(xué)學(xué)報，2003，23（3）：301-304.

［2］陸傳來.排隊(duì)論［M］.北京：北京郵電大學(xué)出版社，2000：20-150.

［3］孫力娟，王汝傳.基于蟻群算法和遺傳算法融合的QoS組播路由問題求解［J］.電子學(xué)報，2006，34（8）：1391-1395.

〔編輯：白潔〕

TP18

A

10.15913/j.cnki.kjycx.2017.13.059

2095-6835（2017）13-0059-03