Logic-based Genetic Programming with Definite Clause Translation Grammars
Inhaltsverzeichnis
Reference
Brian J. Ross: Logic-based Genetic Programming with Definite Clause Translation Grammars. New Generation Computing, v.19, n.4, 2001, pp. 313-337.
DOI
http://dx.doi.org/10.1007/BF03037572
http://link.springer.com/article/10.1007%2FBF03037572
Abstract
DCTG-GP is a genetic programming system that uses definite clause translation grammars. A DCTG is a logical version of an attribute grammar that supports the definition of context-free languages, and it allows semantic information associated with a language to be easily accommodated by the grammar. This is useful in genetic programming for defining the interpreter of a target language, or incorporating both syntactic and semantic problem-specific constraints into the evolutionary search. The DCTG-GP system improves on other grammar-based GP systems by permitting nontrivial semantic aspects of the language to be defined with the grammar. It also automatically analyzes grammar rules in order to determine their minimal depth and termination characteristics, which are required when generating random program trees of varied shapes and sizes. An application using DCTG-GP is described.
Extended Abstract
Bibtex
Used References
Abramson, H. and Dahl, V.,Logic Grammars, Springer-Verlag, 1989.
Alonso, L. and Schott, R.,Random Generation of Trees, Kluwer Academic Publishers, 1995.
Angluin, D., “Computational Learning Theory: Survey and Selected Bibliography,” inProc. of the 24th Annual ACM Symposium on the Theory of Computing, ACM Press, pp. 351–369, 1992.
Banzhaf, W., Nordin, P., Keller, R.E., and Francone, F. D.,Genetic Programming: An Introduction, Morgan Kaufmann, 1998.
Böhm, W. and Geyer-Schulz, A., “Exact Uniform Initialization for Genetic Programming,” inFoundations of Genetic Algorithms 4 (Belew, R. K. and Vose, M., eds.), Morgan Kaufmann, 1997.
Brave, S., “Evolving Deterministic Finite Automata using Cellular Encoding,” inProc. of Genetic Programming 1997 (Koza, J. R.,eaet al, ed.), Stanford University, CA, USA, Morgan Kaufmann, pp. 39–44, 1997.
Charniak, E.,Statistical Language Learning, MIT Press, 1993.
Clocksin, W. F. and Mellish, C. S.,Programming in Prolog (4th ed), Springer-Verlag, 1994.
Cousot, P., “Abstract Interpretation,”ACM Computing Surveys, 28, 2, pp. 324–328, 1996. http://dx.doi.org/10.1145/234528.234740
Dupont, P., “Regular Grammatical Inference from Positive and Negative Samples by Genetic Search: the GIG Method,” in2nd Intl. Coll. on Grammatical Inference and Applications, Springer-Verlag, pp. 236–245, 1994.
Freeman, J. J., “A Linear Representation for GP using Context Free Grammars,” inProc. of Genetic Programming 1998 (Koza, J. R.et al., ed.), Morgan Kaufmann, pp. 72–77, 1998.
Fu, K. S. and Booth, T. L., “Grammatical Inference: Introduction and Survey-Part I,”IEEE Transactions on Systems, Man, and Cybernetics, 5, 1, pp. 95–111, 1975.
Garg, V. K., Kumar, R. and Marcus, S. I., “Probabilistic Language Framework for Stochastic Discrete Event Systems,”Technical Report 96-18, Institute for Systems Research, University of Maryland, April 1996, http://www.isr.umc.edu/.
Geyer-Schulz, A., “Fuzzy Rule-Based Expert Systems and Genetic Machine Learning,”Studies in Fuzziness and Soft Computing, 3, 2nd revised edition, Physica-Verlag, Heidelberg, 1996.
Geyer-Shulz, A., “The Next 700 Programming Languages for Genetic Programming,” inProc. of Genetic Programming 1997 (Koza, J. R.,et al, ed.), Stanford University, CA, USA, Morgan Kaufmann, pp. 128–136, 1997.
Gruau, F., On Using Syntactic Contraints with Genetic Programming. inAdvances in Genetic Programming II (Angeline, P. J. and Kinnear, K. E., eds.), MIT Press, pp. 377–394, 1996.
Haynes, T. D., Schoenefeld, D. A. and Wainwright, R. L., “Type Inheritance in Strongly Typed Genetic Programming,” inAdvances in Genetic Programming II (Angeline, P. J. and Kinnear, K. E., editors), MIT Press, pp. 359–375, 1996.
Holland, J. H.,Adaption in Natural and Artificial Systems, MIT Press, 1992.
Hopcroft, J. E. and Ullman, J. D.,Introduction to Automata Theory, Languages, and Computation, Addison Wesley, 1979.
Hussain, T. S. and Browse, R. A., “Attribute Grammars for Genetic Representations of Neural Networks and Syntactic Constraints of Genetic Programming, inAIVIGI’98: Workshop on Evolutionary Computation, 1998.
Iba, H., “Random Tree Generation for Genetic Programming,” inParallel Problem Solving from Nature IV (Voigt, H.-M. Ebeling, W., Rechenberg, I. and Schwefel, H.-P., eds.),Proc. of the International Conference on Evolutionary Computation, Springer-Verlag, pp. 144–153, 1996.
Jacob, C., “Evolving Evolution Programs: Genetic Programming and L-Systems,” inProc. of Genetic Programming 1996 (Koza, J. R.,et al, ed.), MIT Press, pp. 107–115, 1996.
Kammeyer, T. E. and Belew, R. K., “Stochastic Context-free Grammar Induction with a Genetic Algorithm Using Local Search,” inFoundations of Genetic Algorithms IV (Belew, R. K. and Vode, M., eds.), Morgan-Kaufmann, 1997.
Koza, J. R.,Genetic Programming, MIT Press, 1992.
Koza, J. R.,Genetic Programming II, MIT Press, 1994.
Lankhorst, M. M., “Grammatical Inference with a Genetic Algorithm,” inProc. of the 1994 EUROSIM Conference on Massively parallel Processing Applications and Development, pp. 423–430, 1994.
Longshaw, T., “Evolutionary learning of large grammars,” inProc. of Genetic Programming 1997 (Koza, J. R.eaet al, ed.), Stanford University, CA, USA, Morgan Kaufmann, pp. 406–409, 1997.
Lucas, S., “Structuring Chromosomes for Context-free Grammar Evolution,” inProc. of 1st International Conference on Evolutionary Computation, IEEE Press, pp. 130–135, 1994.
McKay, R. I., “Fitness Sharing in Genetic Programming,” in Whitley, D.et al., ed.,Proc. of GECCO 2000, Morgan Kaufmann, 2000.
McKay, R. I., “Partial Functions in Fitness-Shared Genetic Programming,” inProc. of Congress on Evolutionary Computation (Zalzala, A., ed.), IEEE Press, 2000.
Montana, D. J., “Strongly Typed Genetic Programming,”Evolutionary Computation, 3, 2, pp. 199–230, 1995. http://dx.doi.org/10.1162/evco.1995.3.2.199
Pereira, F. C. N. and Warren, D. H. D., “Definite Clause Grammars for Language Analysis — A Survey of the Formalism and a Comparison with Augmented Transition Networks,”Artificial Intelligence, 13, Elsevier, pp. 231–278, 1980. http://dx.doi.org/10.1016/0004-3702(80)90003-X
Press, W. H., Teukolsky, S. A., Vetterling, W. T. and Flannery, B. P.,Numerical Recipes in C. Cambridge University Press, 2 ed., 1992.
Rabiner, L. R., “A Tutorial on Hidden Markov Models and Selected Applications in Speech Recognition,” inProc. of the IEEE, 77, 2, pp. 257–286, 1989.
Ross, B. J., “Probabilistic Pattern Matching and the Evolution of Stochastic Regular Expressions,”Applied Intelligence, Kluwer, 2000.
Ryan, C., Collins, J. J. and O’Neill, M., “Grammatical Evolution: Evolving Programs for an Arbitrary Language,” inProc. of First European Workshop in Genetic Programming (EuroGP-98), (Banzhaf, W.,et al., ed.), Springer-Verlag, pp. 83–96, 1998.
Sakakibara, Y., “Recent Advances of Grammatical Inference,”Theoretical Computer Science, 185, Elsevier, pp. 15–45, 1997. http://dx.doi.org/10.1016/S0304-3975(97)00014-5
Schwehm, M. and Ost, A., “Inference of Stochastic Regular Grammars by Massively Parallel Genetic Algorithms,” inProc. of 6th Intl. Conf. on Genetic Algorithms, Morgan-Kaufmann, 1995.
SICS.SICStus Prolog V.3 User’s Manual, June 1995, http://www.sics.se/isl/sicstus.html.
Svingen, B., “Learning Regular Languages Using Genetic Programming,” inProc. of Genetic Programming 1998 (Koza, J. R.,et al, ed.), Morgan Kaufmann, pp. 374–376, 1998.
Whigham, P. A., “Grammatically-based Genetic Programming,” inProc. of Workshop on Genetic Programming: From Theory to Real-World Applications (Rosca, J. P. ed.), pp. 31–41, 1995.
Whigham, P. A., “Inductive Bias and Genetic Programming,” in1st International Conference on Genetic Algorithms in Engineering Systems: Innovations and Applications (GALESIA), (Zalzala, A. M. S., ed.), pp. 461–466, 1995.
Wong, M. L. and Leung, K. S., “Evolutionary Program Induction Directed by Logic Grammars,”Evolutionary Computation, 5, 2, IEEE, pp. 143–180, 1997. http://dx.doi.org/10.1162/evco.1997.5.2.143
Zhou, H. and Grefenstette, J. J., “Induction of Finite Automata by Genetic Algorithms,” inProc. of 1986 IEEE Intl. Conference on Systems, Man, and Cybernetics, Atlanta, GA, IEEE Press, pp. 170–174, 1986.
Links
Full Text
http://www.cosc.brocku.ca/~bross/research/dctg_gp_ngc.pdf
Sonstige Links
Download system here: http://www.cosc.brocku.ca/~bross/dctggp/
