Automatic freeway incident detection system and method using artificial neural network and genetic algorithms

• US 6,470,261 B1
• Filed: 01/16/2001
• Issued: 10/22/2002
• Est. Priority Date: 07/31/1998
• Status: Expired due to Term

• Current Assignee: Cet Technoloiges Pte., Ltd. (Singapore Technologies Engineering Limited)
• Original Assignee: Cet Technoloiges Pte., Ltd. (Singapore Technologies Engineering Limited)
• Inventors: Ng, Kim Chwee, Ng, Yew Liam
• Primary Examiner(s): Beaulieu, Yonel
• Application Number:
  US09/743,992
• Time in Patent Office: 644 Days
• Field of Search: 701/117-119, 701/301, 701/302, 340/901, 340/903, 340/905, 340/425.5, 706/15, 706/13
• US Class Current: 701/117
• CPC Class Codes: G06N 3/086 using evolutionary algorithms, e.g. genetic algorithms or genetic programming
• CPC Class Codes: G06V 10/82 using neural networks
• CPC Class Codes: G06V 20/54 of traffic, e.g. cars on the road, trains or boats

Abstract

Design of a neural network for automatic detection of incidents on a freeway is described. A neural network is trained using a combination of both back-propagation and genetic algorithm-based methods for optimizing the design of the neural network. The back-propagation and genetic algorithm work together in a collaborative manner in the neural network design. The training starts with incremental learning based on the instantaneous error and the global total error is accumulated for batch updating at the end of the training data being presented to the neural network. The genetic algorithm directly evaluates the performance of multiple sets of neural networks in parallel and then use the analyzed results to breed new neural networks that tend to be better suited to the problems at hand.

Claims

1. An automatic traffic incident detection system for identifying the presence or absence of incidents of traffic congestion, comprising:

sensors for acquiring traffic data;

a data server for collecting and storing the traffic data acquired from the sensors;

an incident detection processor connected to the data server, the incident detection processor including at least one neural network for evaluating the traffic data to determine the incident status for that time instance; and

a neural network design system for updating the at least one neural network used by the incident detection processor in incident determinations, the neural network design system receiving the traffic data as input and utilizing both a global search and a local search for optimizing the design of the updated neural network.

2. The automatic traffic incident detection system of claim 1 further comprising a simulation system for receiving traffic data stored in the data server and generating therefrom simulated traffic data with pre-defined incident occurrences, such that the neural network design system receives the simulated traffic data as input in optimizing the design of the updated neural network.

3. The automatic traffic incident detection system of claim 1 wherein the traffic data input to the neural network design system is formatted as rows of data set instances that include incident status, traffic volume at time instances collected at an upstream traffic measurement station, occupancy at time instances collected at an upstream traffic measurement station, traffic volume at time instances collected at a downstream measurement location, and occupancy at time instances collected at a downstream traffic measurement location.

4. The automatic traffic incident detection system of claim 1 wherein the neural network design system generates an initial population of neural network design candidates encoded in chromosomes, each candidate being assigned with a fitness value obtained from evaluation of performance, and performs a genetic evolution process of genetic reproduction on the candidates with the implementation of both the local and global searches until a stop criterion is reached to yield an updated neural network.

5. The automatic incident detection system of claim 1 wherein the incident detection processor implements a neural network by deriving neural network parameters from a coded chromosome optimized by the neural network design system, each configuration of the neural network with its associated connection weights being stored in the chromosome, whereupon a decoding function is performed to reconstruct the neural network and the traffic data at each time instance is evaluated by performing forward pass and error computation functions to assert the incident status.

6. The automatic incident detection system of claim 5 wherein neural network design parameters of the coded chromosome are stored in a binary file after being optimized and then later are input to the incident detection system for updating the neural network by replacing the existing chromosome for the neural network.

7. The automatic traffic incident detection system of claim 1 wherein the neural network design system generates an initial population of neural network design candidates encoded in chromosomes, each candidate being assigned with a fitness value obtained from evaluation of performance, and performs a genetic evolution process of genetic reproduction on the candidates until a stop criterion is reached to yield an updated neural network, the genetic evolution process being implemented by computer program instructions comprising:

(i) instructions for generating an initial population of neural network design candidates encoded in chromosomes, each candidate being assigned with a fitness value obtained from evaluation of performance;

(ii) instructions for ranking the initial neural network design candidates from best to worst and for maintaining a global record of the best fitness neural network design candidate so far maintained;

(iii) instructions for performing mating population selection operations followed by crossover and mutation operations on the selected neural network design candidates to generate a new population of neural network design candidates, so that a global search has been executed via the rank-based selection, crossover and mutation operations;

(iv) instructions for decoding each chromosome in the new population to construct a neural network and for performing at least one epoch of a back propagation training operation, so that the local search has been executed and weights of the neural network'"'"'s connections are modified;

(v) instructions for evaluating the fitness of the back-propagated neural network design candidates and, for previously decoded chromosomes, encoding design parameters back into chromosomes each having associated therewith an assigned fitness value, so that a new population of neural network design candidates is generated;

(vi) instructions for performing a generation gap operation that selects candidates from both previous and new populations of neural network design candidates that will survive into the next evolution; and

(vii) instructions for repeating the evolution process of genetic reproduction until a stop criterion is reached.

8. The neural network design system of claim 7, whereupon the instructions for performing at least one back propagation training operation include instructions for implementing both batch and incremental learning schemes.

