鬼佬大哥大
  • / 12
  • 下載費用:30 金幣  

基于混合遺傳算法的1553B總線消息傳輸優化方法.pdf

摘要
申請專利號:

CN201510758135.9

申請日:

2015.11.06

公開號:

CN105205536A

公開日:

2015.12.30

當前法律狀態:

授權

有效性:

有權

法律詳情: 授權|||實質審查的生效IPC(主分類):G06N 3/12申請日:20151106|||公開
IPC分類號: G06N3/12; G06F13/42 主分類號: G06N3/12
申請人: 天津津航計算技術研究所
發明人: 趙昶宇
地址: 300308 天津市東麗區空港經濟區保稅路357號
優先權:
專利代理機構: 中國兵器工業集團公司專利中心 11011 代理人: 劉東升
PDF完整版下載: PDF下載
法律狀態
申請(專利)號:

CN201510758135.9

授權公告號:

||||||

法律狀態公告日:

2017.11.10|||2016.01.27|||2015.12.30

法律狀態類型:

授權|||實質審查的生效|||公開

摘要

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

權利要求書

權利要求書
1.  一種基于混合遺傳算法的1553B總線消息傳輸優化方法,其特征在于,包括以下步驟:
S1、基于排隊論建立1553B總線消息傳輸的數學模型,得到目標函數:
將1553B總線上消息的傳輸過程看作是一種單服務員單隊列的排隊系統,排隊模型為一個M|M|1排隊模型,總線上的每一條消息指令為等待服務的顧客,總線為提供數據傳輸的服務員,服務時間為消息傳輸時間;
該排隊系統的排隊規則為:
消息的相繼到達時間間隔獨立,假設到達時間服從泊松分布;
排隊隊列的長度為無限長,服務方式服從先來先服務;
S2、基于改進遺傳算法得到1553B總線消息調度可行解:
利用遺傳算法對染色體進行編碼,確定初始種群,通過遺傳算法中的遺傳操作對初始種群進行優化,即根據自識別交叉和變異概率,對初始種群進行交叉、變異操作,根據所述目標函數對染色體種群進行評估,當染色體種群進化速率小于預設閾值時終止遺傳算法,得到1553B總線消息調度可行解;
S3、基于改進蟻群算法得到1553B總線消息調度最優解:
根據遺傳算法得到的全局搜索信息設置信息素初始值,根據1553B總線消息調度的完成情況,調整信息素;在消息準備傳輸時,觀察各個空閑資源的信息素,按照概率大小選擇資源使用;在消息傳輸結束后,對消息進行評價,根據信息匹配度進行信息素反饋,得到最優的調度方案。

2.  如權利要求1所述的方法,其特征在于,步驟S1得到的目標函數為:其中λ為消息的平均到達率,μ為總線的平均服務率,cs為當μ=1時總線消息傳輸所耗費的時間,cw為每條消息在總線中排隊等候所耗費的時間。

3.  如權利要求2所述的方法,其特征在于,步驟S2具體包括:
S21、進行染色體編碼:
設定消息個數為m,消息周期個數為n,m個消息要被安排在n個周期上,個體染色體上的每個基因位置編號代表消息編號,每個基因位用0~(m-1)之間的整數表示,代表某條消息所在的周期編號;
S22、確定初始種群:
首先隨機產生N個個體,個體長度為Length,u是種群內的第一個個體,v是與u進行相似度比較的個體,它們之間的相似度定義為:
sim(u,v)=1-dist(u,v),其中dist(u,v)為海明距離函數
通過比較個體相似度,要求規定能夠入選初始個體相似度滿足如下條件:
sim(u,v)<Length-dLength,u&NotEqual;v]]>
其中d表示調節常數,用于控制期望的相似度;
S23、確定適應度函數
所述適應度函數用于評價染色體的優劣,函數值越大表示染色體生存能力越強,對應的解越優,得到適應度函數為:
fitness(f(x))=1csμ+cw&CenterDot;λμ-λ]]>
S24、執行交叉操作
采用多點位單基因交叉的方式,用父代最優解Tmax與子代染色體池進行交叉操作;
S25、執行變異操作
在單個染色體Ti=(ti1,ti2,…,tim)上隨機選擇連續多個基因,對多個基因進行重新排列實現染色體的變異,i=1,2,…,n;
S26、執行復制操作
基于適應度函數fitness(f(x))對染色體個體進行評價,將適應度 高于預設閾值的染色體直接復制到下一代染色體中;
S27、執行選擇操作
經過上述操作,得到新一代的染色體種群,基于目標函數z對得到的染色體種群進行評估,若對當前調度方案不滿意,則重復上述步驟S21至S26的遺傳操作過程;當染色體種群進化速率小于預設閾值時終止遺傳算法。

