基于改進差分進化算法的MVB周期調(diào)度表優(yōu)化設(shè)計

張 夢 璇， 于 躍,2， 顧 宏*

( 1.大連理工大學(xué) 控制科學(xué)與工程學(xué)院， 遼寧 大連 116024；2.中車大連電力牽引研發(fā)中心有限公司， 遼寧 大連 116045 )

基于改進差分進化算法的MVB周期調(diào)度表優(yōu)化設(shè)計

張 夢 璇1， 于 躍1,2， 顧 宏*1

( 1.大連理工大學(xué) 控制科學(xué)與工程學(xué)院， 遼寧 大連 116024；2.中車大連電力牽引研發(fā)中心有限公司， 遼寧 大連 116045 )

多功能車輛總線(MVB)周期調(diào)度表的優(yōu)化設(shè)計對提高列車通信網(wǎng)絡(luò)實時通信的可靠性和均衡網(wǎng)絡(luò)負荷具有重要作用．考慮到已有的多功能車輛總線周期調(diào)度表優(yōu)化方案存在的不足，提出了一種基于改進的差分進化算法的優(yōu)化設(shè)計方法．首先建立調(diào)度問題的數(shù)學(xué)模型，根據(jù)IEC61375-1國際標(biāo)準(zhǔn)和可調(diào)度性要求建立了優(yōu)化目標(biāo)和約束條件；然后根據(jù)周期調(diào)度表的生成特點對原差分進化算法的變異和選擇階段進行了改進，提出了適用于MVB周期調(diào)度的優(yōu)化方法；最后通過仿真實驗與現(xiàn)有優(yōu)化算法進行比較，驗證了本文所提的改進的差分進化算法對周期調(diào)度表的構(gòu)建具有更佳的優(yōu)化效果．

多功能車輛總線；改進的差分進化算法；周期調(diào)度表；均勻度

0 引 言

根據(jù)國際電工委員會定義的列車通信網(wǎng)絡(luò)國際標(biāo)準(zhǔn)IEC61375-1[1]，列車通信網(wǎng)絡(luò)實時能力的提高是列車網(wǎng)絡(luò)控制系統(tǒng)實時能力的重要保證．而在列車通信網(wǎng)絡(luò)中，周期信息傳輸?shù)膶崟r能力則依賴于周期調(diào)度表．

對于一般的現(xiàn)場總線，多功能車輛總線(MVB)周期調(diào)度表的構(gòu)建方法主要包括最小截止期優(yōu)先算法、單調(diào)速率算法、延遲釋放算法[2]、均勻度優(yōu)先算法[3]、逐步填空法[4]．然而隨著列車通信網(wǎng)絡(luò)的日漸復(fù)雜，需要處理的周期消息增多，上述傳統(tǒng)算法已不能有效地構(gòu)建周期調(diào)度表，智能優(yōu)化算法被更多地運用于周期調(diào)度表的優(yōu)化研究中．文獻[5]運用多目標(biāo)粒子群算法優(yōu)化周期調(diào)度表；文獻[6]采用Pareto蟻群算法優(yōu)化周期調(diào)度表，并且得到了優(yōu)于多目標(biāo)粒子群算法和基本蟻群算法的結(jié)果，但是該算法的參數(shù)設(shè)定嚴(yán)重依賴于人的經(jīng)驗，因而難以使算法性能達到最優(yōu)；文獻[7]采用模擬退火算法進行周期表的優(yōu)化調(diào)度，但是該算法收斂速度較慢，不利于實際調(diào)度過程中實時處理周期信息的需要．考慮到差分進化算法具有結(jié)構(gòu)簡單、收斂速度快、自適應(yīng)性強的優(yōu)點，有學(xué)者將差分進化算法運用到周期調(diào)度表的優(yōu)化[8]，而且得到了優(yōu)于逐步填空法的結(jié)果，然而未考慮到該算法缺乏局部搜索能力、難以選取變異策略的不足．

本文就如何得到滿足國際標(biāo)準(zhǔn)且性能更優(yōu)的周期調(diào)度表，提出改進的差分進化算法．不同于文獻[8]中固定的周期信息時長，本文兼顧非周期信息的處理，動態(tài)分配周期信息與非周期信息時長[9]．通過建模將差分進化算法應(yīng)用到周期調(diào)度表的優(yōu)化，自適應(yīng)的變異策略能夠提升算法的局部搜索能力，在選擇階段結(jié)合調(diào)度表的生成特點加入容忍度旨在選出符合約束條件的更優(yōu)個體．最后在已有的3組周期信息數(shù)據(jù)上分別與蟻群算法、模擬退火算法、差分進化算法進行對比，驗證改進的差分進化算法對周期調(diào)度表的優(yōu)化效果．

1 多功能車輛總線通信的建模

1.1 MVB信息通信原理

MVB是用于連接可編程的站及簡單傳感器或執(zhí)行機構(gòu)的車輛總線，總線上支持兩種類型的數(shù)據(jù)傳送: 周期性數(shù)據(jù)及偶發(fā)性數(shù)據(jù)[1]．周期性數(shù)據(jù)是按一個特征周期間隔，在總線的周期相內(nèi)周期性發(fā)送的過程數(shù)據(jù)，且與設(shè)備狀態(tài)的傳輸相關(guān)聯(lián)．周期信息的實時傳輸能滿足列車網(wǎng)絡(luò)系統(tǒng)對周期信息實時通信提出的要求，如確保機車速度、司機命令及電機電壓電流等周期信息在規(guī)定時間內(nèi)及時刷新．周期相在每個基本周期中占有一固定的部分，在周期相中總線主按預(yù)定順序輪詢各設(shè)備以獲取周期性數(shù)據(jù)，這種通信稱為周期性通信[1]．偶發(fā)性數(shù)據(jù)是在MVB總線的偶發(fā)相內(nèi)按需求發(fā)送的數(shù)據(jù)，總線負載的變化會影響其傳輸時延，在突發(fā)情況下，非周期相通過監(jiān)視數(shù)據(jù)和消息數(shù)據(jù)的傳輸完成非周期信息通信．列車運行速度的提高及車載系統(tǒng)的復(fù)雜化對列車系統(tǒng)的通信性能提出了更高的要求．

1.2 周期信息調(diào)度表模型

在MVB總線管理器中，將由主幀排列次序構(gòu)成的一個表稱為周期調(diào)度表，主幀的排列次序決定了源設(shè)備發(fā)送周期數(shù)據(jù)報文的先后次序．

MVB實時調(diào)度表的規(guī)模主要由周期信息的基本周期和宏周期決定．總線活動被分為若干周期，其最短的即為基本周期Tbp，它由周期相(對過程數(shù)據(jù))和偶發(fā)相(對消息數(shù)據(jù)和監(jiān)視數(shù)據(jù))組成[1]，1.0 ms≤Tbp≤1.5 ms．宏周期Tmacro是所有周期信息重復(fù)出現(xiàn)的最小間隔，其包含基本周期的數(shù)目為N=Tmacro/Tbp．同一源的相同過程數(shù)據(jù)兩次連續(xù)發(fā)送的間隔稱為特征周期Tip，特征周期是基本周期的2n倍[1]，即Tip=2λ-1Tbp，其中λ為其特征周期的級別，λ∈{1,2,…,10}．

假設(shè)一個MVB總線網(wǎng)絡(luò)系統(tǒng)上有n個周期信息參與通信，周期數(shù)據(jù)的傳輸任務(wù)集為m={m1,m2,…,mn}，產(chǎn)生周期數(shù)據(jù)的源端口地址和該周期數(shù)據(jù)的特征周期決定了每個周期的數(shù)據(jù)報文在任務(wù)集中的序號．任務(wù)集排序的一般規(guī)則為特征周期小的周期數(shù)據(jù)，序號在前；若數(shù)據(jù)的特征周期相同，則源端口地址小的序號在前．第i個周期信息mi可描述為mi=(ti,λi,si)，i∈{1,2,…,n}．其中，ti表示周期信息報文的傳輸時間；λi表示周期信息的特征周期級別；si表示第i個周期信息首次出現(xiàn)的基本周期序號．第i個周期信息的特征周期為Tip(i)=2λi-1Tbp．

1.3 約束條件

根據(jù)國際通信標(biāo)準(zhǔn)和實際工程需求，調(diào)度優(yōu)化問題中的約束條件可總結(jié)如下：

約束條件1 為了使最后生成的周期調(diào)度表唯一對應(yīng)一種調(diào)度策略s=(s1,s2,…,sn)，周期信息在宏周期內(nèi)首次出現(xiàn)的序號sj需在其特征周期內(nèi)，即sj≤2λj-1．

1.4 優(yōu)化目標(biāo)

