CN107293120A - A kind of methods of self-tuning of the Algorithm for Traffic Incidents Detection based on genetic algorithm - Google Patents

Abstract

The invention discloses a parameter self-tuning method of a traffic incident detection algorithm based on a genetic algorithm, which includes: first: completing offline tuning of threshold parameters; second: configuring system information; third: capturing system time t; fourth: reading the Traffic flow data; Step 5: Obtain the detection results of each detection cycle; 6: Store the detection results and corresponding traffic flow data in real time; 7: Obtain the current algorithm threshold, estimate and store the traffic incident detection performance in the corresponding time window; Eight: Introduce the forgetting factor λ to calculate the current algorithm performance index; Nine: Determine whether the detection performance of the current algorithm meets the performance requirements. If it meets the performance requirements, the California algorithm parameters will not be updated. If not, return to step 2 to update the information. The present invention aims at problems such as difficult and unreasonable calibration of the threshold value of the California algorithm, and the parameter self-tuning method proposed by the present invention can improve the portability and adaptability of the California algorithm, and improve the overall effect of traffic incident detection.

Description

A Parameter Self-tuning Method of Traffic Incident Detection Algorithm Based on Genetic Algorithm

technical field

The invention relates to the field of intelligent traffic, and in particular to the self-tuning of the parameters of the traffic event detection algorithm by using a genetic algorithm.

Background technique

At present, highways provide people with a comfortable and fast way of life. However, the increasing traffic demand and relatively low road capacity have produced contradictions, resulting in accidental traffic accidents, vehicle breakdowns, and scattered goods on the road. The frequent occurrence of incidents reduces the efficiency of expressways and causes adverse social impacts. It has become an important issue in the operation of expressways. Therefore, the use of event detection methods to detect traffic incidents in a timely and accurate manner is crucial to ensuring the safety of expressways and the travel of the public. Fluency is of great significance.

The traffic incident detection algorithm is the premise and key technology for incident detection, grasping abnormal road operation status and road operation management. Among them, the California algorithm is a classic traffic incident detection algorithm. Because the algorithm has the advantages of simple principle and intuitive process, it has been maturely used in various engineering practices at home and abroad. However, there are still some problems that affect the detection effect in practical applications. However, there are still problems such as difficult and unreasonable calibration of the algorithm threshold, and with the change of external conditions such as road section attributes and traffic environment, the fixed threshold will lead to algorithm detection. The performance is degraded, which leads to the poor adaptability of the algorithm and the increase of the false alarm rate.

At present, the process of determining algorithm parameters is actually to use event and non-event data to test each parameter combination of the algorithm, and obtain a set of values of detection rate, false alarm rate and detection time through statistics. By comprehensively comparing these evaluation values, select Identify the parameters that work best. However, this method of parameter calibration is inefficient and cannot adapt to changes in traffic conditions in a timely manner. Therefore, finding an intelligent method to replace the traditional calibration method can effectively improve the efficiency of threshold determination and improve the adaptability of the algorithm.

Contents of the invention

In view of this, the purpose of the present invention is to provide a parameter self-tuning method of the traffic incident detection algorithm based on the genetic algorithm, allowing the machine to help people adjust the parameters of the California algorithm, and improve its portability, continuous learning ability and adaptability of the algorithm .

The purpose of the present invention is achieved by the following technical solutions, a parameter self-tuning method of the traffic incident detection algorithm based on genetic algorithm, comprising

Step 1: Using historical data, with the performance index of event detection as the target, the genetic algorithm is used to optimize the threshold parameters of the detection algorithm, and the offline tuning of the threshold parameters is completed;

Step 2: Configure system information, including the initial parameters of the algorithm and the performance index requirements that the algorithm needs to meet;

Step 3: capture the system time t, judge whether it is the sampling period, if not, wait;

Step 4: If the time has reached the sampling period, read the traffic flow data in the database, and perform data preprocessing and road segment matching;

Step 5: Start the traffic incident detection algorithm, obtain the detection results of each detection cycle, and perform alarm and release alarm processing according to the detection results;

Step 6: Establish a sliding time window t-m+1, and store the detection results and corresponding traffic flow data in real time, where t is the current time and m is the length of the time window;

Step 7: Obtain the current algorithm threshold, combine the traffic flow data in the time window t-m+1, use the self-tuning condition model based on the event detection performance to estimate the traffic event detection performance effect in the corresponding time window and store it;

Step 8: Introduce the forgetting factor λ, and use the weighted sum of the detection performance results stored in the past to calculate the current algorithm performance index;

Step 9: Judging whether the detection performance of the current algorithm meets the performance requirements, if so, do not update the California algorithm parameters, if not, use the improved genetic algorithm to update the California algorithm parameters until the performance requirements are met, and return to step 2 to update the system information;

Step 10: The current discrimination cycle is over, and the next detection cycle is waiting for arrival.

Further, the genetic algorithm is used to optimize the threshold parameters of the detection algorithm, and the off-line tuning of the threshold parameters is completed, including

Step (1) Transform the solved space into the encoded solution space through the genetic coding strategy;

Step (2) Construct a fitness function according to specific research questions;

Step (3) determines relevant parameters in the algorithm execution process;

Step (4) Randomly generate the initial population, and use the fitness function to evaluate the fitness value of each individual;

Step (5) judges whether to meet the end condition, if it is satisfied, the parameter result is output, and if it is not satisfied, step (6) is executed;

Step (6) Apply selection, replication, crossover and mutation operators to the population to generate a new generation of population; return to step (5).

Further, in the described starting traffic incident detection algorithm, obtain the detection result of each detection period, described traffic incident detection algorithm is:

Step (1) compares the difference between the occupancy rate of the upstream and downstream detectors with the threshold K1, if the difference between the occupancy rates of the upstream and downstream detectors is greater than or equal to the threshold K1, then proceed to step (2), otherwise it is judged that there is no traffic incident;

Step (2) comparing the ratio of the occupancy rate difference between the upstream and downstream detectors to the occupancy rate of the upstream detector with the threshold K2, if the ratio of the occupancy rate difference between the upstream and downstream detectors to the occupancy rate of the upstream detector is greater than or equal to K2, Then proceed to step (3), otherwise judge that there is no traffic incident;

Step (3) Compare the difference between the occupancy rate of the upstream and downstream detectors with the ratio of the occupancy rate of the downstream detector with the threshold K3, if the difference between the occupancy rates of the upstream and downstream detectors is greater than or equal to the threshold K3, it means that there is a traffic incident, otherwise Make no traffic accident judgment.

Further, in the process of estimating and storing the traffic event detection performance effect in the corresponding time window by using the self-tuning condition model based on event detection performance, the acquisition method of the self-tuning condition model based on event detection performance is:

Step (1) select multiple groups of California algorithm thresholds to test, and obtain the relationship between the performance effect of the detection algorithm and the algorithm threshold according to statistics of different spatio-temporal influence factors;

Step (2) Combining the characterization parameters of different spatio-temporal influencing factors, using the multivariate statistical analysis method, establishing a relationship model between spatio-temporal influencing factor parameters, algorithm thresholds and algorithm performance indicators, and realizing real-time estimation of traffic incident detection performance.

Owing to adopting above-mentioned technical scheme, the present invention has following advantage:

The present invention aims at problems such as difficult and unreasonable calibration of the threshold value of the California algorithm, and the parameter self-tuning method proposed by the present invention can improve the portability and adaptability of the California algorithm, and improve the overall effect of traffic incident detection.

Description of drawings

In order to make the purpose, technical solutions and advantages of the present invention clearer, the present invention will be described in further detail below in conjunction with the accompanying drawings, wherein:

Fig. 1 is the flow chart of California algorithm parameter self-tuning system based on genetic algorithm;

Figure 2 is a structure diagram of California algorithm parameter offline tuning;

Fig. 3 is the flow chart of genetic algorithm iterative operation;

Fig. 4 is a graph of the genetic algorithm fitness function curve in the parameter self-tuning process;

Fig. 5 is a traffic incident detection California algorithm flow chart;

Fig. 6 is a structure diagram of California algorithm parameter online tuning;

Figure 7 is a flowchart of online tuning of algorithm parameters.

detailed description

The preferred embodiments of the present invention will be described in detail below in conjunction with the accompanying drawings; it should be understood that the preferred embodiments are only for illustrating the present invention, rather than limiting the protection scope of the present invention.

The flow chart of the parameter self-tuning method of traffic incident detection algorithm based on genetic algorithm is shown in Figure 1. The following is the specific process of implementation:

Step 1. Using historical data and targeting the performance indicators of event detection, the genetic algorithm is used to optimize the threshold parameters of the detection algorithm, and the offline tuning of California algorithm parameters is completed.

Firstly, it is necessary to optimize the initial parameters of the California algorithm by using the genetic algorithm in the offline state, and the parameter offline tuning structure diagram is shown in Figure 2. The flow chart of the iterative operation of the genetic algorithm is shown in Figure 3, and the following steps need to be completed:

(1) Transform the solved space into the encoded solution space through a specific genetic coding strategy.

Genetic algorithm first transforms the solution space into the coded space through genetic coding. Genetic algorithm gene encoding methods include binary encoding, floating-point encoding and symbol encoding. In order to make the operation of the genetic operator easy to realize, the present invention selects the most commonly used binary coding method in the genetic algorithm, wherein the range of values of each parameter to be adjusted, the setting precision and the number of genes should satisfy the relational expression as follows:

U _e -U _s = δ(2 ^k -1)

Among them, U _e -U _s represent the value range of the parameter;

δ represents the value accuracy;

k represents the number of genes.

(2) According to the specific research questions, construct the fitness function;

The present invention selects three event detection performance indexes (DR—detection rate, FAR—false alarm rate, MTTD—average detection time) as the fitness function of the genetic algorithm. The multi-objective problem is transformed into a single-objective problem solution. Common methods include weighted summation method, ε-constraint method, minimum-maximum method and step method, etc. The present invention adopts the most commonly used weighted summation method to convert the multi-objective optimization problem Each sub-objective in is transformed into a single objective in the form of linear combination to optimize the solution.

The fitness function is shown in the following formula:

f=α*DR+β*(1-FAR)+γMTTD'

Among them, MTTD′ is the normalized MTTD. Since MTTD has dimensions, it cannot be directly synthesized with DR and FAR, so it is normalized;

α is the weight of the detection rate DR, β is the weight of (1-FAR), γ is the weight of MTTD′, and the three weights satisfy α+β+γ=1.

The greater the weight in the formula, the greater the role of the corresponding component in the fitness function. According to the importance of performance indicators, different weights are assigned to each component in the fitness function. The present invention initially sets α=β=γ=1/3.

(3) Determine the relevant parameters in the algorithm process, such as the number of iterations and population size and other inheritance;

Before the genetic algorithm performs the optimization process, it is necessary to set parameters such as the length l of the individual code string, the number of populations M, the initial crossover rate p _c0 , the initial mutation rate p _m0 , and the number of termination iterations T.

The individual code string length l in the present invention can be determined as 24 by the expected solution precision; For the optimization problem of the present invention, the analysis population number M is crucial to the operating speed of the algorithm, but too small or too large is easy to occur Premature phenomenon; the crossover rate will affect the global search ability of the algorithm; the mutation rate within a certain range can protect the existing good patterns in the population; the number of termination iterations T is generally 100-1000. Therefore, through experiment analysis, it is found that the parameters of the present invention are set population number M=50, initial crossover rate p _c0 =0.9, initial mutation rate p _m0 =0.001, and termination iteration number T=250.

(4) Randomly generate the initial population, and use the fitness function to evaluate the fitness value of each individual;

Generate the initial population, use the fitness function constructed in step (2) to calculate the fitness value of each individual in the initial population, calculate the average fitness function value, and select the best fitness function value.

(5) Judging whether the end condition is satisfied, if it is satisfied, the parameter result is output, and if it is not satisfied, step (6) is performed;

The end condition of the genetic algorithm in the off-line tuning process of the California algorithm threshold parameter proposed by the present invention is that the event detection performance index is within a certain range, that is, the detection rate is greater than 60%, and the false alarm rate is less than 10%, and the genetic algorithm is optimized, that is, the calculation The change values of the optimal fitness function value and the average fitness function value of the adjacent two generations are not more than 0.1%.

(6) Apply operation operators such as selective replication, crossover and mutation to the population to generate a new generation of population; return to step (5).

There are three main types of genetic operators, including:

1) Select the copy operator

In the genetic algorithm, the selection and replication operation embodying the "survival of the fittest" guides the population to continuously evolve in the direction of adapting to the environment, so the selection and replication operation is the most basic operation of the genetic algorithm. The present invention selects the random competitive selection replication operator to carry out the selective replication operation, and determines the probability of the individual being selected and replicated in the process of generating the next generation population by calculating the proportion of the fitness of the individual to the sum of the fitness of all individuals in this generation . The selected probability calculation formula of the individual designed in the present invention is shown in the following formula:

Among them, p _i is the probability of individual i surviving;

f _i is the fitness of the individual;

I is the population number.

2) Crossover operator

The genetic algorithm crossover operation can retain the excellent genes in the parent individuals and generate more new individuals, which is a basic operation of the genetic algorithm. In this paper, single-point crossover is selected for the crossover operation of genes. Single-point crossover pairs individuals in pairs, and randomly selects the position of a certain gene as the crossover point for the paired individuals according to a random number. Part of the genes of two individuals are exchanged to produce a new individual. Due to the increase in the number of evolutions in the later stage of evolution, the population is gradually approaching the optimal solution, and the convergence process is delayed. Therefore, the present invention designs an adaptive crossover rate, as shown in the following formula:

p _c ＝p _c0 -(p _c0 -p _cmin )*d/D

Among them, p _c0 is the initial crossing rate;

p _cmin is the minimum crossing rate;

d is the current number of evolutions;

D is the total evolution times.

3) Mutation operator

In the genetic algorithm, the mutation operation of changing some gene bits can produce many new individuals, which is a basic operation of the genetic algorithm. The present invention selects the basic bit mutation operation, and the basic bit mutation determines the variation point through the variation probability, and then inverts the gene value of each variation point to generate a new individual. In order to make the variation of the gene change within its allowable range, and to speed up the convergence speed of the algorithm, the present invention designs and adopts the following adaptive mutation rate:

Among them, p _m0 is the initial mutation rate;

p _mmin is the minimum mutation rate;

is the average fitness of the current population;

is the maximum fitness of the group so far.

The fitness function curve of the genetic algorithm in the offline tuning process of California algorithm parameters based on the genetic algorithm is shown in Figure 4.

Step 2. Configure system information, including the initial parameters of the algorithm and the performance index requirements that the algorithm needs to meet.

The configuration includes the traffic incident detection system information such as the initial parameters of the algorithm and the performance index requirements that the algorithm needs to meet.

Step 3. Capture system time

The system program captures the system time t, judges whether the sampling period is reached, and waits if it is not.

Step 4: Read the traffic flow data in the database, and perform preprocessing and link matching on the traffic flow data.

Obtain the traffic data of the upstream and downstream detectors of the detected road section, and perform data preprocessing. Through the vehicle detector data provided by the Expressway Group, the average speed of the vehicle within 5 minutes of the detection section, the code of the vehicle detector, and the driving direction can be directly obtained. The definition of expressway traffic data fields is shown in Table 1:

Table 1: Freeway traffic data field definition table

Step 5: Start the traffic incident detection algorithm, obtain the detection results of each detection cycle, and perform alarm and release alarm operations based on the detection results.

The traffic incident detection algorithm module adopts the California algorithm, and uses the algorithm flow shown in Figure 5 to calculate the event detection results of the detection cycle.

Specifically, the traffic event detection algorithm is:

Step (1) compares the difference between the occupancy rate of the upstream and downstream detectors with the threshold K1, if the difference between the occupancy rates of the upstream and downstream detectors is greater than or equal to the threshold K1, then proceed to step (2), otherwise it is judged that there is no traffic incident;

Step (2) comparing the ratio of the occupancy rate difference between the upstream and downstream detectors to the occupancy rate of the upstream detector with the threshold K2, if the ratio of the occupancy rate difference between the upstream and downstream detectors to the occupancy rate of the upstream detector is greater than or equal to K2, Then proceed to step (3), otherwise judge that there is no traffic incident;

Step (3) Compare the difference between the occupancy rate of the upstream and downstream detectors with the ratio of the occupancy rate of the downstream detector with the threshold K3, if the difference between the occupancy rates of the upstream and downstream detectors is greater than or equal to the threshold K3, it means that there is a traffic incident, otherwise Make no traffic accident judgment.

Among them, OCC(i,t) represents the occupancy rate of the upstream detector, and OCC(i+1,t) represents the occupancy rate of the downstream detector.

Step 6. Store traffic flow data and detection results in real time

Establish a sliding time window t-m+1 (t is the current time, m is the length of the time window), store the detection results and corresponding traffic flow data in real time, store a new set of data each time, and delete the oldest set of data at the same time The data.

Step 7. Estimate the detection performance effect in real time

Obtain the threshold of the current algorithm, combined with the traffic flow data in the time window t-m+1, use the self-tuning condition model based on the event detection performance to estimate the traffic event detection performance effect in the corresponding time window and store it.

In the use of the self-tuning condition model based on the event detection performance to estimate and store the traffic incident detection performance effect in the corresponding time window, the acquisition method of the self-tuning condition model based on the event detection performance is:

Step (1) select multiple groups of California algorithm thresholds to test, and obtain the relationship between the performance effect of the detection algorithm and the algorithm threshold according to statistics of different spatio-temporal influence factors;

Step (2) Combining the characterization parameters of different spatio-temporal influencing factors, using the multivariate statistical analysis method, establishing a relationship model between spatio-temporal influencing factor parameters, algorithm thresholds and algorithm performance indicators, and realizing real-time estimation of traffic incident detection performance.

Step 8, the detection performance weighted summation.

Introduce the forgetting factor λ, and use the weighted sum of the detection performance results stored in the past to calculate the current algorithm performance index.

Step 9: Use the real-time data to complete the online tuning of the parameters of the California algorithm.

Judging whether the detection performance of the current algorithm meets the performance requirements, if yes, do not update the parameters of the California algorithm, if not, use the improved genetic algorithm to update the parameters of the California algorithm until the performance requirements are met and return to step 2 to update the system information.

Step 10. Alarm handling

Alarm and release alarm processing, alarm when an event occurs or when an event is released;

Step 11. Wait for the detection cycle

The current discrimination period is over, waiting for the arrival of the next detection period.

The above descriptions are only preferred embodiments of the present invention, and are not intended to limit the present invention. Obviously, those skilled in the art can make various changes and modifications to the present invention without departing from the spirit and scope of the present invention. Thus, if these modifications and variations of the present invention fall within the scope of the claims of the present invention and equivalent technologies thereof, the present invention also intends to include these modifications and variations.

Claims (4)

1. a kind of methods of self-tuning of the Algorithm for Traffic Incidents Detection based on genetic algorithm, it is characterised in that：Including

Step one：Using historical data, using the performance indications of event detection as target, using genetic algorithm to detection algorithm threshold value Parameter carries out optimizing, completes the off-line setting calculation of threshold parameter；

Step 2：Configure system information, including the performance indications requirement that algorithm initial parameter and algorithm need to be met；

Step 3：Capture systems time t, judged whether to the sampling period, less than then waiting；

Step 4：If having timed out the sampling period, the traffic flow data in reading database, line number of going forward side by side Data preprocess and road Section matching；

Step 5：Start Algorithm for Traffic Incidents Detection, the testing result of each detection cycle is obtained, according to testing result, if having Traffic events then carry out alert process, and releasing alert process is carried out if without traffic events；

Step 6：Time slip-window t-m+1, real-time storage testing result and corresponding traffic flow data are set up, wherein, t is to work as Preceding time, m is the length of time window；

Step 7：The traffic flow data in current algorithm threshold value, binding time window t-m+1 is obtained, using based on event detection The Self-tuning System condition model of energy is estimated the traffic incidents detection impact of performance in correspondence time window and stored；

Step 8：Forgetting factor λ is introduced, using the detection results of property weighted sum stored in the past, current algorithm is calculated Can index；

Step 9：Judge whether the detection performance of current algorithm meets performance requirement, California is not updated if meeting Algorithm parameter, California algorithm parameters are updated until meeting performance requirement if being unsatisfactory for using Revised genetic algorithum Untill and return to step two update system information；

Step 10：It is current to differentiate end cycle, wait next detection cycle to arrive.

2. a kind of methods of self-tuning of Algorithm for Traffic Incidents Detection based on genetic algorithm according to claim 1, It is characterized in that：The use genetic algorithm carries out optimizing to detection algorithm threshold parameter, completes the off-line setting calculation of threshold parameter, Including

Step (1) is by gene code strategy, by the spatial transformation solved into the solution space after coding；

Step (2) constructs fitness function according to specifically studying a question；

Step (3) determines the relevant parameter during algorithm performs；

Step (4) is randomly generated initial population, and the fitness value of each individual is evaluated with fitness function；

Step (5) judges whether to meet termination condition, if met with regard to output parameter result, if being unsatisfactory for being carried out step (6)；

Step (6) will select duplication, intersection and mutation operation operator to act on population, generation population of new generation；Return to step (5)。

3. a kind of methods of self-tuning of Algorithm for Traffic Incidents Detection based on genetic algorithm according to claim 1, It is characterized in that：In the startup Algorithm for Traffic Incidents Detection, the testing result for obtaining each detection cycle, the traffic thing Part detection algorithm is：

The difference of upstream and downstream detector occupation rate and threshold k 1 are compared by step (1), if the upstream and downstream detector occupation rate Difference be more than or equal to threshold k 1, then carry out step (2), otherwise make no traffic events and judge；

The ratio between the difference of upstream and downstream detector occupation rate and upstream detector occupation rate are compared by step (2) with threshold k 2, if The ratio between difference and upstream detector occupation rate of the upstream and downstream detector occupation rate are more than or equal to K2, then carry out step (3), otherwise Make to judge without traffic events；

The ratio between the difference of upstream and downstream detector occupation rate and downstream detector occupation rate are compared by step (3) with threshold k 3, if The difference of the upstream and downstream detector occupation rate is more than or equal to threshold k 3, then it represents that has traffic events, otherwise makees no traffic events and sentence It is disconnected.

4. the Self-tuning System condition model according to claim 1 based on event detection performance, it is characterised in that：In the profit The traffic incidents detection impact of performance in correspondence time window is estimated with the Self-tuning System condition model based on event detection performance and is deposited Chu Zhong, the Self-tuning System condition model acquisition methods based on event detection performance are：

Step (1) is chosen multigroup California algorithms threshold value and tested, and is examined for different space-time influence factors statistics The impact of performance of method of determining and calculating and the relation of algorithm threshold value；

Step (2) combines the characterization parameter of different space-time influence factors, using Multivariate Analysis, sets up space-time influence factor The relational model of parameter, algorithm threshold value and algorithm performance index, realizes the real-time estimation of the traffic incidents detection impact of performance.