Article

A linear estimation-of-distribution GP system

Authors:

Nicholas F. McPheeAuthors Info & Claims

EuroGP'08: Proceedings of the 11th European conference on Genetic programming

Pages 206 - 217

Published: 26 March 2008 Publication History

Abstract

We present N-gram GP, an estimation of distribution algorithm for the evolution of linear computer programs. The algorithm learns and samples a joint probability distribution of triplets of instructions (or 3-grams) at the same time as it is learning and sampling a program length distribution. We have tested N-gram GP on symbolic regressions problems where the target function is a polynomial of up to degree 12 and lawn-mower problems with lawn sizes of up to 12×12. Results show that the algorithm is effective and scales better on these problems than either linear GP or simple stochastic hill-climbing.

References

[1]

Abbass, H., Hoai, N., McKay, R.: AntTAG: A new method to compose computer programs using colonies of ants. In: IEEE Congress on Evolutionary Computation (2002).

Digital Library

[2]

Baluja, S., Caruana, R.: Removing the genetics from the standard genetic algorithm. In: Prieditis, A., Russell, S. (eds.) Machine Learning: Proceedings of the Twelfth International Conference, pp. 38-46. Morgan Kaufmann Publishers, San Francisco (1995).

[3]

Koza, J.R.: Genetic Programming II: Automatic Discovery of Reusable Programs. MIT Press, Cambridge (1994).

Digital Library

[4]

Larrañnaga, P., Lozano, J.A.: Estimation of Distribution Algorithms, A New Tool for Evolutionary Computation. Kluwer Academic Publishers, Dordrecht (2002).

Digital Library

[5]

Manning, C., Schütze, H.: Foundations of statistical natural language processing. MIT Press, Cambridge (1999).

Digital Library

[6]

Mühlenbein, H., Mahnig, T.: Convergence theory and application of the factorized distribution algorithm. Journal of Computing and Information Technology 7(1), 19-32 (1999).

[7]

Nordin, P.: A compiling genetic programming system that directly manipulates the machine code. In: Kinnear Jr, K.E. (ed.) K, ch. 14, pp. 311-331. MIT Press, Cambridge (1994).

Digital Library

[8]

Poli, R., McPhee, N.F.: A linear estimation-of-distribution GP system. Tech. Report CES- 479, Dept. of Computing and Electronic Systems, University of Essex (January 2008).

[9]

Rabiner, L.: A tutorial on hidden Markov models and selected applications in speech recognition. Proceedings of the IEEE 77(2), 257-286 (1989).

Digital Library

[10]

Ratle, A., Sebag, M.: Avoiding the bloat with probabilistic grammar-guided genetic programming. In: Collet, P., Fonlupt, C., Hao, J.-K., Lutton, E., Schoenauer, M. (eds.) EA 2001. LNCS, vol. 2310, pp. 255-266. Springer, Heidelberg (2002).

Digital Library

[11]

Salustowicz, R.P., Schmidhuber, J.: Probabilistic incremental program evolution. Evolutionary Computation 5(2), 123-141 (1997).

Digital Library

[12]

Sastry, K., Goldberg, D.E.: Probabilistic model building and competent genetic programming. In: Riolo, R.L., Worzel, B. (eds.) Genetic Programming Theory and Practise, ch. 13, pp. 205-220. Kluwer, Dordrecht (2003).

[13]

Shan, Y., McKay, R.I., Abbass, H.A., Essam, D.: Program evolution with explicit learning: a new framework for program automatic synthesis. In: Sarker, R., Reynolds, R., Abbass, H., Tan, K.C., McKay, B., Essam, D., Gedeon, T. (eds.) Proceedings of the 2003 Congress on Evolutionary Computation CEC 2003, Canberra, December 2003, pp. 1639-1646. IEEE Press, Los Alamitos (2003).

[14]

Shan, Y., McKay, R.I., Essam, D., Abbass, H.A.: A survey of probabilistic model building genetic programming. In: Pelikan, M., Sastry, K., Cantu-Paz, E. (eds.) Scalable Optimization via Probabilistic Modeling: From Algorithms to Applications, Springer, Heidelberg (2006).

[15]

Suen, C.Y.: n-gram statistics for natural language understanding and text processing. IEEE Transactions on Pattern Analysis and Machine Intelligence 1(2), 164-172 (1979).

Digital Library

[16]

Yanai, K., Iba, H.: Estimation of distribution programming based on bayesian network. In: Sarker, R., Reynolds, R., Abbass, H., Tan, K.C., McKay, B., Essam, D., Gedeon, T. (eds.) Proceedings of the 2003 Congress on Evolutionary Computation CEC 2003, pp. 1618-1625. IEEE Press, Los Alamitos (2003).

[17]

Yanai, K., Iba, H.: Program evolution by integrating EDP and GP. In: Deb, K., et al. (eds.) GECCO 2004. LNCS, vol. 3102, pp. 774-785. Springer, Heidelberg (2004).

Cited By

Wittenberg DRothlauf FSchweim DCoello Coello C(2020)DAE-GPProceedings of the 2020 Genetic and Evolutionary Computation Conference10.1145/3377930.3390180(1037-1045)Online publication date: 25-Jun-2020
https://dl.acm.org/doi/10.1145/3377930.3390180
Schweim DRothlauf FTakadama K(2018)An analysis of the bias of variation operators of estimation of distribution programmingProceedings of the Genetic and Evolutionary Computation Conference10.1145/3205455.3205582(1191-1198)Online publication date: 2-Jul-2018
https://dl.acm.org/doi/10.1145/3205455.3205582
Sotto Lde Melo VBosman P(2017)A probabilistic linear genetic programming with stochastic context-free grammar for solving symbolic regression problemsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3071178.3071325(1017-1024)Online publication date: 1-Jul-2017
https://dl.acm.org/doi/10.1145/3071178.3071325
Show More Cited By

Recommendations

HMXT-GP: an information-theoretic approach to genetic programming that maintains diversity
SAC '11: Proceedings of the 2011 ACM Symposium on Applied Computing

This paper applies a recent information--theoretic approach to controlling Genetic Algorithms (GAs) called HMXT to tree--based Genetic Programming (GP). HMXT, in a GA domain, requires the setting of selection thresholds in a population and the ...
An Investigation of Geometric Semantic GP with Linear Scaling
GECCO '23: Proceedings of the Genetic and Evolutionary Computation Conference

Geometric semantic genetic programming (GSGP) and linear scaling (LS) have both, independently, shown the ability to outperform standard genetic programming (GP) for symbolic regression. GSGP uses geometric semantic genetic operators, different from ...
Network Optimization based on Genetic Algorithm and Estimation of Distribution Algorithm
CSSE '08: Proceedings of the 2008 International Conference on Computer Science and Software Engineering - Volume 04

Genetic Algorithm (GA) is a kind of algorithm that simulates the process and the mechanism of the evolution. Because of its unique biologic feature and its suitability to any function, it becomes very popular and has been used in many problems in many ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

EuroGP'08: Proceedings of the 11th European conference on Genetic programming

March 2008

374 pages

ISBN:3540786708

Editors:
Michael O'Neill
University College Dublin, Ireland
,
Leonardo Vanneschi
Università degli Studi di Milano-Bicocca, Italy
,
Steven Gustafson
GE Global Research, Niskayuna, NY
,
Anna Isabel Esparcia Alcázar
Instituto Tecnológico de Informática, Valencia, Spain
,
Ivanoe De Falco
ICAR, CNR, Naples, Italy
,
Antonio Della Cioppa
University of Salerno, Italy
,
Ernesto Tarantino
ICAR, CNR, Naples, Italy

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 26 March 2008

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
3
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wittenberg DRothlauf FSchweim DCoello Coello C(2020)DAE-GPProceedings of the 2020 Genetic and Evolutionary Computation Conference10.1145/3377930.3390180(1037-1045)Online publication date: 25-Jun-2020
https://dl.acm.org/doi/10.1145/3377930.3390180
Schweim DRothlauf FTakadama K(2018)An analysis of the bias of variation operators of estimation of distribution programmingProceedings of the Genetic and Evolutionary Computation Conference10.1145/3205455.3205582(1191-1198)Online publication date: 2-Jul-2018
https://dl.acm.org/doi/10.1145/3205455.3205582
Sotto Lde Melo VBosman P(2017)A probabilistic linear genetic programming with stochastic context-free grammar for solving symbolic regression problemsProceedings of the Genetic and Evolutionary Computation Conference10.1145/3071178.3071325(1017-1024)Online publication date: 1-Jul-2017
https://dl.acm.org/doi/10.1145/3071178.3071325
Wong PLo LWong MLeung KArnold D(2014)Grammar-based genetic programming with dependence learning and bayesian network classifierProceedings of the 2014 Annual Conference on Genetic and Evolutionary Computation10.1145/2576768.2598256(959-966)Online publication date: 12-Jul-2014
https://dl.acm.org/doi/10.1145/2576768.2598256
Hemberg EVeeramachaneni KMcDermott JBerzan CO'Reilly UMoore J(2012)An investigation of local patterns for estimation of distribution genetic programmingProceedings of the 14th annual conference on Genetic and evolutionary computation10.1145/2330163.2330270(767-774)Online publication date: 7-Jul-2012
https://dl.acm.org/doi/10.1145/2330163.2330270
Staunton JClark J(2011)Applications of model reuse when using estimation of distribution algorithms to test concurrent softwareProceedings of the Third international conference on Search based software engineering10.5555/2042243.2042260(97-111)Online publication date: 10-Sep-2011
https://dl.acm.org/doi/10.5555/2042243.2042260
Staunton JClark JLanzi P(2011)Finding short counterexamples in promela models using estimation of distribution algorithmsProceedings of the 13th annual conference on Genetic and evolutionary computation10.1145/2001576.2001834(1923-1930)Online publication date: 12-Jul-2011
https://dl.acm.org/doi/10.1145/2001576.2001834
Ghoulbeigi Edos Santos MShin SOssowski SSchumacher MPalakal MHung C(2010)Probabilistic developmental program evolutionProceedings of the 2010 ACM Symposium on Applied Computing10.1145/1774088.1774328(1138-1142)Online publication date: 22-Mar-2010
https://dl.acm.org/doi/10.1145/1774088.1774328
McPhee NCrane ELahr SPoli RRothlauf F(2009)Developmental plasticity in linear genetic programmingProceedings of the 11th Annual conference on Genetic and evolutionary computation10.1145/1569901.1570039(1019-1026)Online publication date: 8-Jul-2009
https://dl.acm.org/doi/10.1145/1569901.1570039
Hasegawa YIba H(2009)Latent variable model for estimation of distribution algorithm based on a probabilistic context-free grammarIEEE Transactions on Evolutionary Computation10.1109/TEVC.2009.201557413:4(858-878)Online publication date: 1-Aug-2009
https://dl.acm.org/doi/10.1109/TEVC.2009.2015574

View Options

View options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents