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

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

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

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

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

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

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

0 引 言

根據(jù)國際電工委員會(huì)定義的列車通信網(wǎng)絡(luò)國際標(biāo)準(zhǔn)IEC61375-1[1]，列車通信網(wǎng)絡(luò)實(shí)時(shí)能力的提高是列車網(wǎng)絡(luò)控制系統(tǒng)實(shí)時(shí)能力的重要保證．而在列車通信網(wǎng)絡(luò)中，周期信息傳輸?shù)膶?shí)時(shí)能力則依賴于周期調(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)化算法被更多地運(yùn)用于周期調(diào)度表的優(yōu)化研究中．文獻(xiàn)[5]運(yùn)用多目標(biāo)粒子群算法優(yōu)化周期調(diào)度表；文獻(xiàn)[6]采用Pareto蟻群算法優(yōu)化周期調(diào)度表，并且得到了優(yōu)于多目標(biāo)粒子群算法和基本蟻群算法的結(jié)果，但是該算法的參數(shù)設(shè)定嚴(yán)重依賴于人的經(jīng)驗(yàn)，因而難以使算法性能達(dá)到最優(yōu)；文獻(xiàn)[7]采用模擬退火算法進(jìn)行周期表的優(yōu)化調(diào)度，但是該算法收斂速度較慢，不利于實(shí)際調(diào)度過程中實(shí)時(shí)處理周期信息的需要．考慮到差分進(jìn)化算法具有結(jié)構(gòu)簡單、收斂速度快、自適應(yīng)性強(qiáng)的優(yōu)點(diǎn)，有學(xué)者將差分進(jìn)化算法運(yùn)用到周期調(diào)度表的優(yōu)化[8]，而且得到了優(yōu)于逐步填空法的結(jié)果，然而未考慮到該算法缺乏局部搜索能力、難以選取變異策略的不足．

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

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

1.1 MVB信息通信原理

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

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

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

MVB實(shí)時(shí)調(diào)度表的規(guī)模主要由周期信息的基本周期和宏周期決定．總線活動(dòng)被分為若干周期，其最短的即為基本周期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è)一個(gè)MVB總線網(wǎng)絡(luò)系統(tǒng)上有n個(gè)周期信息參與通信，周期數(shù)據(jù)的傳輸任務(wù)集為m={m1,m2,…,mn}，產(chǎn)生周期數(shù)據(jù)的源端口地址和該周期數(shù)據(jù)的特征周期決定了每個(gè)周期的數(shù)據(jù)報(bào)文在任務(wù)集中的序號(hào)．任務(wù)集排序的一般規(guī)則為特征周期小的周期數(shù)據(jù)，序號(hào)在前；若數(shù)據(jù)的特征周期相同，則源端口地址小的序號(hào)在前．第i個(gè)周期信息mi可描述為mi=(ti,λi,si)，i∈{1,2,…,n}．其中，ti表示周期信息報(bào)文的傳輸時(shí)間；λi表示周期信息的特征周期級別；si表示第i個(gè)周期信息首次出現(xiàn)的基本周期序號(hào)．第i個(gè)周期信息的特征周期為Tip(i)=2λi-1Tbp．

1.3 約束條件

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

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

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

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

因此，為了均衡網(wǎng)絡(luò)負(fù)荷，更好地處理偶發(fā)信息，盡可能提高總線利用率和吞吐量，應(yīng)盡量減小周期信息在各周期相中所占時(shí)間的波動(dò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個(gè)周期信息首次出現(xiàn)所在的基本周期序號(hào)；tj表示處理第j個(gè)周期信息的時(shí)長；n表示周期信息的個(gè)數(shù)；Nt表示一個(gè)宏周期內(nèi)的基本周期數(shù)；Tbp為一個(gè)基本周期時(shí)長；λi為第i個(gè)周期信息的特征周期級別；aij表示第j個(gè)周期信息是否在第i個(gè)基本周期中被處理．

(2)

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

(3)

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

2 優(yōu)化算法

2.1 差分進(jìn)化算法的可行性分析

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

2.2 算法的改進(jìn)及實(shí)現(xiàn)

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

(1)編碼與種群初始化

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

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

(4)

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

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

P=rand(M,N)

(5)

(6)

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

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

原始差分進(jìn)化算法采用的是全局策略，仿真中容易陷入局部最優(yōu)，取迭代次數(shù)為5 000次，發(fā)現(xiàn)往往在不到2 000次時(shí)，算法陷入局部最優(yōu)，不再產(chǎn)生更優(yōu)解．差分進(jìn)化算法中可以選擇的策略很多，常見的策略主要分為全局策略和局部策略兩大類，如式(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為群體中隨機(jī)選擇的5個(gè)個(gè)體的標(biāo)號(hào)；xbest為當(dāng)前群體的最優(yōu)個(gè)體；xi為父個(gè)體；xr2-xr3、xr4-xr5為差分向量；Fi為第i個(gè)縮放因子，用于對差分向量的縮放，由于縮放因子F的設(shè)置很敏感，本文對F的取值參考文獻(xiàn)[15]：F∈(-0.9,-0.4)∪(0.4,0.9) ．

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

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

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

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

(12)

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

(4)選擇操作

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

(13)

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

然而考慮到約束條件2，對于適應(yīng)值相差較小的兩個(gè)個(gè)體，適應(yīng)值小的個(gè)體產(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)分別表示一個(gè)宏周期內(nèi)第1、第2、第3和第4個(gè)基本周期．方案1的均勻度為1.73，方案2的均勻度為1.22，方案2中第一個(gè)基本周期中周期信息處理時(shí)長為整個(gè)基本周期時(shí)長的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

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

(14)

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

圖3 改進(jìn)的差分進(jìn)化算法流程圖

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

3 仿真分析

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

文獻(xiàn)[6]的設(shè)備信息數(shù)據(jù)如表1所示，參照文獻(xiàn)[6]取基本周期Tbp=1.3 ms．文獻(xiàn)[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 文獻(xiàn)[6]的設(shè)備信息數(shù)據(jù)

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

(a) 改進(jìn)的差分進(jìn)化算法

(b) Pareto蟻群算法

圖4 改進(jìn)的差分進(jìn)化算法和Pareto蟻群算法總線利用率

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

表2 改進(jìn)的差分進(jìn)化算法與Pareto蟻群算法比較

文獻(xiàn)[7]的設(shè)備信息數(shù)據(jù)如表3所示，參照文獻(xiàn)[7] 取基本周期Tbp=1.0 ms．文獻(xiàn)[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 文獻(xiàn)[7]的設(shè)備信息數(shù)據(jù)

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

(a) 改進(jìn)的差分進(jìn)化算法

(b) 模擬退火算法

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

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

表4 改進(jìn)的差分進(jìn)化算法與模擬退火算法比較

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

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

文獻(xiàn)[8]的設(shè)備信息數(shù)據(jù)如表5所示，將仿真實(shí)驗(yàn)參數(shù)與文獻(xiàn)[8]中的設(shè)為一致：MVB總線基本周期為1 ms，周期相長度為0.7 ms．文獻(xiàn)[8]中由差分進(jìn)化算法得到的解向量為(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 文獻(xiàn)[8]的設(shè)備信息數(shù)據(jù)

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

(a) 改進(jìn)的差分進(jìn)化算法

(b) 差分進(jìn)化算法

圖6 改進(jìn)的差分進(jìn)化算法和差分進(jìn)化算法總線利用率

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

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

表6 改進(jìn)的差分進(jìn)化算法與差分進(jìn)化算法比較

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

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

4 結(jié) 語

本文分析了MVB周期調(diào)度表的構(gòu)建方法，并采用改進(jìn)的差分進(jìn)化算法對其進(jìn)行了優(yōu)化設(shè)計(jì)．首先提出了MVB周期調(diào)度表的模型及相應(yīng)的約束條件，接著提出了本文的優(yōu)化目標(biāo)．然后針對周期調(diào)度表的優(yōu)化這一特定問題提出了對差分進(jìn)化算法具體的改進(jìn)方法．通過與Pareto蟻群算法、模擬退火算法和原始差分進(jìn)化算法的比較可以看出，本文算法改善了周期數(shù)據(jù)負(fù)載在各基本周期中的均勻度，有效地均衡了處理周期信息的負(fù)載，同時(shí)也為非周期信息的處理預(yù)留了更多時(shí)間，對偶發(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] 郭超勇,劉建強(qiáng),鄭瓊林. 350 km/h動(dòng)車組TCN網(wǎng)絡(luò)周期輪詢優(yōu)化算法研究[J]. 鐵道學(xué)報(bào), 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ì)[J]. 鐵道學(xué)報(bào), 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é)報(bào), 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ì)[J]. 大連理工大學(xué)學(xué)報(bào), 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ì)[J]. 計(jì)算機(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] 徐進(jìn)權(quán),王宏志,胡黃水. 差分進(jìn)化MVB總線周期掃描表[J]. 長春工業(yè)大學(xué)學(xué)報(bào)(自然科學(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ù)實(shí)時(shí)性分析與帶寬分配的優(yōu)化設(shè)計(jì)[J]. 機(jī)車電傳動(dòng), 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é)基金資助項(xiàng)目(61502074,U1560102)；高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金資助項(xiàng)目(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