4.  如權利要求3所述的方法,其特征在于,步驟S24具體為:
a)在染色體池T中選擇進行交叉操作的染色體Ti和最優染色體Tmax;
b)隨機生成交叉片段和交叉區域;
c)將Ti的交叉區域加到Tmax前面,將Tmax的交叉區域加到Ti前面;
d)刪除與Ti或Tmax的交叉區域相同的基因,得到兩個新的子代。

5.  如權利要求4所述的方法,其特征在于,步驟S3具體為:
設定bi(t)表示時刻t位于周期pi的螞蟻個數,則有用τi(t)表示t時刻在第i個周期pi的信息素值;
A)將m個螞蟻分別置于相應的周期內,并為各周期的信息素賦初值,τi(0)=ri-loadi(0),其中i=1,2,…,n,ri為第i個周期所擁有的處理消息能力,loadi(0)為遺傳算法終止時得到的當前最優調度方案指派給第i個周期pi的消息所占據的總線負載;
B)將螞蟻放置到有向圖節點上;
C)若有消息從第i個周期pi傳輸成功,則為該周期賦予信息素增量Δτi=Ce×K;否則,為該周期賦予信息素增量Δτi=Cp×K,其中K表示傳輸相應消息所用的時間開銷,Ce和Cp表示相應的獎懲因子;
D)更新所有周期的信息素,即τi(t)=τi(t)+Δτi,其中i=1,2,…,n;
E)根據各個周期的信息素分布情況計算概率:
pim(t)=&lsqb;τi(t)&rsqb;α×&lsqb;ηi&rsqb;βΣi&lsqb;τi(t)&rsqb;α×&lsqb;ηi&rsqb;β]]>
其中:τi(t)為t時刻第i個周期pi的信息素濃度;ηi為第i個周期pi所擁有的處理消息能力;α表示第i個周期信息素的重要性,β表示第i個周期的信息素所擁有的處理消息能力的重要程度,表示消息m在t時刻占用第i個周期pi的概率;
基于得到的最大概率值為每只螞蟻分別選取下一個周期pi;
F)根據所有螞蟻選取的周期,計算對應的適應度函數fitness(f(x)),fitness(f(x))值越大,相應的調度方案越好,記錄當前最優的調度方案;
若達到最大的迭代次數,或者迭代出現退化現象,則當前記錄調度最優解即為所得的最優調度方案;否則,清空所有螞蟻的蟻集,跳轉到步驟C)。

說明書

