基于混合遺傳算法的1553B消息傳輸優化

2017-07-19 10:07:53趙昶宇

科技與創新 2017年13期

趙昶宇

（天津津航計算技術研究所，天津 300308）

趙昶宇

（天津津航計算技術研究所，天津 300308）

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

遺傳算法；蟻群算法；總線消息傳輸；數學模型

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

1 基于排隊論建立1553B總線消息傳輸的數學模型

圖1 M|M|1模型發生率圖

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

設Ek為排隊系統在狀態k處的概率，ρ為總線利用率，建立生滅過程的狀態平衡方程，即：

如果系統內有k條消息，其中，k-1條消息在排隊等候，則排隊等候的消息平均數為：

消息傳輸花費的時間為：

消息排隊等候所花費時間的平均值為：

1553B總線傳輸系統的平均延遲時間為消息傳輸時間和消息排隊等候時間之和。對總線上非周期消息傳輸進行優化的目標是使平均延遲時間最小，并確定達到最優目標值的最優總線平均服務率μ*。

取目標函數z為消息傳輸時間與消息在系統中排隊等候時間之和的期望值，即：

式（1）中：cs為當μ＝1時總線消息傳輸所耗費的時間；cw為每條消息在總線中排隊等候所耗費的時間。

式（2）為1553B總線消息傳輸的數學模型。

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

2.1 染色體編碼

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

2.2 確定初始種群

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

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

式（3）中：d為調節常數，用于控制期望的相似度。

2.3 適應度函數

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

2.4 交叉操作

常用的交叉方式有一點交叉、兩點交叉、多點交叉和一致交叉等。

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

2.5 變異操作

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

2.6 復制操作

基于適應度函數對染色體個體進行評價，將適應度較高的染色體直接復制到下一代染色體中。

2.7 選擇操作

經過上述操作，得到新一代的染色體種群。基于目標函數評估得到的染色體種群，如果對當前調度方案不滿意，則重復上述遺傳操作過程。當染色體種群進化速率比較小時，終止遺傳算法。