基于Pareto蟻群算法的MVB周期輪詢表優(yōu)化設(shè)計(jì)

范 超， 于 躍,2， 顧 宏*

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

電子與信息工程、管理工程

基于Pareto蟻群算法的MVB周期輪詢表優(yōu)化設(shè)計(jì)

范 超1， 于 躍1,2， 顧 宏*1

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

合理的多功能車輛總線(MVB)周期輪詢表有助于均衡網(wǎng)絡(luò)負(fù)荷、提高網(wǎng)絡(luò)處理偶發(fā)信息的能力、保證實(shí)時(shí)通信的可靠性．為此提出一種有效的輪詢表設(shè)計(jì)方法．將MVB周期輪詢表的設(shè)計(jì)抽象成離散優(yōu)化問(wèn)題，根據(jù)IEC 61375-1國(guó)際標(biāo)準(zhǔn)和可調(diào)度性要求建立約束條件，將均勻度和相鄰基本周期時(shí)間差作為優(yōu)化目標(biāo)，利用Pareto蟻群(Pareto ant colony，P-AC)算法求解．每個(gè)優(yōu)化目標(biāo)對(duì)應(yīng)自己的信息素，信息素采用蟻群系統(tǒng)的規(guī)則更新，總信息素由兩者加權(quán)得到，非劣解基于擁擠距離方法維護(hù)．與已有的優(yōu)化算法相比，Pareto蟻群算法優(yōu)化得到的輪詢表均勻度更好，能夠更有效地均衡網(wǎng)絡(luò)負(fù)荷．

Pareto蟻群算法；多功能車輛總線(MVB)；周期輪詢表

0 引 言

多功能車輛總線(MVB)是車廂級(jí)總線，連接廂內(nèi)設(shè)備以構(gòu)成局域網(wǎng)．每個(gè)設(shè)備可以有多個(gè)端口，MVB在運(yùn)行前需要人為配置端口參數(shù)，技術(shù)人員根據(jù)參數(shù)設(shè)計(jì)周期輪詢表，運(yùn)行時(shí)主設(shè)備按照輪詢表讀取從設(shè)備信息．國(guó)內(nèi)外學(xué)者對(duì)列車周期輪詢表優(yōu)化構(gòu)建問(wèn)題做了卓有成效的研究．文獻(xiàn)[1]利用最長(zhǎng)報(bào)文填最短基本周期的思路提高表的均勻度；當(dāng)給定數(shù)據(jù)無(wú)法編排時(shí)，文獻(xiàn)[2]給出一種調(diào)整特征周期的方法；文獻(xiàn)[3-5]利用遺傳算法、多目標(biāo)粒子群優(yōu)化(multi-objective particle swarm optimization，MPSO)算法和蟻群算法(ant colony algorithm，AC)，根據(jù)各自提出的優(yōu)化指標(biāo)建立周期輪詢表．但是文獻(xiàn)[3]的多目標(biāo)粒子群優(yōu)化算法更適用于連續(xù)問(wèn)題，處理離散問(wèn)題的調(diào)度優(yōu)化需要不斷取整，存在缺陷；文獻(xiàn)[4]的蟻群算法雖然更適合離散問(wèn)題，但是優(yōu)化目標(biāo)單一，對(duì)具體的通信指標(biāo)無(wú)法兼顧．為解決已有算法的眾多缺點(diǎn)，本文通過(guò)建模將Pareto蟻群算法應(yīng)用到周期輪詢表的優(yōu)化，引入時(shí)間梯度概念，表示最長(zhǎng)周期與最短周期時(shí)間差，時(shí)間梯度與基本周期的周期相方差加權(quán)求和表示均勻度．將均勻度作為第一個(gè)優(yōu)化目標(biāo)，相鄰基本周期時(shí)間差作為第二個(gè)優(yōu)化目標(biāo)，利用Pareto蟻群算法求解．

1 MVB通信規(guī)則

MVB主設(shè)備將時(shí)間軸劃分成固定長(zhǎng)度時(shí)間片，這里的固定長(zhǎng)度就是基本周期，用Tbp表示，是最小調(diào)度粒度，這能保證實(shí)時(shí)變量確定的響應(yīng)時(shí)間．基本周期取值范圍為1.0 ms≤Tbp≤2.5 ms，本文中Tbp=1.0 ms．

特征周期指周期變量被輪詢的時(shí)間間隔，用Tip表示(i是周期信息編號(hào))，規(guī)定特征周期是基本周期的2λi倍，但不超過(guò)1 024倍，λi表示特征周期級(jí)別．

Tip=2λiTbp;λi∈{0,1,…,10}

(1)

宏周期是最大的特征周期，用Tmacro表示，即Tmacro=max {Tip}．宏周期包含基本周期，數(shù)目為M=Tmacro/Tbp．

一個(gè)基本周期包括周期相、監(jiān)視相、事件相和保護(hù)相，后三相合稱為偶發(fā)相[1]．主設(shè)備在周期相中遵照所設(shè)計(jì)的輪詢表對(duì)周期數(shù)據(jù)輪詢，監(jiān)視相中主設(shè)備進(jìn)行設(shè)備掃描和主權(quán)傳遞，事件相處理突發(fā)報(bào)文．不同的基本周期可以有不同的偶發(fā)時(shí)間，其缺省值為350 μs．

MVB采用主-從工作方式，主幀長(zhǎng)度固定為33 bit，從幀F(xiàn)碼對(duì)應(yīng)5種長(zhǎng)度：33,49,81,153,297 bit，考慮到時(shí)間延遲tms和tsm，MVB完成一次報(bào)文傳輸需要的時(shí)間為

(2)

MVB通信速率v為1.5 Mbit/s, 由式(2)可以計(jì)算每次通信的時(shí)長(zhǎng)．

2 周期輪詢表問(wèn)題描述與模型建立

2.1 任務(wù)描述

考慮對(duì)N個(gè)周期變量編排，每個(gè)周期變量可以表示為

Ci={Tip，F(xiàn)i，Li}；i∈{1，2，…，N}

(3)

式中：Tip是第i個(gè)變量的特征周期；Fi是功能碼，取值為0，1，2，3，4，依次對(duì)應(yīng)5個(gè)從幀長(zhǎng)度，通過(guò)從幀長(zhǎng)度求出完成一次報(bào)文傳輸時(shí)間tmmi；Li為周期變量首次在輪詢表中出現(xiàn)的基本周期編號(hào)，本文的目的就是確定每個(gè)設(shè)備的Li．

2.2 約束條件

(1)最大周期相約束．每個(gè)基本周期中，周期相所占時(shí)間有一定限制，需要留出一定時(shí)間完成監(jiān)視任務(wù)和處理突發(fā)消息．用k表示周期相在一個(gè)基本周期所占比例：

(4)

(2)可調(diào)度性條件．周期信息的截止期等于其特征周期，可調(diào)度性要求響應(yīng)時(shí)間不大于截止期[6]，所以端口首次在輪詢表中出現(xiàn)的時(shí)間不大于其特征周期，即

Li≤Tip

(5)

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

IEC61375-1標(biāo)準(zhǔn)要求周期信息均勻分布，一個(gè)重要指標(biāo)是基本周期周期相的標(biāo)準(zhǔn)差

(6)

(7)

定義時(shí)間梯度為輪詢表最長(zhǎng)周期相和最短周期相之差，用Tgrad表示，用ttotal(i)表示第i個(gè)基本周期內(nèi)周期相長(zhǎng)度，則有

Tgrad=max {ttotal(i)}-min {ttotal(i)}

(8)

Var、Tgrad越小效果越好，利用它們加權(quán)作為第一個(gè)優(yōu)化目標(biāo)以更全面地表達(dá)均勻度要求，用Fit1表示為

Fit1=Var+xTgrad

(9)

為提高網(wǎng)絡(luò)對(duì)偶發(fā)相處理能力，在保證均勻度的基礎(chǔ)上，擴(kuò)大相鄰基本周期的平均時(shí)間差[3]， 此度量用Tdiff表示為

(10)

當(dāng)均勻度相同時(shí)，Tdiff越大表明該編排越能將長(zhǎng)周期和短周期更好地錯(cuò)開．長(zhǎng)周期剩余時(shí)間少，短周期剩余時(shí)間多，若突發(fā)消息在長(zhǎng)周期剩余時(shí)間無(wú)法處理完，在短周期里有足夠剩余時(shí)間處理，這提高了對(duì)偶發(fā)相的處理能力，所以Tdiff越大效果越好．構(gòu)造第二個(gè)優(yōu)化目標(biāo)Fit2為

Fit2=y(Tmax-Tdiff)

(11)

