Article

Free access

Graph grammar encoding and evolution of automata networks

Author:

Martin H. LuerssenAuthors Info & Claims

ACSC '05: Proceedings of the Twenty-eighth Australasian conference on Computer Science - Volume 38

Pages 229 - 238

Published: 01 January 2005 Publication History

Abstract

The global dynamics of automata networks (such as neural networks) are a function of their topology and the choice of automata used. Evolutionary methods can be applied to the optimisation of these parameters, but their computational cost is prohibitive unless they operate on a compact representation. Graph grammars provide such a representation by allowing network regularities to be efficiently captured and reused. We present a system for encoding and evolving automata networks as collective hypergraph grammars, and demonstrate its efficacy on the classical problems of symbolic regression and the design of neural network architectures.

References

[1]

Abbass, H. A. (2003): Speeding up back-propagation using multiobjective evolutionary algorithms. Neural Computation15(11):2705--2726.

Digital Library

[2]

Angeline, P. J., Saunders, G. M., and Pollack, J. B. (1994): An evolutionary algorithm that constructs recurrent neural networks. IEEE Transactions on Neural Networks5(1):54--65.

Digital Library

[3]

Bäck, T. (1996): Evolutionary algorithms in theory and practice. New York, Oxford University Press.

Digital Library

[4]

Bleuler, S., Braek, M., Thiele, L., and Zitzler, E. (2001): Multiobjective genetic programming: reducing bloat using SPEA2. Proceedings of the 2001 IEEE Congress on Evolutionary Computation 2001 (CEC 2001), Seoul, Korea, 1:536--543.

[5]

Boers, E. J. W. and Kuiper, H. (1992): Biological metaphors and the design of modular artificial neural networks. Master's Thesis. Leiden University, The Netherlands.

[6]

Cun, Y., Denker, J., and Solla, S. (1990): Optimal brain damage. In Advances in neural information processing systems, vol. 2. 598--605. Touretzky, D. S. (ed). Morgan Kauffmann.

Digital Library

[7]

Daida, J. M., Bertram, R. R., Stanhope, S. A., Khoo, J. C., Chaudhary, S. A., Chaudhri, O. A., and Polito II, J. A. (2001): What makes a problem GP-hard? analysis of a tunably difficult problem in genetic programming. Genetic Programming and Evolvable Machines2(2):165--191.

Digital Library

[8]

Darwin, C. (1859): On the origin of species by means of natural selection. London, Murray.

[9]

De Jong, E. D. and Pollack, J. B. (2001): Utilizing bias to evolve recurrent neural networks. Proceedings of the IJCNN, Washington, USA, 4:2667--2672.

[10]

Deb, K. (2001): Multi-objective optimization using evolutionary algorithms. Chichester, Wiley.

Digital Library

[11]

Fahlman, S. and Lebière, C. (1990): The cascade-correlation learning architecture. In Advances in neural information processing systems, vol. 2. 524--532. TOURETZKY, D. S. (ed). Morgan-Kauffmann.

Digital Library

[12]

Fisher, R. A. (1936): The use of multiple measurements in taxonomic problems. Annual Eugenics7:179--188.

[13]

Futuyma, D. J. (1998): Evolutionary biology. Sunderland, MA, Sinauer Associates, Inc.

[14]

Goles, E., and Martinez, S. (1990): Neural and automata networks: dynamical behavior and applications. Dordrecht, Germany, Kluwer Academic Publishers.

Digital Library

[15]

Gruau, F. (1994): Neural network synthesis using cellular encoding and the genetic algorithm. Ph.D. thesis. l'Ecole Normale Supérieure de Lyon, France.

[16]

Habel, A. (1992): Hyperedge replacement: grammars and languages. Berlin, Springer-Verlag.

Digital Library

[17]

Halder, G., Callaerts, P., and Gehring, W. (1995): Induction of ectopic eyes by targeted expression of the eyeless gene in Drosophila. Science267:1788--1792.

[18]

Holland, J. (1992): Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence. Cambridge, MIT Press.

[19]

Igel, C. and Toussaint, M (2003): Recent results on no-free-lunch theorems for optimization. arXiv:cs.NE/0303032

[20]

Kitano, H. (1990): Designing neural networks using genetic algorithms with graph generation systems. Complex Systems4(4):461--476.

[21]

Koza, J. R. (1992): Genetic programming: on the programming of computers by means of natural selection. Cambridge, The MIT Press.

Digital Library

[22]

Lindenmayer, A. (1968): Mathematical models for cellular interaction in development, parts I and II. Journal of Theoretical Biology18:280--315.

[23]

Luerssen, M. and Powers, D. (2003): On the artificial evolution of neural graph grammars. Proceedings of the 4th International Conference on Cognitive science (ICCS/ASCS-2003), Sydney, Australia, 369--377.

[24]

Luke, S. and Spector, L. (1996): Evolving graphs and networks with edge encoding: preliminary report. Late Breaking Papers at the Genetic Programming 1996 Conference, Stanford University, USA, 117--124.

[25]

Miller, J. F. and Thomson, P. (2000): Cartesian genetic programming. Proceedings of the Third European Conference on Genetic Programming (EuroGP2000), Edinburgh, UK, LNCS 1802:121--132.

