World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.
Special Issue on Selected Papers from the 20th Annual IEEE International Conference (ICTAI-2008); Guest Editor: Soon M. ChungNo Access


    Tree encodings of programs are well known for their representative power and are used very often in Genetic Programming. In this paper we experiment with a new data structure, named straight line program (slp), to represent computer programs. The main features of this structure are described, new recombination operators for GP related to slp's are introduced and a study of the Vapnik-Chervonenkis dimension of families of slp's is done. Experiments have been performed on symbolic regression problems. Results are encouraging and suggest that the GP approach based on slp's consistently outperforms conventional GP based on tree structured representations.


    • J. R.   Koza , Genetic Programming: On the Programming of Computers by Means of Natural Selection ( The MIT Press , Cambridge MA , 1992 ) . Google Scholar
    • W.   Banzhaf et al. , Genetic Programming – An Introduction: On the Automatic Evolution of Computer Programs and its Applications ( Morgan Kaufmann , 1998 ) . CrossrefGoogle Scholar
    • N. L. Cramer, A Representation for the Adaptive Generation of Simple Sequential Programs, Proceedings of the First International Conference on Genetic Algorithms (IGA'85), ed. J. Grefenstette (Lawrence Erlbaum Associates, 1985) pp. 183–187. Google Scholar
    • W. Banzhaf, Genetic Programming for Pedestrians, Proceedings of the Fifth International Conference on Genetic Algorithms (IGGA'93), ed. S. Forrest (Morgan Kaufmann, 1993) p. 638. Google Scholar
    • P. Nordin, Advances in Genetic Programming, ed. K. E. Kinnear (MIT Press, Cambridge MA, 1994) pp. 311–331. Google Scholar
    • M.   Brameier and W.   Banzhaf , Linear Genetic Programming ( Springer , 2007 ) . Google Scholar
    • P.   Bürguisser , M.   Clausen and M. A.   Shokrollahi , Algebraic Complexity Theory ( Springer , 1997 ) . CrossrefGoogle Scholar
    • S. J. Berkowitz, Information Processing Letters 18, 147 (1984), DOI: 10.1016/0020-0190(84)90018-8. Crossref, ISIGoogle Scholar
    • K. Mulmuley, Combinatorica 7, 101 (1995), DOI: 10.1007/BF02579205. Crossref, ISIGoogle Scholar
    • N. Fitchas, A. Galligo and J. Morgenstern, Delon, Dickman Gongard Seminar. Sélection déxposes 1986-1987 32 (Publications Mathematiques de l'Université, Paris, 1987) pp. 103–145. Google Scholar
    • J. Heintz, M. F. Roy and P. Solerno, Bulletin de la Societé Mathematique de France 118, 101 (1990). Crossref, ISIGoogle Scholar
    • M. Giusti and J. Heintz, Algorithms- disons rapide- pour la décomposition dúna varieté algébrique en composants irreductibles et équidimensionelles, Papers for the symposium: Effective Methods in Algebraic Geometry (MEGA'90), eds. T. Mora and C. Traverso (Birkhäuser, 1990) pp. 169–194. Google Scholar
    • M. Giusti and J. Heintz, La détermination des points isolés et la dimension dúne varité algebrique peut se faire en temps polynomial, Computational Algebraic Geometry and Commutative Algebra, Symposia Matematica XXXIV, eds. D. Eisenbud and L. Robbiano (Cambridge University Press, 1993) pp. 216–256. Google Scholar
    • M. Giustiet al., Journal of Pure and Applied Algebra 124, 121 (1997). Google Scholar
    • J. L. Montaña and L. M. Pardo, Appl. Algebra Engrg. Comm. Comput. 4(1), 1 (1993). Crossref, ISIGoogle Scholar
    • A. Topchy and W. F. Punch, Faster genetic programming based on local gradient search of numeric leaf values, Proc. of Genetic and Evolutionary Computation Conference (GECCO 2001), eds. L. Spectoret al. (Morgan Kaufmann, 2001) pp. 155–162. Google Scholar
    • L. Vanneschiet al., Heterogeneous Cooperative Coevolution: Strategies of Integration between GP and GA, Proc. of the 8th Annual Conference on Genetic and Evolutionary Computation (GECCO 2006), ed. M. Keijzer (ACM, 2006) pp. 361–368. Google Scholar
    • A. Eiben and M. Jelasity, A critical note on experimental research methodology in EC, Proc. of the Congress on Evolutionary Computation (CEC 2002) (IEEE Computer Society, 2002) pp. 582–587. Google Scholar
    • T.   Bäck , Evolutionary Algorithms in Theory and Practice ( Oxford University Press , Oxford , 1996 ) . CrossrefGoogle Scholar
    • V. Vapnik and A. Chervonenkis, Automation and Remote Control 34, 1226 (1974). Google Scholar
    • V. Vapnik and A. Chervonenkis, Theory of Probability and its Applications 16, 264 (1971), DOI: 10.1137/1116025. Crossref, ISIGoogle Scholar
    • V.   Vapnik , Statistical Learning Theory ( John Willey & Sons , 1998 ) . Google Scholar
    • G. Lugosi, A Pattern Classification and Learning Theory (Springer, 2002) pp. 5–62. CrossrefGoogle Scholar
    • P. Goldberg and M. Jerrum, Machine Learning 18, 131 (1995). ISIGoogle Scholar
    • J. L. Montaña, VCD bounds for some GP genotypes, Proc. on the 18th European Conference on Artificial Intelligence (ECAI 2008), ed. M. Ghallab (IOS Press, 2008) pp. 167–171. Google Scholar
    • C. L. Alonso and J. L. Montaña, Finiteness properties of some families of GP-trees, 12th Conference of the Spanish Association for Artificial Intelligence (CAEPIA 2007), eds. D. Borrajo, M. Castillo and J. M. Corchado (Springer, 2007) pp. 190–199. Google Scholar
    • V. Cherkasskyet al., IEEE Transactions on Neural Networks 10(5), 1075. Crossref, ISIGoogle Scholar