Regular PapersNo Access

A GRAMMAR-GUIDED GENETIC PROGRAMMING FRAMEWORK CONFIGURED FOR DATA MINING AND SOFTWARE TESTING

SILVIA REGINA VERGILIO

Computer Science Department, Federal University of Parana – UFPR, C.P. 19081, CEP: 81531-970, Curitiba, Brazil

Search for more papers by this author

and

AURORA POZO

Computer Science Department, Federal University of Parana – UFPR, C.P. 19081, CEP: 81531-970, Curitiba, Brazil

Search for more papers by this author

https://doi.org/10.1142/S0218194006002781Cited by:10 (Source: Crossref)

Abstract

Genetic Programming (GP) is a powerful software induction technique that can be applied to solve a wide variety of problems. However, most researchers develop tailor-made GP tools for solving specific problems. These tools generally require significant modifications in their kernel to be adapted to other domains. In this paper, we explore the Grammar-Guided Genetic Programming (GGGP) approach as an alternative to overcome such limitation. We describe a GGGP based framework, named Chameleon, that can be easily configured to solve different problems. We explore the use of Chameleon in two domains, not usually addressed by works in the literature: in the task of mining relational databases and in the software testing activity. The presented results point out that the use of the grammar-guided approach helps us to obtain more generic GP frameworks and that they can contribute in the explored domains.

Keywords:

References

Discipulus Demo CD, AIM Learning Technology, 1998. , http://www.aimlearning.com . Google Scholar
W. Banzhaf et al. , Genetic Programming — An Introduction on the Automatic Evolution of Computer Programs and Its Applications ( Morgan Kaufmann Publishers , 1998 ) . Google Scholar
G. E. D. Box and D. R. Cox, Journal of Statistical Society B 26, 211 (1964). Web of Science, Google Scholar
R. A. De Millo, R. J. Lipton and F. G. Sayward, IEEE Computer 11, 34 (1978). Web of Science, Google Scholar
R. A. De Millo and A. J. Offutt, IEEE Trans. on Software Engineering 17(9), 900 (1991). Web of Science, Google Scholar
M. E. Delamaro and J. C. Maldonado, A tool for the assesment for test adequacy for C programs, Proc. Conf. on Performability in Computing Systems (1996) pp. 79–95. Google Scholar
M. C. F. P. Emer and S. R. Vergilio, Gptest: A testing tool based on genetic programming, Proc. Genetic and Evolutionary Conference — GECCO (Morgan Kaufmann, 2002) pp. 1343–1350. Google Scholar
M. C. F. P. Emer and S. R. Vergilio , Selection and evaluation of test sets based on genetic programming , Proc. Brazilian Symposium on Software Engineering ( 2002 ) . Google Scholar
A. Faye , D. Laurent and N. Spyratos , Learning rules from facts: extraction and update , Proc. 14th European Meeting on Cybernetics and Systems Research ( 1998 ) . Google Scholar
A. P. Fraser, Genetic Programming in C++, Cybernetics Research Institute, TR 0140, University of Salford, 1994. . Google Scholar
L. Gritz, Evolutionary Controller Syntheses 3-D Character Animation, Ph.D. Thesis, Department of Electrical Engineering and Computer Science, The George Washington University, 1999 . Google Scholar
F. Gruau , Advances in Genetic Programming ( MIT Press , 1996 ) . Google Scholar
M. Harman and B. F. Jones, Information and Software Technology 43, 905 (2001). Web of Science, Google Scholar
J. H. Holland , Adaptation in Natural and Artificial Systems ( MIT Press , 1992 ) . Google Scholar
W. E. Howden, IEEE Trans. on Software Engineering 8(4), 371 (1982). Web of Science, Google Scholar
C. Ishida and A. Pozo, GPSQL miner: SQL-grammar genetic programming in data mining, Proc. World Congress on Computational Intelligence (IEEE Press, 2002) pp. 1226–1231. Google Scholar
J. R. Koza , Genetic Programming: On the Programming of Computers by Means of Natural Selection ( MIT Press , Cambridge, MA , 1992 ) . Google Scholar
J. R. Koza , Genetic Programming II: Automatic Discovery of Reusable Programs ( MIT Press , Cambridge, MA , 1994 ) . Google Scholar
T. S. Lim, W. Y. Loh and Y. S. Shih, Machine Learning Journal 40(3), 203 (2000). Web of Science, Google Scholar
R. S. Michalski and K. A. Kaufman, DM and Knowledge Discovery: A Review of Issues and a Multistrategy Approach, Report of the Machine Learning and Inference Laboratory MLI 97-2, George Mason University, Fairfax, VA, 1997 . Google Scholar
D. Michie, S. Muggleton, D. Page and A. Srinivasan, To the International Computing Community: A New East-West Challenge, Technical Report, Oxford University Computing Laboratory, 1994 . Google Scholar
L. J. Morell, Theoretical insights into fault-based testing, Proc. of Workshop on Software Testing, Verification and Analysis (1988) pp. 45–62. Google Scholar
S. Rapps and E. J. Weyuker, IEEE Trans. on Software Engineering 11(4), 367 (1985). Web of Science, Google Scholar
A. Ratle and M. Sebag, Genetic programming and domain knowledge: Beyond the limitations of grammar-guided machine discovery, Proc. VI Parallel Problem Solving from Nature (Springer Verlag, 2000) pp. 211–220. Google Scholar
G. M. Ruppert , Simultaneous Statistical Inference ( Springer-Verlag , New York , 1981 ) . Google Scholar
R. Sethi , Program Languages: Concepts and Constructs ( Addison-Wesley , 1996 ) . Google Scholar
P. A. Whigham, Grammatically based genetic programming, Proc. ML'95 Workshop on Genetic Programming — From Theory to Real-Word Applications (1995) pp. 33–41. Google Scholar
D. Zongker et al., LIL-GP 1.01 User's Manual, Michigan State University, 1996. . Google Scholar