9. The neural network design system of claim 7, whereupon the instructions for performing at least one back propagation training operation include instructions for performing at least one epoch of back propagation training for the best neural network design candidate so far maintained from the population previous to the new population.

10. The neural network design system of claim 7, whereupon the instructions for evaluating the fitness of the back propagated neural network design candidates include instructions for performing an actual implementation task to compute, for the neural network candidate, performance with new connection weights.

11. A computer program embodied on a computer readable medium for implementation on a computer system that automatically identifies the presence or absence of incidents of traffic congestion at given time instances, the program optimizing the design of a neural network that evaluates traffic data to determine incident status, the program comprising instructions for performing the steps of:

(i) generating an initial population of neural network design candidates encoded in chromosomes, each candidate being assigned with a fitness value obtained from evaluation of performance;

(ii) ranking the initial neural network design candidates from best to worst and for maintaining a global record of the best fitness neural network design candidate so far maintained;

(iii) performing mating population selection operations followed by crossover and mutation operations on the selected neural network design candidates to generate a new population of neural network design candidates, so that a global search has been executed via the rank-based selection, crossover and mutation operations;

(iv) performing a back propagation training operation on the neural network design candidates, so that a local search has been executed and weights of the neural network'"'"'s connections are modified to generate a new population of neural network design candidates;

(v) evaluating the fitness of the back-propagated neural network design candidates and assigning thereto a fitness value;

(vi) performing a generation gap operation that selects candidates from the new population and previous populations of neural network design candidates that will survive into the next evolution; and

(vii) repeating the evolution process of genetic reproduction from step (ii) to step (vi) until a stop criterion is reached.

12. The program of claim 11, wherein the step of performing at least one back propagation training operation includes for implementing both batch and incremental learning schemes.

13. The program of claim 11, wherein the step of performing at least one back propagation training operation includes instructions for performing at least one epoch of back propagation training for the best neural network design candidate so far maintained from the population previous to the new population.

14. The program of claim 11, wherein the step of evaluating the fitness of the back propagated neural network design candidates includes performing an actual implementation task to compute, for the neural network candidate, performance with new connection weights.

15. A method for identifying the presence or absence of incidents of traffic congestion at selected time instances, comprising the steps of:

acquiring traffic data;

storing the acquired traffic data;

using at least one neural network for evaluating the traffic data to determine the incident status for a particular time instance; and

updating the at least one neural network utilizing both a global search and a local search for optimizing the design of the neural network.

16. The method of claim 15 further comprising the steps of receiving traffic data stored in a data server and generating therefrom simulated traffic data with pre-defined incident occurrences, such that the simulated traffic data is used as input in optimizing the design of the updated neural network.

17. The method of claim 15 wherein the traffic data is formatted as rows of data set instances that include incident status, traffic volume at time instances collected at an upstream traffic measurement station, occupancy at time instances collected at an upstream traffic measurement station, traffic volume at time instances collected at a downstream measurement location, and occupancy at time instances collected at a downstream traffic measurement location.

18. The method of claim 15 wherein the step of updating the neural network further comprising the steps of:

(i) generating an initial population of neural network design candidates encoded in chromosomes, each candidate being assigned with a fitness value obtained from evaluation of performance;

(ii) ranking the initial neural network design candidates from best to worst and for maintaining a global record of the best fitness neural network design candidate so far maintained;

(iii) performing mating population selection operations followed by crossover and mutation operations on the selected neural network design candidates to generate a new population of neural network design candidates, so that the global search has been executed via the rank-based selection, crossover and mutation operations;

(iv) performing a back propagation training operation on the neural network design candidates, so that the local search has been executed and weights of the neural network'"'"'s connections are modified to generate a new population of neural network design candidates;

(v) evaluating the fitness of the back-propagated neural network design candidates and assigning thereto a fitness value;

(vi) performing a generation gap operation that selects candidates from the new population and previous populations of neural network design candidates that will survive into the next evolution; and

(vii) repeating the evolution process of genetic reproduction from step (ii) to step (vi) until a stop criterion is reached.

19. A method for constructing a chromosome string to code the architecture of a neural network used in an automatic traffic incident detection system for identifying the presence or absence of incidents of traffic congestion, and for determining the weight of each connection between neurons of the neural network, the method comprising the steps of;

i) defining a maximum number of genes in the chromosome used for the number of hidden layers to be in the neural network;

ii) defining the maximum number of genes in the chromosome used for the number of neurons to be in each hidden layer;

iii) defining the maximum number of genes in the chromosome used for the existence of each particular neuron in each hidden layer;

iv) defining the maximum number of genes in the chromosome used for the choice between three types of activation functions to be used in each neuron of the neural network;

v) defining the maximum number of genes in the chromosome used for the weight of connections to neurons;

vi) defining the maximum number of genes in the chromosome used for the choice of the existence of each connection between neurons;

vii) defining the maximum number of genes in the chromosome used for the choice of the existence of input variables or input nodes; and

viii) coding the maximum network configuration and parameters into a chromosome.

20. A method for identifying the presence or absence of incidents of traffic congestion at selected time instances, comprising the steps of:

storing acquired traffic data;

utilizing a global search and a local search genetic algorithm technique for optimizing the design of a neural network to be used in evaluating the traffic data;

evaluating the traffic data using the neural network to determine the incident status for a particular time instance, the neural network being implemented by deriving neural network parameters from a coded chromosome optimized by the genetic algorithm technique, performing a decoding function to reconstruct the neural network, and performing forward pass and error computation functions to assert the incident status.