Paper:

# Genetic Network Programming with Estimation of Distribution Algorithms for Class Association Rule Mining in Traffic Prediction

## Xianneng Li, Shingo Mabu, Huiyu Zhou,

Kaoru Shimada, and Kotaro Hirasawa

Graduate School of Information, Production and Systems, Waseda University, 2-7 Hibikino, Wakamatsu-ku, Kitakyushu, Fukuoka 808-0135, Japan

Genetic Network Programming (GNP) is one of the evolutionary optimization algorithms, which uses directed-graph structures to represent its solutions. It has been clarified that GNP works well to find class association rules in traffic prediction systems. In this paper, a novel evolutionary paradigm named GNP with Estimation of Distribution Algorithms (GNP-EDAs) is proposed and used to find important class association rules in traffic prediction systems. In GNP-EDAs, a probabilistic model replaces crossover and mutation to enhance the evolution. The new population of individuals is produced from the probabilistic distribution estimated from the selected elite individuals of the previous generation. The probabilistic information on the connections and transitions of GNP-EDAs is extracted from its population to construct the probabilistic model. In this paper, two methods are described to build the probabilistic model for producing the offspring. In addition, a classification mechanism is introduced to estimate the traffic prediction based on the extracted class association rules. We compared GNPEDAs with the conventional GNP and the simulation results showed that GNP-EDAs can extract the class association rules more effectively, when the number of the candidate class association rules increase. And the classification accuracy of the proposed method shows good results in traffic prediction systems.

Kaoru Shimada, and Kotaro Hirasawa, “Genetic Network Programming with Estimation of Distribution Algorithms for Class Association Rule Mining in Traffic Prediction,”

*J. Adv. Comput. Intell. Intell. Inform.*, Vol.14, No.5, pp. 497-509, 2010.

