Skip to main content
Search
Search
Quick Search anywhere
Quick Search anywhere
Quick Search anywhere
Quick Search anywhere
Quick Search anywhere
Quick Search anywhere
Advanced Search
Skip main navigation
No Access

Performance comparison of crossover operators for postfix genetic programming

Published Online:October 16, 2014pp 244-264https://doi.org/10.1504/IJMHEUR.2014.065189

Abstract

In this article, we present three crossover operators for postfix-GP, a GP system that adopts postfix notation for an individual representation. These crossover operators are: GA-like one-point, sub-tree, and semantic aware sub-tree. The algorithm and implementation details for each of these crossover operators are presented. The operators are applied on a set of real-valued symbolic regression problems. The performance comparison of the crossover operators is carried out using two measures, number of successful runs and mean best adjusted fitness. The significance of the obtained results is tested using statistical test. The results suggest that semantic aware sub-tree crossover outperforms GA-like one-point and sub-tree crossovers on all problems.

Keywords

GA-like one-point crossover, sub-tree crossover, semantic aware sub-tree crossover, postfix genetic programming, performance comparison

References

  • 1. Altenberg, L. (1994). ‘The evolution of evolvability in genetic programming’. Advances in Genetic Programming. Cambridge, MA, USA:MIT Press , 47-74 Google Scholar
  • 2. Beadle, L. , Johnson, C. (2008). ‘Semantically driven crossover in genetic programming’. IEEE Congress on Evolutionary Computation, 2008, CEC 2008 (IEEE World Congress on Computational Intelligence), 111-116 Google Scholar
  • 3. Dabhi, V. , Chaudhary, S. (2013). ‘Semantic sub-tree crossover operator for postfix genetic programming’. Proceedings of Seventh International Conference on Bio-Inspired Computing: Theories and Applications (BIC-TA 2012). India:Springer , 391-402, Vol. 201 of Advances in Intelligent Systems and Computing Google Scholar
  • 4. Dabhi, V. , Vij, S. (2011). ‘Empirical modeling using symbolic regression via postfix genetic programming’. International Conference on Image Information Processing (ICIIP), 1-6 Google Scholar
  • 5. Dabhi, V.K. , Chaudhary, S. (2014a). ‘Time series modeling and prediction using postfix genetic programming’. 2014 Fourth International Conference on Advanced Computing Communication Technologies (ACCT), 307-314 Google Scholar
  • 6. Dabhi, V.K. , Chaudhary, S. (2014b). ‘Empirical modeling using genetic programming: a survey of issues and approaches’. Natural Computing. 1-28 Google Scholar
  • 7. Ferreira, C. (2001). ‘Gene expression programming: a new adaptive algorithm for solving problems’. Complex Systems. 13, 2, 87-129 Google Scholar
  • 8. García, S. , Molina, D. , Lozano, M. , Herrera, F. (2009). ‘A study on the use of non-parametric tests for analyzing the evolutionary algorithms’ behaviour: a case study on the CEC’2005 special session on real parameter optimization’. Journal of Heuristics. 15, 6, 617-644 Google Scholar
  • 9. Goldberg, D.E. (1989). Genetic Algorithms in Search, Optimization and Machine Learning. 1st ed., Boston, MA, USA:Addison-Wesley Longman Publishing Co., Inc. Google Scholar
  • 10. Gustafson, S. , Burke, E. , Krasnogor, N. (2005). ‘On improving genetic programming for symbolic regression’. 1, The 2005 IEEE Congress on Evolutionary Computation, 912-919 Google Scholar
  • 11. Hengproprohm, S. , Chongstitvatana, P. (2001). ‘Selective crossover in genetic programming’. ISCIT International Symposium on Communications and Information Technologies, ChiangMai Orchid, ChiangMai Thailand Google Scholar
  • 12. Hoai, N.X. , McKay, R.I. , Essam, D. , Chau, R. (2002). ‘Solving the symbolic regression problem with tree-adjunct grammar guided genetic programming: the comparative results’. Proceedings of the 2002 Congress on Evolutionary Computation, 2002, CEC’02. 2, IEEE, 1326-1331 Google Scholar
  • 13. Holland, J.H. (1992). ‘Adaptation in natural and artificial systems: an introductory analysis with applications to biology’. Control and Artificial Intelligence. Cambridge, USA:MIT Press Google Scholar
  • 14. Ito, T. , Iba, H. , Sato, S. (1998). ‘Non-destructive depth-dependent crossover for genetic programming’. Proceedings of the First European Workshop on Genetic Programming, EuroGP ‘98. London, UK:Springer-Verlag , 71-82 Google Scholar
  • 15. Keith, M.J. , Martin, M.C. (1994). ‘Genetic programming in c++: implementation issues’. Advances in Genetic Programming. Cambridge, MA:MIT Press , 285-310, Chapter 13 Google Scholar
  • 16. Koza, J.R. (1992). Genetic Programming: On the Programming of Computers by Means of Natural Selection. Cambridge, MA, USA:MIT Press Google Scholar
  • 17. Langdon, W.B. (2000). ‘Size fair and homologous tree crossovers for tree genetic programming’. Genetic Programming and Evolvable Machines. 1, 1–2, 95-119 Google Scholar
  • 18. Li, X. , Zhou, C. , Xiao, W. , Nelson, P.C. (2005). ‘Prefix gene expression programming’. Late breaking paper at Genetic and Evolutionary Computation Conference (GECCO’2005), Washington, DC, USA, 25-31 Google Scholar
  • 19. Majeed, H. , Ryan, C. (2007). ‘On the constructiveness of context-aware crossover’. Proceedings of the 9th Annual Conference on Genetic and Evolutionary Computation, GECCO ‘07. New York, NY, USA:ACM , 1659-1666 Google Scholar
  • 20. Microsoft (2014). Microsoft.net Framework Software Development Kit. (accessed 13 January 2014), [online] http://msdn.microsoft.com Google Scholar
  • 21. O’Reilly, U-M. , Oppacher, F. (1994). ‘Program search with a hierarchical variable length representation: genetic programming, simulated annealing and hill climbing’. Proceeding of the Third International Conference on Parallel Problem Solving from Nature (PPSN III). 866, Springer, 397-406, Lecture Notes in Computer Science Google Scholar
  • 22. Poli, R. , Langdon, W.B. , Koza, J.R. Banzhaf, W. Chellapilla, K. Deb, K. Dorigo, M. Fogel, D.B. (1998). ‘On the search properties of different crossover operators in genetic programming’. Genetic Programming 1998: Proceedings of the Third Annual Conference. 293-301 Google Scholar
  • 23. Russell, S.J. , Norvig, P. , Canny, J.F. , Malik, J.M. , Edwards, D.D. (1995). Artificial intelligence: a Modern Approach. 74, Englewood Cliffs:Prentice Hall Google Scholar
  • 24. Tokui, N. , Iha, H. (1999). ‘Empirical and statistical analysis of genetic programming with linear genome’. 1999 IEEE International Conference on Systems, Man, and Cybernetics, 1999, IEEE SMC ‘99 Conference Proceedings. 3, 610-615 Google Scholar
  • 25. Uy, N.Q. , Hoai, N.X. , O’Neill, M. (2009a). ‘Semantic aware crossover for genetic programming: the case for real-valued function regression’. Proceedings of the 12th European Conference on Genetic Programming, EuroGP ‘09. Berlin, Heidelberg:Springer-Verlag , 292-302 Google Scholar
  • 26. Uy, N.Q. , Hoai, N.X. , O’Neill, M. (2009b). ‘Semantics based mutation in genetic programming: the case for real-valued symbolic regression’. 9, 15th International Conference on Soft Computing, Mendel, 73-91 Google Scholar
  • 27. Uy, N.Q. , Hoai, N.X. , O’Neill, M. , Mckay, R.I. , Galván-López, E. (2011). ‘Semantically-based crossover in genetic programming: application to real-valued symbolic regression’. Genetic Programming and Evolvable Machines. 12, 2, 91-119 Google Scholar
  • 28. (2014). (accessed 23 January 2014) Zedgraph [online] http://www.sourceforge.net/projects/zedgraph Google Scholar
Previous article