Top > JACIII > Genetic Network Programming with Estimation of Distribution Al ...

single-jc.php

JACIII Vol.14 No.5 pp. 497-509
doi: 10.20965/jaciii.2010.p0497
(2010)

Paper:

Views over last 60 days: 607

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

Received:
November 10, 2009
Accepted:
April 26, 2010
Published:
July 20, 2010
Creative Commons License
Keywords:
genetic network programming, estimation of distribution algorithms, class association rule mining, traffic prediction
Abstract
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.
Cite this article as:
X. Li, S. Mabu, H. Zhou, K. Shimada, and K. 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.
Data files:
References
  1. [1] C. Zhang and S. Zhang, “Association Rule Mining: models and algorithms,” Springer, 2002.
  2. [2] R. Agrawal and R. Srikant, “Fast Algorithms for Mining Association Rules,” In proc. of the 20th VLDB Conf., pp. 487-499, 1994.
  3. [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. [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. [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. [6] J. H. Holand, “Andaptation in Natural and Artificial Systems,” Ann-Arbor, University of Michigan Press, 1975.
  7. [7] D. E. Goldberg, “Genetic Algorithm in Search, Optimization and Machine Learning,” Addison-Wesley, 1989.
  8. [8] J. R. Koza, “Genetic Programming, on the Programming of Computers by Means of Natural Selection,” MIT Press, 1992.
  9. [9] J. R. Koza, “Genetic Programming II, Automatic Discovery of Reusable Programs,” MIT Press, 1994.
  10. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [22] P. Larranaga and J. A. Lozano, “Estimation of Distribution Algorithms. A New Tool for Evolutionary Computation,” Kluwer Academic Publishers, 2002.
  23. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [33] M. Pelikan, “Hierarchical Bayesian Optimization Algorithm: Toward a New Generation of Evolutionary Algorithms,” New York: Springer-Verlag, 2005.
  34. [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. [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. [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.

Creative Commons License  This article is published under a Creative Commons Attribution-NoDerivatives 4.0 Internationa License.

*This site is desgined based on HTML5 and CSS3 for modern browsers, e.g. Chrome, Firefox, Safari, Edge, Opera.

Last updated on Oct. 01, 2024