說明書基于混合遺傳算法的1553B總線消息傳輸優化方法
技術領域
本發明涉及總線消息傳輸技術領域,具體涉及一種基于混合遺傳算法的1553B總線消息傳輸優化方法。
背景技術
1553B總線是一種集中式控制的飛機內部電子系統聯網的標準,它的高可靠性、實時性以及靈活性使其在航空、航天等領域上得到廣泛的應用。
由于現有電子系統對實時性和可靠性具有很高的要求,必須保證1553B總線上消息傳輸的實時性。當1553B總線上需要處理不同長度不同周期的多種消息時,并且存在異步消息需要處理時,系統的實時性一般很難保證。目前比較常見的1553B總線消息優化算法有基于計算量向量算法、RMS調度算法、長釋放時間間隔優先算法、HTSF算法等。在上述方法中,基于計算量向量算法和RMS調度算法都是基于靜態負載均衡的,沒有解決消息的動態負載均衡問題,當總線上有很多非周期性消息時,容易導致總線堵塞或飽和;長釋放時間間隔優先算法不能保證釋放間隔較小的消息或者突發消息能在截止期前完成調度;HTSF算法沒有考慮同一時刻可能有多條消息同時到達的情況,而且算法執行效率較低。
為了避免出現1553B總線堵塞和飽和現象,提高1553B總線的利用率,降低總線的平均延遲時間,均衡總線負載,需要設計一種優化1553B總線消息傳輸的方法。
發明內容
(一)要解決的技術問題
本發明要解決的技術問題是:如何提高1553B總線的利用率,降 低總線的平均延遲時間,均衡總線負載,達到最優的通信效率。
(二)技術方案
為了解決上述技術問題,本發明提供了一種基于混合遺傳算法的1553B總線消息傳輸優化方法,包括以下步驟:
S1、基于排隊論建立1553B總線消息傳輸的數學模型,得到目標函數:
將1553B總線上消息的傳輸過程看作是一種單服務員單隊列的排隊系統,排隊模型為一個M|M|1排隊模型,總線上的每一條消息指令為等待服務的顧客,總線為提供數據傳輸的服務員,服務時間為消息傳輸時間;
該排隊系統的排隊規則為:
消息的相繼到達時間間隔獨立,假設到達時間服從泊松分布;
排隊隊列的長度為無限長,服務方式服從先來先服務;
S2、基于改進遺傳算法得到1553B總線消息調度可行解:
利用遺傳算法對染色體進行編碼,確定初始種群,通過遺傳算法中的遺傳操作對初始種群進行優化,即根據自識別交叉和變異概率,對初始種群進行交叉、變異操作,根據所述目標函數對染色體種群進行評估,當染色體種群進化速率小于預設閾值時終止遺傳算法,得到1553B總線消息調度可行解;
S3、基于改進蟻群算法得到1553B總線消息調度最優解:
根據遺傳算法得到的全局搜索信息設置信息素初始值,根據1553B總線消息調度的完成情況,調整信息素;在消息準備傳輸時,觀察各個空閑資源的信息素,按照概率大小選擇資源使用;在消息傳輸結束后,對消息進行評價,根據信息匹配度進行信息素反饋,得到最優的調度方案。
(三)有益效果
本發明先通過排隊論建立1553B總線消息調度數學模型,接著引 入遺傳算法快速找到1553B總線消息調度可行解,然后將遺傳算法找到的可行解轉換成蟻群優化算法初始信息素,最后利用蟻群算法的局部尋優和正反饋機制得到1553B總線消息調度最優解。仿真實驗結果表明,利用改進后的遺傳算法對1553B總線消息傳輸進行優化,能夠在滿足每條消息最大延遲時間要求和通訊實時性的前提下,提高了總線利用率,有效地緩解了總線消息擁塞和飽和現象,解決了總線負載均衡的難題,具有較好的處理異步消息的能力。
附圖說明
圖1是M|M|1模型發生率圖;
圖2是本發明實施例的方法流程中改進的遺傳算法流程圖;
圖3是本發明實施例的方法流程中改進的蟻群算法流程圖。
具體實施方式
為使本發明的目的、內容、和優點更加清楚,下面結合附圖和實施例,對本發明的具體實施方式作進一步詳細描述。
為了提高1553B總線消息傳輸的實時性,降低總線的通信延遲率,本文提出了一種改進遺傳算法的1553B總線消息傳輸優化方法,包括以下步驟:
1、基于排隊論建立1553B總線消息傳輸的數學模型
1553B總線上消息的傳輸過程可以看作是一種單服務員單隊列的排隊系統。該模型為一個M|M|1排隊模型。該排隊系統的模型發生率見圖1,其中圓圈中的數字代表排隊系統的狀態,則可知該排隊系統為一個齊次馬爾可夫鏈的生滅過程。
在圖1中,λ為消息的平均到達率,μ為總線的平均服務率,m為消息個數,因此1/λ為消息的平均時間間隔,1/μ為消息的平均傳輸時間。
設Ek為排隊系統在狀態k處的概率,ρ為總線利用率,建立生滅過程的狀態平衡方程:
狀態0:λρ0=μE1,E1=ρE0
狀態1:λρ1=μE2,E2=ρ2E0
……
狀態k:λρk=μEk+1,Ek+1=ρk+1E0(1)
假設消息的平均時間間隔大于消息的平均傳輸時間,即ρ﹤1,則下列級數
Σk=0Ek=E0(1+ρ+ρ2+...+ρk+...)---(2)]]>
=E01-ρ=1]]>收斂
由此得出排隊系統在不同狀態下的概率分別為:
E0=1-ρ
E1=ρ(1-ρ)
……
Ek=ρk(1-ρ)(3)
……
總線利用率為
ρ=λμ---(4)]]>
排隊系統內消息的平均數為:
L=Σk=0kEk=Σk=1k(1-ρ)=ρ(1-ρ)(1+2ρ+3ρ2+...)]]>
=ρ11-ρ=λμ-λ---(5)]]>
若排隊系統內有k條消息,其中k-1條消息在排隊等候,則排隊等候的消息平均數為:
Lq=Σk=1(k-1)Ek=Σk=1kEk-Σk=1Ek=λμ-λ-(1-E0)=λμ-λ-λμ=λ2μ(μ-λ)---(6)]]>
消息傳輸花費的時間為:
W=Σk=1k+1μEk=1μ(Σk=1kEk-Σk=1Ek)=1μ(λμ-λ+1)=1μ-λ---(7)]]>
消息排隊等候所花費時間的平均值為:
Wq=Σk=1kμEk=1μΣk=1kEk=1μ&CenterDot;λμ-λ---(8)]]>
1553B總線傳輸系統的平均延遲時間為消息傳輸時間和消息排隊等候時間之和。對1553B總線上非周期消息傳輸進行優化的目標是使平均延遲時間最小,并確定達到最優目標值的最優的總線平均服務率μ*。
取目標函數z為消息傳輸時間與消息在排隊系統中排隊等候時間之和的期望值:
z=csμ+cwL(9)
其中,cs為當μ=1時總線消息傳輸所耗費的時間,cw為每條消息在總線中排隊等候所耗費的時間。將代入上式,可得
z=csμ+cw&CenterDot;λμ-λ---(10)]]>
上式(10)即為1553B總線消息傳輸的數學模型。
2、基于遺傳算法得到1553B總線消息調度可行解,參考圖2:
(1)染色體編碼
設定消息個數為m,消息周期個數為n,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)確定初始種群
種群的初始化是遺傳算法的關鍵,傳統的遺傳算法確定初始種群多半采取隨機生成法形成染色體方案,以致于迭代開始就可能形成許多不可行的方案,要進行大量的計算后才能得到優化的方案,這在很大程度上降低了算法的運算效率,本發明對經典遺傳算法進行改進,改進后的初始種群的選擇算法能有效抑制“早熟”現象,其全局搜索能力和搜索效果都有了明顯的提高。改進后的初始種群的產生方式如下:
首先隨機產生N個個體,個體長度為Length,設x和y為兩個個體,u是種群內的第一個個體,v是與u進行相似度比較的個體,它們之間的相似度定義為:
sim(u,v)=1-dist(u,v)(dist(u,v)是海明距離函數)(11)
通過比較個體相似度,要求規定能夠入選初始個體相似度必須滿足如下條件:
sim(u,v)<Length-dLength(u&NotEqual;v)---(12)]]>
其中,d表示調節常數,用于控制期望的相似度。
(3)適應度函數
適應度函數用于評價染色體的優劣,其函數值越大表示染色體生存能力越強,對應的解最優。公式(10)給出了1553B總線傳輸系統的平均延遲時間函數,因此本發明采用的適應度函數為:
fitness(f(x))=1csμ+cw&CenterDot;λμ-λ---(13)]]>
(4)交叉操作
常用的交叉方式有一點交叉、兩點交叉、多點交叉和一致交叉等。本發明對遺傳算法進行改進,采用多點位單基因交叉的方式,用父代最優解Tmax與子代染色體池進行交叉操作,該方法能夠避免算法過早地喪失進化能力。具體步驟如下:
a)在染色體池T中選擇進行交叉操作的染色體Ti和最優染色體Tmax;
b)隨機生成交叉片段和交叉區域;
c)將Ti的交叉區域加到Tmax前面,將Tmax的交叉區域加到Ti前面;
d)刪除與Ti或Tmax的交叉區域相同的基因,得到兩個新的子代。
(5)變異操作
變異運算中變異率通常取0.1,在單個染色體Ti=(ti1,ti2,…,tim)上隨 機選擇連續多個基因,對多個基因進行重新排列實現染色體的變異。由于采用了最優個體Tmax保留的策略,所以在變異運算中,可以加大在當前最優個體附近進行搜索的概率,不用擔心破壞已經存在的優良染色體。
(6)復制操作
基于適應度函數fitness(f(x))對染色體個體進行評價,將適應度高于預設閾值的染色體直接復制到下一代染色體中。
(7)選擇操作
經過上述操作,得到新一代的染色體種群。基于目標函數z對得到的染色體種群進行評估,若對當前調度方案不滿意,則重復上述步驟(1)至(6)的遺傳操作過程;當染色體種群進化速率小于預設閾值時終止遺傳算法。
3、基于蟻群算法得到1553B總線消息調度最優解,參考圖3:
設定bi(t)表示時刻t位于周期pi的螞蟻個數,則有用τi(t)表示t時刻在第i個周期pi的信息素值,初始時刻τi(0)=ri-loadi(0),其中i=1,2,…,n,ri為第i個周期所擁有的處理消息能力,loadi(0)為遺傳算法終止時得到的當前最優調度方案指派給第i個周期pi的消息所占據的總線負載。
改進的蟻群算法描述如下:
a)將m個螞蟻分別置于相應的周期內,并為各周期的信息素賦初值,τi(0)=ri-loadi(0),其中i=1,2,…,n;
b)將螞蟻放置到有向圖節點上;
c)若有消息從第i個周期pi傳輸成功,則為該周期賦予信息素增量Δτi=Ce×K;否則,為該周期賦予信息素增量Δτi=Cp×K。其中K表示傳輸相應消息所用的時間開銷,Ce和Cp表示相應的獎懲因子;
d)更新所有周期的信息素,即τi(t)=τi(t)+Δτi,其中i=1,2,…,n;
e)根據各個周期的信息素分布情況,計算概率:
pim(t)=&lsqb;τi(t)&rsqb;α×&lsqb;ηi&rsqb;βΣi&lsqb;τi(t)&rsqb;α×&lsqb;ηi&rsqb;β---(14)]]>
其中:τi(t)為t時刻第i個周期pi的信息素濃度;ηi為第i個周期pi所擁有的處理消息能力;α表示第i個周期信息素的重要性,β表示第i個周期的信息素所擁有的處理消息能力的重要程度,表示消息m在t時刻占用第i個周期pi的概率;
基于得到的最大概率值為每只螞蟻分別選取下一個周期pi;
f)根據所有螞蟻選取的周期,計算對應的適應度函數fitness(f(x)),fitness(f(x))值越大,相應的調度方案越好,記錄當前最優的調度方案;
g)若達到最大的迭代次數,或者迭代出現退化現象,則當前記錄調度最優解即為所得的最優調度方案;否則,清空所有螞蟻的蟻集,跳轉到步驟c)。
改進后的蟻群算法和改進前的蟻群算法相比,在步驟c)和步驟d)上引進了獎懲因子Ce和Cp,避免了將傳輸時間短的消息安排到較大的傳輸周期上,通調整各個周期被選取的概率,更加合理的為每個消息分配周期,有利于提高總線消息傳輸效率。
以上所述僅是本發明的優選實施方式,應當指出,對于本技術領域的普通技術人員來說,在不脫離本發明技術原理的前提下,還可以做出若干改進和變形,這些改進和變形也應視為本發明的保護范圍。

關 鍵 詞:
基于 混合 遺傳 算法 1553 總線 消息 傳輸 優化 方法
  專利查詢網所有資源均是用戶自行上傳分享,僅供網友學習交流,未經上傳用戶書面授權,請勿作他用。
關于本文
本文標題:基于混合遺傳算法的1553B總線消息傳輸優化方法.pdf
鏈接地址:http://www.wwszu.club/p-6405731.html
關于我們 - 網站聲明 - 網站地圖 - 資源地圖 - 友情鏈接 - 網站客服客服 - 聯系我們

[email protected] 2017-2018 zhuanlichaxun.net網站版權所有
經營許可證編號:粵ICP備17046363號-1 
 


收起
展開
鬼佬大哥大