文章快速检索     高级检索
  浙江大学学报(工学版)  2018, Vol. 52 Issue (9): 1658-1666  DOI:10.3785/j.issn.1008-973X.2018.09.005
0

引用本文 [复制中英文]

张曼, 施树明. 面向汽车运行工况设计的马氏链非等长交叉进化算法[J]. 浙江大学学报(工学版), 2018, 52(9): 1658-1666.
dx.doi.org/10.3785/j.issn.1008-973X.2018.09.005
[复制中文]
ZHANG Man, SHI Shu-ming. Non-isometric crossover evolution algorithm of Markov chain for designing vehicle driving cycles[J]. Journal of Zhejiang University(Engineering Science), 2018, 52(9): 1658-1666.
dx.doi.org/10.3785/j.issn.1008-973X.2018.09.005
[复制英文]

基金项目

国家自然科学基金资助项目(51475199)

作者简介

张曼(1990—),女,博士生,从事汽车运行工况设计、车辆运行仿真研究.
orcid.org/0000-0001-8648-9895.
E-mail: m15104682686@163.com.

通信联系人

施树明,男,教授.
orcid.org/0000-0001-7018-0682.
E-mail: shishuming@jlu.edu.cn
.

文章历史

收稿日期:2017-05-13
面向汽车运行工况设计的马氏链非等长交叉进化算法
张曼, 施树明     
吉林大学 交通学院,吉林 长春 130022
摘要: 为解决马尔科夫链和传统遗传算法设计汽车运行工况时效率低、质量差的问题,提出用于设计汽车运行工况的马氏链非等长交叉进化方法. 设计子代满足马尔科夫链转移关系的非等长交叉算子, 解除等位等长交叉段的限制,使遗传算法更好地适用于汽车运行工况的设计. 根据试验数据,应用马氏链非等长交叉进化方法构建非等长初始种群,使用满意准则模型和指数加权平均数设定目标函数,设计三参数汽车运行工况. 随机生成3种不同长度的三参数高速公路代表性工况. 分析结果表明,期望运行工况与原始数据库特征参数的相对偏差均在设定范围内,速度和加速联合分布相关系数均高于90%,生成工况具有代表性. 相比于马尔科夫链和传统遗传算法相结合的设计方法,马氏链非等长交叉进化方法的平均运行工况生成效率提高了66%,运行工况质量更优.
关键词: 汽车运行工况    马尔科夫链    非等长交叉    遗传算法    进化    
Non-isometric crossover evolution algorithm of Markov chain for designing vehicle driving cycles
ZHANG Man , SHI Shu-ming     
College of Transportation, Jilin University, Changchun 130022, China
Abstract: A non-isometric crossover evolution algorithm for designing vehicle driving cycles with Markov property was proposed, in order to solve the low efficiency and poor quality caused by the Markov Chain and typical genetic algorithm when designing vehicle driving cycles. Individuals were designed to satisfy the Markov property by exchanging with non-isometric cross segments; a new crossover was designed based on the genetic algorithm, which broke the restriction of allelic crossover segments and was applicable for designing driving cycles. According to a collected highway database, the method was used to design three-parameter highway driving cycles, which included constructing non-isometric initial populations and designing an objective function by using the satisfaction rule model and exponential weighted average. Three kinds of three-parameter representative driving cycles with different lengths were generated. Results show that the relative deviations of indices between the desired cycles and the original database are within a reasonable range and correlation coefficients of velocity and acceleration joint probability distribution are above 90%, which indicates the representativeness of the generated driving cycles. Compared with the results of the method which combines Markov Chain with typical genetic algorithm, the average design efficiency of the new method increases by 66%, and the design quality of driving cycles is better.
Key words: vehicle driving cycles    Markov chain    non-isometric crossover    genetic algorithm    evolution    

设计具有代表性的汽车运行工况是汽车技术领域的重要内容. 节能减排是当前热点,汽车运行工况在节能减排仿真试验和性能认证,以及混合动力汽车能量源的设计优化等方面有重要作用[1-3].

基于马尔科夫链设计汽车运行工况的方法备受青睐. 该方法依据汽车运行工况的马尔科夫性,运用马尔科夫链随机模拟生成运行工况序列. Lin[4]把运行工况的速度时间序列定义为随机过程,把速度微行程定义为状态,利用马尔科夫链的理论设计汽车运行工况. Patil等[5]为研究实际行驶交通环境对串联插电式混合动力电动汽车设计的影响,以速度片段作为状态,使用马尔科夫链生成合成运行工况,结果发现,实际环境下的运行工况与美国城市道路循环(urban dynamometer driving schedule,UDDS)工况相比,需要更高的动能和电能,插电式混合动力汽车需配备更大的电池和发动机. Gong等[6]采集混合动力汽车车队的运行工况数据,以速度和加速度的时间序列作为状态,构造马尔科夫链模型,生成运行工况用于混合动力汽车的仿真和分析. Souffran等[7]为评估混合动力汽车能量源的额定功率以及优化传动系,建立速度、加速度和坡度三参数的马尔科夫链模型. Shi等[8]从车辆动力学和车辆跟驰模型等角度证明汽车运行工况具有马尔科夫性. 其他学者利用马尔科夫性对运行工况进行了拓展性研究. Silvas等[9]以构建重型车运行工况为目标,拓展现存的研究方法,提出基于多维度马尔科夫链的方法,并生成含道路坡度的运行工况以证明所提出方法的精确性. 尽管马尔科夫模型在汽车运行工况设计中已较成熟[10-11],生成期望运行工况的能力仍然有限.

利用马尔科夫链模型设计运行工况的本质是随机模拟采样,设计效率比较低.在采样过程中加入进化元素可以提高随机采样效率,广泛使用的遗传算法具有较强的进化能力[12-15]. 遗传算法优化求解实际问题的进化效果得到公认但是直接使用传统遗传算法和马尔科夫链相结合的方法设计汽车运行工况的效果不理想. 这是因为在遗传算法中起关键作用的交叉算子是等位等长交叉,不符合运行工况的马尔科夫性,导致交叉效率过低、生成效果不佳.

为此,本文提出面向汽车运行工况设计的马氏链非等长交叉进化方法. 将其应用于实际运行工况设计,检验新方法是否可以生成任意时间长度的代表性工况,并验证新方法的正确性.

1 数据来源与原始数据的状态转移矩阵统计

数据为一款牵引车在高速公路上的运行数据. 试验路线如图1所示。路线起点为天津市双街镇,途径晋州市周家庄乡和广州市白云区,行驶至佛山市陈村镇,最后由佛山市陈村镇返回天津市双街镇. 历时3d,共行驶3 765 km. 使用设备为DEWE-50,同步获取DEWE-VGPS信号、CAN总线信号以及加速传感器信号. 数据采集频率为10 Hz,采集参数包括速度、加速度和高程等. 对数据进行去噪和滤波处理,利用Yue等[16]提出的坡度计算方法获取坡度信息,最终获得该款牵引车在高速公路上行驶3 355 km 的有效数据.

图 1 采集数据的试验路线 Fig. 1 Experiment routes to collect highway driving data

如果对任意正整数n和状态空间I中的i, j, i0, i1···, in–1,随机序列 $\{X_n\}$ 满足

$\begin{split}\!\!P&\left({{X_{n + 1}} = j|{X_n} = i,\;{X_{n - 1}} = {i_{n - 1}},\, \cdot \cdot \cdot ,\,{X_0} = {i_0}} \right) = \\&P\left({{X_{n + 1}} = j|{X_n} = i} \right) =P\left({{X_{n + 1}} = j|{X_0} = i} \right);\;i,\,j \in I. \end{split} $ (1)

式中: ${X_0}$ 为初始时刻的状态, ${X_n}$ 为第 $n$ 时刻的状态, $\{X_n\}$ 为时间齐次马尔科夫链.

马尔科夫链的转移概率为

${{P_{ij}}}=p\left({{X_1} = j|{X_0} = i} \right);\quad i,j \in I.$ (2)

马尔科夫链的一步转移概率矩阵,即状态转移矩阵[17]

${{P}} = {\left({{p_{ij}}} \right)_{i,\,j \in I}}\,.$ (3)

在短时间尺度(1 s)内,汽车运行工况具有马尔科夫性[8],引用Yue等[16]提出的构造方法统计汽车高速公路行驶工况数据库的三参数(速度、加速度和坡度)状态转移矩阵. 转移概率计算方法基于Lin[4]和Grimshaw等[18]提出的最大似然估计方法:

${{P}} = \left[ {\begin{array}{*{20}{c}} {{p_{11}}}&{{p_{12}}}& \cdots &{{p_{1m}}} \!\!\!\!\!\\ {{p_{21}}}&{{p_{22}}}& \cdots &{{p_{2m}}} \!\!\!\!\!\\ \vdots & \vdots & & \vdots &{} \!\!\!\!\!\\ {{p_{m1}}}&{{p_{m2}}}& \cdots &{{p_{mm}}} \!\!\!\!\!\end{array}} \right].$ (4)

式中: ${p_{ij}} = {N_{ij}}/{N_i}$ ${p_{ ij}}$ 为一维空间状态 ${s_i}$ 到一维空间状态 ${s_j}$ 的转移概率,Nij为状态si转移到状态sj的频数,Ni为状态si转移到其他状态的频数之和,S为空间状态集合, $m$ 为一维空间状态个数.

马尔科夫链要求状态具有离散性. 划分试验数据三参数状态时,首先根据原始数据确定速度、加速度和坡度三参数的范围和步长. 速度范围为0~ ${v_{\max }}$ ;加速度范围为 ${a_{\min }}$ ~ ${a_{\max }}$ ;坡度范围为 ${g_{\min }}$ ~ ${g_{\max }}$ . 考虑到步长过小时状态数会急剧增大,设定速度步长 $\Delta v$ 为0.5 m/s,加速度步长 $\Delta a$ 为0.1 m/s2,坡度步长 $\Delta g$ 为1%. 设定怠速范围对应速度区间为0~0.1 m/s,加速度区间为–0.02~0.02 m/s2,坡度区间为–0.2%~0.2%. 最后设定状态的编码,使用区间码表示参数某个区间内的值, $t$ 时刻的速度 ${v_t}$ 的区间码 ${m_t}$

$\!\!\!\!\!\!\!\!{m_t} = \left\lfloor {{v_t}/\Delta v } \right\rfloor + 1 .$ (5)

加速度 ${A_t}$ 区间码 ${n_t}$

${n_t} = \left\lfloor {\frac{{{a_t} - {a_{\min }}}}{{\Delta a}}} \right\rfloor + 1 .$ (6)

坡度 ${G_t}$ 的区间码 ${p_t}$

${p_t} = \left\lfloor { {{\frac{{{g_t} - {g_{\min }}}}{{\Delta g}}}} } \right\rfloor + 1 .$ (7)

由当前 $t$ 时刻的 ${m_t}$ ${n_t}$ ${p_t}$ 计算当前时刻的状态编码 :

${s_t} = {m_t} + \left({{n_t} - 1} \right) M + \left({{p_t} - 1} \right) M N.$ (8)

式中: $M$ 为速度区间码个数, $M = {\mathop{\rm }\nolimits} \left\lfloor{{v_{\max }}/\Delta v} \right\rfloor + 1$ $N$ 为加速度区间码个数, $N = {\mathop{\rm }\nolimits} \left\lfloor{\left({{a_{\max }} - {a_{\min }}} \right)/\Delta a} \right\rfloor + $ 1,最终共得到4 644个状态.

根据式(4)得到三参数运行工况的状态转移概率矩阵(transition probability matrix, TPM). 三维状态转移矩阵的二维投影如图2所示,si为当前状态,si+1为下一时刻状态. 实圆圈大小表示当前状态 ${s_i}$ 转移到下一时刻状态 ${s_{i{\rm{ + }}1}}$ 的概率. 汽车运行工况的马尔科夫特性决定状态转移矩阵具有极强的规律性.

图 2 三参数的状态转移概率矩阵的投影图 Fig. 2 Projection of three-parameter state transition probability matrix
2 马尔科夫链与传统遗传算法结合的设计方法分析

使用马尔科夫链和传统遗传算法相结合的方法生成三参数的高速公路代表性运行工况. 结合运行工况构建初始种群和设计目标函数,利用Matlab中自带的遗传算法工具箱进化出具有代表性的运行工况.

利用运行工况马尔科夫链模型的随机模拟方法[19-20],生成长度为1 800 s首尾为怠速的状态序列。通过整数编码方式,将工况状态编码为基因,将状态序列编码为染色体。马尔科夫链模型随机模拟得到多条工况状态序列,可以组成任意大小的初始种群.

目标函数是期望运行工况的反映. 文献[8-9]通过评价指标衡量生成工况是否具有代表性. 目标函数利用11个特征参数评价生成工况与原始数据库的一致性,包括怠速时间比例(Pi)、加速时间比例(Pa)、匀速时间比例(Pc)、减速时间比例(Pd)、平均速度(vm)、平均行驶速度(vdm)、行驶速度标准差(vsd)、单位距离上的正加速动能(PKE)、平均爬坡度(gam)、平均下坡度(gdm)、速度和加速度的概率分布相关系数(Cva). 其中PKE的计算公式[21-22]

${\rm{PKE}} = \sum {\frac{{v_{\rm f}^2 - v_{\rm i}^2}}{D}} ,\,\,\,\,{\rm{ }}\frac{{{\rm{d}}v}}{{{\rm{d}}t}} > 0.$ (9)

式中: ${v_{\rm f}}$ ${v_{\rm i}}$ 分别为单个加速过程中终止和起始速度,D为总行驶里程.

为解决多目标优化问题,采用Shi等[23]提出的满意准则模型(satisfaction rule model, SRM). 模型将以上11个参数合并成为一个工况设计评价指标,并将其作为遗传算法的目标函数.

${{f}}({{X}})\leqslant \overline {{f}},\,{{g}}({{X}})\leqslant {\bf 0}.$ (10)

式中:X $ \in $ RnX为期望运行工况n维设计变量向量,g (X)为 $p$ 维约束函数向量,f (X)为 $m$ 维目标函数向量, $\overline {{f}}$ $m$ 维目标函数满意值向量.

构造辅助函数:

${{T_i}\left({{X}} \right) = {f_i}\left({{X}} \right) + \overline {{{f}}_i} - \min\, \left({{f_i}\left({{X}} \right),\overline {{{{f}}_i}} } \right).}$ (11)

满意解的求解问题为

$\begin{array}{*{20}{c}} {\min \,{T}_i{\left({ X} \right)}} ;\,{{ X} \in {S}} .\end{array}$ (12)

设计期望运行工况的目标函数. 设 ${{{I}}_{\rm o}}$ 为原始数据库的特征参数, ${{{I}}_{\rm e}}$ 为期望工况的特征参数, $d$ 为允许偏差,特征参数的允许偏差绝对值应当满足:

$\left| {I{}_{{\rm o}i} - {I_{{\rm e}i}}\left({{X}} \right)} \right| \leqslant {d_i};\,\,\,{i = 1,2, \cdots ,m} ,\,\, m = 11.$ (13)

为了引入满意准则模型,令 $f_{i}\left({{X}} \right) = \left| {1 - \displaystyle\frac{{{I_{{\rm e}i}}\left({{X}} \right)}}{{{I_{{\rm o}i}}}}} \right|$ ,表示期望运行工况与原始数据库的相对偏差绝对值,令 ${ {\overline f}_i}\left({{X}} \right) = {{{d_i}}} / {{{I_{{\rm o}i}}}}$ ,表示相对允许偏差绝对值,将式(13)转化为

$\left| {1 - \frac{{{I_{{\rm e}i}}\left({{X}} \right)}}{{{I_{{\rm o}i}}}}} \right| \leqslant \frac{{{d_i}}}{{{I_{{\rm o}i}}}}.$ (14)

构造辅助函数式(11),根据式(12)求解满意解.

当多目标问题转化为单目标问题时,比如当式(11)转化为式(12)时,权重应该自适应变化而不是采用相同权重. 权重设计原则为偏差大的权重大,偏差小的权重小. 利用指数加权平均数[24]

$\sum\nolimits_{j = 1}^\infty {\lambda {{\left({1 - \lambda } \right)}^j}} = 1 ,$ (15)

归一化指标加权平均数,可以得出指标权重为

${\omega _j} = \frac{{\lambda {{\left({1 - \lambda } \right)}^j}}}{{\displaystyle\sum\nolimits_{ j = 1}^m {\lambda {{\left({1 - \lambda } \right)}^j}} }};\,\,\, j = 1,2, \cdots ,m.$ (16)

根据原则,计算最终目标函数:

