Abstract
The application of Genetic Programming to the discovery of empirical laws is often impaired by the huge size of the search space, and consequently by the computer resources needed. In many cases, the extreme demand for memory and CPU is due to the massive growth of non-coding segments, the introns. The paper presents a new program evolution framework which combines distribution-based evolution in the PBIL spirit, with grammar-based genetic programming; the information is stored as a probability distribution on the grammar rules, rather than in a population. Experiments on a real-world like problem show that this approach gives a practical solution to the problem of introns growth.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
J. R. Koza. Genetic Programming: On the Programming of Computers by means of Natural Evolution. MIT Press, Massachusetts, 1992.
W. Banzhaf, P. Nordin, R.E. Keller, and F.D. Francone. Genetic Programming–An Introduction On the Automatic Evolution of Computer Programs and Its Applications. Morgan Kaufmann, 1998.
B. McKay, M.J. Willis, and G.W. Barton. Using a tree structures genetic algorithm to perform symbolic regression. In IEEE Conference publications, n. 414, pages 487–492, 1995.
J. Duffy and J. Engle-Warnick. Using symbolic regression to infer strategies from experimental data. In Evolutionary Computation in Economics andFinance. Springer Verlag, 1999.
N. J. Radcliffe. Equivalence class analysis of genetic algorithms. Complex Systems, 5:183–20, 1991.
C. Z. Janikow. A knowledge-intensive genetic algorithm for supervised learning. Machine Learning, 13:189–228, 1993.
A. Ratle and M. Sebag. Genetic programming and domain knowledge: Beyond the limitations of grammar-guided machine discovery. In M. Schoenauer et al., editor, Proceedings of the 6 th Conference on Parallel Problems Solving from Nature, pages 211–220. Springer-Verlag, LNCS 1917, 2000.
F. Gruau. On using syntactic constraints with genetic programming. In P.J. Angeline and K.E. Kinnear Jr., editors, Advances in Genetic Programming II, pages 377–394. MIT Press, 1996.
P.A. Whigham. Inductive bias and genetic programming. In IEEE Conference publications, n. 414, pages 461–466, 1995.
W. B. Langdon and R. Poli. Fitness causes bloat. In Soft Computing in Engineering Design and Manufacturing, pages 13–22. Springer Verlag, 1997.
S. Baluja and R. Caruana. Removing the genetics from the standard genetic algorithms. In A. Prieditis and S. Russel, editors, Proceedings of ICML95, pages 38–46. Morgan Kaufmann, 1995.
R. Salustowicz and J. Schmidhuber. Evolving structured programs with hierarchical instructions and skip nodes. In J. Shavlik, editor, Proceedings of the 15 th International Conference on Machine Learning, pages 488–496. Morgan Kaufmann, 1998.
David J. Montana. Strongly typed genetic programming. Evolutionary Computation, 3(2):199–230, 1995.
C. Ryan, J.J. Collins, and M. O’Neill. Grammatical evolution: Evolving programs for an arbitrary language. In W. Banzhaf, R. Poli, M. Schoenauer, and T.C. Fogarty, editors, Genetic Programming, First European Workshop, EuroGP98, volume LNCS 1391, pages 83–96. Springer Verlag, 1998.
M. Sebag and A. Ducoulombier. Extending population-based incremental learning to continuous search spaces. In Th. Bäck, G. Eiben, M. Schoenauer, and H.-P. Schwefel, editors, Proceedings of the 5 th Conference on Parallel Problems Solving from Nature, pages 418–427. Springer Verlag, 1998.
P. Larranaga and J. A. Lozano. Estimation of Distribution Algorithms. A New Tool for Evolutionary Computation. Kluwer Academic Publishers, 2001.
P. Nordin, W. Banzhaf, and F.D. Francone. Introns in nature and in simulated structure evolution. In D. Lundh, B. Olsson, and A. Narayanan, editors, Biocomputing and Emergent Computation, pages 22–35. World Scientific, 1997.
Byoung-Tak Zhang and Heinz Mühlenbein. Balancing accuracy and parsimony in genetic programming. Evolutionary Computation, 3(1):17–38, 1995.
I.M. Ward. Mechanical Properties of SolidPolymers. Wiley, Chichester, 1985.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-VerlagBerlin Heidelberg
About this paper
Cite this paper
Ratle, A., Sebag, M. (2002). Avoiding the Bloat with Stochastic Grammar-Based Genetic Programming. In: Collet, P., Fonlupt, C., Hao, JK., Lutton, E., Schoenauer, M. (eds) Artificial Evolution. EA 2001. Lecture Notes in Computer Science, vol 2310. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-46033-0_21
Download citation
DOI: https://doi.org/10.1007/3-540-46033-0_21
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43544-0
Online ISBN: 978-3-540-46033-6
eBook Packages: Springer Book Archive