周期調(diào)度表合理設(shè)計需要盡可能使各個基本周期的周期變量分布均勻[5]，目的是均衡周期信息負荷，并使每個基本周期留出盡可能多的時間給偶發(fā)相來處理突發(fā)信息．最理想的情況是每一個基本周期中用來處理周期信息的時長均相等，然而在周期信息的調(diào)度過程中，每一個周期信息的特征周期不全相同，而且處理每個周期信息的時長也有差別，因而理想的情況一般不可能存在．另外，如果某些基本周期內(nèi)處理周期信息的時長占比超過60%，需要擴大調(diào)度表的宏周期來滿足約束條件2．然而宏周期的擴大會減小MVB總線的網(wǎng)絡(luò)利用率和吞吐量[10]．

因此，為了均衡網(wǎng)絡(luò)負荷，更好地處理偶發(fā)信息，盡可能提高總線利用率和吞吐量，應(yīng)盡量減小周期信息在各周期相中所占時間的波動．因而周期調(diào)度表的優(yōu)化問題可以表示為

(1)

si≤2λi-1

式中：優(yōu)化目標(biāo)為周期調(diào)度表的均勻度；s=(s1,s2,…,sn)為優(yōu)化目標(biāo)的輸入，sj表示第j個周期信息首次出現(xiàn)所在的基本周期序號；tj表示處理第j個周期信息的時長；n表示周期信息的個數(shù)；Nt表示一個宏周期內(nèi)的基本周期數(shù)；Tbp為一個基本周期時長；λi為第i個周期信息的特征周期級別；aij表示第j個周期信息是否在第i個基本周期中被處理．

(2)

tave表示一個宏周期內(nèi)處理所有周期信息的總時間平均到每個基本周期的時間，表示如下：

(3)

由于在每個宏周期內(nèi)，第i個周期信息的處理時長ti不變，特征周期λi不變，平均到每個基本周期的周期信息處理時長tave也不變．

2 優(yōu)化算法

2.1 差分進化算法的可行性分析

MVB周期調(diào)度表的優(yōu)化問題可以抽象為已知每個周期信息的處理時長和特征周期，尋找周期信息主幀最優(yōu)排列組合．這類問題可以歸納為排列組合的優(yōu)化問題．當(dāng)網(wǎng)絡(luò)上的周期信息數(shù)較少時，滿足約束條件下生成的所有周期調(diào)度表可以用窮舉法手動列舉出來，找出均勻度最小的組合方法對應(yīng)的周期調(diào)度表．但隨著高速列車車載設(shè)備的增多，信息量隨之增大，可以證明MVB周期調(diào)度表的優(yōu)化問題屬于NP難題[4]．本文將采用適用于求解NP難題的差分進化算法[11-13]對問題進行研究．

2.2 算法的改進及實現(xiàn)

差分進化算法是一類基于群體的自適應(yīng)全局優(yōu)化算法，屬于演化算法的一種．算法的基本流程有編碼與初始化、差分變異操作、變量邊界的約束控制、雜交操作和選擇操作．該算法具有結(jié)構(gòu)簡單、容易使用、魯棒性強等優(yōu)點，因而易于處理調(diào)度表的優(yōu)化問題；但具有缺乏局部搜索能力、參數(shù)設(shè)置敏感、變異策略選取困難等缺點，本文將結(jié)合調(diào)度表優(yōu)化的具體情況改進該算法．將差分進化算法運用于周期調(diào)度表優(yōu)化的具體步驟如下：

(1)編碼與種群初始化

周期調(diào)度表中每個周期信息首次被處理的基本周期序號可以選擇1到Tip，每個周期信息首次處理的基本周期序號構(gòu)成了個體中的每一維．常規(guī)的初始化方法為

P=(p1p2…pM)T= rand int (M,N,[a,b])

(4)

式中：pi表示矩陣中第i個行向量，即群體P中的第i個個體；M為群里中的個體數(shù)，N為個體的維度；rand int(M,N,[a,b])表示生成M×N矩陣且矩陣中的每個元素都是在[a,b]上均勻采樣后取整得到的隨機整數(shù)．

在調(diào)度表中，每一個周期信息對應(yīng)的特征周期不一樣，因而個體中每一維的取值范圍均不同．本文參考文獻[14]的編碼方式，將差分進化算法成功地運用到離散的組合優(yōu)化問題中．采取的方法具體如式(5)、(6)所示．首先生成隨機群體P；在計算每個個體對應(yīng)的調(diào)度策略時，將每個個體與以特征周期為對角線的對角矩陣相乘，最終取整得到該隨機個體對應(yīng)的由周期序號構(gòu)成的向量，即調(diào)度策略．

P=rand(M,N)

(5)

(6)

