基于改进差分进化算法的MVB周期调度表优化设计

张 梦 璇， 于 跃,2， 顾 宏*

( 1.大连理工大学 控制科学与工程学院， 辽宁 大连 116024；2.中车大连电力牵引研发中心有限公司， 辽宁 大连 116045 )

基于改进差分进化算法的MVB周期调度表优化设计

张 梦 璇1， 于 跃1,2， 顾 宏*1

( 1.大连理工大学 控制科学与工程学院， 辽宁 大连 116024；2.中车大连电力牵引研发中心有限公司， 辽宁 大连 116045 )

多功能车辆总线(MVB)周期调度表的优化设计对提高列车通信网络实时通信的可靠性和均衡网络负荷具有重要作用．考虑到已有的多功能车辆总线周期调度表优化方案存在的不足，提出了一种基于改进的差分进化算法的优化设计方法．首先建立调度问题的数学模型，根据IEC61375-1国际标准和可调度性要求建立了优化目标和约束条件；然后根据周期调度表的生成特点对原差分进化算法的变异和选择阶段进行了改进，提出了适用于MVB周期调度的优化方法；最后通过仿真实验与现有优化算法进行比较，验证了本文所提的改进的差分进化算法对周期调度表的构建具有更佳的优化效果．

多功能车辆总线；改进的差分进化算法；周期调度表；均匀度

0 引 言

根据国际电工委员会定义的列车通信网络国际标准IEC61375-1[1]，列车通信网络实时能力的提高是列车网络控制系统实时能力的重要保证．而在列车通信网络中，周期信息传输的实时能力则依赖于周期调度表．

对于一般的现场总线，多功能车辆总线(MVB)周期调度表的构建方法主要包括最小截止期优先算法、单调速率算法、延迟释放算法[2]、均匀度优先算法[3]、逐步填空法[4]．然而随着列车通信网络的日渐复杂，需要处理的周期消息增多，上述传统算法已不能有效地构建周期调度表，智能优化算法被更多地运用于周期调度表的优化研究中．文献[5]运用多目标粒子群算法优化周期调度表；文献[6]采用Pareto蚁群算法优化周期调度表，并且得到了优于多目标粒子群算法和基本蚁群算法的结果，但是该算法的参数设定严重依赖于人的经验，因而难以使算法性能达到最优；文献[7]采用模拟退火算法进行周期表的优化调度，但是该算法收敛速度较慢，不利于实际调度过程中实时处理周期信息的需要．考虑到差分进化算法具有结构简单、收敛速度快、自适应性强的优点，有学者将差分进化算法运用到周期调度表的优化[8]，而且得到了优于逐步填空法的结果，然而未考虑到该算法缺乏局部搜索能力、难以选取变异策略的不足．

本文就如何得到满足国际标准且性能更优的周期调度表，提出改进的差分进化算法．不同于文献[8]中固定的周期信息时长，本文兼顾非周期信息的处理，动态分配周期信息与非周期信息时长[9]．通过建模将差分进化算法应用到周期调度表的优化，自适应的变异策略能够提升算法的局部搜索能力，在选择阶段结合调度表的生成特点加入容忍度旨在选出符合约束条件的更优个体．最后在已有的3组周期信息数据上分别与蚁群算法、模拟退火算法、差分进化算法进行对比，验证改进的差分进化算法对周期调度表的优化效果．

1 多功能车辆总线通信的建模

1.1 MVB信息通信原理

MVB是用于连接可编程的站及简单传感器或执行机构的车辆总线，总线上支持两种类型的数据传送: 周期性数据及偶发性数据[1]．周期性数据是按一个特征周期间隔，在总线的周期相内周期性发送的过程数据，且与设备状态的传输相关联．周期信息的实时传输能满足列车网络系统对周期信息实时通信提出的要求，如确保机车速度、司机命令及电机电压电流等周期信息在规定时间内及时刷新．周期相在每个基本周期中占有一固定的部分，在周期相中总线主按预定顺序轮询各设备以获取周期性数据，这种通信称为周期性通信[1]．偶发性数据是在MVB总线的偶发相内按需求发送的数据，总线负载的变化会影响其传输时延，在突发情况下，非周期相通过监视数据和消息数据的传输完成非周期信息通信．列车运行速度的提高及车载系统的复杂化对列车系统的通信性能提出了更高的要求．

1.2 周期信息调度表模型

在MVB总线管理器中，将由主帧排列次序构成的一个表称为周期调度表，主帧的排列次序决定了源设备发送周期数据报文的先后次序．

MVB实时调度表的规模主要由周期信息的基本周期和宏周期决定．总线活动被分为若干周期，其最短的即为基本周期Tbp，它由周期相(对过程数据)和偶发相(对消息数据和监视数据)组成[1]，1.0 ms≤Tbp≤1.5 ms．宏周期Tmacro是所有周期信息重复出现的最小间隔，其包含基本周期的数目为N=Tmacro/Tbp．同一源的相同过程数据两次连续发送的间隔称为特征周期Tip，特征周期是基本周期的2n倍[1]，即Tip=2λ-1Tbp，其中λ为其特征周期的级别，λ∈{1,2,…,10}．

假设一个MVB总线网络系统上有n个周期信息参与通信，周期数据的传输任务集为m={m1,m2,…,mn}，产生周期数据的源端口地址和该周期数据的特征周期决定了每个周期的数据报文在任务集中的序号．任务集排序的一般规则为特征周期小的周期数据，序号在前；若数据的特征周期相同，则源端口地址小的序号在前．第i个周期信息mi可描述为mi=(ti,λi,si)，i∈{1,2,…,n}．其中，ti表示周期信息报文的传输时间；λi表示周期信息的特征周期级别；si表示第i个周期信息首次出现的基本周期序号．第i个周期信息的特征周期为Tip(i)=2λi-1Tbp．

1.3 约束条件

根据国际通信标准和实际工程需求，调度优化问题中的约束条件可总结如下：

约束条件1 为了使最后生成的周期调度表唯一对应一种调度策略s=(s1,s2,…,sn)，周期信息在宏周期内首次出现的序号sj需在其特征周期内，即sj≤2λj-1．

1.4 优化目标

周期调度表合理设计需要尽可能使各个基本周期的周期变量分布均匀[5]，目的是均衡周期信息负荷，并使每个基本周期留出尽可能多的时间给偶发相来处理突发信息．最理想的情况是每一个基本周期中用来处理周期信息的时长均相等，然而在周期信息的调度过程中，每一个周期信息的特征周期不全相同，而且处理每个周期信息的时长也有差别，因而理想的情况一般不可能存在．另外，如果某些基本周期内处理周期信息的时长占比超过60%，需要扩大调度表的宏周期来满足约束条件2．然而宏周期的扩大会减小MVB总线的网络利用率和吞吐量[10]．

因此，为了均衡网络负荷，更好地处理偶发信息，尽可能提高总线利用率和吞吐量，应尽量减小周期信息在各周期相中所占时间的波动．因而周期调度表的优化问题可以表示为

(1)

si≤2λi-1

式中：优化目标为周期调度表的均匀度；s=(s1,s2,…,sn)为优化目标的输入，sj表示第j个周期信息首次出现所在的基本周期序号；tj表示处理第j个周期信息的时长；n表示周期信息的个数；Nt表示一个宏周期内的基本周期数；Tbp为一个基本周期时长；λi为第i个周期信息的特征周期级别；aij表示第j个周期信息是否在第i个基本周期中被处理．

(2)

tave表示一个宏周期内处理所有周期信息的总时间平均到每个基本周期的时间，表示如下：

(3)

由于在每个宏周期内，第i个周期信息的处理时长ti不变，特征周期λi不变，平均到每个基本周期的周期信息处理时长tave也不变．

2 优化算法

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

MVB周期调度表的优化问题可以抽象为已知每个周期信息的处理时长和特征周期，寻找周期信息主帧最优排列组合．这类问题可以归纳为排列组合的优化问题．当网络上的周期信息数较少时，满足约束条件下生成的所有周期调度表可以用穷举法手动列举出来，找出均匀度最小的组合方法对应的周期调度表．但随着高速列车车载设备的增多，信息量随之增大，可以证明MVB周期调度表的优化问题属于NP难题[4]．本文将采用适用于求解NP难题的差分进化算法[11-13]对问题进行研究．

2.2 算法的改进及实现

差分进化算法是一类基于群体的自适应全局优化算法，属于演化算法的一种．算法的基本流程有编码与初始化、差分变异操作、变量边界的约束控制、杂交操作和选择操作．该算法具有结构简单、容易使用、鲁棒性强等优点，因而易于处理调度表的优化问题；但具有缺乏局部搜索能力、参数设置敏感、变异策略选取困难等缺点，本文将结合调度表优化的具体情况改进该算法．将差分进化算法运用于周期调度表优化的具体步骤如下：

(1)编码与种群初始化

周期调度表中每个周期信息首次被处理的基本周期序号可以选择1到Tip，每个周期信息首次处理的基本周期序号构成了个体中的每一维．常规的初始化方法为

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

(4)

式中：pi表示矩阵中第i个行向量，即群体P中的第i个个体；M为群里中的个体数，N为个体的维度；rand int(M,N,[a,b])表示生成M×N矩阵且矩阵中的每个元素都是在[a,b]上均匀采样后取整得到的随机整数．

在调度表中，每一个周期信息对应的特征周期不一样，因而个体中每一维的取值范围均不同．本文参考文献[14]的编码方式，将差分进化算法成功地运用到离散的组合优化问题中．采取的方法具体如式(5)、(6)所示．首先生成随机群体P；在计算每个个体对应的调度策略时，将每个个体与以特征周期为对角线的对角矩阵相乘，最终取整得到该随机个体对应的由周期序号构成的向量，即调度策略．

P=rand(M,N)

(5)

(6)

式(5)中借用Matlab中的符号rand(M,N)表示生成M×N的均匀随机矩阵．式(6)中借用Matlab 中的符号ceil(a)表示不小于a的最小整数，Di表示第i个个体对应的调度策略，Tip(N)表示第N个周期信息的特征周期．

(2)自适应变异操作

原始差分进化算法采用的是全局策略，仿真中容易陷入局部最优，取迭代次数为5 000次，发现往往在不到2 000次时，算法陷入局部最优，不再产生更优解．差分进化算法中可以选择的策略很多，常见的策略主要分为全局策略和局部策略两大类，如式(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个个体的标号；xbest为当前群体的最优个体；xi为父个体；xr2-xr3、xr4-xr5为差分向量；Fi为第i个缩放因子，用于对差分向量的缩放，由于缩放因子F的设置很敏感，本文对F的取值参考文献[15]：F∈(-0.9,-0.4)∪(0.4,0.9) ．

全局策略具有较强的搜索能力，能在解空间内大范围尽可能地搜索更优解；局部策略的特点在于开采能力强，在较优解附近寻找优于较优解的个体．基于两类策略的特点，为保持种群的多样性，在算法迭代前期，更多地采用全局策略来产生变异向量，有助于算法找到全局的最优解．为了使算法更好地择优，在算法迭代后期，更多地采用局部策略产生变异向量，在上一次迭代产生的最优解周围尽可能寻找更优的个体．将两类变异策略结合使用的优势在于同时兼顾了算法迭代过程中的多样性和择优[16]．

本文选取全局变异策略1作为全局策略，局部变异策略3作为局部策略．考虑到Sigmoid函数的值域为(0,1)，可以将选取每种策略的概率映射到Sigmoid 函数值上．再者，Sigmoid函数前期上升平缓，在函数值为0.5时对应最大的变化率，运用在策略选择上，可以实现策略选择的转换．根据实验迭代观察，实验进展到2 000次左右时便会陷入局部最优，因而取2 000次为策略的变换点，使得算法在2 000次迭代后更倾向于选择局部变异策略．因而本文采用Sigmoid函数作为自适应函数，可以实现在迭代前期，种群在大范围内搜索更优解，保持种群的多样性；在迭代后期，采用局部策略，使得算法有针对性地在较优解附近搜索更优解，使种群更好地择优．

调度的总次数为5 000次，自适应函数为P(x)=1/(1+e(2 000-x)/200)，如图1所示．其中x代表迭代次数，P(x)代表算法选择局部策略的可能性．

图1 选择策略的自适应函数

(3)杂交操作

差分进化算法中杂交操作是将变异向量与父个体向量进行离散杂交得到尝试向量的操作．交叉系数取值越大，尝试向量每一维取变异向量对应值的可能性越大，反之越小．具体表示为

通信公司具有庞大的人力资源管理系统，在实际的管理过程中，依然存在一定的问题。其中，人力资源管理理念滞后就是存在的问题之一。管理理念滞后的原因主要在于管理方式选择不当。目前，部分通信公司还采用职能制的管理方式，这种管理方式不利于大型的人力资源管理，随着通信行业的飞速发展，显然不适用于通信公司。还有部分通信公司采用分割制管理方式，其不利于企业管理者与员工很好的沟通，进而对于公司的发展会产生限制。总之，无论是哪种管理方式，都难以促使人力资源发挥应有的作用[1]。

(12)

式中：γ表示(0,1)上均匀分布生成的随机数；Cr为交叉系数，本文中Cr的取值参考文献[17]：Cr∈(0.1,0.9)；j=1,…,N，N是每个个体的维度；jrand是自然数集{1,2,…,D}中的一个随机整数，保证尝试向量ui中至少有一维来自变异向量vi，为了避免尝试向量与父个体向量完全一样．

(4)选择操作

原始差分进化算法的选择规则：如果杂交操作产生的尝试向量ui所对应的适应值优于父个体向量对应的适应值，则取该尝试向量替代父个体向量．具体表示为

(13)

其中f(·)为适应值函数．

然而考虑到约束条件2，对于适应值相差较小的两个个体，适应值小的个体产生的周期调度表不一定更优．如图2所示对应一组周期信息{V0,V1,V2,V3,V4,V5,V6,V7,V8,V9}的两种调度方案，其中周期信息V0和V1的特征周期为Tbp，V2、V3、V4、V5的特征周期为2Tbp，V6、V7、V8、V9的特征周期为4Tbp，对应的调度表的宏周期为4Tbp．在图2中用BP(0)、BP(1)、BP(2)、BP(3)分别表示一个宏周期内第1、第2、第3和第4个基本周期．方案1的均匀度为1.73，方案2的均匀度为1.22，方案2中第一个基本周期中周期信息处理时长为整个基本周期时长的70%，无法满足约束条件2，因而尽管方案2对应的均匀度小于方案1，但是不能采纳方案2为周期调度方案．

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

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

图2 适应值不同的两方案对比

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

在选择过程中加入一个容忍度指标，其含义为尝试向量与父个体向量的适应值之差所能承受的最大值，用α表示．同时，为了避免周期调度表中少数基本周期预留给非周期信息的处理时间较短，从而导致在这些基本周期内出现的突发信息得不到及时处理的情况，取周期调度表中周期信息处理时长占基本周期比例最大值尽量小的调度策略，该比例用P表示．改进后的选择规则可表示为

(14)

最后，总结本文所提优化算法的流程图如图3所示．

图3 改进的差分进化算法流程图

本文对差分进化算法的改进体现为针对原差分进化算法易陷入局部最优的不足，采用Sigmoid 函数自适应地调整算法迭代时使用的变异策略，提升了算法的局部搜索能力；在算法中加入容忍度使最终优化调度方案中每个基本周期的利用率在60%以下，以满足列车通信网络标准所提要求．

3 仿真分析

为了验证改进差分进化算法对生成MVB周期调度表这一实际问题的有效性，分别与文献[6]中运用Pareto蚁群算法、文献[7]中运用模拟退火算法和文献[8]中运用差分进化算法生成的周期调度表的效果进行对比．在仿真中算法的参数设定为缩放因子F∈(-0.9,-0.4)∪(0.4,0.9)，杂交因子Cr∈(0.1,0.9)，种群中个体数目Np=50，迭代次数Nk=5 000，容忍度α=1．

文献[6]的设备信息数据如表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]的设备信息数据

图4为改进的差分进化算法和Pareto蚁群算法对应的调度方案的总线利用率R分布图．在总线利用率分布图中，如果每个基本周期的利用率在平均利用率附近分布，且波动越小，对应的调度效果越好．用均匀度来度量调度效果，若均匀度越小，则表明每个基本周期的周期信息处理时长越均匀，调度效果越好；反之亦然．由图4可看出图4(a)的总线利用率分布比图4(b)更均匀．表2(其中粗体部分表示最好的效果值)结果说明在改进的差分进化算法中，通过对每个基本周期内参与通信的周期信息的合理安排，可以优化周期调度表的均匀度，在均匀度得到优化的情况下，各基本周期内周期信息处理时长的波动更小，有效地平均了每个基本周期的负载，同时提高了调度的稳定性．

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

(b) Pareto蚁群算法

图4 改进的差分进化算法和Pareto蚁群算法总线利用率

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

表2 改进的差分进化算法与Pareto蚁群算法比较

文献[7]的设备信息数据如表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]的设备信息数据

图5为改进的差分进化算法与模拟退火算法对应的调度方案的总线利用率分布图，尽管图5(a) 中最大总线利用率高于图5(b)，但是两方案中总线利用率均小于42%，已经符合国际标准要求的60%以下．另外，可看出图5(a)中总线利用率的整体分布较图5(b)更均匀．表4(粗体部分表示效果最好的值)为改进的差分进化算法与模拟退火算法的效果比较，改进的差分进化算法的最终调度方案对应的均匀度更小，说明由改进的差分进化算法得到的周期调度表内每个基本周期的负载分布更均匀，调度稳定性更好．

(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]的设备信息数据如表5所示，将仿真实验参数与文献[8]中的设为一致：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]的设备信息数据

图6为改进的差分进化算法与差分进化算法对应的总线利用率分布图，由该图可看出图6(a)中总线利用率的分布较图6(b)的分布更均匀．

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

(b) 差分进化算法

图6 改进的差分进化算法和差分进化算法总线利用率

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

表6(粗体部分表示效果最好的值)为改进的差分进化算法与差分进化算法的效果对比，改进的差分进化算法对应调度策略的均匀度更小，相比于差分进化算法有助于提高列车系统中周期信息传输的稳定性．

表6 改进的差分进化算法与差分进化算法比较

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

算法均匀度最大总线利用率/%最小总线利用率/%改进的差分进化算法10.4070.0063.14差分进化算法32.9675.8660.14

4 结 语

本文分析了MVB周期调度表的构建方法，并采用改进的差分进化算法对其进行了优化设计．首先提出了MVB周期调度表的模型及相应的约束条件，接着提出了本文的优化目标．然后针对周期调度表的优化这一特定问题提出了对差分进化算法具体的改进方法．通过与Pareto蚁群算法、模拟退火算法和原始差分进化算法的比较可以看出，本文算法改善了周期数据负载在各基本周期中的均匀度，有效地均衡了处理周期信息的负载，同时也为非周期信息的处理预留了更多时间，对偶发信息的处理具有重要意义．另外，周期信息的合理调度避免宏周期通过加倍来满足调度约束条件的情况，使得网络性能指标如信息吞吐量和网络利用率尽可能高．

[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网络周期轮询优化算法研究[J]. 铁道学报, 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] 王永翔,王立德. 多功能车辆总线周期扫描表的最优化设计[J]. 铁道学报, 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] 陈佳凯,韦 巍. 基于多目标粒子群优化的多功能车辆总线周期性扫描表的优化[J]. 铁道学报, 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周期轮询表优化设计[J]. 大连理工大学学报, 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] 曾秋芬,陈特放. 多功能车辆总线周期扫描表优化设计[J]. 计算机工程与应用, 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] 徐进权,王宏志,胡黄水. 差分进化MVB总线周期扫描表[J]. 长春工业大学学报(自然科学版), 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] 朱 俊,李 芳,王丽芳. 多功能车辆总线非周期数据实时性分析与带宽分配的优化设计[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]. 电子技术应用, 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．

国家自然科学基金资助项目(61502074,U1560102)；高等学校博士学科点专项科研基金资助项目(20120041110008).

张梦璇(1991-)，女，硕士生，E-mail:1057421354@qq.com；于 跃(1977-)，男，硕士，教授级高工；顾 宏*(1961-)，男，教授，博士生导师，E-mail:guhong@dlut.edu.cn.

1000-8608(2017)02-0207-09

TP302.7；U285.4

A

10.7511/dllgxb201702015