research-article

Measures of complexity for artificial embryogeny

Author:

Taras KowaliwAuthors Info & Claims

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

Pages 843 - 850

https://doi.org/10.1145/1389095.1389259

Published: 12 July 2008 Publication History

Abstract

We aim for a more rigorous discussion of "complexity" for Artificial Embryogeny. Initially, we review several existing measures from Biology and Mathematics. We argue that measures which rank complexity through a Turing machine, or measures of information contained in a genome about an environment, are not desireable here; Instead, we argue for measures which provide the environment "for free", allowing us to quantify the capacity for a genome to exploit a provided area of growth. This leads to our definition of Environmental Kolmogorov Complexity and Logical Depth, along with our introduction of novel measures of functional complexity. Next, we attempt at defining an exceptionally simple model of embryogenesis, the Terminating Cellular Automata. The described measures are computed in this context, and contrasted.

References

[1]

C. Adami. What is complexity? BioEssays, 24:1085--1094, 2002.

[2]

L. Altenberg. Evolving better representations through selective genome growth. In IEEE CEC, 1994.

[3]

T. Baldwin and S. Shelah. On the classifiability of cellular automata. Theoretical Computer Science, 230:117--129, 2000.

Digital Library

[4]

W. Banzhaf. On evolutionary design, embodiment, and artificial regulatory networks. In F. I. phet al, editor, Embodied Artificial Intelligence, LNAI. Springer-Verlag, 2004.

[5]

W. Banzhaf and J. Miller. The challenge of complexity. In A. Menon, editor, Frontiers in Evolutionary Computation. Kluwer Academic, 2004.

[6]

V. Becher and S. Figueira. An example of a computable absolutely normal number. Theoretical Computer Science Archive, 270(1-2):947--958, 2002.

Digital Library

[7]

G. Bell and A. Mooers. Size and complexity among multicellular organisms. Biological Journal of the Linnean Society, 60:345--363, 1997.

[8]

C. H. Bennet. On the nature and origin of complexity in discrete, homogeneous, locally interacting systems. Foundations of Physics, 16(585), 1986.

[9]

N. Brodu. Practical Investigations of Complex Systems. Ph.D. thesis, Concordia U., 2007.

Digital Library

[10]

S. Camazine, J. Deneubourg, N. Franks, J. Sneyd, G. Theraulaz, and E. Bonabeau. Self-Organization in Biological Systems. Princeton U. Press, 2001.

Digital Library

[11]

G. Chaitin. The Limits of Mathematics. Springer-Verlag, 1998.

[12]

A. Deutsch and S. Dormann. Cellular Automaton Modelling of Biological Pattern Formation: Characterization, Applications and Analysis. Birkauser, 2005.

[13]

D. Federici and K. Downing. Evolution and development of a multicellular organism: Scalability, resilience, and neutral complexification. Artificial Life, 12(3):381--409, 2006.

Digital Library

[14]

S. J. Gould. The Structure of Evolutionary Theory. The Belknap Press of Harvard University Press, 2002.

[15]

P. Grünwald and P. Vitányi. Shannon information and Kolmogorov complexity. arXiv:cs.IT/0410002, 2006.

[16]

G. Hornby. Measuring, enabling and comparing modularity, regularity and hierarchy in evolutionary design. In GECCO-2005, 2005.

Digital Library

[17]

A. Ilachinski. Cellular Automata: A Discrete Universe. World Scientific, 2001.

Digital Library

[18]

T. Kowaliw, P. Grogono, and N. Kharma. Environment as a spatial constraint on the growth of structural form. In GECCO-2007, 2007.

Digital Library

[19]

P. Lehre and M. Hartmann. Development and complexity-based fitness function modifiers. In Workshop on Regeneration and Learning in Developmental Systems, 2004.

[20]

M. Li and P. Vitányi. An Introduction to Kolmogorov Complexity and Its Applications. Springer, 1993.

Digital Library

[21]

C. J. Lowe and G. A. Wray. Radical alterations in the roles of homeobox genes during echinoderm evolution. Nature, 389:718--721, 1997.

[22]

D. McShae. Complexity and evolution: What everybody knows. Biology and Phil., 6:303--324, 1991.

[23]

D. McShae. Functional complexity in organisms: Parts as proxies. Biology and Phil., 15:641--668, 2000.

[24]

R. M. H. Merks and J. A. Glazier. A cell-centred approach to developmental biology. Physica A, 352:113--130, 2005.

[25]

C. Shalizi, K. Shalizi, and R. Haslinger. Quantifying self-organization with optimal predictors. Phys. Rev. Lett., 93(118701), 2004.

[26]

C. E. Shannon. A mathematical theory of communication. Bell System Technical Journal, 27:379--423 & 623--656, 1948.

Digital Library

[27]

K. Stanley. Exploiting regularity without development. In AAAI Fall Symposium on Developmental Systems, 2006.

[28]

T. A. Welch. A technique for high-performance data compression. Computer, 17:8--19, 1984.

Digital Library