式(5)中借用Matlab中的符號rand(M,N)表示生成M×N的均勻隨機矩陣．式(6)中借用Matlab 中的符號ceil(a)表示不小于a的最小整數(shù)，Di表示第i個個體對應(yīng)的調(diào)度策略，Tip(N)表示第N個周期信息的特征周期．

(2)自適應(yīng)變異操作

原始差分進化算法采用的是全局策略，仿真中容易陷入局部最優(yōu)，取迭代次數(shù)為5 000次，發(fā)現(xiàn)往往在不到2 000次時，算法陷入局部最優(yōu)，不再產(chǎn)生更優(yōu)解．差分進化算法中可以選擇的策略很多，常見的策略主要分為全局策略和局部策略兩大類，如式(7)～(11)所示．

全局變異策略1：

vi=xr1+Fi(xr2-xr3)

(7)

全局變異策略2：

vi=xr1+Fi(xr2-xr3)+Fi(xr4-xr5)

(8)

局部變異策略1：

vi=xbest+Fi(xr2-xr3)

(9)

局部變異策略2：

vi=xbest+Fi(xr2-xr3)+Fi(xr4-xr5)

(10)

局部變異策略3：

vi=xi+Fi(xbest-xi)+Fi(xr2-xr3)

(11)

式中：vi是變異向量；r1≠r2≠r3≠r4≠r5≠i為群體中隨機選擇的5個個體的標(biāo)號；xbest為當(dāng)前群體的最優(yōu)個體；xi為父個體；xr2-xr3、xr4-xr5為差分向量；Fi為第i個縮放因子，用于對差分向量的縮放，由于縮放因子F的設(shè)置很敏感，本文對F的取值參考文獻[15]：F∈(-0.9,-0.4)∪(0.4,0.9) ．

全局策略具有較強的搜索能力，能在解空間內(nèi)大范圍盡可能地搜索更優(yōu)解；局部策略的特點在于開采能力強，在較優(yōu)解附近尋找優(yōu)于較優(yōu)解的個體．基于兩類策略的特點，為保持種群的多樣性，在算法迭代前期，更多地采用全局策略來產(chǎn)生變異向量，有助于算法找到全局的最優(yōu)解．為了使算法更好地擇優(yōu)，在算法迭代后期，更多地采用局部策略產(chǎn)生變異向量，在上一次迭代產(chǎn)生的最優(yōu)解周圍盡可能尋找更優(yōu)的個體．將兩類變異策略結(jié)合使用的優(yōu)勢在于同時兼顧了算法迭代過程中的多樣性和擇優(yōu)[16]．

本文選取全局變異策略1作為全局策略，局部變異策略3作為局部策略．考慮到Sigmoid函數(shù)的值域為(0,1)，可以將選取每種策略的概率映射到Sigmoid 函數(shù)值上．再者，Sigmoid函數(shù)前期上升平緩，在函數(shù)值為0.5時對應(yīng)最大的變化率，運用在策略選擇上，可以實現(xiàn)策略選擇的轉(zhuǎn)換．根據(jù)實驗迭代觀察，實驗進展到2 000次左右時便會陷入局部最優(yōu)，因而取2 000次為策略的變換點，使得算法在2 000次迭代后更傾向于選擇局部變異策略．因而本文采用Sigmoid函數(shù)作為自適應(yīng)函數(shù)，可以實現(xiàn)在迭代前期，種群在大范圍內(nèi)搜索更優(yōu)解，保持種群的多樣性；在迭代后期，采用局部策略，使得算法有針對性地在較優(yōu)解附近搜索更優(yōu)解，使種群更好地擇優(yōu)．

調(diào)度的總次數(shù)為5 000次，自適應(yīng)函數(shù)為P(x)=1/(1+e(2 000-x)/200)，如圖1所示．其中x代表迭代次數(shù)，P(x)代表算法選擇局部策略的可能性．

圖1 選擇策略的自適應(yīng)函數(shù)

(3)雜交操作

差分進化算法中雜交操作是將變異向量與父個體向量進行離散雜交得到嘗試向量的操作．交叉系數(shù)取值越大，嘗試向量每一維取變異向量對應(yīng)值的可能性越大，反之越?。唧w表示為

通信公司具有龐大的人力資源管理系統(tǒng)，在實際的管理過程中，依然存在一定的問題。其中，人力資源管理理念滯后就是存在的問題之一。管理理念滯后的原因主要在于管理方式選擇不當(dāng)。目前，部分通信公司還采用職能制的管理方式，這種管理方式不利于大型的人力資源管理，隨著通信行業(yè)的飛速發(fā)展，顯然不適用于通信公司。還有部分通信公司采用分割制管理方式，其不利于企業(yè)管理者與員工很好的溝通，進而對于公司的發(fā)展會產(chǎn)生限制。總之，無論是哪種管理方式，都難以促使人力資源發(fā)揮應(yīng)有的作用[1]。

(12)

式中：γ表示(0,1)上均勻分布生成的隨機數(shù)；Cr為交叉系數(shù)，本文中Cr的取值參考文獻[17]：Cr∈(0.1,0.9)；j=1,…,N，N是每個個體的維度；jrand是自然數(shù)集{1,2,…,D}中的一個隨機整數(shù)，保證嘗試向量ui中至少有一維來自變異向量vi，為了避免嘗試向量與父個體向量完全一樣．

(4)選擇操作

原始差分進化算法的選擇規(guī)則：如果雜交操作產(chǎn)生的嘗試向量ui所對應(yīng)的適應(yīng)值優(yōu)于父個體向量對應(yīng)的適應(yīng)值，則取該嘗試向量替代父個體向量．具體表示為

(13)

其中f(·)為適應(yīng)值函數(shù)．

然而考慮到約束條件2，對于適應(yīng)值相差較小的兩個個體，適應(yīng)值小的個體產(chǎn)生的周期調(diào)度表不一定更優(yōu)．如圖2所示對應(yīng)一組周期信息{V0,V1,V2,V3,V4,V5,V6,V7,V8,V9}的兩種調(diào)度方案，其中周期信息V0和V1的特征周期為Tbp，V2、V3、V4、V5的特征周期為2Tbp，V6、V7、V8、V9的特征周期為4Tbp，對應(yīng)的調(diào)度表的宏周期為4Tbp．在圖2中用BP(0)、BP(1)、BP(2)、BP(3)分別表示一個宏周期內(nèi)第1、第2、第3和第4個基本周期．方案1的均勻度為1.73，方案2的均勻度為1.22，方案2中第一個基本周期中周期信息處理時長為整個基本周期時長的70%，無法滿足約束條件2，因而盡管方案2對應(yīng)的均勻度小于方案1，但是不能采納方案2為周期調(diào)度方案．

BP(0)V0V1V2V3V4V5BP(1)V0V1BP(2)V0V1V2V3V4V5BP(3)V0V1V6V7V8V9→基本周期←(a)方案1

BP(0)V0V1V2V4V6V7V8BP(1)V0V1V3V5BP(2)V0V1V2V4V9BP(3)V0V1V3V5→基本周期←(b)方案2

圖2 適應(yīng)值不同的兩方案對比

Fig.2 The comparison of two plans with different fitness value

在選擇過程中加入一個容忍度指標(biāo)，其含義為嘗試向量與父個體向量的適應(yīng)值之差所能承受的最大值，用α表示．同時，為了避免周期調(diào)度表中少數(shù)基本周期預(yù)留給非周期信息的處理時間較短，從而導(dǎo)致在這些基本周期內(nèi)出現(xiàn)的突發(fā)信息得不到及時處理的情況，取周期調(diào)度表中周期信息處理時長占基本周期比例最大值盡量小的調(diào)度策略，該比例用P表示．改進后的選擇規(guī)則可表示為

(14)

最后，總結(jié)本文所提優(yōu)化算法的流程圖如圖3所示．

圖3 改進的差分進化算法流程圖

本文對差分進化算法的改進體現(xiàn)為針對原差分進化算法易陷入局部最優(yōu)的不足，采用Sigmoid 函數(shù)自適應(yīng)地調(diào)整算法迭代時使用的變異策略，提升了算法的局部搜索能力；在算法中加入容忍度使最終優(yōu)化調(diào)度方案中每個基本周期的利用率在60%以下，以滿足列車通信網(wǎng)絡(luò)標(biāo)準(zhǔn)所提要求．

3 仿真分析

為了驗證改進差分進化算法對生成MVB周期調(diào)度表這一實際問題的有效性，分別與文獻[6]中運用Pareto蟻群算法、文獻[7]中運用模擬退火算法和文獻[8]中運用差分進化算法生成的周期調(diào)度表的效果進行對比．在仿真中算法的參數(shù)設(shè)定為縮放因子F∈(-0.9,-0.4)∪(0.4,0.9)，雜交因子Cr∈(0.1,0.9)，種群中個體數(shù)目Np=50，迭代次數(shù)Nk=5 000，容忍度α=1．

文獻[6]的設(shè)備信息數(shù)據(jù)如表1所示，參照文獻[6]取基本周期Tbp=1.3 ms．文獻[6]中由蟻群算法得到的解向量為(2 1 2 2 4 4 3 1 7 7 6 2 1 7 14 11 2 10 11 3 13 5 1 15)．本文算法仿真得到的解向量為(1 1 2 1 1 1 2 4 4 2 4 2 3 2 12 16 14 14 16 7 6 8 15 31)．

表1 文獻[6]的設(shè)備信息數(shù)據(jù)

圖4為改進的差分進化算法和Pareto蟻群算法對應(yīng)的調(diào)度方案的總線利用率R分布圖．在總線利用率分布圖中，如果每個基本周期的利用率在平均利用率附近分布，且波動越小，對應(yīng)的調(diào)度效果越好．用均勻度來度量調(diào)度效果，若均勻度越小，則表明每個基本周期的周期信息處理時長越均勻，調(diào)度效果越好；反之亦然．由圖4可看出圖4(a)的總線利用率分布比圖4(b)更均勻．表2(其中粗體部分表示最好的效果值)結(jié)果說明在改進的差分進化算法中，通過對每個基本周期內(nèi)參與通信的周期信息的合理安排，可以優(yōu)化周期調(diào)度表的均勻度，在均勻度得到優(yōu)化的情況下，各基本周期內(nèi)周期信息處理時長的波動更小，有效地平均了每個基本周期的負載，同時提高了調(diào)度的穩(wěn)定性．

(a) 改進的差分進化算法

(b) Pareto蟻群算法

圖4 改進的差分進化算法和Pareto蟻群算法總線利用率

Fig.4 Bus utilization of improved differential evolution algorithm and Pareto ant colony algorithm

表2 改進的差分進化算法與Pareto蟻群算法比較

文獻[7]的設(shè)備信息數(shù)據(jù)如表3所示，參照文獻[7] 取基本周期Tbp=1.0 ms．文獻[7]中由模擬退火算法得到的解向量為(1 2 3 4 2 1 4 1 3 3 2 3 2 10 14 7 7 15 22 6)，本文算法得到的解向量為(1 1 3 4 4 2 2 3 4 8 8 1 12 4 13 9 13 5 17 1)．

表3 文獻[7]的設(shè)備信息數(shù)據(jù)

圖5為改進的差分進化算法與模擬退火算法對應(yīng)的調(diào)度方案的總線利用率分布圖，盡管圖5(a) 中最大總線利用率高于圖5(b)，但是兩方案中總線利用率均小于42%，已經(jīng)符合國際標(biāo)準(zhǔn)要求的60%以下．另外，可看出圖5(a)中總線利用率的整體分布較圖5(b)更均勻．表4(粗體部分表示效果最好的值)為改進的差分進化算法與模擬退火算法的效果比較，改進的差分進化算法的最終調(diào)度方案對應(yīng)的均勻度更小，說明由改進的差分進化算法得到的周期調(diào)度表內(nèi)每個基本周期的負載分布更均勻，調(diào)度穩(wěn)定性更好．

(a) 改進的差分進化算法

(b) 模擬退火算法

圖5 改進的差分進化算法和模擬退火算法總線利用率

Fig.5 Bus utilization of improved differential evolution algorithm and simulation annealing algorithm

表4 改進的差分進化算法與模擬退火算法比較

Tab.4 The comparison of improved differential evolution algorithm and simulation annealing algorithm

算法均勻度最大總線利用率/%最小總線利用率/%改進的差分進化算法13.9041.134.2差分進化算法25.3541.131.5模擬退火算法20.5039.632.1

文獻[8]的設(shè)備信息數(shù)據(jù)如表5所示，將仿真實驗參數(shù)與文獻[8]中的設(shè)為一致：MVB總線基本周期為1 ms，周期相長度為0.7 ms．文獻[8]中由差分進化算法得到的解向量為(1 2 1 4 4 5 7 2 3 3 3 2 15 14 7 6 10 7 22 6)，本文算法得到的解向量為(1 2 3 3 1 4 4 1 1 2 7 5 6 14 14 3 2 10 11 27)．

表5 文獻[8]的設(shè)備信息數(shù)據(jù)

圖6為改進的差分進化算法與差分進化算法對應(yīng)的總線利用率分布圖，由該圖可看出圖6(a)中總線利用率的分布較圖6(b)的分布更均勻．

(a) 改進的差分進化算法

(b) 差分進化算法

圖6 改進的差分進化算法和差分進化算法總線利用率

Fig.6 Bus utilization of improved differential evolution algorithm and differential evolution algorithm

表6(粗體部分表示效果最好的值)為改進的差分進化算法與差分進化算法的效果對比，改進的差分進化算法對應(yīng)調(diào)度策略的均勻度更小，相比于差分進化算法有助于提高列車系統(tǒng)中周期信息傳輸?shù)姆€(wěn)定性．

表6 改進的差分進化算法與差分進化算法比較

Tab.6 The comparison of improved differential evolution algorithm and differential evolution algorithm

算法均勻度最大總線利用率/%最小總線利用率/%改進的差分進化算法10.4070.0063.14差分進化算法32.9675.8660.14

4 結(jié) 語

本文分析了MVB周期調(diào)度表的構(gòu)建方法，并采用改進的差分進化算法對其進行了優(yōu)化設(shè)計．首先提出了MVB周期調(diào)度表的模型及相應(yīng)的約束條件，接著提出了本文的優(yōu)化目標(biāo)．然后針對周期調(diào)度表的優(yōu)化這一特定問題提出了對差分進化算法具體的改進方法．通過與Pareto蟻群算法、模擬退火算法和原始差分進化算法的比較可以看出，本文算法改善了周期數(shù)據(jù)負載在各基本周期中的均勻度，有效地均衡了處理周期信息的負載，同時也為非周期信息的處理預(yù)留了更多時間，對偶發(fā)信息的處理具有重要意義．另外，周期信息的合理調(diào)度避免宏周期通過加倍來滿足調(diào)度約束條件的情況，使得網(wǎng)絡(luò)性能指標(biāo)如信息吞吐量和網(wǎng)絡(luò)利用率盡可能高．

[1] IEC. Electric Railway Equipment-Train Bus-Part 1:Train Communication Network:IEC61375-1:1999 [S]. Geneva:IEC, 1999.

[2] TOVAR E, VASQUES F. Distributed computing for the factory-floor:a real-time approach using WorldFIP networks [J]. Computers in Industry, 2001, 44(1):11-31.

[3] 郭超勇,劉建強,鄭瓊林. 350 km/h動車組TCN網(wǎng)絡(luò)周期輪詢優(yōu)化算法研究[J]. 鐵道學(xué)報, 2011, 33(12):46-50.

GUO Chaoyong, LIU Jianqiang, ZHENG Qionglin. Research on the TCN network periodic polling optimization algorithm for the 350 km/h electrical multiple units [J]. Journal of the China Railway Society, 2011, 33(12):46-50. (in Chinese)

[4] 王永翔,王立德. 多功能車輛總線周期掃描表的最優(yōu)化設(shè)計[J]. 鐵道學(xué)報, 2009, 31(6):46-52.

WANG Yongxiang, WANG Lide. The optimization method of the MVB period polling table [J]. Journal of the China Railway Society, 2009, 31(6):46-52. (in Chinese)

[5] 陳佳凱,韋 巍. 基于多目標(biāo)粒子群優(yōu)化的多功能車輛總線周期性掃描表的優(yōu)化[J]. 鐵道學(xué)報, 2012, 34(11):60-66.

CHEN Jiakai, WEI Wei. Optimization of the MVB period polling table based on multi-objective particle swarm optimization [J]. Journal of the China Railway Society, 2012, 34(11):60-66. (in Chinese)

[6] 范 超,于 躍,顧 宏. 基于Pareto 蟻群算法的MVB周期輪詢表優(yōu)化設(shè)計[J]. 大連理工大學(xué)學(xué)報, 2015, 55(3):319-325.

FAN Chao, YU Yue, GU Hong. Optimization design of MVB period polling table based on Pareto ant colony algorithm [J]. Journal of Dalian University of Technology, 2015, 55(3):319-325. (in Chinese)

[7] 曾秋芬,陳特放. 多功能車輛總線周期掃描表優(yōu)化設(shè)計[J]. 計算機工程與應(yīng)用, 2015, 51(7):30-34, 55.

ZENG Qiufen, CHEN Tefang. Optimization design of MVB periodic scanning table based on simulated annealing algorithm [J]. Computer Engineering and Applications, 2015, 51(7):30-34, 55. (in Chinese)

[8] 徐進權(quán),王宏志,胡黃水. 差分進化MVB總線周期掃描表[J]. 長春工業(yè)大學(xué)學(xué)報(自然科學(xué)版), 2016, 37(1):36-41.

XU Jinquan, WANG Hongzhi, HU Huangshui. Periodic polling table in multifunction vehicle bus based on the differential evolution algorithm [J]. Journal of Changchun University of Technology (Natural Science Edition), 2016, 37(1):36-41. (in Chinese)

[9] 朱 俊,李 芳,王麗芳. 多功能車輛總線非周期數(shù)據(jù)實時性分析與帶寬分配的優(yōu)化設(shè)計[J]. 機車電傳動, 2014(3):24-28.

ZHU Jun, LI Fang, WANG Lifang. Research on real-time performance of aperiodic message and optimized design of bandwidth allocation in multifunction vehicle bus [J]. Electric Drive for Locomotives, 2014(3):24-28. (in Chinese)

[10] 曾秋芬,陳特放,劉毅斌. MVB非周期信息的通信帶寬分配策略研究[J]. 電子技術(shù)應(yīng)用, 2011, 37(4):106-108.

ZENG Qiufen, CHEN Tefang, LIU Yibin. Study on bandwidth allocation strategy of MVB aperiodic communication [J]. Application of Electronic Technique, 2011, 37(4):106-108. (in Chinese)

[11] NERI F, TIRRONEN V. Recent advances in differential evolution:a survey and experimental analysis [J]. Artificial Intelligence Review, 2010, 33(1/2):61-106.

[12] PAN Quanke, TASGETIREN M F, LIANG Y C. A discrete differential evolution algorithm for the permutation flowshop scheduling problem [J]. Computers & Industrial Engineering, 2008, 55(4):795-816.

[13] LIU Ying, YIN Minghao, GU Wenxiang,etal. An effective differential evolution algorithm for permutation flow shop scheduling problem [J]. Applied Mathematics and Computation, 2014, 248:143-159.

[14] NEARCHOU A C, OMIROU S L. Differential evolution for sequencing and scheduling optimization [J]. Journal of Heuristics, 2006, 12(6):395-411.

[15] KAELO P, ALI M M. A numerical study of some modified differential evolution algorithms [J]. European Journal of Operational Research, 2006, 169(3):1176-1184.

[16] XIANG Wanli, MENG Xuelei, AN Meiqing,etal. An enhanced differential evolution algorithm based on multiple mutation strategies [J]. Computational Intelligence and Neuroscience, 2015:285730.

[17] YANG Zhenyu, YAO Xin, HE Jingsong. Making a difference to differential evolution [M] // Advances in Metaheuristics for Hard Optimization. Berlin: Springer Berlin Heidelberg, 2007:397-414.

[18] ZHU Qinyu, QIN A K, SUGANTHAN P N,etal. Evolutionary extreme learning machine [J]. Pattern Recognition, 2005, 38(10):1759-1763.

Optimized design of MVB periodic dispatch table based on improved differential evolution algorithm

ZHANG Mengxuan1, YU Yue1,2, GU Hong*1

( 1.School of Control Science and Engineering, Dalian University of Technology, Dalian 116024, China；2.CRRC Dalian Electric Traction R&D Center Co., Ltd., Dalian 116045, China )

Optimization design of multifunction vehicle bus (MVB) periodic dispatch table is of great importance to improving the reliability of real-time communication of train and balancing the network load. To tackle the disadvantage of existing optimal schemes of MVB periodic dispatch table, an optimization design method is proposed based on improved differential evolution algorithm. Firstly, the mathematical model of the dispatch problem is built, and the optimal objective and constraints are obtained according to the IEC61375-1 international standard and dispatching requirements. Then, the variation and selection phases of differential evolution algorithm are modified with respect to the characteristics of the generation of periodic dispatch table, an optimization method for MVB periodic table is proposed. Finally, the simulation results prove that the improved differential evolution algorithm can achieve the better optimization results of MVB periodic dispatch table compared with existing optimization algorithms.

multifunction vehicle bus (MVB); improved differential evolution algorithm; periodic dispatch table; evenness

2016-10-20；

2017-02-20．

國家自然科學(xué)基金資助項目(61502074,U1560102)；高等學(xué)校博士學(xué)科點專項科研基金資助項目(20120041110008).

張夢璇(1991-)，女，碩士生，E-mail:1057421354@qq.com；于 躍(1977-)，男，碩士，教授級高工；顧 宏*(1961-)，男，教授，博士生導(dǎo)師，E-mail:guhong@dlut.edu.cn.

1000-8608(2017)02-0207-09

TP302.7；U285.4

A

10.7511/dllgxb201702015