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

### 引用本文 [复制中英文]

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
[复制英文]

### 作者简介

orcid.org/0000-0001-8648-9895.
E-mail: m15104682686@163.com.

### 通信联系人

orcid.org/0000-0001-7018-0682.
E-mail: shishuming@jlu.edu.cn
.

### 文章历史

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 数据来源与原始数据的状态转移矩阵统计

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

 $\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)

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

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

 ${{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)

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

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

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

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

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

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

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

 ${{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)

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

 $\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)

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

 图 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

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

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

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

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

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

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

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

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

 图 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.