With the recent examples of the human-competitiveness of evolutionary design systems, it is not of interest to scale them up to produce more sophisticated designs. Here we argue that for computer-automated design systems to scale to producing more sophisticated results they must be able to produce designs with greater structure and organization. By “structure and organization” we mean the characteristics of modularity, reuse and hierarchy (MR&H), characteristics that are found both in man-made and natural designs. We claim that these characteristics are enabled by implementing the attributes of combination, control-flow and abstraction in the representation, and define metrics for measuring MR&H and define two measures of overall structure and organization by combining the measures of MR&H. To demonstrate the merit of our complexity measures, we use an evolutionary algorithm to evolve solutions to different sizes for a table design problem, and compare the structure and organization scores of the best tables against existing complexity measures. We find that our measures better correlate with the complexity of good designs than do others, which supports our claim that MR&H are important components of complexity. We also compare evolution using five representations with different combinations of MR&H, and find that the best designs are achieved when all three of these attributes are present. The results of this second set of experiments demonstrate that implementing representations with MR&H can greatly improve search performance.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Abelson, H., Sussman, G. J., and Sussman, J. (1996). Structure and Interpretation of Computer Programs. McGraw-Hill, second edition.
Bennett, C. H. (1986). On the nature and origin of complexity in discrete, homogenous, locally-interacting systems. Foundations of Physics, 16:585-592.
Bentley, P. J. (1999). Evolutionary Design by Computers. Morgan Kaufmann, San Francisco.
Bentley, Peter J. and Corne, David W. (2001). An introduction to creative evolutionary systems. In Bentley, Peter J. and Corne, David W., editors, Creative Evolutionary Systems, pages 1-75. Morgan Kaufmann.
Chaitin, G. J. (1966). On the length of programs for computing finite binary sequences. Journal of the Association of Computing Machinery, 13:547-569.
Edmunds, B. (1999). Syntactic Measures of Complexity. PhD thesis, Dept. of Philosophy, University of Manchester.
Goldwasser, M., Latombe, J.-C., and Motwani, R. (1996). Complexity measures for assembly sequences. In Proc. IEEE Intl. Conf. on Robotics and Automation, pages 1581-1587, Minneapolis, MN.
Holland, J. H. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor.
Hornby, G. S. (2006). ALPS: The age-layered population structure for reducing the problem of premature convergence. In M. Keijzer et al., editor, Proc. of the Genetic and Evolutionary Computation Conference, GECCO-2006, pages 815-822, New York, NY. ACM Press.
Hornby, Gregory S. (2004). Functional scalability through generative representations: the evolution of table designs. Environment and Planning B: Planning and Design, 31(4):569-587.
Hornby, Gregory S. and Pollack, Jordan B. (2002). Creating high-level components with a generative representation for body-brain evolution. Artificial Life, 8:223-246.
Hornby, Gregory Scott (2003). Generative Representations for Evolutionary Design Automation. PhD thesis, Brandeis University, Dept. of Computer Science, Boston, MA, USA.
Huang, C. C. and Kusiak, A. (1998). Modularity in design of products and systems. IEEE Transactions on Systems, Man, and Cybernetics, Part A, 28 (1):66-77.
Kolmogorov, A. N. (1965). Three approaches to the quantitative definition of information. Problems of Information Transmission, 1:1-17.
Koppel, M. (1987). Complexity, depth and sophistication. Complex Systems, 1:1087-1091.
Meyer, B. (1988). Object-oriented Software Construction. Prentice Hall, New York.
Rosen, B. K. (1974). Syntactic complexity. Information and Control, 24:305-335.
Solomonoff, R. J. (1964). A formal theory of inductive inference. Information and Control, 7:1-22,224-254.
Ulrich, K. and Tung, K. (1991). Fundamentals of product modularity. In Proc. of ASME Winter Annual Meeting Symposium on Design and Manufacturing Integration, pages 73-79.
Yngve, V. H. (1960). A model and an hypothesis for language structure. In Proceedings of the American Philosophical Society, pages 444-466.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2008 Springer Science+Business Media, LLC
About this chapter
Cite this chapter
Hornby, G.S. (2008). Improving the Scalability of Generative Representations for Openended Design. In: Riolo, R., Soule, T., Worzel, B. (eds) Genetic Programming Theory and Practice V. Genetic and Evolutionary Computation Series. Springer, Boston, MA. https://doi.org/10.1007/978-0-387-76308-8_8
Download citation
DOI: https://doi.org/10.1007/978-0-387-76308-8_8
Publisher Name: Springer, Boston, MA
Print ISBN: 978-0-387-76307-1
Online ISBN: 978-0-387-76308-8
eBook Packages: Computer ScienceComputer Science (R0)