Measuring Complexity by Measuring Structure and Organization
Inhaltsverzeichnis
Reference
Gregory S. Hornby: Measuring Complexity by Measuring Structure and Organization. 2007 IEEE Congress on Evolutionary Computation, pp. 2017-2024, IEEE Press, 25-28 September 2007.
DOI
http://dx.doi.org/10.1109/CEC.2007.4424721
Abstract
Necessary for furthering the development of more powerful evolutionary design systems, capable of scaling to evolving more sophisticated and complex artifacts, is the ability to meaningfully and objectively compare these systems by applying complexity measures to the artifacts they evolve. Previously we have proposed measures of modularity, reuse and hierarchy (MR&H), here we compare these measures to ones from the fields of complexity, systems engineering and computer programming. In addition, we propose several ways of combining the MR&H measures into a single measure of structure and organization. We compare all of these measures empirically as well as on three sample objects and find that the best measures of complexity are two of the proposed measures of structure and organization.
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.
C. H. Bennett. On the nature and origin of complexity in discrete, homogenous, locally-interacting systems. Foundations of Physics, 16:585-592, 1986. http://dx.doi.org/10.1007/BF01886523
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.
P. J. Bentley, editor. Evolutionary Design by Computers. Morgan Kaufmann, San Francisco, 1999.
P. J. Bentley and D. W. Corne, editors. Creative Evolutionary Systems, Morgan Kaufmann, San Francisco, 2001.
G. J. Chaitin. On the length of programs for computing finite binary sequences. Journal of the Association of Computing Machinery, 13:547-569, 1966. http://dx.doi.org/10.1145/321356.321363
B. Edmunds. Syntactic Measures of Complexity. PhD thesis. Dept. of Philosophy, University of Manchester, 1999. http://dx.doi.org/10.1109/SCT.1991.160276
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. http://dx.doi.org/10.1109/ROBOT.1996.506981
J. H. Holland. Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor, 1975.
G. Hornby. Functional scalability through generative representations: the evolution of table designs. Environment and Planning B: Planning and Design, 31(4):569-587, July 2004. http://dx.doi.org/10.1068/b3015
G. S.Hornby. Generative Representations for Evolutionary Design Automation. PhD thesis. Michtom School of Computer Science. Brandeis University. Waltham, MA, 2003.
G. S. Hornby. Measuring, enabling and comparing modularity, regularity and hierarchy in evolutionary design. In H.-G. B. et al., editor, Proc. of the Genetic and Evolutionary Computation Conference, GECCO-2005, pages 1729-1736, New York, NY, 2005. ACM Press.
G. S. Hornby. ALPS: The age-layered population structure for reducing the problem of premature convergence. In M. K. et al., editor, Proc. of the Genetic and Evolutionary Computation Conference, GECCO-2006, pages 815-822, New York," NY. 2006. ACM Press.
A. N. Kolmogorov. Three approaches to the quantitative definition of information. Problems of Information Transmission, 1:1-17, 1965.
M. Komosinski and A. Rotaru-Varga. Comparison of different genotype encodings for simulated 3d agents. Artificial Life, 7(4):395-418, 2001. http://dx.doi.org/10.1162/106454601317297022
M. Koppel. Complexity, depth and sophistication. Complex Systems, 1:1087-1091, 1987. http://dx.doi.org/10.1109/TMM.2011.2128862
J. R. Koza. Genetic Programming: on the programming of computers by means of natural selection. MIT Press, Cambridge, MA, 1992.
P. Prusinkiewicz and A. Lindenmayer. The Algorithmic Beauty of Plants. Springer-Verlag, 1990.
B. K. Rosen. Syntactic complexity. Information and Control, 24:305-335, 1974. http://dx.doi.org/10.1016/S0019-9958(74)80058-6
H. A. Simon. The Sciences of the Artificial. MIT Press, Cambridge, MA. 1969.
R. J. Solomonoff. A formal theory of inductive inference. Information and Control, 7:1-22, 224-254, 1964. http://dx.doi.org/10.1016/S0019-9958(64)90131-7
K. O. Stanley and R. Miikkulainen, A taxonomy for artificial embryogeny. Artificial Life, 9(2):93-130, 2003. http://dx.doi.org/10.1162/106454603322221487
V. H. Yngve. A model and an hypothesis for language structure. In Proceedings of the American Philosophical Society, pages 444-466, 1960. http://dx.doi.org/10.1515/9783110814156.365
Links
Full Text
[extern file]
