Expressway traffic flow predictionusing chaos cloud particle swarm algorithm and PPPR model

Zhao Zehui Kang Haigui Li Mingwei

(Faculty of Infrastructure Engineering, Dalian University of Technology, Dalian 116024, China)

The accurate and real-time forecasting for the expressway short-term traffic flow is an important link in expressway intelligent management, and many scholars have been attempting to do research and make improvements on their forecasting methods, which are mainly divided into two categories, that is, the method based on the determination of the mathematical model(Category Ⅰ), such as the time series forecasting model[1]and the Kalman filtering model[2], and the method of the knowledge-based intelligent model(Category Ⅱ), such as the neural network model[3]and the forecasting model[4]based on the chaos theory. Owing to that, the model of Category Ⅰ involves fewer factors; its calculation is relatively simple, but it is unable to overcome the influence of the random disturbance factors on the traffic flow. The typical representative model of Category Ⅱ is the BP neural network model, but the neural network model appears to be in the presence of the curse of difficult dimensionality problems in the treatment of the high-dimensional nonlinear problem and cannot guarantee higher forecasting accuracy.

The parameter projection pursuit regression (PPPR) model makes the high-dimensional data do the optimal linear projection to the one-dimensional subspace through a three-step optimization of the projection direction, the polynomial coefficients and the number of the ridge functions[5], which may make the point-set projected to one-dimensional space possess radiation non-variability and denseness on the one hand, and it may minimize the loss of the quantity of information through the projections on the other hand. Thus, the practical problems, such as small samples, nonlinearity, high dimensionality, local minimum etc., were well solved by the PPPR model[6], and the curse of difficult dimensionality problem was overcome, which has obvious advantages in solving such problems as the small number of samples and the relatively large dimensionality. The PPPR model is applied to the expressway short-term traffic flow forecasting in this paper, and its core is the optimal combination solution of the projection directiona, the polynomial coefficientcand the numberMof ridge functions. Therefore, the selection of the model’s parameters may affect its application to a great extent. However, the model does not give the selection method of each parameter, and, owing to that, some errors exist with regard to the commonly traditional algorithms of parameter optimization.

The particle swarm optimization (PSO) is an optimization method which was first proposed by Eberhart and Kennedy for the simulation of the foraging behavior of the natural biotic populations[7]. The PSO algorithm has been widely concerned and successfully applied in system identification, communication system design, constrained optimization, process optimization, economic management, traffic control, and FIR digital filter design etc. For the monotonic function and strictly convex function or unimodal problems, the optimal solution can be gained rapidly by the algorithm. However, the algorithm depends greatly on the initial values, and the swarm diversity drops rapidly with the increase in the number of iterations, which makes the algorithm unable to jump out of the local extreme points and leads to premature convergence. Thus, its global search capacity is affected, and especially for the high-dimensional multimodal functions, premature phenomena may easily appear. On the basis of the advantages of the chaotic ergodicity of the Cat mapping and the randomness and stable tendency of the cloud model, and, with respect to that, the PSO algorithm has the deficiencies of weakened diversity and slow search speed in the later evolution period, the chaos cloud particle swarm optimization (CCPSO)[8]algorithm is proposed.

The CCPSO-PPPR expressway traffic flow forecasting model, adopting the CCPSO algorithm to search the optimal projection directionain its inner layer while the numberMof the ridge functions is optimized in its outer layer, is established. In the forecasting process, the traffic flows, weather factors and travel dates are taken as the input vectors of the model in the first four time intervals of the forecasting road section. This paper uses actual westbound traffic flow of a section in Henan Changji Expressway to compare the forecasting performance of the proposed CCPSO-PPPR model with the ARIMA model, the PSO-BP neural network model, the conventional SMART-PPR model and the PSO-PPPR model.

1 Parameter Projection Pursuit Regression Model

In 1981, Friedman and Stuetzle et al.[9]proposed the analysis theory of the projection pursuit regression (PPR) with respect to the high-dimensional problem in the multiple regression analysis. The basic idea of the method is that the high-dimensional data are projected to the low-dimensional subspace through some combination and the use of computer technology, and in order to realize the research and analysis goal of the high-dimensional data, the projection, capable of reflecting the structure and characteristics of the original data, is determined through minimization of some projection indices. The principle of the PPR technology is as follows.

(1)

(2)

(3)

(4)

whereadis the projection direction;Qandxidrefer to the number of the impact factors and the value of thek-th impact factor of thei-th input sample, respectively.hij(Zi) in Eq.(3) is the Hermite polynomial and can be calculated as

hij(Zi)=(j!)0.5π0.252(j-1)/2Hj(Zi)φ(Zi)

(5)

and it can be given via the following recursion forms,

(6)

In Eq.(5), the standard Gauss functionφ(Zi) is calculated by

(7)

The optimal projection directionaand the optimal numberMof the ridge function are estimated by solving the following minimization problems:

d=1,2,…,Q;j=0,1,2…,r-1

(8)

The core of building the PPPR model is to solve the projection directiona, the polynomial coefficientscand the numberMof the ridge function, and so the solution to parametersa,candMdetermines the performance of the model to a certain degree. In order to enhance the generalization performance of the PPPR model and improve the forecasting accuracy for the expressway short-term traffic flow, this investigation tries to employ the CCPSO algorithm to determine the projection directionaof the PPPR model.

2 Modified PSO

(10)

(11)

wherewis the inertia weight and is employed to control the influence of the previous history of velocities on the current velocity;c1andc2are the learning factors, which are usually taken as 2, respectively;r1andr2are random numbers distributed uniformly in the range [0,1].

Based on the Cat mapping and the cloud model, the CCPSO algorithm is proposed to improve the optimal performance of the PSO. The procedure of the CCPSO algorithm is illustrated as follows: When the PSO operates for a certain generations mix_gen*gen, the particles of the current swarm are sequenced in view of the fitness values, and divided into pop_distr*pop_size excellent individuals and (1-pop_distr)*pop_size poorer individuals. For the pop_distr*pop_size excellent individuals, the cloud model for local search is adopted to accelerate the algorithm search speed, and for (1-pop_distr)*pop_size poorer individuals, the Cat mapping for implementing global chaos disturbance is used to increase the swarm diversity. On the basis of the above processes, the obtained new pop_distr*pop_size excellent individuals and new (1-pop_distr)*pop_size excellent individuals disturbance are mixed to form a new swarm, which can be used to execute the next evolution operation of the PSO again. The hybrid control parameter mix_gen is employed to control the mixing times of the PSO algorithm, the Cat mapping and the cloud model. The swarm distribution coefficient pop_distr is adopted to determine the distribution ratio of particles for local search and global disturbance during the process of algorithm evolution.

2.1 Global search with the Cat mapping

The chaos optimization method is an optimization technique that has appeared in recent years, which makes use of such properties as chaos ergodicity and sensitivity of initial values as its global optimization mechanism. However, the current PSO algorithm based on the chaos optimization method mostly adopts logistic mapping[10], Tent mapping[11]and An mapping[12]as the chaotic sequence generator. Owing to the fact that the probability density of the chaotic sequence generated by the logistic mapping mostly obeys the Chebyshev distribution with more density values at its both ends and lesser density values in its middle, its acceptance values focus mostly on those in the two ends of the density function. The chaotic sequence of the Tent mapping may rapidly fall into a minor cycle or a fixed point as a result of the limit of the computer’s word length and precision. The chaotic variable quantity of An mapping takes values from small to large and their occurrence number gradually decreases, so that the uniformity of the generated variable quantity is unable to be guaranteed. Therefore, the Cat mapping with good ergodic uniformity and less possibility of falling into a minor cycle or the fixed point is used to the global disturbance of the PSO algorithm.

The two-dimensional Cat mapping equation is

(12)

wherexmod 1=x-[x].

The specific procedure of the global disturbance of the CCPSO algorithm with the Cat mapping is illustrated in Ref.[8].

2.2 Local search with the cloud model

In consideration of the current value being closer to the optimal solution after the evolution of the PSO algorithm for a period of time in the process of searching for the optimal solution, more advantages are available around the local optimal points. According to the social statistics principle[13], the more the optimal point around the local optimal points, the more opportunities of finding the optimal solution in its surrounding. Therefore, in order to improve the convergence speed of the PSO algorithm, the normal cloud model is used to implement the local search for the pop_distr*pop_size excellent individuals in the current population.

Suppose thatTis the value in the discourse domainu, and map CT(x):u→[0,1], ?x∈u,x→CT(x), then the distribution of CT(x) onuis referred to as the membership cloud underT, which is called as “the cloud”, for short. When CT(x) obeys the normal distribution, it is known as the normal cloud model. The overall characteristics of the cloud model can be represented by three digital features, which are the expectationE, the entropySand the hyper-entropyH. The normal cloud generator is employed to realize the local search of the more excellent individuals. The specific procedure of the local search of the CCPSO algorithm with the cloud model is illustrated in Ref.[8].

3 CCPSO-PPPR Expressway Traffic Flow Forecasting Model

In order to improve the optimization efficiency of the CCPSO-PPPR model, the regression serial variance is taken as the fitness value of the individual evolution; that is

(13)

Based on the CCPSO embedded optimal projection directiona, the calculation procedures of the CCPSO-PPPR expressway traffic flow forecasting model are as follows:

Step1The measured data and the initial interval of the PPPR model’s parameters are normalized on the basis of

x(i)=(x(i)-xmin)/(xmax-xmin)

(14)

wherex(i) is thei-th value in the sequence to be treated;xmaxandxminare the maximum and minimum values in the sequence to be treated, respectively.

Set the particle population size pop_size, the acceleration constantsc1andc2, the maximum evolution generation gen, the maximum optimization generation gen*, the population distribution coefficient pop_distr, the mixed control parameter mix_gen, the relative error of the optimal individual fitness valueE, the number of the maximum ridge functionsLmaxand the minimum fitting residual errorεmin.

Step3LetG=1, andg=1.

Step4If the current population meets the evolution stopping criterionR1, go to Step 8; otherwise, go to Step 5. The evolution stopping criterionR1adopts the combination of the maximum evolution generation gen and the relative errorEbetween the optimal individual fitness values of two adjacent generations.

Step5Ifg≤mix_gen*gen, go to Step 6; otherwise, go to Step 7.

(15)

wherewis the renewed weight;wminandwmaxare the minimum and maximum values of inertia weight, respectively. In general, their acceptance values are 0.4 and 0.9, respectively.

Step7The current particles are sequenced according to their fitness values, which divides the whole population into pop_distr*pop_size excellent individuals and (1-pop_distr)*pop_size poorer individuals. The local search for pop_distr*pop_size excellent individuals is done in accordance with Section 2.1, and thus the new pop_distr*pop_size excellent individuals are obtained. The overall chaos disturbance for (1-pop_distr)*pop_size poorer individuals is determined on the basis of Section 2.2, and the new (1-pop_distr)*pop_size excellent individuals after disturbance are obtained. An elite population with the population quantity of pop_size is formed, and the fitness values of the pop_size elite individuals are calculated. LetG=G+1, andg=0, go to Step 4.

Step9The impact factors are input to the PPPR model according to the global optimal parameteraand its corresponding polynomial coefficientc, and the forecast values are computed according to Eq.(9).

The flowchart of the CCPSO-PPPR expressway short-term traffic flow forecasting model is shown in Fig.1.

4 Numerical Examples

4.1 Selection of influencing factors for expressway traffic flow forecasting

The features of traffic flow are similar to those of the fluid features with a continuous distribution in time. The next time interval’s traffic flow in some road section is inevitably correlated with that of the previous several time intervals in the same road section. Therefore, the previous several time intervals’ traffic flow data in this road section can be used to forecast the next time interval’s traffic flow in the same road section. Suppose thattexpresses the current time interval of observing the traffic flow;Y(t-3),Y(t-2),Y(t-1) andY(t) are the first four time intervals’ traffic flows in the forecasted road section, respectively, andY(t+1) is the next time interval’s traffic flow in the same road section mentioned above. So the forecasted result of the traffic flowY(t+1) att+1 is influenced by the combined action of the traffic flowsY(t-3),Y(t-2),Y(t-1) andY(t).

Fig.1 Flowchart of CCPSO-PPPR expressway short-term traffic flow forecasting model

Considering that the travel of the expressway is subjected to the effects of weather changes, the fifth input parameterX1(t) is introduced, which is set to be 1, 0.75, 0.5, 0.25 and 0 for heavy snow or heavy sleet, light snow or light sleet, heavy rain, light rain and fine or cloudy, respectively. Meanwhile, people’s travel habits can also affect the traffic flow on expressways. One week is taken as the forecasting period of the traffic flow, which may have its different variation rules in different days of each week and increase especially on the weekend. Therefore, the travel date is taken as the sixth input parameterX2(t) of the model, which is set to be 1/7, 2/7, 3/7, 4/7, 5/7, 6/7 and 1(7/7) on Monday, Tuesday, Wednesday, Thursday, Friday, Saturday and Sunday, respectively. Thus six influencing factorsX, affecting the next time interval’s traffic flow in the forecasted road section, are obtained as the input vector of the model.

In this paper, the numerical experimental part adopts the partial traffic flow data obtained by using the westbound traffic flow detector on Changji Expressway in Jiyuan City from May 1, 2010 to March 1, 2011, and its sampling interval is 10 min. In order to verify the forecasting performance of the forecasting model under various weather conditions, 500 groups of valid data under various weather conditions are selected, and their quantification processing is implemented for their corresponding weather conditions and sampling dates to form the training sample set of the model. 50 groups of valid data are taken as the testing sample set.

4.2 Example forecasting and performance analysis

In the training process of the CCPSO-PPPR model, its parameters are set as follows: The evaluation range ofais [-1,1]; the Hermite polynomial order isr=4;c1=c2=2.0, pop_size=100; gen=500; mix_gen=0.7, pop_distr=0.7; the maximum ridge function numberLmax=4; the change rate of fitness value of the optimal individual for adjacent generationE=0.01; the minimum fitting residualεmin=0.001.

According to the CCPSO-PPPR hybrid optimization process in Section 3, the combination of parametersa,candMis optimized, and the CCPSO-PPPR hybrid optimization expressway short-term traffic flow forecasting model is finally obtained as follows:

ak4xi4+ak5xi5+ak6xi6)

(16)

where

{akd}2×6=

and

The fitting residual error curves of the first and second ridge functions are shown in Fig.2.As we can see from the two fitting residual error curves in Fig.2 that the second fitting residual error is obviously less than the first fitting residual error; thus the increase in the number of the ridge functions can clearly reduce the fitting error to make the fitting sequence gradually approach the actual sequence.

Fig.2 Fitting residual error curves

The forecasting model obtained through optimization is used for the short-term traffic flow forecasting. The comparison diagram of the actual traffic flow and its traffic flow forecasted by the model is shown in Fig.3, and the actual partial traffic flow and its forecasted results are shown in Tab.1. The comparison results show that the forecasted flow curve basically coincides with its actual traffic flow curve and their error values are controlled within [-6,6] on the whole, except for a few error values.

Fig.3 Comparison diagram of the actual traffic flow and its forecasted traffic flow

In order to test the forecasting performance of the CCPSO-PPPR model proposed in this paper, the ARIMA model, the PSO-BP neural network model, the conventional SMART-PPR model and the PSO-PPPR model are selected simultaneously for model building and simulation forecasting. For ensuring the comparability of the four kinds of models above, they are all programmed by using models above, they are all programmed by using Matlab 7.1 and run on the same computer. The conventional SMART-PPR model is computed with edited SMART software and debugged again and again under the various combinations of the smoothing coefficientS, the maximum terms numberMof the ridge function and the optimal combination term numberMu. WhenS=0.5,M=2 andMu=4, the fitting effect of the model is at its best. Considering that the optimization effect can be improved by increasing the optimizing times, the maximum number of iterations of the PSO-BP and PSO-PPPR models should be the same as the number of iterations of the CCPSO-PPPR model. Meanwhile, for making a comparative analysis on the performances of the three models above, three evaluation indices are adopted as follows.

Tab.1 Excerpt from the forecasted results pcu/10 min

1) Mean absolute relative error (MARE):

(17)

2) Maximum absolute relative error (MAXARE):

(18)

3) Root mean square error (RMSE):

(19)

The testing of five models are implemented according to the given comparison model parameters and the actual traffic flow data, respectively. The forecasting values of the five trained models are calculated by inputting the influence factors. Three kinds of error indices of the five models’ forecasted traffic flow values are shown in Tab.2, which are obtained by using Eqs.(17), (18) and (19).

Tab.2 Comparison of the forecasted error index of five kinds of models

As seen in Tab.2, the ARIMA model, the SMART-PPPR model, the PSO-PPPR model and the CCPSO-PPPR model are obviously superior to the PSO-BP neural network model in forecasting the model’s performance based on different structures, and the forecasting accuracy of the PPPR model based on the PSO algorithm is superior to the SMART-PPPR model which adopts the conventional layer and group iteration alternating optimization method. All evaluation indices of the CCPSO-PPPR model are superior to those of the PSO-PPPR model, and the CCPSO-PPPR model obtains higher forecasting accuracy than that gained by the ARIMA model and the CCPSO-PPPR model.

5 Conclusion

The CCPSO-PPPR expressway short-term traffic flow forecasting model overcomes some shortcomings of the PPPR model regarding the difficulty in selecting model parameters and the low accuracy of the forecasted results, and it improves the generalization and self-study capacities of the PPPR model. In the forecasting process, the influence of such factors as the traffic flow of the first four time intervals of the road section, the weather and the travel dates are comprehensively considered in this paper, and the data assurance can be provided for the accurate forecasting of the traffic flow. The simulation forecasting results for some expressway traffic flow examples show that the forecasting accuracy of the CCPSO-PPPR model is superior to those of the other four models, and the absolute error of the actual and forecasted traffic flow values are basically controlled within [-6,6], which improves the forecasting accuracy of expressway traffic flow and can meet its application requirements. Based on the real-time information of traffic flow data, weather, date etc., the expressway short-term traffic flow may be forecasted dynamically and accurately through continuously updating the model’s parameters. The theoretical proof of the CCPSO-PPPR model and the quantification criteria of its relevant weather and travel date need to be further researched.

[1]Han Chao. Real-time short-term traffic flow adaptive forecasting method based on time series analysis[D]. Beijing: School of Electronic Information and Control Engineering of Beijing University of Technology, 2004: 41-51. (in Chinese)

[2]Lu Jianchang, Niu Dongxiao, Jia Zhengyuan. A study of short-term load forecasting based on ARIMA-ANN [C]//Proceedingsof2004InternationalConferenceonMachineLearningandCybernetics. Shanghai, China, 2004: 3183-3187.

[3]Ye Yan, Lu Zhilin. Neural network short-term traffic flow forecasting model based on particle swarm optimization[J].ComputerEngineeringandDesign, 2009,30(18): 4296-4299. (in Chinese)

[4]Guo Min, Lan Jinhui, Xiao Xiang, et al. Forecasting short-time traffic flow for Beijing and ring road using chaos theory[J].JournalofTransportationSystemsEngineeringandInformationTechnology, 2010,10(2): 107-110.

[5]Friedman J H,Tukey J W. A projection pursuit algorithm for exploratory data analysis[J].IEEETransactionsonComputers, 1974,C-23(9): 881-890.

[6]Diaconis P, Friedman D. Asymptotics of graphical projection pursuit[J].AnnStatis, 1984,12: 793-815.

[7]Kennedy J, Eberhart R C. Particle swarm optimization[C]//Proceedingsofthe1995IEEEInternationalConferenceonNeuralNetworks. Perth, Australia, 1995: 1942-1948.

[8]Li Mingwei, Kang Haigui, Zhou Pengfei, et al. Hybrid optimization algorithm based on chaos, cloud and particle swarm optimization algorithm[J].JournalofSystemsEngineeringandElectronics, 2013,24(2): 324-334.

[9]Friedman J H, Stuetzle W. Projection pursuit regression[J].JAmerStatistAssoc, 1981,76(376): 817-823.

[10]Lü Xiaoming, Huang Kaoli, Lian Guangyao. Optimizing strategy of system level fault diagnosis based on chaos particle swarm optimization[J].SystemsEngineeringandElectronics, 2010,32(1): 217-220.

[11]Sheng Yuxiang, Pan Haitian, Xia Luyue, et al. Hybrid chaos particle swarm optimization algorithm and application in benzene-toluene flash vaporization[J].JournalofZhejiangUniversityofTechnology, 2010,38(3): 319-322. (in Chinese)

[12]Dong Yong, Guo Haimin. Adaptive chaos particle swarm optimization based on colony fitness variance[J].ApplicationResearchofComputers, 2011,28(3): 855-859. (in Chinese)

[13]Zhang Yingjie, Shao Suifeng. Cloud hyper mutation particle swarm optimization algorithm based on cloud model[J].PatternRecognitionandArtificialIntelligent, 2010,24(1): 91-95. (in Chinese)