- [1] C. Zhang and S. Zhang, “Association Rule Mining: models and algorithms,” Springer, 2002.
- [2] R. Agrawal and R. Srikant, “Fast Algorithms for Mining Association Rules,” In proc. of the 20th VLDB Conf., pp. 487-499, 1994.
- [3] T. Eguchi, K. Hirasawa, J. Hu, and N. Ota, “A Study of Evolutionary Multiagent Models Based on Symbiosis,” IEEE Trans. on Systems, Man and Cybernetics, Part B, Vol.36, No.1, pp. 179-193, 2006.
- [4] 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.
- [5] 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.
- [6] J. H. Holand, “Andaptation in Natural and Artificial Systems,” Ann-Arbor, University of Michigan Press, 1975.
- [7] D. E. Goldberg, “Genetic Algorithm in Search, Optimization and Machine Learning,” Addison-Wesley, 1989.
- [8] J. R. Koza, “Genetic Programming, on the Programming of Computers by Means of Natural Selection,” MIT Press, 1992.
- [9] J. R. Koza, “Genetic Programming II, Automatic Discovery of Reusable Programs,” MIT Press, 1994.
- [10] K. Shimada, K. Hirasawa, and J. Hu, “Genetic Network Programming with Acquisition Mechanisms of Association Rules,” J. of Advanced Computational Intelligence and Intelligent Informatics, Vol.10, No.1 pp. 102-111, 2006.
- [11] H. Zhou, W. Wei, K. Shimada, S. Mabu, and K. Hirasawa, “Time Related Association Rules Mining with Attribute Accumulation Mechanism and its Application to Traffic Prediction,” J. of Advanced Computational Intelligence and Intelligent Informatics, Vol.12, No.5, pp. 467-478, 2008.
- [12] B. Liu, W. Hsu, and Y. Ma, “Integrating Classification and Association Rule Mining,” In proc. of the ACM Int’l Conf. on Knowledge Discovery and Data Mining, pp. 80-86, 1998.
- [13] H. Zhou, W. Wei, M. K. Mainali, K. Shimada, S. Mabu, and K. Hirasawa, “Class Association Rules Mining with Time Series and Its Application to Traffic Load Prediction,” In proc. of the SICE Annual Conf., pp. 1187-1192, 2008.
- [14] H. Zhou, K. Shimada, S. Mabu, and K. Hirasawa, “Generalized Time Related Sequential Association Rule Mining and Traffic Prediction,” In proc. of the IEEE Congress on Evolutionary Computation 2009, pp. 2654-2661, 2009
- [15] A. K. H. Tung, H. Lu, J. Han, and L. Feng, “Efficient Mining of Intertransaction Association Rules,” IEEE Trans. on Knowledge and Data Engineering, Vol.15, No.1, pp. 43-56, 2003.
- [16] S. Wu and Y. Chen, “Mining Nonambiguous Temporal Patterns for Interval-Based Events,” IEEE Trans. on Knowledge and Data Engineering, Vol.19, No.6, pp. 742-458, 2007.
- [17] C. W. Omlin and C. L. Giles, “Extraction of Rules from Discretetime Recurrent Neural Networks,” Neural Networks, Vol.9, No.1, pp. 41-52, 1996.
- [18] M. Pelikan, D. E. Goldberg, and F. G. Lobo, “A Survey of Optimization by Building and Using Probabilistic Models,” Computational Optimization and Applications, Kluwer Academic Publishers, Vol.21, pp. 5-20, 2002.
- [19] X. Li, S. Mabu, H. Zhou, K. Shimada, and K. Hirasawa, “Genetic Network Programming with Estimation of Distribution Algorithms and its Application to Association Rule Mining for Traffic Prediction,” In proc. of the ICROS-SICE Int’l Conf., pp. 3457-3462, 2009.
- [20] H. Mühlenbein and G. Paaß, “From Recombination of Genes to the Estimation of Distributions I. Binary Parameters,” In proc. of the 4th Conf. on Parallel Problem Solving from Nature, pp. 178-187, 1996.
- [21] S. Baluja, “Population-based Incremental Learning: A Method for Integrating Genetic Search Based Function Optimization and Competitive Leaning,” Tech. Report. No.CMU-CS-94-163, Carnegie Mellon University, 1994.
- [22] P. Larranaga and J. A. Lozano, “Estimation of Distribution Algorithms. A New Tool for Evolutionary Computation,” Kluwer Academic Publishers, 2002.
- [23] S. Baluja, “An Empirical Comparison of Seven Iterative and Evolutionary Function Optimization Heuristics,” Tech. Report. No.CMUCS-95-193, Carnegie Mellon University, 1995.
- [24] S. Baluja and R. Caruana, “Removing the Genetics from Standard Genetic Algorithm,” In proc. of the Int’l Conf. on Machine Learning, pp. 38-46, 1995.
- [25] H. Mühlenbein, “The Equation for Response to Selection and Its Use for Prediction,” Evolutionary Computation, Vol.5, No.3, pp. 303-346, 1997.
- [26] G. R. Harik, F. G. Lobo, and D. E. Goldberg, “The Compact Genetic Algorithm,” In proc. of the IEEE Conf. on Evolutionary Computation, pp. 523-528, 1998
- [27] J. S. De Bonet, C. L. Isbell, and P. Viola, “MMIC: Finding Optima by Estimating Probability Densities,” Advances in Neural Information Processing Systems, MIT press, pp. 424-430, 1997.
- [28] H. Mühlenbein and T. Mahnig, “Convergence Theory and Applications of the Factorized Distribution Algorithm,” J. of Computing and Information Technology, Vol.7, No.1, pp. 19-32, 1999.
- [29] H. Mühlenbein and T. Mahnig, “FDA – a Scalable Evolutionary Algorithm for the Optimization of Additively Decomposed Functions,” Evolutionary Computation, MIT press, Vol.7, No.4, pp. 353-376, 1999.
- [30] H. Mühlenbein, T. Mahnig, and A. R. Ochoa, “Distributions and Graphical Models in Evolutionary Optimization,” J. of Heuristics, pp. 215-247, 1999.
- [31] M. Pelikan, D. E. Goldberg, and E. Cantu-Paz, “Linkage Problem, Distribution Estimation, and Bayesian Networks,” Evolutionary Computation, Vol.8, No.3, pp. 311-341, 2002.
- [32] M. Pelikan, D. E. Goldberg, and E. Cantu-Paz, “The Bayesian Optimization Algorithm,” In proc. of the Genetic and Evolutionary Computation Conference, pp. 525-532, 1999.
- [33] M. Pelikan, “Hierarchical Bayesian Optimization Algorithm: Toward a New Generation of Evolutionary Algorithms,” New York: Springer-Verlag, 2005.
- [34] Q. Zhang, J. Sun, and E. Tsang, “EDA+GA: Evolutionary Algorithm with Guided Mutation for the Maximum Clique Problem,” IEEE Trans. on Evolutionary Computation, Vol.9, No.2, pp. 192-200, 2005.
- [35] Q. Zhang, J. Sun, and E Tsang, “Combinations of Estimation of Distribution Algorithms and Other Techniques,” Int’l J. of Automation & Computing, pp. 273-280, 2007.
- [36] Y. Chen, E. Ohkawa, S. Mabu, K. Shimada, and K. Hirasawa, “A Portfolio Optimization Model using Genetic Network Programming with Control Nodes,” Expert Sytems with Applications, Vol.36, pp. 10735-10745, 2009.