1119Accesses
29Citations
1Altmetric
Abstract
Probabilistic model-building algorithms (PMBA), a subset of evolutionary algorithms, have been successful in solving complex problems, in addition providing analytical information about the distribution of fit individuals. Most PMBA work has concentrated on the string representation used in typical genetic algorithms. A smaller body of work has aimed to apply the useful concepts of PMBA to genetic programming (GP), mostly concentrating on tree representation. Unfortunately, the latter research has been sporadically carried out, and reported in several different research streams, limiting substantial communication and discussion. In this paper, we aim to provide a critical review of previous applications of PMBA and related methods in GP research, to facilitate more vital communication. We illustrate the current state of research in applying PMBA to GP, noting important perspectives. We use these to categorise practical PMBA models for GP, and describe the main varieties on this basis.
This is a preview of subscription content,log in via an institution to check access.
Access this article
Subscribe and save
- Get 10 units per month
- Download Article/Chapter or eBook
- 1 Unit = 1 Article or 1 Chapter
- Cancel anytime
Buy Now
Price includes VAT (Japan)
Instant access to the full article PDF.





Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Notes
In Shan’s survey [107] they were referred to as EDA-GP; we prefer to use the more general terminology PMB-GP, reserving EDA-GP for systems more closely modelled on EDA.
By ‘positional determinacy’, we mean that in generating, or learning from, an individual, the decision over which random variable to use is completely determined by the absolute location of the specific node relative to the root. This concept has been previously used by Shan et al. [107] using the term ‘positional dependence’. Unfortunately their terminology has sometimes led to confusion: particularly in a statistical context, ‘positional dependence’ covers cases where the dependence is probabilistic, rather than deterministic. We use ‘determinate’ to avoid any ambiguity.
From another perspective, a typical GA can be modelled as a PMBA in which crossover and mutation act to change the distribution over the phenotype space [90].
References
H.A. Abbass, X. Hoai, R.I. McKay. AntTAG: A new method to compose computer programs using colonies of ants. In Proceedings of the 2002 IEEE Congress on Evolutionary Computation, vol. 2, Honolulu, HI, USA. (IEEE Press, New York, 2002), p. 1654–1659
P.J. Angeline. Subtree crossover: Building block engine or macromutation? In Genetic Programming 1997: Proceedings of the Second Annual Conference, pages 9–17, Stanford University, CA, USA, 13–16 July 1997. Morgan Kaufmann
P.J. Angeline, J.B. Pollack. Coevolving high-level representations. In Artificial Life III, vol. XVII of Santa Fe Institute Series, pages 55–71, Santa Fe, New Mexico, USA, 15–19 June 1994. Addison-Wesley, USA
S. Baluja. Population-based incremental learning: a method for integrating genetic searching based function optimization. Technical Report CMU-CS-94-163, Computer Science Dept, Carnegie Mellon University, Pittsburgh, PA, USA, 1994
W. Banzhaf. Genetic programming for pedestrians. In Proceedings of the 5th International Conference on Genetic Algorithms, ICGA-93, p. 628, Urbana-Champaign, IL, USA, 17–21 July 1993. Morgan Kaufmann
W. Banzhaf, P. Nordin, R.E. Keller, F.D. Francone. Genetic Programming: An Introduction; On the Automatic Evolution of Computer Programs and Its Applications. Morgan Kaufmann, San Francisco, 1998
H.G. Beyer, An alternative explanation for the manner in which genetic algorithms operate. BioSystems41, 1–15 (1997)
M. Birattari, G. Di Caro, and M. Dorigo. Toward the formal foundation of ant programming. In Proceedings of the Third International Workshop on Ant Algorithms, volume 2463 of Lecture Notes in Computer Science, pages 188–201, Brussels, Belgium September 2002. (Springer, Berlin), p. 12–14
C.M. Bishop, Pattern Recognition and Machine Learning (Information Science and Statistics). (Springer, New York, Inc., Secaucus, 2006)
M. Boryczka, Eliminating introns in ant colony programming. Fundamenta Informaticae68(1-2), 1–19 (2005)
M. Boryczka. Ant colony programming with the candidate list. In Proceedings of the Agent and Multi-Agent Systems: Technologies and Applications, Second KES International Symposium, KES-AMSTA 2008, volume 4953 of Lecture Notes in Computer Science, pp. 302–311, Incheon, Korea, 26–28 March 2008. (Springer, Berlin)
M. Boryczka, Z.J. Czech. Solving approximation problems by ant colony programming. In GECCO 2002: Proceedings of the Genetic and Evolutionary Computation Conference, New York, USA, 9-13 July 2002. (Morgan Kaufmann Publishers), p. 133
P.A.N. Bosman, E.D. de Jong. Grammar transformations in an EDA for genetic programming. In Proceedings of the Optimization by Building and Using Probabilistic Models OBUPM Workshop at the Genetic and Evolutionary Computation Conference—GECCO-2004, Seattle, Washington, USA, June 2004. (Springer, Berlin)
P.A.N. Bosman, E.D. de Jong. Learning probabilistic tree grammars for genetic programming. In Parallel Problem Solving from Nature - PPSN VIII, volume 3242 of Lecture Notes in Computer Science Birmingham, UK, Sep 2004. (Springer, Berlin), p. 192–201
P.A.N. Bosman, D. Thierens. Continuous iterated density estimation evolutionary algorithms within the IDEA framework. In Proceedings of the Optimization by Building and Using Probabilistic Models OBUPM Workshop at the Genetic and Evolutionary Computation Conference (GECCO-2000), Las Vegas, Nevada, USA, 8–12 July 2000. (Morgan Kaufmann, Burlington), p. 197–200
E.K. Burke, M.R. Hyde, G. Kendall, G. Ochoa, E. Ozcan, and J.R. Woodward. Exploring hyper-heuristic methodologies with genetic programming, volume 1 of Intelligent systems Reference Library, chapter 6 Springer, 2009, pp 177–201
J. Clegg. Combining cartesian genetic programming with an estimation of distribution algorithm. In GECCO ’08: Proceedings of the 10th annual conference on Genetic and evolutionary computation, Atlanta, GA, USA, 12-16 July 2008. ACM, p. 1333–1334
N. L. Cramer. A representation for the adaptive generation of simple sequential programs. In Proceedings of an International Conference on Genetic Algorithms and the Applications, Carnegie Mellon University, Pittsburgh, PA, USA, 24-26 July 1985, p. 183–187
A.S. d’Avila Garcez, K. Broda, D.M. Gabbay, Symbolic knowledge extraction from trained neural networks: a sound approach. Artif. Intell.125(1-2), 155–207 (2001)
A.P Dempster, N.M. Laird, D.B. Rubin, Maximum likelihood from incomplete data via the EM algorithm. J. Roy. Statis. Soc. Series B (Methodological)39(1), 1–38 (1977)
M. Dorigo, T. Stützle, Ant Colony Optimization. (MIT Press, Cambridge, MA, 2004)
L. Getoor, B. Taskar, Introduction to Statistical Relational Learning. (The MIT Press, Cambridge, 2007)
A. Geyer-Schulz, Fuzzy Rule-Based Expert Systems and Genetic Machine Learning, volume 3 of Studies in Fuzziness. (Physica-Verlag, Heidelberg, 1995)
D.E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning. (Addison-Wesley, USA, 1989)
J. Green, J.L. Whalley, C.G. Johnson. Automatic programming with ant colony optimization. In Proceedings of the 2004 UK Workshop on Computational Intelligence, UK, 6–8 September 2004. (Loughborough University, Loughborough), pp. 70–77
F. Gruau. Genetic synthesis of modular neural networks. In Proceedings of the 5th International Conference on Genetic Algorithms, ICGA-93, Urbana-Champaign, IL, USA, 17-21 July 1993. (Morgan Kaufmann, Burlington), pp. 318–325
P. Haddawy. Generating bayesian networks from probability logic knowledge bases. In Proceedings of the Tenth Conference on Uncertainty in Artificial Intelligence, Seatle, WA, USA, 29-31 July 1994. (Morgan Kaufmann Publishers Inc, Burlington) pp. 262–269
S. Handley. On the use of a directed acyclic graph to represent a population of computer programs. In Proceedings of the First IEEE Conference on Evolutionary Computation, IEEE World Congress on Computational Intelligence, vol. 1, pp. 154–159, 1994
N. Hansen and A. Ostermeier. Adapting arbitrary normal mutation distributions in evolution strategies: The covariance matrix adaptation. In Evolutionary Computation, 1996., Proceedings of IEEE International Conference on. IEEE, 1996, pp. 312–317
G. Harik, F. Lobo, and K. Sastry. Linkage Learning via Probabilistic Modeling in the Extended Compact Genetic Algorithm (ECGA), volume 33 of Studies in Computational Intelligence. (Springer, Berlin, 2006), pp. 39–61
Y. Hasegawa and H. Iba. Estimation of Bayesian network for program generation. In Proceedings of the Third Asian-Pacific workshop on Genetic Programming, pp. 35–46, Military Technical Academy, Hanoi, VietNam, 2006
Y. Hasegawa and H. Iba. Estimation of distribution algorithm based on probabilistic grammar with latent annotations. In Proceedings of the 2007 IEEE Congress on Evolutionary Computation, Singapore, 25–28 September 2007. IEEE Computational Intelligence Society, IEEE Press, pp. 1043–1050
Y. Hasegawa, H. Iba, A Bayesian network approach to program generation. IEEE Trans. Evol. Comput.12(6), 750–764 (2008)
Y. Hasegawa, H. Iba, Latent variable model for estimation of distribution algorithm based on a probabilistic context-free grammar. IEEE Trans. Evol. Comput.13(4), 858–878 (2009)
E. Hemberg, K. Veeramachaneni, J. McDermott, C. Berzan, and U.M. O’Reilly. An investigation of local patterns for estimation of distribution genetic programming. In GECCO ’12: Proceedings of the fourteenth international conference on Genetic and evolutionary computation conference. ACM, 7-11July 2012, pages 767–774
H. Iba, Y. Hasegawa, T.K. Paul, Genetic Programming and Machine Learning. (CRC Complex and Enterprise Systems Engineering. CRC Press, Boca Raton, 2009)
C.Z. Janikow. Adapting representation in genetic programming. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO 2004), volume 3103 of Lecture Notes in Computer Science. (Springer, Berlin , 2004), pp. 507–518
A.K. Joshi, L.S. Levy, M. Takahashi, Tree adjunct grammars. J. Comput. Syst. Sci.10(1), 136–163 (1975)
W. Kantschik and W. Banzhaf. Linear-tree GP and its comparison with other GP structures. In Genetic Programming, Proceedings of EuroGP’ 2001, volume 2038 of Lecture Notes in Computer Science, Lake Como, Italy, 18–20 April 2001. Springer, Berlin, pp. 302–312
H. Katagiri, K. Hirasama, and J. Hu. Genetic network programming-application to intelligent agents. In 2000 IEEE International Conference on Systems, Man, and Cybernetics, vol 5. IEEE, 8-11 October 2000, pp. 3829–3834
H. Katagiri, K. Hirasawa, J. Hu, and J. Murata. Network structure oriented evolutionary model—genetic network programming–and its comparison with. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2001), San Francisco, California, USA, 7–11 July 2001. (Morgan Kaufmann Publishers Inc., Burlington) p. 179
C. Keber, M. G. Schuster. Option valuation with generalized ant programming. In GECCO 2002: Proceedings of the Genetic and Evolutionary Computation Conference, Newyork, USA, 9–13 July 2002. (Morgan Kaufmann Publishers, Burlington), p. 74–81
K. Kim, B.(R.I.) McKay, D. Punithan. Sampling bias in estimation of distribution algorithms for genetic programming using prototype trees. In PRICAI 2010: 11th Pacific Rim International Conference on AI, volume 6230 of Lecture Notes in Artificial Intelligence. (Springer, Berlin 2010), pp. 100–111
K. Kim, R.I.(Bob) McKay, Stochastic diversity loss and scalability in estimation of distribution genetic programming. IEEE Trans. Evol. Comput.17(3), 301–320 (2013)
D. Koller, N. Friedman, Probabilistic Graphical Models: Principles and Techniques. (The MIT Press, Cambridge, 2009)
J.R. Koza. Genetic programming: A paradigm for genetically breeding populations of computer programs to solve problems. Technical Report STAN-CS-90-1314, Dept. of Computer Science, Stanford University, June 1990
J.R. Koza, Genetic Programming: On the Programming of Computers by Means of Natural Selection. (MIT press, Cambridge, 1992)
W.B. Langdon, R. Poli, Foundations of Genetic Programming. (Springer, Berlin, 2002)
P. Larranaga, Estimation of Distribution Algorithms: A New Tool for Evolutionary Computation (Genetic Algorithms and Evolutionary Computation). (Springer, Berlin, 2001)
P. Larranaga, H. Karshenas, C. Bielza, R. Santana, A review on probabilistic graphical models in evolutionary computation. J. Heuristics18, 795–819 (2012)
P.P. Le, A. Bah, L. H. Ungar. Using prior knowledge to improve genetic network reconstruction from microarray data. In Silico Biology, 4(27), 2004
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 Proceedings of ICROS-SICE International Conference, 2009, Fukuoka, Japan, 18–21August 2009. IEEE, pages 3457–3462
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. In Proceedings of 2010 IEEE Congress on Evolutionary Computation (CEC 2010), Barcelona, Spain, 18–23 July 2010. (IEEE Press, New York) pp. 37–44
X. Liu, Y. Wu, and J. Ye. An improved estimation of distribution algorithm in dynamic environments. In 2008 Fourth International Conference on Natural Computation(ICNC’08), volume 6, p. 269–272, 2008
M. Looks. Scalable estimation-of-distribution program evolution. In Proceedings of the 9th annual conference on Genetic and evolutionary computation, volume 1 of GECCO ’07, London, UK, 7–11 July 2007. (ACM Press, New York) pp. 539–546
M. Looks, B. Goertzel, and C. Pennachin. Learning computer programs with the Bayesian optimization algorithm. In Proceedings of the 2005 conference on Genetic and evolutionary computation, volume 1 of GECCO ’05, pp. 747–748, Washington DC, USA, 25–29 June 2005. ACM Press, New York
C.D. Manning, H. Schutze, Foundations of Statistical Natural Language Processing. (MIT Press, Cambridge, 1999)
T. Matsuzaki, Y. Miyao, and J. Tsujii. Probabilistic CFG with latent annotations. In Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics (ACL’05), Ann Arbor, Michigan, USA, 25-30 June 2005. Association for Computational Linguistics., pp 75–82
N.F. McPhee, B. Ohs, T. Hutchison. Semantic building blocks in genetic programming. In Proceedings of the 11th European conference on Genetic programming, EuroGP 2008, volume 4971 of Lecture Notes in Computer Science, Naples, Italy, 26-28 March 2008. Springer, Berlin p. 134–145
R.S. Michalski, Learnable evolution model: Evolutionary processes guided by machine learning. Mach Learn38, 9–40 (2000)
R.S. Michalski and J. Wojtusiak. The distribution approximation approach to learning from aggregated data. Technical Report MLI 08-2, Reports of the Machine Learning and Inference Laboratory, George Mason University, 2008
J.F. Miller. An empirical study of the efficiency of learning boolean functions using a cartesian genetic programming approach. In Proceedings of the Genetic and Evolutionary Computation Conference, volume 2, Orlando, Florida, USA, 13–17 July 1999. (Morgan Kaufmann Publishers Inc., San Francisco) pp. 1135–1142
J.F. Miller and P. Thomson. Cartesian genetic programming. In Genetic Programming, Proceedings of EuroGP’2000, volume 1802 of Lecture Notes in Computer Science, Edinburgh, UK, 15-16 April 2000. Springer, Berlin, pp121–132
D.J. Montana. Strongly typed genetic programming. BBN Technical Report #7866, Bolt Beranek and Newman, Inc., 10 Moulton Street, Cambridge, MA 02138, USA, 7 May 1993
D.J. Montana, Strongly typed genetic programming. Evol. Comput.3(2), 199–230 (1995)
H. Mühlenbein, J. Bendisch, and H.-M. Voigt. From recombination of genes to the estimation of distributions: II. continuous parameters. In Proceedings of the 4th International Conference on Parallel Problem Solving from Nature, volume 1141 of Lecture Notes in Computer Science, Berlin, Germany, 22-26 September 1996. (Springer, Berlin) pp. 188–197
H. Mühlenbein and G. Paass. From recombination of genes to the estimation of distributions I. binary parameters. In Proceedings of the 4th International Conference on Parallel Problem Solving from Nature, volume 1141 of Lecture Notes in Computer Science, Berlin, Germany, 22-26 September 1996. (Springer, Berlin) pp. 178–187
X.H. Nguyen, R.I. McKay, D. Essam, Representation and structural difficulty in genetic programming. IEEE Trans. Evol. Comput.10(2), 157–166 (2006)
P. Nordin. A compiling genetic programming system that directly manipulates the machine code. In Advances in genetic programming, chapter 14, pp. 311–331. (MIT Press, Cambridge, 1994)
P. Nordin and W. Banzhaf. Complexity compression and evolution. In Genetic Algorithms: Proceedings of the Sixth International Conference (ICGA95), Pittsburgh, PA, USA, 15-19July 1995. (Morgan Kaufmann Publisher Inc., San Francisco), pp. 310–317
P. Nordin, F. Francone, and W. Banzhaf. Explicitly defined introns and destructive crossover in genetic programming. In Peter J. Angeline and K. E. Kinnear, Jr., editors, Advances in Genetic Programming 2, chapter 6. (MIT Press, Cambridge, 1996), pp. 111–134
J.L. Olmo, J. R. Romero, and S. Ventura. A grammar based ant programming algorithm for mining classification rules. In Proceedings of 2010 IEEE Congress on Evolutionary Computation (CEC 2010), Barcelona, Spain, 18–23 July 2010. IEEE Press, pages 225–232
O’Neill M., Ryan C. (2001) Grammatical evolution. IEEE Trans. Evol. Comput. 5(4):349–358
U.M. O’Reilly. An Analysis of Genetic Programming. PhD thesis, Carleton University, Ottawa-Carleton Institute for Computer Science, Ottawa, Ontario, Canada, 22 September 1995
U.M. O’Reilly. Investigating the generality of automatically defined functions. In Genetic Programming 1996: Proceedings of the First Annual Conference, Stanford University, CA, USA, 28–31 July 1996. MIT Press, pages 351–356
U.M. O’Reilly and F. Oppacher. The troubling aspects of a building block hypothesis for genetic programming. In Foundations of Genetic Algorithms 3, Estes Park, Colorado, USA, 31 July–2 August 1994. Morgan Kaufmann Publishers Inc. Published 1995, pages 73–88
A. Ortega, de la M. Cruz, M. Alfonseca, Christiansen grammar evolution: Grammatical evolution with semantics. IEEE Trans. Evol. Comput.11(1), 77–90 (2007)
S.J. Pan, Q. Yang, A survey on transfer learning. IEEE Trans. Know. Data Eng.22(10), 1345–1359 (2010)
M. Pelikan. A simple implementation of bayesian optimization algorithm (boa) in C++ (version 1.0). Technical Report 99011, IlliGAL, University of Illinois at Urbana–Champaign, 1999
M. Pelikan. A C++ implementation of bayesian optimization algorithm with decision graphs. Technical Report 2000025, IlliGAL, University of Illinois at Urbana–Champaign, 2000
M. Pelikan. Implementation of the dependency-tree estimation of distribution algorithm in C++. Technical Report 2006010, IlliGAL, University of Illinois at Urbana–Champaign, 2006
M. Pelikan, D.E. Goldberg. Escaping hierarchical traps with competent genetic algorithms. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO2001), San Francisco, California, July 2001. Morgan Kaufmann Publishers Inc
M. Pelikan, D. E. Goldberg, and E. Cantu-Paz. BOA: The Bayesian optimization algorithm. In Proceedings of the Genetic and Evolutionary Computation Conference GECCO-99, volume 1, Orlando, Florida, USA, 13-17 July 1999. Morgan Kaufamann, pp. 525–532
M. Pelikan, D. E. Goldberg, and F. G. Lobo. A survey of optimization by building and using probabilistic models. In Proceedings of the 2000 American Control Conference, volume 5, Baltimore, MD, USA, 28–30 June 2000, pages 3289–3293
M. Pelikan, D.E. Goldberg, F.G. Lobo, A survey of optimization by building and using probabilistic models. Comput. Optim. Appl.21(1), 5–20 (2002)
M. Pelikan, M. Hauschild, and P. Lanzi. Transfer learning, soft distance-based bias, and the hierarchical boa. In Parallel Problem Solving from Nature - PPSN XII, volume 7491 of Lecture Notes in Computer Science. Springer Berlin Heidelberg, 2012, pages 173–183
Poli R., Langdon W.B. (1998) Schema theory for genetic programming with one-point crossover and point mutation. Evol. Comput. 6(3):231–252
R. Poli and N. F. McPhee. A linear estimation-of-distribution GP system. In Proceedings of the 11th European conference on Genetic Programming, EuroGP 2008, volume 4971 of Lecture Notes in Computer Science, Naples, Italy, 26-28 March 2008. (Springer, Berlin), p. 206–217
A. Ratle and M. Sebag. Avoiding the bloat with probabilistic grammar-guided genetic programming. In Artificial Evolution 5th International Conference, Evolution Artificielle, EA 2001, volume 2310 of Lecture Notes in Computer Science, Creusot, France, 29-31 October 2001. (Springer, Berlin), p. 255–266
C.R. Reeves, J.E. Rowe, Genetic algorithms : principles and perspectives ; a guide to GA theory. (Kluwer, Netherland, 2004)
E.N. Regolin, A.T.R. Pozo. Bayesian automatic programming. In Proceedings of the 8th European Conference on Genetic Programming, EuroGP 2005, volume 3447 of Lecture Notes in Computer Science, Lausane, Switzerland, 30 Mar–1 Apr 2005. (Springer, Berlin, p. 38–49)
J. Rissanen, Modeling by shortest data description. Automatica14(5), 465–471 (1978)
S.A. Rojas, P.J. Bentley. A grid-based ant colony system for automatic program synthesis. In Late Breaking Papers at the 2004 Genetic and Evolutionary Computation Conference, Seattle, Washington, USA, 26 July 2004
J.P. Rosca. Analysis of complexity drift in genetic programming. In Genetic Programming 1997: Proceedings of the Second Annual Conference, Stanford University, CA, USA, 13-16 July 1997. Morgan Kaufmann Publishers Inc., pp. 286–294
J.P. Rosca, D.H. Ballard. Genetic programming with adaptive representations. Technical Report TR 489, University of Rochester, Computer Science Department, Rochester, NY, USA, February 1994
O. Roux, C. Fonlupt. Ant programming: or how to use ants for automatic programming. In Proceedings of the Second International Conference on Ant Algorithms (ANTS2000), Brussels, Belgium, September 2000, p. 121–129
A. Salehi-Abari and T. White. Enhanced generalized ant programming (EGAP). In Proceedings of the 10th annual conference on Genetic and evolutionary computation(GECCO ’10), Portland, Oregon, USA, 7-11 July 2008. ACM New York, pages 111–118
R.P. Salustowicz, J. Schmidhüber, Probabilistic incremental program evolution. Evol. Comput.5(2), 123–141 (1997)
R. Santana, Estimation of distribution algorithms with Kikuchi approximations. Evol. Comput.13(1), 67–97 (2005)
R. Santana, C. Echegoyen, A. Mendiburu, C. Bielza, J. A. Lozano, P. Larraaga, R. Armaanzas, and S. Shakya. Mateda: A suite of EDA programs in Matlab. Technical Report EHU-KZAA-IK-2/09, University of the Basque Country, Feb 2009
R. Santana, R.I. McKay, and J.A. Lozano. Symmetry in evolutionary and estimation of distribution algorithms. In IEEE Congress on Evolutionary Computation, page To Appear. IEEE Computational Intelligence Society, (IEEE Press, New York 2013)
R. Santana, A. Mendiburu, and J.A. Lozano. Structural transfer using EDAs: An application to multi-marker tagging SNP selection. In 2012 IEEE Congress on Evolutionary Computation (CEC), p. 1–8, 2012
K. Sastry, L. de la Ossa, F.G. Lobo. χ–ary extended compact genetic algorithm for matlab in C++. Technical Report 2006013, IlliGAL, University of Illinois at Urbana–Champaign, 2006
K. Sastry, D.E. Goldberg. Probabilistic model building and competent genetic programming. Genetic Programming Theory and Practise, p. 205–220, 2003
Y. Shan, R.I. McKay, H.A. Abbass, D. Essam. Program evolution with explicit learning: a new framework for program automatic synthesis. In Proceedings of the 2003 IEEE Congress on Evolutionary Computation, CEC2003, pages 1639–1646, Canberra, Australia, 8-12 December 2003. University of New South Wales, IEEE Press, New York
Y. Shan, R.I. McKay, R. Baxter, H. Abbass, D. Essam, H.X. Nguyen. Grammar model-based program evolution. In Proceedings of the 2004 IEEE Congress on Evolutionary Computation, Portland, Oregon, USA, 20-23 June 2004. (IEEE Press, New York), p. 478–485
Y. Shan, R. I. McKay, D. Essam, and H. A. Abbass. A survey of probabilistic model building genetic programming. In Scalable Optimization via Probabilistic Modeling: From Algorithms to Applications, volume 33 of Studies in Computational Intelligence, chapter 6. (Springer, Berlin, 2006), p. 121–160
Y. Shan, R. I. McKay, D. Essam, and J. Liu. Modularity and position independence in EDA-GP. In Proceedings of The Second Asian-Pacific Workshop on Genetic Programming, Cairns, Australia, 2004
Y. Shan, R. I. McKay, C. J. Lokan, and D. L. Essam. Software project effort estimation using genetic programming. In Proceedings of the IEEE 2002 International Conference on Communications, Circuits and Systems and West Sino Expositions, volume 2. IEEE, 2002, p. 1108–1112
J.L. Shapiro, Drift and scaling in estimation of distribution algorithms. Evol. Comput.13(1), 99–123 (2005)
J.L. Shapiro. Diversity loss in general estimation of distribution algorithms. In Parallel Problem Solving from Nature, volume 4193 of Lecture Notes in Computer Science, Reykjavik, Iceland, September 2006. Springer, pages 92–101
S. Shirakawa, S. Ogino, T. Nagao, Dynamic ant programming for automatic construction of programs. IEEJ Trans. Elect. Elect. Eng.3(5), 540–548 (2008)
B. Su, Y. Shen. Maximum margin transfer learning. In Proceedings of the first ACM/SIGEVO Summit on Genetic and Evolutionary Computation, GEC ’09, New York, NY, USA, 2009. ACM, pages 957–960
I. Tanev, Genetic programming incorporating biased mutation for evolution and adaptation of snakebot. Genetic Programming and Evolvable Machines8(1), 39–59 (2007)
A. Teller. Evolving programmers: The co-evolution of intelligent recombination operators. In Advances in Genetic Programming 2, chapter 3. (MIT Press, Cambridge, 1996), p. 45–68
A. Teller, M. Veloso. PADO: Learning tree structured algorithms for orchestration into an object recognition system. Technical Report CMU-CS-95-101, Department of Computer Science, (Carnegie Mellon University, Pittsburgh, 1995)
G.G. Towell, J.W. Shavlik, Extracting refined rules from knowledge-based neural networks. Mach. Learn.13(1), 71–101 (1993)
L.G. Valiant. Learning disjunctions of conjunctions. In Proceedings of the Ninth International Joint Conference on Artificial Intelligence, volume 1, Los Angeles, CA, USA, August 1985. (Morgan Kaufmann Publisher Inc., Burlington), pp. 560–566
C.S. Wallace, D.M. Boulton, An information measure for classification. Comput. J.11(2), 185–194 (1968)
P.A. Whigham. Grammatically-based genetic programming. In Proceedings of the Workshop on Genetic Programming: From Theory to Real-World Applications, p. 33–41, Tahoe City, California, USA, 9 July 1995
P.A. Whigham. Inductive bias and genetic programming. In Proceedings of First International Conference on Genetic Algorithms in Engineering Systems: Innovations and Applications, Sheffield, UK, 12-14 September 1995. IEEE, p. 461–466
P.A. Whigham. A schema theorem for context-free grammars. In Proceedings of the 1995 IEEE Conference on Evolutionary Computation, volume 1, Perth, Austrailia, 29 November - 1 December 1995. (IEEE Press, New York) p. 178–181
P.A. Whigham. Grammatical bias for evolutionary learning. PhD thesis, School of Computer Science, University College, University of New South Wales, Australian Defence Force Academy, Canberra, Australia, 1996
P.A. Whigham, R.I. McKay, Genetic approaches to learning recursive relations. Prog. Evol. Comput.956, 17–27 (1995)
G. Wilson, M. Heywood, Introducing probabilistic adaptive mapping developmental genetic programming with redundant mappings. Genet. Program. Evolvable Mach.8(2), 187–220 (2007)
M.L. Wong and K. S. Leung. Applying logic grammars to induce sub-functions in genetic programming. In 1995 IEEE Conference on Evolutionary Computation, volume 2, Perth, Australia, 29 November - 1 December 1995. IEEE Press, pages 737–740
M.L. Wong, K.S. Leung, Genetic logic programming and applications. IEEE Expert10(5), 68–76 (1995)
M.L. Wong, K.S. Leung. An induction system that learns programs in different programming languages using genetic programming and logic grammars. In Proceedings of the 7th IEEE International Conference on Tools with Artificial Intelligence, Herndon, Virginia, USA, 5-8 November 1995
K. Yanai, H. Iba. Estimation of distribution programming based on Bayesian network. In Proceedings of the 2003 IEEE Congress on Evolutionary Computation, CEC2003, Canberra, Australia, 8-12 December 2003. IEEE Press, pages 1618–1625
K. Yanai, H. Iba. Probabilistic model-building genetic programming based on dependency relationship. In Proceedings of The Second Asian-Pacific Workshop on Genetic Programming, Cairns, Australia, 6-7 December 2004
K. Yanai, H. Iba. Program evolution by integrating EDP and GP. In Proceedings of Genetic and Evolutionary Computation—GECCO-2004, Part I, volume 3102 of Lecture Notes in Computer Science, Seattle, WA, USA, 26-30 June 2004. Springer, pages 774–785
K. Yanai, H. Iba. Probabilistic distribution models for EDA-based GP. In GECCO 2005: Proceedings of the 2005 conference on Genetic and evolutionary computation, volume 2, Washington DC, USA, 25-29 June 2005. ACM Press, pages 1775–1776
M. Zlochin, M. Birattari, N. Meuleau, M. Dorigo, Model-based search for combinatorial optimization: A critical survey. Ann. Oper. Res.131(1), 373–395 (2004)
Acknowledgments
This research was supported by the Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education, Science and Technology (Project No. 2012-004841). Xuan Hoai Nguyen was partly funded by The Vietnam National Foundation for Science and Technology Development (NAFOSTED), under Grant Number 102.01–2011.08, for doing this work. The ICT at Seoul National University provided research facilities for this study.
Author information
Authors and Affiliations
Structural Complexity Laboratory, Department of Computer Science and Engineering, Seoul National University, Seoul, Korea
Kangil Kim & R. I. McKay
Australian Government Department of Human Services, Canberra, Australia
Yin Shan
Hanoi University, Hanoi, VietNam
Xuan Hoai Nguyen
- Kangil Kim
You can also search for this author inPubMed Google Scholar
- Yin Shan
You can also search for this author inPubMed Google Scholar
- Xuan Hoai Nguyen
You can also search for this author inPubMed Google Scholar
- R. I. McKay
You can also search for this author inPubMed Google Scholar
Corresponding author
Correspondence toR. I. McKay.
Index
Index
Abbass, Hussein Aly, 6.1.3, 6.3.3
ACP, 6.3.1
Ant Colony Programming, 6.3.1
Ant Programming, 6.1.1
Ant Tree Adjoining Grammar, 6.3.3
AntTAG, 6.3.3
AP, 6.1.1
bACP, 6.3.1
BAP, 6.3.3
Baxter, Rohan, 6.1.3
Bayesian Automatic Programming, 6.3.3
Bentley, Peter J., 6.3.1
Berzan, Constantin, 6.1.2
BOA Programming, 6.3.3
BOAP, 6.3.3
Boryckza Ant Colony Programming, 6.3.1
Boryczka, Mariusz, 6.3.1
Bosman, Peter A. N., 6.1.3
Cartesian Genetic Programming with Estimation of Distribution Algorithms, 6.3.3
CFGR, 6.4
CFGT, 6.1.3
CGP-EDA, 6.3.3
Context Free Grammar Refinement, 6.4
Context Free Grammar Transformation, 6.1.3
Context Sensitive Grammar Refinements, 6.1.3
CSGR, 6.1.3
Czech, Zbigniew J., 6.3.1
DAP, 6.3.1
de Jong, E.D., 6.1.3
Dynamic Ant Programming, 6.3.1
ECGP, 6.1.1
EDP, 6.1.1
EGAP, 6.3.2
Enhanced Generalized Ant Programming, 6.3.2
Essam, Daryl, 6.1.3
Estimation of Distribution Programming, 6.1.1
Extended Compact Genetic Programming, 6.1.1
Fonlupt, Cyril, 6.1.1
GACP, 6.3.1
gACP, 6.3.1
GAP, 6.3.2
GBAP, 6.3.2
Generalized Ant Programming, 6.3.2
Genetic Network Programming with Estimation of Distribution Algorithm, 6.2
GMPE, 6.1.3
GNP-EDA, 6.2
Goertzel, Ben, 6.3.3
Goldberg, David E., 6.1.1
Grammar Based Ant Programming, 6.3.2
Grammar Model-based Program Evolution, 6.1.3
Green Ant Colony Programming, 6.3.1
Green, Jennifer, 6.3.1
Grid-based Ant Colony Programming, 6.3.1
Hasegawa, Yoshihiko, 6.1.1, 6.1.3
Hemberg, Erik, 6.1.2
Heywood, Malcolm, 6.4
Hirasawa, Kotaro, 6.2
Iba, Hitoshi, 6.1.1, 6.1.3
Janet Clegg, 6.3.3
Johnson, Colin G., 6.3.1
Keber, Christian, 6.3.2
Li, Xianneng, 6.2
Looks, Moshe, 6.3.3
Mabu, Shingo, 6.2
McDermott, James, 6.1.2
McKay, Robert I. (Bob), 6.1.3, 6.3.3
McPhee, Nicholas Freitag, 6.3.3
Meta-Optimizing Semantic Evolutionary Search, 6.4
MOSES, 6.4
Moshe Looks, 6.4
N-gram GP, 6.3.3
Nagao, Tomoharu, 6.3.1
Nguyen, Xuan Hoai, 6.1.3, 6.3.3
Nunes Regolin, Evandro, 6.3.3
O’Reilly, Una-May, 6.1.2
OFGP, 6.1.2
Ogino, Shintaro, 6.3.1
Olmo, Juan Luis, 6.3.2
Operator Free Genetic Programming, 6.1.2
PAGE, 6.1.3
PAM-DGP, 6.4
PEEL, 6.1.3
Pennachin, Cassio, 6.3.3
POLE, 6.1.1
Poli, Riccardo, 6.3.3
Probabilistic Adaptive Mapping Developmental Genetic Programming, 6.4
Probabilistic Incremental Program Evolution, 6.1.1
Program Evolution with Explicit Learning, 6.1.3
Program Optimization with Linkage Estimation, 6.1.1
Program with Annotated Grammar Estimation, 6.1.3
Ramirez Pozo, Aurora Trinidad, 6.3.3
Ratle, Alain, 6.1.3
Rojas, Sergio A., 6.3.1
Romero, José Raúl, 6.3.2
Roux, Olivier H., 6.1.1
Salehi-Abari, Amirali, 6.3.2
Salustowicz, Rafal, 6.1.1
Sastry, Kumara, 6.1.1
Scalar Stochastic Grammar-based Genetic Programming, 6.1.3
Schmidhuber, Jürgen, 6.1.1
Schuster, Matthias G., 6.3.2
Sebag, Michèle, 6.1.3
SG-GP, 6.1.3
Shan, Yin, 6.1.3
Shirakawa, Shinichi, 6.3.1
sSG-GP, 6.1.3
Stochastic Grammar-based Genetic Programming, 6.1.3
Tanev, Ivan, 6.1.3
Vectorial Stochastic Grammar-based Genetic Programming, 6.1.3
Veeramachaneni, Kalyan, 6.1.2
Ventura, Sebasti´an, 6.3.2
vSG-GP, 6.1.3
Whalley, Jacqueline L., 6.3.1
Whigham, Peter A., 6.4
White, Tony, 6.3.2
Wilson, Garnett, 6.4
Yanai, Kohsuke, 6.1.1
Rights and permissions
About this article
Cite this article
Kim, K., Shan, Y., Nguyen, X.H.et al. Probabilistic model building in genetic programming: a critical review.Genet Program Evolvable Mach15, 115–167 (2014). https://doi.org/10.1007/s10710-013-9205-x
Received:
Revised:
Published:
Issue Date:
Share this article
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative