Measuring, enabling and comparing modularity, regularity and hierarchy in evolutionary design
Inhaltsverzeichnis
Reference
Hornby, G.: Measuring, enabling and comparing modularity, regularity and hierarchy in evolutionary design. In: Proceedings of the 2005 Conference on Genetic and Evolutionary Computation, pp. 1729–1736. ACM (2005).
DOI
http://dx.doi.org/10.1145/1068009.1068297
Abstract
For computer-automated design systems to scale to complex designs they must be able to produce designs that exhibit the characteristics of modularity, regularity and hierarchy -- characteristics that are found both in man-made and natural designs. Here we claim that these characteristics are enabled by implementing the attributes of combination, control-flow and abstraction in the representation.To support this claim we use an evolutionary algorithm to evolve solutions to different sizes of a table design problem using five different representations, each with different combinations of modularity, regularity and hierarchy enabled and show that the best performance happens when all three of these attributes are enabled.We also define metrics for modularity, regularity and hierarchy in design encodings and demonstrate that high fitness values are achieved with high values of modularity, regularity and hierarchy and that there is a positive correlation between increases in fitness and increases in the measured values of modularity, regularity and hierarchy.
Extended Abstract
Bibtex
Used References
P. J. Angeline. Morphogenic evolutionary computations: Introduction, issues and examples. In J. McDonnell, B. Reynolds, and D. Fogel, editors, Proc. of the Fourth Annual Conf. on Evolutionary Programming, pages 387--401. MIT Press, 1995.
P. Bentley and S. Kumar. Three ways to grow designs: A comparison of embryogenies of an evolutionary design problem. In W. Banzhaf, J. Daida, A. E. Eiben, M. H. Garzon, V. Honavar, M. Jakiela, and R. E. Smith, editors, Genetic and Evolutionary Computation Conference, pages 35--43. Morgan Kaufmann, 1999.
M. Goldwasser, J. Latombe, and R. Motwani. Complexity measures for assembly sequences. In Proc. IEEE Intl. Conf. on Robotics and Automation, pages 1581--1587, Minneapolis, MN, Apr. 1996.
John H. Holland, Adaptation in natural and artificial systems, MIT Press, Cambridge, MA, 1992 http://dl.acm.org/citation.cfm?id=129194&CFID=588525319&CFTOKEN=29804931
Gregory Scott Hornby , Jordan B. Pollack, Generative representations for evolutionary design automation, Brandeis University, Waltham, MA, 2003 http://dl.acm.org/citation.cfm?id=936568&CFID=588525319&CFTOKEN=29804931
G. S. Hornby. Functional scalability through generative representations: the evolution of table designs. Environment and Planning B: Planning and Design, 31(4):569--587, July 2004.
Gregory S. Hornby , Jordan B. Pollack, Creating high-level components with a generative representation for body-brain evolution, Artificial Life, v.8 n.3, p.223-246, 2002 http://dx.doi.org/10.1162/106454602320991837
Chun-Che Huang , A. Kusiak, Modularity in design of products and systems, IEEE Transactions on Systems, Man, and Cybernetics, Part A: Systems and Humans, v.28 n.1, p.66-77, January 1998 http://dx.doi.org/10.1109/3468.650323
Maciej Komosinski , Adam Rotaru-Varga, Comparison of different genotype encodings for simulated three-dimensional agents, Artificial Life, v.7 n.4, p.395-418, March 2002 http://dx.doi.org/10.1162/106454601317297022
Ming Li , Paul Vitányi, An introduction to Kolmogorov complexity and its applications, Springer-Verlag New York, Inc., New York, NY, 1993 http://dl.acm.org/citation.cfm?id=161259&CFID=588525319&CFTOKEN=29804931
Bertrand Meyer, Object-Oriented Software Construction, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988 http://dl.acm.org/citation.cfm?id=534929&CFID=588525319&CFTOKEN=29804931
Zbigniew Michalewicz, Genetic algorithms + data structures = evolution programs (2nd, extended ed.), Springer-Verlag New York, Inc., New York, NY, 1994 http://dl.acm.org/citation.cfm?id=184675&CFID=588525319&CFTOKEN=29804931
Kenneth O. Stanley , Risto Miikkulainen, A Taxonomy for artificial embryogeny, Artificial Life, v.9 n.2, p.93-130, Spring 2003 http://dx.doi.org/10.1162/106454603322221487
K. Ulrich and K. Tung. Fundamentals of product modularity. Issues in Design/Manufacture Integration - 1991 American Society of Mechanical Engineers, Design Engineering Division (Publication) DE, 39:73--79, 1991.
Links
Full Text
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.75.4204&rep=rep1&type=pdf