Digital Library

[26]

Miller, J. F. and Thomson, P. (2003): A developmental method for growing graphs and circuits. Fifth International Conference on Evolvable Systems: From Biology to Hardware, LNCS 2606:93--104.

Digital Library

[27]

Rumelhart, D. E., Hinton, G. E., and Williams, R. J. (1986): Learning representation by back-propagating errors. Nature323:533--536.

[28]

Shan, Y., McKay, R. I., Baxter, R., Abbass, H. A., Essam, D. L., and Nguyen, H. X. (2004): Grammar model-based program evolution. Proceedings of the 2004 IEEE Congress on Evolutionary Computation (CEC 2004), Portland, USA, 1:478--485.

[29]

Silva, S. and Almeida, J. (2003): Dynamic maximum tree depth - a simple technique for avoiding bloat in tree-based GP. Proceedings of the Genetic and Evolutionary Computation Conference (GECCO-2003), Chicago, USA, LNCS 2724:1776--1787.

Digital Library

[30]

Silva, S. and Almeida, J. (2003): GPLAB - a genetic programming toolbox for MATLAB. Proceedings of the nordic MATLAB conference (NMC-2003), Copenhagen, Denmark, 273--278.

[31]

Toussaint, M. (2003): The evolution of genetic representations and modular neural adaptation. Ph.D thesis. Institut für Neuroinformatik, Ruhr-Universität Bochum.

[32]

Wagner, G. P. and Altenberg, L. (1996): Complex adaptations and the evolution of evolvability. Evolution50(3):967--976.

[33]

Whigham, P. A. (1995): Grammatically-based genetic programming. Proceedings of the Workshop on Genetic Programming: From Theory to Real-World Applications, Tahoe City, USA, 33--41.

[34]

Whitley, D., Gordon, V., and Mathias, K. (1994): Lamarckian evolution, the Baldwin effect and function optimization. Parallel problem solving from nature (PPSN 3), Jerusalem, Israel, LNCS 866:6--15.

Digital Library

[35]

Yao, X. (1999): Evolving artificial neural networks. Proceedings of the IEEE87:1423--1447.

Cited By

Aguinaga SChiang DWeninger T(2019)Learning Hyperedge Replacement Grammars for Graph GenerationIEEE Transactions on Pattern Analysis and Machine Intelligence10.1109/TPAMI.2018.281087741:3(625-638)Online publication date: 1-Mar-2019
https://dl.acm.org/doi/10.1109/TPAMI.2018.2810877
Gan ZYang ZShang TYu TJiang M(2010)Automated synthesis of passive analog filters using graph representationExpert Systems with Applications: An International Journal10.1016/j.eswa.2009.07.01337:3(1887-1898)Online publication date: 1-Mar-2010
https://dl.acm.org/doi/10.1016/j.eswa.2009.07.013

Index Terms

Graph grammar encoding and evolution of automata networks

Recommendations

Genetically Evolving Higher Order Neural Networks by Direct Encoding Method
ICCIMA '05: Proceedings of the Sixth International Conference on Computational Intelligence and Multimedia Applications

There are two major ways of encoding a neural network into a chromosome, as required in design of a Genetic Algorithm (GA). These are Explicit (direct) and Implicit (Indirect) encoding methods. The proposed direct encoding method to design Higher Order ...
Neural network crossover in genetic algorithms using genetic programming
Abstract
The use of genetic algorithms (GAs) to evolve neural network (NN) weights has risen in popularity in recent years, particularly when used together with gradient descent as a mutation operator. However, crossover operators are often omitted from ...
Finite graph automata for linear and boundary graph languages

Graph grammars can be regarded as a generalization of context-free grammars from strings to graphs. Over the past 30 years a rich theory of graph grammars and their languages has been developed. However, there are no graph automata. There is no duality ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image DL Hosted proceedings

ACSC '05: Proceedings of the Twenty-eighth Australasian conference on Computer Science - Volume 38

January 2005

365 pages

ISBN:1920682201

Editor:
Vladimir Estivill-Castro
Griffith University.

Publisher

Australian Computer Society, Inc.

Australia

Publication History

Published: 01 January 2005

Author Tags

Qualifiers

Article

Conference

ACSC '05

ACSC '05: Computer Science

01 01 2005

Newcastle, Australia

Acceptance Rates

Overall Acceptance Rate 136 of 379 submissions, 36%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
486
Total Downloads

Downloads (Last 12 months)28
Downloads (Last 6 weeks)11

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Aguinaga SChiang DWeninger T(2019)Learning Hyperedge Replacement Grammars for Graph GenerationIEEE Transactions on Pattern Analysis and Machine Intelligence10.1109/TPAMI.2018.281087741:3(625-638)Online publication date: 1-Mar-2019
https://dl.acm.org/doi/10.1109/TPAMI.2018.2810877
Gan ZYang ZShang TYu TJiang M(2010)Automated synthesis of passive analog filters using graph representationExpert Systems with Applications: An International Journal10.1016/j.eswa.2009.07.01337:3(1887-1898)Online publication date: 1-Mar-2010
https://dl.acm.org/doi/10.1016/j.eswa.2009.07.013

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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