其中y表征兩個(gè)優(yōu)化目標(biāo)的相對(duì)重要性，一般y<0.1．

因?yàn)楸容^Tdiff指標(biāo)的前提是均勻度相同，當(dāng)均勻度不同時(shí)不能通過(guò)簡(jiǎn)單比較Tdiff來(lái)判斷某個(gè)解的性能．由此引入相對(duì)指標(biāo)用于評(píng)價(jià)解的性能表現(xiàn)，表達(dá)式為

(12)

Relative_diff越大，認(rèn)為均勻度相同時(shí)相鄰周期的時(shí)間差異越大，說(shuō)明網(wǎng)絡(luò)處理偶發(fā)消息的能力越強(qiáng)，性能也就越好．

3 基于Pareto蟻群算法建立周期輪詢表

3.1 Pareto蟻群算法

蟻群算法利用群體合作和正反饋機(jī)制搜索解空間，不易陷入局部最優(yōu)，在離散的優(yōu)化調(diào)度問(wèn)題上尋優(yōu)效果好．蟻群系統(tǒng)(antcolonysystem，ACS)算法[7-8]相比基本蟻群算法和其他改進(jìn)算法，其全局搜索能力更強(qiáng)．本文的Pareto蟻群算法是在蟻群系統(tǒng)算法的基礎(chǔ)上添加規(guī)則提出的，能用于多目標(biāo)優(yōu)化問(wèn)題[9]．

蟻群系統(tǒng)算法先利用最近鄰思想[2]構(gòu)造初始游歷，其適應(yīng)值為f0，則信息素增強(qiáng)系數(shù)

(13)

信息素矩陣各元素初始化值為Q．螞蟻從第i個(gè)節(jié)點(diǎn)選擇第k條路徑走到第i+1個(gè)節(jié)點(diǎn)的概率為

(14)

式中：τi,i+1為信息素強(qiáng)度，ηi,i+1為啟發(fā)函數(shù)，α為信息啟發(fā)因子，β為期望啟發(fā)因子．由式(5)得第i個(gè)節(jié)點(diǎn)可選擇路徑有Tip條，則啟發(fā)函數(shù)表示為

ηi,i+1=1/Tip

(15)

求得每條備選路徑概率后，利用輪盤賭方式選擇下一條路徑．

蟻群系統(tǒng)算法的信息素更新規(guī)則包括局部更新和全局更新，如

(16)

(17)

式中：ρ1、ρ2為信息素?fù)]發(fā)系數(shù)，fb表示最優(yōu)路徑的適應(yīng)值．螞蟻每走一步，都利用局部更新規(guī)則更新信息素；當(dāng)所有螞蟻遍歷結(jié)束，對(duì)全局最優(yōu)的路徑利用全局更新規(guī)則更新信息素．

Pareto蟻群算法包含F(xiàn)it1和Fit2兩個(gè)目標(biāo)，兩個(gè)目標(biāo)對(duì)應(yīng)信息素τ1和τ2，根據(jù)上述規(guī)則獨(dú)立維護(hù)各自的信息素，路徑上總的信息素由τ1和τ2加權(quán)得到：

τ=pτ1+(1-p)τ2

(18)

其中p體現(xiàn)兩個(gè)目標(biāo)的重要程度，考慮到Fit1為主要目標(biāo)，取p>0.7．

蟻群算法與研究問(wèn)題建立如圖1所示的對(duì)應(yīng)關(guān)系[4]，圖中每個(gè)端口對(duì)應(yīng)一個(gè)節(jié)點(diǎn)，螞蟻只準(zhǔn)從起點(diǎn)依次經(jīng)過(guò)各個(gè)節(jié)點(diǎn)最后到達(dá)端口N．由式(5)得從第i-1個(gè)節(jié)點(diǎn)走到第i個(gè)節(jié)點(diǎn)可選擇路徑有Tip條，如果選擇第k條路徑則表示第i個(gè)端口在輪詢表中首次出現(xiàn)的特征周期編號(hào)為k．每只螞蟻?zhàn)咄暌槐榫蜁?huì)生成一個(gè)解向量，每個(gè)解向量對(duì)應(yīng)一個(gè)輪詢表．利用Pareto蟻群算法搜索解空間，就可以得到性能優(yōu)越的非劣解．

圖1 周期輪詢表的蟻群算法Fig.1 The ant colony algorithm of period polling table

3.2 非劣解維護(hù)

假設(shè)解A的兩個(gè)適應(yīng)值都小于解B的適應(yīng)值，稱A支配B，否則B不受A支配．不受任何解支配的解，稱之為非劣解．

多目標(biāo)優(yōu)化問(wèn)題一般沒(méi)有絕對(duì)的最優(yōu)解，本文的目標(biāo)是找出非劣解的集合形成Pareto沿．假設(shè)解集的容納量為Num_nd，當(dāng)?shù)玫降姆橇咏鈹?shù)目過(guò)多，需要根據(jù)規(guī)則剔除一部分．非劣解集基于擁擠距離[10]來(lái)維護(hù)，擁擠距離表征該解周圍其他解分布的密集程度，點(diǎn)的擁擠距離越小，說(shuō)明該點(diǎn)周圍的解分布越密集，該解被剔除的概率越大．擁擠距離的計(jì)算如下：

針對(duì)每一個(gè)優(yōu)化目標(biāo)m

根據(jù)適應(yīng)值升序排序，S=sort(S,m)

fori=2 to (Num_nd-1)S[i].distance=S[i].distance+(S[i+1].m-S[i-1].m)

對(duì)于邊界點(diǎn)，S[1].distance=S[Num_nd].distance=maximumdistance

獲得Pareto沿后，根據(jù)下列式子計(jì)算沿上每一個(gè)點(diǎn)的評(píng)價(jià)指數(shù)ψ：

ψ=0.75Fit1+0.25Fit2

(19)

其中ψ包含了各個(gè)指標(biāo)的信息，將其升序排列，從前3個(gè)點(diǎn)中隨機(jī)選擇一個(gè)，該點(diǎn)對(duì)應(yīng)的向量L即為最終解，最后以此為依據(jù)建立周期輪詢表．

綜上所述，利用Pareto蟻群算法優(yōu)化MVB周期輪詢表的流程如圖2所示．

圖2 Pareto蟻群算法流程圖Fig.2 Flow chart of the P-AC algorithm

4 方法比較與結(jié)果分析

基于文獻(xiàn)[3]和[4]的實(shí)驗(yàn)數(shù)據(jù)，將本文算法與已經(jīng)提出的蟻群算法和多目標(biāo)粒子群優(yōu)化算法進(jìn)行比較．Pareto蟻群算法的參數(shù)設(shè)定：α=1，β=2，ρ1=0.05，ρ2=0.10，螞蟻數(shù)目為10，信息素增強(qiáng)系數(shù)由式(13)求得，非劣解集容納量為24，程序迭代200次．

文獻(xiàn)[3]的設(shè)備信息數(shù)據(jù)如表1所示，式(4)中k=75%，利用文獻(xiàn)[3]的多目標(biāo)粒子群優(yōu)化算法得到的解向量為(2 2 1 2 2 4 3 1 6 3 6 1 5 16 3 3 4 16 13 1 9 11 7 23)．利用本文的Pareto蟻群算法仿真生成的非劣解如圖3所示．根據(jù)式(19)計(jì)算排序，最終選取的解向量為(2 1 2 2 4 4 3 1 7 7 6 2 1 7 14 11 2 10 11 3 13 5 1 15)．兩種算法的評(píng)價(jià)參數(shù)見表2．

表1 文獻(xiàn)[3]的設(shè)備信息表Tab.1 Device information list of Lit. [3]

圖3 Pareto蟻群算法基于表1產(chǎn)生的非劣解Fig.3 Non-dominated solutions created by P-AC algorithm based on Tab. 1

表2 標(biāo)準(zhǔn)解性能指標(biāo)Tab.2 Performance indicators of the standard solutions

由表2可得，Pareto蟻群算法得到解的標(biāo)準(zhǔn)差是67.79，遠(yuǎn)小于多目標(biāo)粒子群優(yōu)化算法的115.75；其Tgrad指標(biāo)是236.00，同樣遠(yuǎn)小于多目標(biāo)粒子群優(yōu)化算法的376.00，說(shuō)明本文算法能保證各基本周期波動(dòng)小，在均勻度上的表現(xiàn)更好．Pareto蟻群算法的Relative_diff為1.48，而多目標(biāo)粒子群優(yōu)化算法的僅為1.42，說(shuō)明Pareto蟻群算法得到的解能更好地將長(zhǎng)短周期錯(cuò)開，提高網(wǎng)絡(luò)處理偶發(fā)消息的能力．因?yàn)镻areto蟻群算法較多目標(biāo)粒子群優(yōu)化算法更適合處理離散優(yōu)化問(wèn)題，所以它的結(jié)果表現(xiàn)更優(yōu)秀．

圖4是兩種算法解的周期相利用率分布．Pareto 蟻群輪詢表最大利用率為97%，較小的也在70%以上，分布集中；而多目標(biāo)粒子群優(yōu)化算法對(duì)應(yīng)表最大利用率為100%，還有多個(gè)周期低于65%，分布零散．對(duì)比發(fā)現(xiàn)，Pareto蟻群算法構(gòu)建的周期輪詢表中各周期相波動(dòng)較小，均勻度更好，利用率更接近平均值，這樣的周期輪詢表能夠更好地均衡網(wǎng)絡(luò)負(fù)荷，預(yù)防局部通信壓力過(guò)大．

(a) 多目標(biāo)粒子群優(yōu)化算法周期相時(shí)間散點(diǎn)圖

(b) Pareto蟻群算法周期相時(shí)間散點(diǎn)圖

圖4 Pareto蟻群算法與多目標(biāo)粒子群優(yōu)化算法的周期相利用率比較

Fig.4 Comparison of cycle phase utilization between P-AC and MPSO algorithms

文獻(xiàn)[4]的設(shè)備信息數(shù)據(jù)如表3所示，式(4)中k=65%，利用文獻(xiàn)[4]的蟻群算法得到的向量為(1 1 1 3 3 2 4 4 3 6 7 5 5 4 6 1 8 10 2 10)．利用Pareto蟻群算法仿真生成的Pareto沿如圖5所示．根據(jù)式(19)計(jì)算排序，最終選取的解向量為(1 1 2 1 4 2 3 4 2 4 7 1 7 5 3 6 4 8 5 18)．表4列出對(duì)應(yīng)參數(shù)指標(biāo)．

表3 文獻(xiàn)[4]的設(shè)備信息表Tab.3 Device information list of Lit. [4]

圖5 Pareto蟻群算法基于表3產(chǎn)生的非劣解

Fig.5 Non-dominated solutions created by P-AC algorithm based on Tab.3

表4 兩個(gè)解的性能指標(biāo)Tab.4 Performance indicators of the two solutions

由表4可得，Pareto蟻群算法對(duì)應(yīng)的標(biāo)準(zhǔn)差和Tgrad分別為57.89和265.00，明顯小于基本蟻群算法的，充分證明Pareto蟻群算法能更好地保證輪詢表的均勻度；Pareto蟻群算法的Relative_diff為1.22，大于基本蟻群算法的0.97，證明其能夠更有效地錯(cuò)開長(zhǎng)短周期，均衡網(wǎng)絡(luò)負(fù)荷．

圖6是兩種算法解的周期相利用率分布．Pareto 蟻群算法對(duì)應(yīng)輪詢表的利用率只有一個(gè)超過(guò)85%，利用率在70%以下的僅有5個(gè)周期；基本蟻群算法輪詢表的利用率跨度很大，最大已經(jīng)達(dá)到100%，利用率在70%以下的很多，對(duì)比可知Pareto蟻群算法均衡網(wǎng)絡(luò)負(fù)荷能力更強(qiáng)．

(a) 基本蟻群算法周期相時(shí)間散點(diǎn)圖

(b) Pareto蟻群算法周期相時(shí)間散點(diǎn)圖

圖6 Pareto蟻群算法與基本蟻群算法的周期相利用率比較

Fig.6 Comparison of cycle phase utilization between P-AC and AC algorithms

5 結(jié) 語(yǔ)

在IEC 61375-1標(biāo)準(zhǔn)的基礎(chǔ)上，構(gòu)造出兩個(gè)優(yōu)化目標(biāo)，這樣既能優(yōu)化均勻度，又能夠保證將長(zhǎng)短周期錯(cuò)開，全面提高輪詢表質(zhì)量．在此基礎(chǔ)上建立模型并利用Pareto蟻群算法求解．比較證明，本文算法得到的解的性能比基本蟻群算法和多目標(biāo)粒子群優(yōu)化算法得到的解的性能更好，證明了利用本文算法構(gòu)建MVB周期輪詢表，更有助于MVB均衡網(wǎng)絡(luò)負(fù)荷，提高網(wǎng)絡(luò)處理偶發(fā)信息的能力，保證實(shí)時(shí)通信．

[1] 李 銳,李永宗,費(fèi)巧玲,等. 一種多功能車輛總線周期掃描表優(yōu)化設(shè)計(jì)方案[J]. 機(jī)車電傳動(dòng), 2013(4):92-94.

LI Rui, LI Yong-zong, FEI Qiao-ling,etal. An optimization solution of the MVB periodic polling table [J]. Electric Drive for Locomotives, 2013(4):92-94. (in Chinese)

[2]蔣 瑾,王長(zhǎng)林. 多功能車輛總線MVB周期掃描表配置分析[J]. 鐵道機(jī)車車輛, 2011, 31(3):34-36.

JIANG Jin, WANG Chang-lin. Analysis on periodic polling table configuration of multifunction vehicle bus MVB [J]. Railway Locomotive & Car, 2011, 31(3):34-36. (in Chinese)

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

CHEN Jia-kai, 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)

[4]朱 俊,李 芳,王麗芳. 基于蟻群算法的多功能車輛周期掃描表的優(yōu)化設(shè)計(jì)[J]. 鐵道學(xué)報(bào), 2013, 35(7):57-62.

ZHU Jun, LI Fang, WANG Li-fang. Optimized design method of periodic list in multifunction vehicle bus based on the ant colony algorithm [J]. Journal of the China Railway Society, 2013, 35(7):57-62. (in Chinese)

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

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

[6]朱琴躍,謝維達(dá),譚喜堂,等. MVB周期信息的實(shí)時(shí)調(diào)度[J]. 計(jì)算機(jī)應(yīng)用, 2007, 27(12):3108-3111.

ZHU Qin-yue, XIE Wei-da, TAN Xi-tang,etal. Real-time scheduling of periodic messages for MVB [J]. Computer Applications, 2007, 27(12):3108-3111. (in Chinese)

[7]Dorigo M, Gambardella L M. Ant colony system:a cooperative learning approach to the traveling salesman problem [J]. IEEE Transactions on Evolutionary Computation, 1997, 1(1):53-66.

[8]李士勇,陳永強(qiáng),李 研. 蟻群算法及其應(yīng)用[M]. 哈爾濱:哈爾濱工業(yè)大學(xué)出版社, 2004:29-40.

LI Shi-yong, CHEN Yong-qiang, LI Yan. Ant Colony Algorithms with Applications [M]. Harbin:Harbin Institute of Technology Press, 2004:29-40. (in Chinese)

[9]Doerner K F, Gutjahr W J, Hartl R F,etal. Pareto ant colony optimization with ILP preprocessing in multiobjective project portfolio selection [J]. European Journal of Operational Research, 2006, 171(3):830-841.

[10]Raquel C R, Naval P C Jr. An effective use of crowding distance in multiobjective particle swarm optimization [C] // GECCO 2005 - Genetic and Evolutionary Computation Conference. New York:Association for Computing Machinery, 2005:257-264.

Optimization design of MVB period polling table based on Pareto ant colony algorithm

FAN Chao1, YU Yue1,2, GU Hong*1

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

Good multifunction vehicle bus (MVB) period polling table contributes to balancing the network load and improving the ability of network processing sporadic messages, which can ensure the reliability of the real time communication. An effective polling table design method is proposed. The design of the MVB period polling table is abstracted into a discrete optimization problem. Constraints are obtained according to the IEC 61375-1 international standard and request of schedulability. The optimal objective consists of uniformity and adjacent basic period time interval. The solution is achieved by Pareto ant colony algorithm. In this algorithm, every objective has updated its own pheromone independently by rule of the ant colony system algorithm and the total pheromone is calculated by weighted summation of the two pheromones. The non-dominated solutions sets are maintained by the crowding distance method in this multi-objective problem. The experimental results show that the Pareto ant colony algorithm can perform better than the existing algorithms in uniformity and balancing the network load.

Pareto ant colony algorithm; multifunction vehicle bus (MVB); period polling table

1000-8608(2015)03-0319-07

2014-09-09；

2014-11-08.

國(guó)家自然科學(xué)基金資助項(xiàng)目(61305034)；高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金資助項(xiàng)目(20120041110008).

范 超(1989-)，男，碩士生，E-mail:zidonghuafc@126.com；顧 宏*(1961-)，男，教授，博士生導(dǎo)師，E-mail:guhong@dlut.edu.cn.

U269.9

A

10.7511/dllgxb201503014