$\!F = \left\{ \begin{array}{l}\!\!\!\!\!\!\!\! \begin{array}{*{20}{c}}{\min }\\{{ X} \in S} \!\!\!\!\end{array}\left( {\displaystyle\sum\limits_{j = 1}^m \;{{\omega _j}{T_j}\left( {{X}} \right)} } \right),\exists {T_i}\left( {{X}} \right) \ne {T_k}\left( {{X}} \right), \\ \quad\quad\quad\quad\quad\quad\quad\quad\quad\quad i \ne k\;{\text {且}}\;i,k \in [1,m];\\\!\!\!\!\!\!\!\! \begin{array}{*{20}{c}}{\min }\\{{ X} \in S} \!\!\!\!\end{array}\left( {\displaystyle\frac{1}{m}\displaystyle\sum\limits_{j = 1}^m \;{{T_j}\left( {{X}} \right)} } \right),\forall {T_i}\left( {{X}} \right) = \overline {{f_i}} , \,\, i \in [1,m].\end{array} \right.$ (17)

式中: ${T_j}\left({{X}} \right)$ 为辅助函数, $\omega $ 为指数权重, ${ X}$ 为运行工况状态. $m$ =11. 当设定各个指标的相对允许偏差绝对值即 $\overline {{f_i}} $ 均为0.1时,由目标函数得出最小输出值为0.1.

为保证运行工况状态符合马尔科夫性,利用统计得到的状态转移概率矩阵TPM构造运行工况状态转移关系的非线性不等式约束.

${p_{\min }} - \operatorname{TPM} \left({{X_i},{X_{i + 1}}} \right) \leqslant 0, \,\, i = 1,2, \cdots ,n - 1.$ (18)

式中: ${p_{\min }}$ $\operatorname{TPM} $ 中非零转移概率的最小值, $\operatorname{TPM} \left({X{}_i,{X_{i + 1}}} \right)$ 为运行工况序列中第i位置状态 ${X}_i$ 转移到第i+1位置状态 ${X_{i + 1}}$ 的概率,n为运行工况状态序列长度.

迭代次数G设置为200次,带有非线性约束的传统遗传算法工具箱分别经过3.60、3.57和3.29 h的3次长时间的进化,结果如图3~5所示. 如 图3所示最佳适应值fval不仅没有达到0.1,并且在生成工况中某些状态不满足马尔科夫性. 如图4所示为某次结果的速度状态sv,序列中异常转移状态的特征明显,表现为针状. 3次输出工况的指标偏差如图5所示,个别指标偏差不符合允许偏差,尤其是Cva为15%~20%,无法达到应用要求. 使用马尔科夫链和传统的传统遗传算法相结合的方法生成的工况不理想.

图 3 不同进化时长下传统遗传算法的最佳适应值随迭代次数的变化曲线 Fig. 3 Curves of the best fitness value with iterations of traditional genetic algorithm under different evolutionary time lengths
图 4 使用马尔科夫链与传统遗传算法结合方法的工况设计结果中的速度状态序列 Fig. 4 Velocity state series from one designed driving cycle result using combined method of method of Markov chain and traditional genetic algorithm
图 5 不同进化时长下传统遗传算法设计工况的指标偏差 Fig. 5 Histogram of index deviations of driving cycles designed by traditional genetic algorithm under different evolutionary time

图4所示,出现异常针状特征的根本原因是传统遗传算法,而非马氏链模拟或其他因素。首先,初始种群中工况的状态序列由马尔科夫链蒙特卡洛随机模拟生成,马尔科夫蒙特卡洛模拟方法能够从原理上保证随机生成的工况数据点满足马尔科夫状态转移关系,种群符合工况的马尔科夫性,即状态转移关系;其次,目标函数用于判断个体是否具有代表性,即判断工况序列的各项指标是否符合设定的指标允许偏差,不影响个体状态服从马尔科夫性;最后,遗传算法中改变影响个体状态转移关系的是交叉和变异算子. 遗传算法能够使用非线性不等式约束使状态序列满足马尔科夫性,但遗传算法的交叉算子通过交换随机选择的2个等位基因之间的交叉段生成子代,由于等位等交叉段的交换过于严格,随机选择的交叉点不一定满足状态转移关系. 变异算子通过随机选择某个基因位进行基因变异的方式,实现变异。序列的变异点也不一定能够满足状态转移关系。因此需要对传统遗传算法的交叉和变异算法进行修正,提出新的进化算法.

3 设计汽车运行工况的马氏链非等长交叉进化方法

为了生成原始数据库的三参数代表性运行工况,使用马氏链的非等长交叉进化算法设计汽车运行工况,结构框架如图6所示. 在遗传算法基础上,根据图2的状态转移概率矩阵,利用马尔科夫链随机模拟构建任意长度个体的初始种群;利用满意准则模型和指数加权平均数设定目标函数;设计满足马尔科夫性的非等长交叉算子和变异算子,利用新的进化方法生成工况.

图 6 面向汽车运行工况设计的马氏链非等长交叉进化算法结构框架图 Fig. 6 Structure of non-isometric crossover evolution method for designing vehicle driving cycles with Markov property
3.1 非等长初始种群

通过整数编码的方式,对汽车运行工况马尔科夫链的状态变量进行编码,借助三参数状态转移概率矩阵,应用马尔科夫链随机模拟方法生成任意长度并且起止为怠速状态的状态序列,将序列编码为染色体. 经过多次随机模拟,非等长个体可以构成任意大小的初始种群.

3.2 满足马尔科夫性的非等长交叉算子

根据如图6所示的结构框架,研究非等长交叉段的交叉算子,使交叉算子的个体在进化过程中满足马尔科夫性. 马氏链非等长交叉算子的交叉原理如图7所示。在运行工况设计中,n维设计变量的向量X的含义为一条运行工况的状态序列,状态在遗传算法中的含义为基因。据此, ${{{X}}^{\left(1 \right)}}$ ${{{X}}^{\left(2 \right)}}$ 表示父代的运行工况状态序列, ${{X}}_{\rm{c}}^{\left({\rm{1}} \right)}$ ${{X}}_{\rm{c}}^{\left(2 \right)}$ 表示交叉后生成子代的工况序列, $X_i^{\left(1 \right)}$ $X_{i{\rm{ + }}1}^{\left(1 \right)}$ $X_{i'}^{\left(1 \right)}$ $X_{i'{\rm{ + }}1}^{\left(1 \right)}$ 分别表示 ${{{X}}^{\left(1 \right)}}$ 中相邻位置基因, $X_j^{\left(2 \right)}$ $X_{j{\rm{ + }}1}^{\left(2 \right)}$ $X_{j'}^{\left(2 \right)}$ $X_{j'{\rm{ + }}1}^{\left(2 \right)}$ 分别表示 ${{{X}}^{\left(2 \right)}}$ 中相邻位置基因, $\operatorname{} {\rm TPM}\left({X_i^{\left(1 \right)},X_{j + 1}^{\left(2 \right)}} \right) > 0$ 为在 ${{{X}}^{\left(1 \right)}}$ 序列中第i位置基因 $X_i^{\left(1 \right)}$ ${{{X}}^{\left(2 \right)}}$ 序列中第 $j + 1$ 位置基因 $X_{j + 1}^{\left(2 \right)}$ 存在转移概率,其他类推.

图 7 非等长交叉算子原理 Fig. 7 Schematic of non-isometric crossover

交叉算子选择任意长度的2个状态序列X(1)X(2),当随机的2个非等交叉段l1l2发生交换时,当且仅当X(1)X(2)中4个基因满足状态转移关系时,生成的交叉子代个体一定满足马尔科夫性.

利用新交叉算子的伪代码,可以实现任意两条状态序列通过交换各自任意的非等长交叉段生成2条满足马尔科夫性的状态序列.

输入X1X2分别为任意的2条状态序列个体,TPM为汽车运行工况的状态转移概率矩阵,LX1LX2分别为X1X2这2条序列的长度. K为非等长交叉算子伪代码中的当前循环次数,输出Xc为交叉后生成的状态序列. 非等长随机搜索交叉算子伪代码如下.

Begin initialize X1X2和TPM, LX1, LX2

1. flag=0;

2. for k=1 to K do

3. 在X1中随机选择一个基因xi; 其位置记为i; 其相邻基因为 xi+1;

4. 初始化AIO=cell(1,2); BIO=cell(1,2);

5. 把X2中满足TPM(Xi,Xp)>0的基因Xp赋给 AIO{1,1};

6. 把在X2中满足TPM(Xq,Xi+1)>0的基因Xq赋给AIO{1,2};

7. 把AIO{1,1}在X2中的位置赋给BIO{1,1};

8. 把AIO{1,2}在X2中的位置赋给BIO{1,2};

9. 初始化J={};

10. If BIO{1,1}非空且PIO{1,2}非空 then

11. 把xi的可交叉位置赋给J;

12. 随机选择一个xi的可交叉位置j $ \; \subset \;$ J;

13. 在X1中随机选择一个l1 $ \subset $ [1: LX1i–1];

14. 在X2中随机选择一个l2 $ \subset $ [1: LX2j–1];

15. Xi= X1(i+l1); Xi′+1= X1(i+l1+1);

16. Yj= X2(j+l2); Yj′+1= X2(j+l2+1);

17. If TPM(Xi, Yj′+1)>0 且TPM(Yj, Xi′+1)>0

18. flag=1;

19. Y=[i, i+l1, j, j+l2];

20. Xc=[X1(1:Y(1)) X2((Y(3)+1):Y(4))X1((Y(2)+1):end)];

21. break;

22. End if

23. End if

24. End for

25. If flag==0

26. Xc=X1;

27. End if

End

为了保证非等长交叉算子的有效性,即执行一次交叉算法确保发生交叉的概率足够大,需要确定K值.例如长度为1 800 s的2条工况序列,通过非等长交叉算子计算,发生交叉的概率Rc及平均用时tmK的关系如图8所示. 可以看到,Rctm都随着K的增加而增加,Rc接近100%时,tm趋于一个稳定值. 为了保证交叉算子的有效性,用于生成汽车运行工况的交叉算子中K设置为250,以确保发生交叉的概率接近100%.

图 8 非等长交叉算子发生交叉的概率及平均用时与当前循环次数的变化曲线 Fig. 8 Curves of crossover probability and average time with current iteration from non-isometric crossover
3.3 满足马尔科夫性的非等长变异算子

马尔科夫链随机模拟来自平稳分布的状态序列,具有更好的收敛性[25],本身符合马尔科夫性. 利用马尔科夫链随机模拟方法,可生成首尾为怠速且任意长度的状态序列。将生成具有该特征状态序列的过程作为变异算子。

4 结果验证 4.1 期望工况的生成

按照图6设计汽车运行工况,在完成规定的步骤后,编写新进化方法主程序并把新操作算子编入到遗传算法中. 由于非等长交叉算子生成不同长度的状态序列,算法程序将初始种群改为元胞存储,易于处理. 种群大小设置为100.

利用进化方法分别进化3种不同的初始种群(个体长度分别介于1 000~2 000 s,1 000~3 600 s,1 000~5 400 s的3个初始种群),设计期望运行工况. 综合考虑非等长交叉算子中Rctm的关系,K设置为250.

图9展示3条不同时间长度的运行工况,均为汽车运行工况马氏链的非等长交叉进化方法自动进化的结果. 速度和加速度都保持了高速特征.

图 9 不同时间长度代表性运行工况的三参数时间序列 Fig. 9 Time series of three parameters of representative diving cycles with different time lengths
4.2 结果分析

首先从两方面分析生成的运行工况是否满足马尔科夫性. 新方法生成的工况速度序列不存在异常针状形态特征,符合实际的速度形态;经过验证,新方法生成的工况中的状态转移关系来自于状态转移矩阵,不存在异常状态的转移.

其次分析生成工况的代表性. 表1为生成工况与原始高速数据库的指标对比. 3种不同长度运行工况所有指标的相对偏差绝对值均小于或等于初始设定值(10%);特征参数的相对偏差说明期望运行工况与原始数据一致. 两者的Cva高于90%,说明两者具有高度一致性. 3种不同长度的运行工况都可以代表原始数据,说明非等长交叉算子可以任意生成不同长度的代表性工况.

表 1 生成的不同长度的高速公路工况与原始数据库的指标对比 Table 1 Comparison of generated highway driving cycles with different lengths and original database

最后分析运行工况质量与生成效率. 汽车运行工况马氏链的非等长交叉进化方法在相同的迭代次数G=200下进化的3次结果如图10所示. 输出的最佳适应值fval=0.1,用时分别为0.67、1.67和1.20 h,平均用时为1.18 h. 把马尔科夫链的转移条件转化为非线性不等式约束,利用传统遗传算法进化多次结果的平均用时为3.49 h,并且结果没有达到最佳适应值. 新进化方法不仅性能更好,而且平均效率更高.

图 10 不同进化时长下马氏链非等长交叉进化方法的最佳适应值随迭代次数的变化曲线 Fig. 10 Curves of best fitness value with iteration of non-isometric crossover evolution method of Markov chain under different evolutionary time lengths
5 结 论

(1)通过非线性约束使个体序列满足马尔科夫性的方式,分析了马尔科夫链和传统遗传算法相结合的方法. 生成运行工况方法存在的性能差而且效率低的问题.

(2)提出了汽车运行工况马氏链非等长交叉进化算法,解决了交叉算子满足马尔科夫性的问题,并且提高了交叉效率.

(3)将进化方法应用于汽车运行工况设计,多次生成运行工况的结果表明,该方法能够得到合理并且具有代表性的高速公路运行工况. 生成工况与试验采集数据库两者所有特征参数的相对偏差绝对值均小于或等于初始设定偏差,验证了方法的正确性,说明方法能够有效解决传统遗传算法性能不佳的问题,效率高.

与传统设计方法相比,本文提出的工况设计方法能够生成设计效率更高、设计质量更佳的工况. 在后续研究中,将根据试验车辆参数,构建车辆仿真模型,将设计工况输入模型中,输出挡位、转速、转矩和油耗信息,并对比原始数据库的实际信息,完成对设计工况的动力性和经济性检验.

参考文献
[1]
SCHWARZER V, GHORBANI R. Drive cycle generation for design optimization of electric vehicles[J]. IEEE Transactions on Vehicular Technology, 2013, 62(1): 89-97. DOI:10.1109/TVT.2012.2219889
[2]
KNEZ M, MUNEER T, JEREB B, et al. The estimation of a driving cycle for Celje and a comparison to other European cities[J]. Sustainable Cities and Society, 2014, 11(2/3): 56-60.
[3]
BRADY J, O’MAHONY M. Development of a driving cycle to evaluate the energy economy of electric vehicles in urban areas[J]. Applied Energy, 2016, 177: 165-178. DOI:10.1016/j.apenergy.2016.05.094
[4]
LIN J. A Markov process approach to driving cycle development [D]. Davis: University of California, 2002.
[5]
PATIL R, ADORNATO B, FILIPI Z. Design optimization of a series plug-in hybrid electric vehicle for real-world driving conditions[J]. SAE International Journal of Engines, 2010, 3(1): 655-665. DOI:10.4271/2010-01-0840
[6]
GONG Q, MIDLAM-MOHLER S, MARANO V, et al. An iterative Markov Chain approach for generating vehicle driving cycles[J]. SAE International Journal of Engines, 2011(1): 1035-1045.
[7]
SOUFFRAN G, MIEGEVILLE L, GUERIN P. Simulation of real-world vehicle missions using a stochastic Markov model for optimal powertrain sizing[J]. IEEE Transactions on Vehicular Technology, 2012, 61(8): 3454-3465. DOI:10.1109/TVT.2012.2206618
[8]
SHI S, LIN N, ZHANG Y, et al. Research on Markov property analysis of driving cycles and its application[J]. Transportation Research Part D Transport and Environment, 2016, 47: 171-181. DOI:10.1016/j.trd.2016.05.013
[9]
SILVAS E, HEREIJGERS K, PENG H, et al. Synthesis of realistic driving cycles with high accuracy and computational speed, including slope information[J]. IEEE Transactions on Vehicular Technology, 2016, 65(6): 4118-4128. DOI:10.1109/TVT.2016.2546338
[10]
ASHTARI A, BIBEAU E, SHAHIDINEJAD S. Using large driving record samples and a stochastic approach for real-world driving cycle construction: winnipeg driving cycle[J]. Transportation Science, 2014, 48(2): 170-183. DOI:10.1287/trsc.1120.0447
[11]
FILEV D P, KOLMANOVSKY I. Generalized Markov models for real-time modeling of continuous systems[J]. IEEE Transactions on Fuzzy Systems, 2014, 22(4): 983-998. DOI:10.1109/TFUZZ.2013.2279535
[12]
雷英杰. MATLAB遗传算法工具箱及应用 [M]. 西安: 西安电子科技大学出版社, 2014: 1-8.
[13]
LIU L, HUANG C, LIU M, et al. Study on the combined design method of transient driving cycles for passenger car in Changchun [C] // IEEE Vehicle Power and Propulsion Conference. Harbin: IEEE, 2008: 1-5.
[14]
PERHINSCHI M G, MARLOWE C, TAMAYO S, et al. Evolutionary algorithm for vehicle driving cycle generation[J]. Journal of the Air and Waste Management Association, 2011, 61(9): 923-931. DOI:10.1080/10473289.2011.596742
[15]
AHMED A, ZHAO C L, HAN K, et al. Using design of experiment and genetic algorithm to obtain the optimum gear shifting strategy for a real driving cycles[J]. Applied Mechanics and Materials, 2012, 224: 497-503.
[16]
YUE B, SHI S, LIN N, et al. Study on the design method of driving cycle with road grade based on Markov chain model [C] // IEEE Vehicle Power and Propulsion Conference. Montreal: IEEE, 2015: 1-5.
[17]
盛骤, 谢式千, 潘承毅. 概率论与数理统计 [M]. 北京: 高等教育出版社, 2011: 319-334.
[18]
GRIMSHAW S D, ALEXANDER W P. Markov chain models for delinquency: transition matrix estimation and forecasting[J]. Applied Stochastic Models in Business and Industry, 2011, 27(3): 267-279.
[19]
陈国汉. 蒙特卡洛模拟及其Stata应用实现 [M]. 北京: 经济科学出版社, 2015: 15-100.
[20]
MARTINEZ W L. Computational statistics in MATLAB®[J]. Wiley Interdisciplinary Reviews: Computational Statistics, 2011, 3(1): 69-74. DOI:10.1002/wics.138
[21]
JEON S I, JO S T, LEE J M. Multimode driving control of a parallel hybrid electric vehicle using driving pattern recognition[J]. Journal of Dynamic Systems Measurement and Control, 2002, 124(1): 489-494.
[22]
WANG Q, HUO H, HE K, et al. Characterization of vehicle driving patterns and development of driving cycles in Chinese cities[J]. Transportation Research Part D Transport and Environment, 2008, 13(5): 289-297. DOI:10.1016/j.trd.2008.03.003
[23]
SHI S, WEI S, KUI H, et al. Improvements of the design method of transient driving cycle for passenger car [C] // IEEE Vehicle Power and Propulsion Conference. Dearborn: IEEE, 2009: 1581-1586.
[24]
孙洪祥. 随机过程[M]. 北京: 机械工业出版社, 2008: 86-200.
[25]
ROBERT C, CASELLA G. Monte Carlo statistical methods [M]. [S. l.]: Springer Science and Business Media, 2013: 205-265.