CN101982843A - Method for selecting state vector in nonparametric regression short-time traffic flow prediction - Google Patents

Abstract

The invention discloses a method for selecting state vectors in non-parametric regression short-term traffic flow forecasting, and relates to the technical field of short-term traffic flow forecasting. The provided method improves prediction accuracy, stability, speed and portability, shortens running time, and verifies the validity and necessity of the method provided by the invention.

Description

A Method of Selecting State Vectors in Nonparametric Regression Short-term Traffic Flow Forecasting

technical field

The invention relates to the technical field of short-term traffic flow prediction, in particular to a method for selecting state vectors in non-parametric regression short-term traffic flow prediction.

Background technique

At present, many researchers at home and abroad apply the non-parametric regression method to the research of short-term traffic flow forecasting, and make necessary improvements to the non-parametric regression method according to the needs of practical problems. In 1991, Davis and Nihan really applied the method of non-parametric regression to traffic forecasting. Although problems such as model selection and parameter setting were avoided, the method required a large representative historical database and the time consumed by the method was longer. In 1995, Smith applied the non-parametric regression method to single-point short-term traffic flow prediction. The experimental results achieved better results than the historical average and neural network, but there was also the problem of too slow search speed. Aiming at the problem that the search speed is too slow, Oswald et al. set out to establish a fuzzy nearest neighbor method from the KD tree, thereby improving the historical data structure mode and the nearest neighbor search method in the non-parametric regression method, and improving the operating efficiency of the method. Zhang Xiaoli proposed a K-neighborhood non-parametric short-term traffic flow forecasting method based on balanced binary tree, using clustering method and balanced binary tree structure to establish a case database, thereby improving the prediction accuracy and meeting the real-time requirements. These are mainly improved from the storage mode of the historical database and the nearest neighbor search method.

However, the selection of state vectors that describe the causal relationship between the flow of the upstream road section and the road section to be tested mainly includes principal component analysis, correlation coefficient method, and autocorrelation coefficient. These methods are all analyzed from a statistical point of view. The factors related to the flow rate are used as the components of the state vector, but there is a lack of research on whether the state vector is selected and whether the prediction effect is improved. It is worth noting that even if the running time of the method is shortened by improving the storage mode of the historical database and the neighbor search method, if the selection of the state vector is not enough to describe the flow causality between the upstream road section and the road section to be tested, then the final prediction effect Not enough to be satisfying either.

Contents of the invention

In order to solve the above problems, improve prediction accuracy, shorten running time, and meet the needs of practical applications, the present invention provides a method for selecting state vectors in non-parametric regression short-term traffic flow prediction. The method includes the following steps:

(1) judging whether the upstream road section related to the road section to be tested is in the upstream road section set according to the first preset criterion, if yes, perform step (2); if not, the upstream road section is not in the upstream road section set;

(2) Obtain the average speed of the traffic flow within the radius L of the road section to be tested through preset data;

(3) According to the average speed and the forecast period, obtain the maximum number of historical retrospective periods m;

(4) Acquire an initial state vector according to the set of upstream road sections and the maximum cycle number m of the history tracing;

(5) determine the encoding length of the particle according to the dimension M of the initial state vector;

(6) Set the number of particles as Z, and randomly generate Z particles;

(7) define fitness function, obtain the fitness of Z particle according to described fitness function;

(8) Acquiring individual extremum and global extremum of particles according to the fitness of the Z particles;

(9) Interleave the codes of the Z particles with the codes of the individual extremum and the code of the global extremum, and perform a mutation operation according to a preset probability to obtain the global optimal particle;

(10) Judging whether the preset number of times is reached, if yes, output the globally optimal particle; if not, re-execute step (7);

(11) Perform a dot product operation on the global optimal particle and the initial state vector to obtain a state vector.

The first preset criterion described in step (1) is specifically:

$\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; j</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}\mathrm{<span\; class="notranslate">\; dis</span>}<span\; class="notranslate">\; (</span>{\mathrm{<span\; class="notranslate">\; p</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}^{\mathrm{<span\; class="notranslate">\; upstream</span>}}<span\; class="notranslate">\; ,</span>{\mathrm{<span\; class="notranslate">\; p</span>}}_{\mathrm{<span\; class="notranslate">\; j</span>}}^{\mathrm{<span\; class="notranslate">\; inter</span>}\mathrm{<span\; class="notranslate">\; sec</span>}\mathrm{<span\; class="notranslate">\; the\; action</span>}}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; \&le;</span>\mathrm{<span\; class="notranslate">\; L</span>}$

表示上游路段中的第i条路段中点的坐标位置和上游路段第j个交叉路口中心的坐标位置之间的距离。in, Indicates the coordinate position of the midpoint of the i-th road segment in the upstream road segment, Indicates the coordinate position of the jth intersection center of the upstream section,

Indicates the distance between the coordinate position of the midpoint of the i-th road segment in the upstream road segment and the coordinate position of the j-th intersection center of the upstream road segment.

In step (3), the maximum number of cycles m of history tracing is specifically:

C表示预测周期，

表示平均速度。

C represents the forecast period,

Indicates the average speed.

The dimension M of the initial state vector described in step (5) is specifically:

M=(s+1)(m+1), s represents the number of elements in the upstream link number set.

The fitness function described in step (7) is specifically:

F(VAR, ARE, PER, EC)＝λ ₁ EV+λ ₂ ARE+λ ₃ /PER+λ ₄ /EC, EV means the variance of forecast error, ARE means average relative error, PER means forecast relative error in interval [ 0, α], EC represents the equalization coefficient, λ ₁ represents the weight of EV, λ ₂ represents the weight of ARE, λ ₃ represents the weight of PER, λ ₄ represents the weight of EC, and α represents the relative prediction error.

Obtaining the fitness of Z particles according to the fitness function described in step (7) specifically includes:

Define the flow state pattern for the current forecast period;

Perform a dot multiplication operation on the encoding of the particles and the flow state mode of the current forecast period to obtain the current flow state mode;

Do a dot multiplication operation on the code of the particle and the flow state mode of the historical database to obtain the current flow state mode of the historical database;

According to the current traffic state mode and the current historical database traffic state mode, predict the traffic in the next period of the current forecast period through K-nearest neighbor matching and equal weight prediction, obtain a first forecast error, and use the first forecast error as The fitness of the current particle.

The beneficial effects of the technical solution provided by the invention are:

The embodiment of the present invention provides a method for selecting state vectors in non-parametric regression short-term traffic flow forecasting. The method provided by the present invention improves the prediction accuracy, Stability, speed and portability shorten the running time and verify the validity and necessity of the method provided by the invention.

Description of drawings

Fig. 1 is the flowchart of the non-parametric regression provided by the present invention;

Fig. 2 is the distance method schematic diagram that the present invention provides;

Fig. 3 is the flow chart of the selection method of state vector in the non-parametric regression short-term traffic flow prediction that the present invention provides;

Fig. 4 obtains the schematic diagram of the fitness of Z particles according to the fitness function F provided by the present invention;

Fig. 5 is the comparative figure of forecasting result during peak hours provided by the present invention;

Fig. 6 is a comparison chart of prediction results during flat peak periods provided by the present invention;

Fig. 7 is a comparison chart of prediction results during low peak hours provided by the present invention;

Fig. 8 is a comparison chart of all-weather forecast results provided by the present invention.

Detailed ways

In order to make the object, technical solution and advantages of the present invention clearer, the implementation manner of the present invention will be further described in detail below in conjunction with the accompanying drawings.

In order to solve the above problems, improve prediction accuracy, shorten running time, and meet the needs of practical applications, an embodiment of the present invention provides a method for selecting state vectors in non-parametric regression short-term traffic flow prediction.

Referring to Figure 1, nonparametric regression is a data-driven heuristic forecasting mechanism that predicts future values by searching historical databases for data similar to current observations. It can usually be divided into five components: selection of historical data, generation of sample database, definition of data similarity, K-nearest neighbor matching and prediction method. When non-parametric regression is used to predict short-term traffic flow, the historical database must first be constructed. If all traffic flow data are stored in the database without distinction, it will inevitably lead to an unbearable database scale and a "dimension disaster" when matching data. "And other issues. Therefore, the selected traffic flow data should be the complete and typical flow or flow combination that is most closely related to the flow of the measured road section. At the same time, the sample database is the core of non-parametric regression, and its structure (including logical structure and physical structure) and the space-time efficiency of the search data algorithm play a decisive role in the performance of non-parametric regression. Therefore, the research focus of the embodiment of the present invention is how to reasonably select the organizational mode (ie, state vector) of the sample database so that it can describe the flow causality between the upstream road section and the road section to be tested, save storage space, and speed up search efficiency. After the sample database is generated, the definition of data similarity, K-nearest neighbor matching and prediction can be performed. After the relevant elements of the non-parametric regression model are set, the K-nearest neighbor matching with the current real-time observation data can be found from the historical database. Finally, the traffic flow forecast at the next moment of the current moment can be obtained by using the forecast. When comparing the current traffic flow observation data with the traffic flow historical database, a comparison standard is needed, and the state vector is the description of this standard. Such as road occupancy rate, driving speed and weather conditions will affect the traffic flow of this road segment at the next moment. Even if it is the most closely adjacent moment, the traffic flow data of adjacent road sections also involves the problem of taking several adjacent time intervals and several adjacent road sections. Whether the state vector is reasonable or not is directly related to the prediction accuracy. At present, there is no unified standard for the selection of state vectors. Considering as many factors as possible in the state vectors will not improve the prediction accuracy, but will lead to longer running time; however, if the selected state vectors are not enough to describe The main causal relationship between upstream and downstream traffic flow also fails to achieve good prediction results. The selection of the K value of the nearest neighbor point in K-nearest neighbor matching is very important. If the K value is too large or too small, it will affect the prediction accuracy. If the value of K is chosen to be equal to the number of patterns in the historical database, then nonparametric regression is inaccurate. However, the selection of K value should not be too small, if it is too small, it will increase the component of accidental factors and affect the accuracy of prediction. In addition, during some abnormal time periods, the flow rate of some road sections decreases significantly while the flow rate of other road sections suddenly increases. K can take a small value. If it takes a large value, the information will be weakened, resulting in a large prediction error. Therefore, in the case of an abnormally large flow rate or a low flow range, the value of K can be set smaller or a prediction interval can be used for prediction. However, when it comes to short-term traffic forecasting, there is no uniform paradigm to determine the precise K value, which requires participating in offline forecasting tests based on different series of sample data, and selecting the most accurate value by analyzing the curve of forecast error and K value. Good K value. Since the flow causality between the upstream road section and the road section to be tested is different at different times of the day, when performing online rolling prediction, the method provided by the embodiment of the present invention and the historical data of the corresponding time period should be used first to perform necessary offline detection and analysis to obtain the described traffic flow The state vector of the causal relationship, and then use the state vector to make real-time online predictions for the corresponding period of the road section to be tested. In both the off-peak period and all-weather conditions, the relative error of the average correction of the forecast is relatively high due to the fact that the flow rate is low or even 0. In order to improve the practicability and operability of the prediction, two different K values can be selected to construct the prediction interval, as long as the predicted value is acceptable within the corresponding prediction interval, thus improving the non-parametric regression prediction to a certain extent The mean corrected relative error of the result. Assume that the real-time traffic flow data pattern is:

{v _i (tm), V _i (t-m+1), L, V _i (t)}, i∈U+{f}, where U is the set of relevant upstream link numbers, and the upstream link number set U The number of elements is set to s, f is the number of the road section to be tested, {f} is the set of road section numbers to be tested, m is the maximum cycle number of history tracing, t is the prediction time, and i is the label of the upstream road section. The traffic flow data pattern of the historical database is {V _ih (tm), V _ih (t-m+1), LV _ih (t)}, i∈U+{f}. The distance measures the matching degree between the real-time data and the sample data. However, different distance measurement criteria will search for different K neighbors, which will affect the accuracy of the predicted value. The distance measurement criterion adopted in the embodiment of the present invention is as follows:

$\mathrm{<span\; class="notranslate">\; D.</span>}<span\; class="notranslate">\; =</span>\underset{\mathrm{<span\; class="notranslate">\; i</span>}<span\; class="notranslate">\; \&Element;</span>\mathrm{<span\; class="notranslate">\; u</span>}<span\; class="notranslate">\; +</span><span\; class="notranslate">\; \{</span>\mathrm{<span\; class="notranslate">\; f</span>}<span\; class="notranslate">\; \}</span><span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; l</span>}<span\; class="notranslate">\; \&Element;</span><span\; class="notranslate">\; \{</span>\mathrm{<span\; class="notranslate">\; 0,1</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; L</span>}<span\; class="notranslate">\; ,</span>\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; \}</span>}{\mathrm{<span\; class="notranslate">\; max</span>}}<span\; class="notranslate">\; |</span>{\mathrm{<span\; class="notranslate">\; V</span>}}_{\mathrm{<span\; class="notranslate">\; i</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; l</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; -</span>{\mathrm{<span\; class="notranslate">\; V</span>}}_{\mathrm{<span\; class="notranslate">\; i\; h</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; l</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; |</span>$

Among them, the distance measurement criterion D is (s+1)(m+1) dimensional, and the component distance with the largest distance is selected as the matching metric among the (s+1)(m+1) dimensional components of real-time data and sample data guidelines. This distance measurement criterion fully considers different distance information in (s+1)(m+1) dimensions, which is equivalent to a (s+1)(m+1)-dimensional hypercube, and its side length is the one with the largest distance. Dimension, namely D, the smaller the value of D, the higher the matching similarity.

Select the K nearest historical state vectors in the historical database through the distance measurement criterion, assuming that K neighbors are found in the historical database, the distances between the real-time data and the K neighbors are D _k (k=1, 2, L, K ), the flow rate of the next prediction period of the road section to be tested corresponding to these neighbors is V _kh (t+1).

Forecasting methods mainly include weighted forecasting methods and equal weighted forecasting methods. Because the traffic system contains determinism and randomness: the determinism is reflected by the neighbors, that is, when the state vector is close, the predicted value and the real value are also close to a certain degree; but the system is random, so there is no "the closer the state vector , the closer the predicted value is to the real value”. According to the proposition that there are no two identical propositions in the world, it can be known that when 95% of the characteristics of two leaves are almost identical, the possibility of significant differences in the other 5% of the characteristics is higher. Therefore, the prediction method in the embodiment of the present invention adopts an equal-weight prediction method, and the expression is as follows:

$\mathrm{<span\; class="notranslate">\; V</span>}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span><span\; class="notranslate">\; =</span>\frac{\mathrm{<span\; class="notranslate">\; 1</span>}}{\mathrm{<span\; class="notranslate">\; K</span>}}\underset{\mathrm{<span\; class="notranslate">\; k</span>}<span\; class="notranslate">\; =</span>\mathrm{<span\; class="notranslate">\; 1</span>}}{\overset{\mathrm{<span\; class="notranslate">\; K</span>}}{\mathrm{<span\; class="notranslate">\; \&Sigma;</span>}}}{\mathrm{<span\; class="notranslate">\; V</span>}}_{\mathrm{<span\; class="notranslate">\; kh</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; +</span>\mathrm{<span\; class="notranslate">\; 1</span>}<span\; class="notranslate">\; )</span>$

Referring to Fig. 2, the number of relevant upstream road sections s and the maximum cycle number m of historical tracing can be roughly determined by the distance method. The section marked with a black diamond is the section to be tested, the section marked with a black dot is the center point of the intersection, and the section marked with a black square is the upstream section of the section to be tested. Through empirical analysis, it is found that if the upstream road sections whose distance to the city to be tested is within the range of L have a significant impact on the flow of the tested road section, then these upstream road sections constitute the upstream road section set of the state vector, where the number of upstream road sections s The value of the range of L and L is determined according to the specific application situation in the actual application, and the embodiment of the present invention does not limit it during specific implementation. According to the road network characteristics and the distance method, a rough state vector is obtained, and then the first prediction error is optimized by using the PSO (Particle Swarm Optimization, particle swarm optimization algorithm)-GA (Genetic Algorithm, genetic algorithm) hybrid intelligent algorithm and test data, Thus, a state vector capable of describing the flow causality between the upstream section and the section to be tested is obtained. Finally, the found state vector can be used for real-time online traffic prediction. Referring to Fig. 3, the specific implementation process of the embodiment of the present invention is introduced in detail:

101: Determine whether the upstream road segment related to the road segment to be tested is in the upstream road segment set according to the first preset criterion, if yes, perform step 102; if not, the upstream road segment is not in the upstream road segment set;

表示上游路段中的第i条路段中点的坐标位置，

表示上游路段第j个交叉路口中心的坐标位置，

表示上游路段中的第i条路段中点的坐标位置和上游路段第j个交叉路口中心的坐标位置之间的距离，当满足第一预设准则时，则上游路段在上游路段集合中，即i∈U；当不满足第一预设准则时，则上游路段不在上游路段集合中，即

Among them, the first preset criterion is

Indicates the coordinate position of the midpoint of the i-th road segment in the upstream road segment,

Indicates the coordinate position of the jth intersection center of the upstream section,

Indicates the distance between the coordinate position of the midpoint of the i-th road segment in the upstream road segment and the coordinate position of the j-th intersection center of the upstream road segment. When the first preset criterion is met, the upstream road segment is in the upstream road segment set, that is i∈U; when the first preset criterion is not satisfied, the upstream road segment is not in the upstream road segment set, that is

102: Obtain the average speed of the traffic flow within the radius L of the road section to be tested through preset data

Among them, the preset data is the traffic flow of a certain road section in the morning rush hour, afternoon peak hour and evening peak hour. Through the statistics and analysis of the traffic flow, it can be obtained within the radius L of the road section to be tested. average speed of traffic

103: According to the average speed and the forecast cycle, obtain the maximum number of historical retrospective cycles m;

C表示预测周期，

表示平均速度。

C represents the forecast period,

Indicates the average speed.

Wherein, the prediction cycle is set according to the specific application conditions in the actual application, and can be set to 5 minutes, 10 minutes, and 15 minutes, etc., and the embodiment of the present invention does not limit this during specific implementation, and the embodiment of the present invention uses 5 minutes as an example for illustration.

104: Obtain the initial state vector according to the upstream road section set U and the maximum cycle number m of history tracing;

{V _i (tm), V _i (t-m+1), L, V _i (t)}, i∈U+{f}

105: Determine the encoding length of the particle according to the dimension M of the initial state vector;

Wherein, the dimension of the initial state vector is M=(s+1)(m+1), and s represents the number of elements in the upstream link number set.

106: set the number of particles to Z, and randomly generate Z particles;

Among them, the dimension of each particle is the dimension M of the initial state vector.

107: Define a fitness function F, and obtain the fitness of Z particles according to the fitness function F;

F(VAR, ARE, PER, EC) = λ ₁ EV + λ ₂ ARE + λ ₃ /PER + λ ₄ /EC

表示整体预测效果的好坏；λ₁表示EV的权重、λ₂表示ARE的权重、λ₃表示PER的权重、λ₄表示EC的权重，α表示预测相对误差。λ₁、λ₂、λ₃和λ₄的取值根据实际应用中的情况来确定，通过对λ₁、λ₂、λ₃和λ₄的调节来调整EV、ARE、PER和EC在适应度函数F中所占的比例，α通常的取值范围为20％或30％。Among them, EV represents the variance of the prediction error, representing the robustness of the prediction algorithm; ARE represents the average relative error, representing the overall performance of the prediction algorithm; PER represents the percentage of the relative prediction error in the interval [0, α], representing the prediction effect The individual performance of ; EC means the coefficient of equality,

Indicates the quality of the overall prediction effect; λ ₁ represents the weight of EV, λ ₂ represents the weight of ARE, λ ₃ represents the weight of PER, λ ₄ represents the weight of EC, and α represents the relative prediction error. The values of λ ₁ , λ ₂ , λ ₃ and λ ₄ are determined according to the actual application situation, and the fitness of EV, ARE, PER and EC can be adjusted by adjusting λ ₁ , λ ₂ , λ ₃ and λ ₄ The proportion of function F, α usually ranges from 20% or 30%.

The fitness function F represents the fitness of the particle, and the smaller the value of the fitness function F, the stronger the adaptability of the particle, and the more likely its good genes will be passed on to the next generation. In each iteration process, each particle adjusts itself by tracking two extreme values, so that it adapts itself more and more to the environment in which it lives. One is the individual extreme value that the particle itself can find, and the other is the entire particle group. The global extremum that can be found so far. Referring to Figure 4, this step specifically includes the following steps, which are described below for details:

1. Define the flow state mode CM of the current forecast period;

CM＝[V _s (tm)V _s (t-m+1)LV _s (t)LV _f (tm)V _f (t-m+1)LV _f (t)]1 _×M

2. Perform a dot multiplication operation on the coding of the particles and the flow state mode of the current forecast period to obtain the current flow state mode CM ^* ;

Among them, the embodiment of the present invention takes binary code as an example for illustration. The binary code of a particle is particle=[1 0 L 1 L 1 0 L 0]1 _×M , and the particle is multiplied by each state mode in CM, Obtain the current flow state mode: CM ^* =[V _s (tm)0LV _s (t)LV _f (tm)0L0] _1×M .

3. Do a dot multiplication operation on the coding of the particles and the flow state mode HM of the historical database to obtain the current historical database flow state mode HM ^* ;

HM＝{V _ih (tm), V _ih (t-m+1), LV _ih (t)} _H×M , i∈U+{f}

${\mathrm{<span\; class="notranslate">\; H\; M</span>}}^{<span\; class="notranslate">\; *</span>}<span\; class="notranslate">\; =</span>{\left[\begin{array}{ccccccccc}{\mathrm{<span\; class="notranslate">\; V</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}\mathrm{<span\; class="notranslate">\; the\; s</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; )</span>& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; L</span>}& {\mathrm{<span\; class="notranslate">\; V</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}\mathrm{<span\; class="notranslate">\; the\; s</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; )</span>& \mathrm{<span\; class="notranslate">\; L</span>}& {\mathrm{<span\; class="notranslate">\; V</span>}}_{\mathrm{<span\; class="notranslate">\; 1</span>}\mathrm{<span\; class="notranslate">\; f</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; )</span>& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; L</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ {\mathrm{<span\; class="notranslate">\; V</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}\mathrm{<span\; class="notranslate">\; the\; s</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; )</span>& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; L</span>}& {\mathrm{<span\; class="notranslate">\; V</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}\mathrm{<span\; class="notranslate">\; the\; s</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; )</span>& \mathrm{<span\; class="notranslate">\; L</span>}& {\mathrm{<span\; class="notranslate">\; V</span>}}_{\mathrm{<span\; class="notranslate">\; 2</span>}\mathrm{<span\; class="notranslate">\; f</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; )</span>& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; L</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\\ \mathrm{<span\; class="notranslate">\; m</span>}& \mathrm{<span\; class="notranslate">\; m</span>}& & \mathrm{<span\; class="notranslate">\; m</span>}& & \mathrm{<span\; class="notranslate">\; m</span>}& \mathrm{<span\; class="notranslate">\; m</span>}& & \mathrm{<span\; class="notranslate">\; m</span>}\\ {\mathrm{<span\; class="notranslate">\; V</span>}}_{\mathrm{<span\; class="notranslate">\; Hs</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; )</span>& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; L</span>}& {\mathrm{<span\; class="notranslate">\; V</span>}}_{\mathrm{<span\; class="notranslate">\; Hs</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; )</span>& \mathrm{<span\; class="notranslate">\; L</span>}& {\mathrm{<span\; class="notranslate">\; V</span>}}_{\mathrm{<span\; class="notranslate">\; f</span>}}<span\; class="notranslate">\; (</span>\mathrm{<span\; class="notranslate">\; t</span>}<span\; class="notranslate">\; -</span>\mathrm{<span\; class="notranslate">\; m</span>}<span\; class="notranslate">\; )</span>& \mathrm{<span\; class="notranslate">\; 0</span>}& \mathrm{<span\; class="notranslate">\; L</span>}& \mathrm{<span\; class="notranslate">\; 0</span>}\end{array}\right]}_{\mathrm{<span\; class="notranslate">\; h</span>}<span\; class="notranslate">\; \&times;</span>\mathrm{<span\; class="notranslate">\; m</span>}}$

Among them, H is the number of traffic state patterns in the historical database, h ∈ [1, H], do a dot multiplication operation between particle and each state pattern in HM to obtain the current historical database traffic state pattern HM ^* . The capacity of the constructed historical database is large enough and representative, that is, the historical database contains various trends and typical laws of traffic status, and the current collected real-time data patterns can find similar historical data patterns in it.

4. According to the current traffic state mode CM ^* and the current historical database traffic state mode HM ^*, predict the next cycle traffic of the current forecast cycle through K-nearest neighbor matching and equal weight prediction, obtain the first prediction error, and use the first prediction error as The fitness of the current particle.

108: Obtain the individual extremum and global extremum of particles according to the fitness of Z particles;

Among them, the minimum fitness value of each particle is used as the individual extremum of each particle, and the smallest value among the Z individual extremums is used as the global extremum.

109: Interleave the codes of the Z particles with the codes corresponding to the individual extremum and the code corresponding to the global extremum, and perform mutation operations according to the preset probability to obtain the global optimal particle;

Wherein, this step specifically includes: defining a single-point crossover operator, and according to the defined single-point crossover operator, the codes of the Z particles are respectively crossed with the codes corresponding to the individual extremum and the codes corresponding to the global extremum. Interleaving the codes of Z particles with the particle codes corresponding to the individual extremum can make each particle inherit its own better part of genes. Interleaving the codes of Z particles with the particle codes corresponding to the global extremum can make each particle inherit the best part of the gene of the particle swarm. Define the mutation operator. After the codes of the two parent individuals are recombined, there may be mutations in the child individuals, and the child individuals will change with a preset probability. In specific implementation, firstly, a sub-individual is randomly selected from a group of sub-individuals, and the value of a bit coded in the sub-individual is randomly changed with a preset probability for the selected sub-individual. Like the biological world, the probability of mutation in GA is very low, usually the preset probability value is between 0.001-0.01, and mutation provides opportunities for the generation of new sub-individuals.

There are many encoding methods of particles, such as binary encoding, real number encoding, etc., the embodiment of the present invention preferably adopts binary encoding, 0 represents that the state vector component has no significant influence on the prediction result; 1 represents that the state vector component has a significant influence on the prediction result, After iterative PSO-GA hybrid intelligent algorithm, the optimal binary coded individual is obtained. Among them, the number of parent individuals is defined according to the dimension of the initial state vector, and the intersection point p of the parent individual is randomly generated. The range of the intersection point p is [1, M-1], and the parent individual 1 The exchange of the high p-bit of and the high p-bit of the parent individual 2. For example: the dimension M of the initial state vector is equal to 9, and the parent individual 1 can be defined as 101011101; the parent individual 2 is 010101010; the range of the intersection p is [1, 8]. When the intersection position p=5, in At intersection point 5, the upper 5 bits of parent individual 1 and the upper 5 bits of parent individual 2 are exchanged, and two child individuals are generated after the intersection: child individual 1: 010101101; child individual 2: 101011010. For binary-coded sub-individuals, mutation means that the value of a certain bit is flipped. For each sub-individual, the change of the coded value of which bit is random, for example: the sub-individual before mutation is: 010101101, if the fourth bit is mutated, the sub-individual after mutation is: 010001101. In order to prevent convergence to a local optimal solution, the preset probability needs to be linearly increasing, and the specific value of the preset probability is set according to the specific application situation in the actual application, which is not limited in the embodiment of the present invention during specific implementation.

110: Judging whether the preset number of times has been reached, if yes, output the globally optimal particle; if not, re-execute step 107.

Wherein, the preset number of times is specifically set according to the actual application situation, which is not limited in the embodiment of the present invention, and usually the preset number of times is about 2000.

111: Do a dot product of the global optimal particle and the initial state vector to obtain the state vector.

To sum up, the embodiment of the present invention provides a method for selecting state vectors in non-parametric regression short-term traffic flow forecasting. The method improves prediction accuracy, stability, speed and portability, and verifies the validity and necessity of the method provided by the embodiment of the present invention.

A test is adopted below to verify the feasibility of the selection method of the state vector in the non-parametric regression short-term traffic flow prediction provided by the embodiment of the present invention, see the following description for details:

The traffic data used in this paper comes from the University of Minnesota Duluth (http://www.d.umn.edu/tdrl/traffic/). In order to verify the effectiveness and necessity of the PSO-GA algorithm proposed in this paper in searching for the optimal state vector in the process of offline analysis, the prediction effect is compared with the prediction effect without offline analysis of the PSO-GA algorithm under different traffic conditions. The comparison prediction effect is shown in Table 1, and the comparison prediction results are shown in Figure 5, Figure 6, Figure 7 and Figure 8.

Table 1

From the test data in Table 1, the feasibility of the embodiment of the present invention can be verified by analyzing data such as EV, ARE, PER and EC. From Fig. 5, Fig. 6, Fig. 7 and Fig. 8, through the method provided by the embodiment of the present invention, the direct prediction result obtained by the method in the prior art and the comparison between the actual value of the road section, it can be known that the implementation of the present invention The feasibility of a non-parametric regression method for selecting state vectors in short-term traffic flow forecasting is provided by the example, which improves the forecasting accuracy, obtains better forecasting results, and meets the needs of practical applications.

Those skilled in the art can understand that the accompanying drawing is only a schematic diagram of a preferred embodiment, and the serial numbers of the above-mentioned embodiments of the present invention are for description only, and do not represent the advantages and disadvantages of the embodiments.

The above descriptions are only preferred embodiments of the present invention, and are not intended to limit the present invention. Any modifications, equivalent replacements, improvements, etc. made within the spirit and principles of the present invention shall be included in the protection of the present invention. within range.

Claims (6)

1. A method for selecting a state vector in non-parametric regression short-time traffic flow prediction is characterized by comprising the following steps:

(1) judging whether an upstream road section related to the road section to be detected is in the upstream road section set according to a first preset criterion, and if so, executing the step (2); if not, the upstream road segment is not in the upstream road segment set;

(2) acquiring the average speed of the traffic flow in the range of a square circle L of a road section to be detected through preset data;

(3) obtaining historical retroactive maximum cycle number m according to the average speed and the prediction cycle;

(4) acquiring an initial state vector according to the upstream road section set and the historical retroactive maximum cycle number m;

(5) determining the encoding length of the particle according to the dimension M of the initial state vector;

(6) setting the number of particles as Z, and randomly generating Z particles;

(7) defining a fitness function, and acquiring the fitness of Z particles according to the fitness function;

(8) acquiring an individual extreme value and a global extreme value of the particles according to the fitness of the Z particles;

(9) respectively performing cross operation on the codes of the Z particles, the codes of the individual extremum and the global extremum, and performing mutation operation according to a preset probability to obtain global optimal particles;

(10) judging whether the preset times is reached, if so, outputting the global optimal particles; if not, re-executing the step (7);

(11) and performing dot product operation on the global optimal particles and the initial state vector to obtain a state vector.

2. The method for selecting the state vector in the nonparametric regression short-term traffic flow prediction according to claim 1, wherein the first preset criterion in the step (1) is specifically:

<math><mrow><munder><mi>&Sigma;</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow></munder><mi>dis</mi><mrow><mo>(</mo><msubsup><mi>p</mi><mi>i</mi><mi>upstream</mi></msubsup><mo>,</mo><msubsup><mi>p</mi><mi>j</mi><mrow><mi>inter</mi><mi>sec</mi><mi>tion</mi></mrow></msubsup><mo>)</mo></mrow><mo>&le;</mo><mi>L</mi></mrow></math>

wherein,

indicating the coordinate position of the point in the ith link in the upstream link,

a coordinate position indicating the j-th intersection center of the upstream link,

and represents the distance between the coordinate position of the midpoint of the ith road segment in the upstream road segment and the coordinate position of the jth intersection center of the upstream road segment.

3. The method for selecting the state vector in the nonparametric regression short-term traffic flow prediction according to claim 1, wherein the historical retroactive maximum cycle number m in the step (3) is specifically:

c denotes a prediction period of the time period,the average speed is indicated.

4. The method for selecting the state vector in the non-parametric regression short-time traffic flow prediction according to claim 1, wherein the dimension M of the initial state vector in the step (5) is specifically:

m is (s +1) (M +1), and s represents the number of elements in the upstream segment number set.

5. The method for selecting the state vector in the nonparametric regression short-term traffic flow prediction according to claim 1, wherein the fitness function in the step (7) is specifically:

F(VAR，ARE，PER，EC)＝λ₁EV+λ₂ARE+λ₃/PER+λ₄EC, EV represents the variance of the prediction error, ARE represents the average relative error, PER represents the prediction relative error in the interval [0, alpha ]]In percent between, EC representsConstant coefficient, λ₁Denotes the weight of EV, λ₂Denotes the weight of ARE, λ₃Represents the weight of PER, λ₄Denotes the weight of EC and α denotes the prediction relative error.

6. The method for selecting the state vector in the nonparametric regression short-term traffic flow prediction according to claim 1, wherein the step (7) of obtaining the fitness of the Z particles according to the fitness function specifically comprises:

defining a current prediction period flow state mode;

performing dot product operation on the particle codes and the current prediction period flow state mode to obtain a current flow state mode;

performing dot product operation on the particle codes and the historical database flow state mode to obtain the current historical database flow state mode;

predicting the flow of the next cycle of the current prediction cycle through K neighbor matching and equal weight prediction according to the current flow state mode and the current historical database flow state mode to obtain a first prediction error, and taking the first prediction error as the fitness of the current particles.

Images