[29]

E. Zamir, P. Rupp, and C. Little. Studying in vivo dynamics of vasculogenesis using time-lapse computational imaging. In New Frontiers in Angiogenesis. Springer-Verlag, 2006.

Cited By

Cisneros HSivic JMikolov T(2019)Evolving Structures in Complex Systems2019 IEEE Symposium Series on Computational Intelligence (SSCI)10.1109/SSCI44817.2019.9002840(230-237)Online publication date: Dec-2019
https://doi.org/10.1109/SSCI44817.2019.9002840
Nichele SWold HTufte G(2014)Investigation of Genome Parameters and Sub-Transitions to Guide Evolution of Artificial Cellular OrganismsApplications of Evolutionary Computation10.1007/978-3-662-45523-4_10(113-124)Online publication date: 29-Nov-2014
https://doi.org/10.1007/978-3-662-45523-4_10
Nichele STufte G(2014)Measuring Phenotypic Structural Complexity of Artificial Cellular OrganismsInnovations in Bio-inspired Computing and Applications10.1007/978-3-319-01781-5_3(23-35)Online publication date: 2014
https://doi.org/10.1007/978-3-319-01781-5_3
Show More Cited By

Index Terms

Measures of complexity for artificial embryogeny
1. Computing methodologies
  1. Artificial intelligence
    1. Control methods
    2. Search methodologies
2. Theory of computation

Recommendations

Heterochrony and artificial embryogeny: A method for analyzing artificial embryogenies based on developmental dynamics

Artificial embryogenies are an extension to evolutionary algorithms, in which genotypes specify a process to grow phenotypes. This approach has become rather popular recently, with new kinds of embryogenies being increasingly reported in the literature. ...
Evolutionary growth of genome representations on artificial cellular organisms with indirect encodings

Evolutionary design targets systems of continuously increasing complexity. Thus, indirect developmental mappings are often a necessity. Varying the amount of genotype information changes the cardinality of the mapping, which in turn affects the ...
A Taxonomy for artificial embryogeny

A major challenge for evolutionary computation is to evolve phenotypes such as neural networks, sensory systems, or motor controllers at the same level of complexity as found in biological organisms. In order to meet this challenge, many researchers are ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '08: Proceedings of the 10th annual conference on Genetic and evolutionary computation

July 2008

1814 pages

ISBN:9781605581309

DOI:10.1145/1389095

Conference Chair:
Conor Ryan
University of Limerick, Ireland
,
Editor:
Maarten Keijzer
Chordiant Software International B.V., The Netherlands

Copyright © 2008 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 July 2008

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO08

Sponsor:

GECCO08: Genetic and Evolutionary Computation Conference

July 12 - 16, 2008

GA, Atlanta, USA

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
161
Total Downloads

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

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Cisneros HSivic JMikolov T(2019)Evolving Structures in Complex Systems2019 IEEE Symposium Series on Computational Intelligence (SSCI)10.1109/SSCI44817.2019.9002840(230-237)Online publication date: Dec-2019
https://doi.org/10.1109/SSCI44817.2019.9002840
Nichele SWold HTufte G(2014)Investigation of Genome Parameters and Sub-Transitions to Guide Evolution of Artificial Cellular OrganismsApplications of Evolutionary Computation10.1007/978-3-662-45523-4_10(113-124)Online publication date: 29-Nov-2014
https://doi.org/10.1007/978-3-662-45523-4_10
Nichele STufte G(2014)Measuring Phenotypic Structural Complexity of Artificial Cellular OrganismsInnovations in Bio-inspired Computing and Applications10.1007/978-3-319-01781-5_3(23-35)Online publication date: 2014
https://doi.org/10.1007/978-3-319-01781-5_3
Kowaliw TBanzhaf WMoore J(2012)The unconstrained automated generation of cell image features for medical diagnosisProceedings of the 14th annual conference on Genetic and evolutionary computation10.1145/2330163.2330316(1103-1110)Online publication date: 7-Jul-2012
https://dl.acm.org/doi/10.1145/2330163.2330316
Kowaliw TBanzhaf W(2012)Mechanisms for Complex Systems Engineering Through Artificial DevelopmentMorphogenetic Engineering10.1007/978-3-642-33902-8_13(331-351)Online publication date: 13-Dec-2012
https://doi.org/10.1007/978-3-642-33902-8_13
Nichele STufte G(2012)Genome parameters as information to forecast emergent developmental behaviorsProceedings of the 11th international conference on Unconventional Computation and Natural Computation10.1007/978-3-642-32894-7_18(186-197)Online publication date: 3-Sep-2012
https://dl.acm.org/doi/10.1007/978-3-642-32894-7_18
Tufte GNichele SLanzi P(2011)On the correlations between developmental diversity and genomic compositionProceedings of the 13th annual conference on Genetic and evolutionary computation10.1145/2001576.2001779(1507-1514)Online publication date: 12-Jul-2011
https://dl.acm.org/doi/10.1145/2001576.2001779

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

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten