Traffic Flow Prediction with Genetic Network Programming (GNP)
Huiyu Zhou, Shingo Mabu, Wei Wei, Kaoru Shimada,
and Kotaro Hirasawa
Graduate School of Information, Production and Systems, Waseda University, Hibikino 2-7, Wakamatsu-ku, Kitakyushu, Fukuoka 808-0135, Japan,
In this paper, a method for traffic flow prediction has been proposed to obtain prediction rules from the past traffic data using Genetic Network Programming (GNP). GNP is an evolutionary approach which can evolve itself and find the optimal solutions. It has been clarified that GNP works well especially in dynamic environments since GNP is consisted of directed graph structures, creates quite compact programs and has an implicit memory function. In this paper, GNP is applied to create a traffic flow prediction model. And we proposed the spatial adjacency model for the prediction and two kinds of models for N-step prediction. Additionally, the adaptive penalty functions are adopted for the fitness function in order to alleviate the infeasible solutions containing loops in the training process. Furthermore, the sharing function is also used to avoid the premature convergence.
and Kotaro Hirasawa, “Traffic Flow Prediction with Genetic Network Programming (GNP),” J. Adv. Comput. Intell. Intell. Inform., Vol.13, No.6, pp. 713-725, 2009.
-  I. Kaysi, M. Ben-Akiva, and H. Koutsopoulos, “An Integrated Approach to Vehicle Routing and Congestion Predictions for Real-time Driver Guidance,” Transportation Research Records, 1408, Transportation Research Board, Washington D.C., pp. 66-74, 1993.
-  P. J. Lingras and P. Osborne, “Effect of noise on regression and neural network predictions,” In Proc. of the Conf. of Canadian Society of Civil Engineers, Sherbrooke, Quebec, June, pp. 331-339, 1997.
-  J. G. Wardrop, “Some theoretical aspects of road traffic research,” Proc., Institute of Civil Engineers, PART II, Vol.1, pp. 325-378.
-  A. S. Schulz and N. E. Stier-Moses, “On the performance of user equilibria in traffic networks,” In Proc. of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Baltimore, MD, pp. 86-87, SIAM, Philadelphia, PA, 2003.
-  D. Joksimovic, M. Bliemler, and P. Bovy, “Optimal toll design problem in dynamic traffic networks with joint route and departure time choice,” In Proc. of the 84th Annual Meeting of the Transportation Research Board, Washington, DC., 2005.
-  U. S. Alspector, Patent 4,874,963, “Neuromorphic learning networks,” October 17, 1989.
-  S. Mabu, K. Hirasawa, and J. Hu, “A Graph-Based Evolutionary Algorithm: Genetic Network Programming (GNP) and Its Extension Using Reinforcement Learning,” Evolutionary Computation, MIT Press, Vol.15, No.3, pp. 369-398, 2007.
-  T. Eguchi, K. Hirasawa, J. Hu, and N. Ota, “Study of evolutionary multiagent models based on symbiosis,” IEEE Trans. Syst., Man and Cybern. B, Vol.36, No.1, pp. 179-193, 2006.
-  K. Hirasawa, T. Eguchi, J. Zhou, L. Yu, and S. Markon, “A Double-Deck Elevator Group Supervisory Control System Using Genetic Network Programming,” IEEE Trans. on Systems, Man and Cybernetics, Part C, Vol.38, No.4, pp. 535-550, 2008/7.
-  D. W. Coit, A. E. Smith, and D. M. Tate, “Adaptive penalty methods for genetic optimization of constrained combinatorial problems,” INFORMS J. on Computing, Vol.8, No.2, pp. 173-182, 1996.
-  A. E. Smith and D. W. Coit, “Penalty functions,” In T. Back, D. B. Fogel and Z. Michalewicz (Eds.), Handbook on Evolutionary Computation, pages C5.2:1.6., Oxford University Press, 1997.
-  D. E. Goldberg and J. Richardson, “Genetic algorithms with sharing for multimodal function optimization,” In Proc. of the 2nd Int. Conf. on genetic algorithms, ICGA 2, Cambridge, Massachusetts, USA, July 1987, Lawrence Erlbaum Associates, Hillsdale, New Jersey, pp. 41-49, 1987.
-  J. H. Holland, “Adaptation in Natural and Artificial Systems,” Ann Arbor, University of Michigan Press, 1975.
-  D. E. Goldberg, “Genetic Algorithm in search, optimization and machine learning,” Addison-Wesley, 1989.
-  J. R. Koza, “Genetic Programming, on the programming of computers by means of natural selection,” Cambridge, Mass., MIT Press, 1992.
-  J. R. Koza, “Genetic Programming II, Automatic Discovery of Reusable Programs,” Cambridge, Mass., MIT Press, 1994.
-  M. K. Mainali, K. Shimada, S. Mabu, and K. Hirasawa, “Optimal Route of Road Networks by Dynamic Programming,” In Proc. of the IEEE World Congress on Computational Intelligence 2008 (WCCI2008), pp. 3416-3420, 2008.