Spatial complexity measure for characterising cellular automata generated 2D patterns

Aus de_evolutionary_art_org
Wechseln zu: Navigation, Suche


Javaheri Javid, M.A., Blackwell, T., Zimmer, R., Al-Rifaie, M.M.: Spatial complexity measure for characterising cellular automata generated 2D patterns. In: Pereira, F., Machado, P., Costa, E., Cardoso, A. (eds.) EPIA 2015. LNCS, vol. 9273, pp. 201–212. Springer, Heidelberg (2015)



Cellular automata (CA) are known for their capacity to generate complex patterns through the local interaction of rules. Often the generated patterns, especially with multi-state two-dimensional CA, can exhibit interesting emergent behaviour. This paper addresses quantitative evaluation of spatial characteristics of CA generated patterns. It is suggested that the structural characteristics of two-dimensional (2D) CA patterns can be measured using mean information gain. This information-theoretic quantity, also known as conditional entropy, takes into account conditional and joint probabilities of cell states in a 2D plane. The effectiveness of the measure is shown in a series of experiments for multi-state 2D patterns generated by CA. The results of the experiments show that the measure is capable of distinguishing the structural characteristics including symmetry and randomness of 2D CA patterns.

Extended Abstract


author="Javaheri Javid, Mohammad Ali and Blackwell, Tim and Zimmer, Robert and Al-Rifaie, Mohammad Majid",
editor="Pereira, Francisco and Machado, Penousal and Costa, Ernesto and Cardoso, Am{\'i}lcar",
title="Spatial Complexity Measure for Characterising Cellular Automata Generated 2D Patterns ",
bookTitle="Progress in Artificial Intelligence: 17th Portuguese Conference on Artificial Intelligence, EPIA 2015, Coimbra, Portugal, September 8-11, 2015. Proceedings",
publisher="Springer International Publishing",

Used References

1. Andrienko, Y.A., Brilliantov, N.V., Kurths, J.: Complexity of two-dimensional patterns. Eur. Phys. J. B 15(3), 539–546 (2000)

2. Bates, J.E., Shepard, H.K.: Measuring complexity using information fluctuation. Physics Letters A 172(6), 416–425 (1993)

3. Brown, P.: Stepping stones in the mist. In: Creative Evolutionary Systems, pp. 387–407. Morgan Kaufmann Publishers Inc. (2001)

4. Cover, T.M., Thomas, J.A.: Elements of Information Theory (Wiley Series in Telecommunications and Signal Processing). Wiley-Interscience (2006)

5. Frazer, J.: An evolutionary architecture. Architectural Association Publications, Themes VII (1995)

6. Javaheri Javid, M.A., Al-Rifaie, M.M., Zimmer, R.: Detecting symmetry in cellular automata generated patterns using swarm intelligence. In: Dediu, A.-H., Lozano, M., Martín-Vide, C. (eds.) TPNC 2014. LNCS, vol. 8890, pp. 83–94. Springer, Heidelberg (2014)

7. Javaheri Javid, M.A., te Boekhorst, R.: Cell dormancy in cellular automata. In: Alexandrov, V.N., van Albada, G.D., Sloot, P.M.A., Dongarra, J. (eds.) ICCS 2006. LNCS, vol. 3993, pp. 367–374. Springer, Heidelberg (2006)

8. Langton, C.G.: Studying artificial life with cellular automata. Physica D: Nonlinear Phenomena 22(1), 120–149 (1986)

9. Miranda, E.: Composing Music with Computers. No. 1 in Composing Music with Computers. Focal Press (2001)

10. Scha, I.R.: Kunstmatige Kunst. De Commectie 2(1), 4–7 (2006)

11. Schwartz, L., Schwartz, L.: The Computer Artist’s Handbook: Concepts, Techniques, and Applications. W W Norton & Company Incorporated (1992)

12. Shannon, C.: A mathematical theory of communication. The Bell System Technical Journal 27, 379–423, 623–656 (1948)

13. Wackerbauer, R., Witt, A., Atmanspacher, H., Kurths, J., Scheingraber, H.: A comparative classification of complexity measures. Chaos, Solitons & Fractals 4(1), 133–173 (1994)

14. Wolfram, S.: Statistical mechanics of cellular automata. Reviews of Modern Physics 55(3), 601–644 (1983)

15. Wolfram, S.: Universality and complexity in cellular automata. Physica D: Nonlinear Phenomena 10(1), 1–35 (1984)

16. Wolfram, S.: A New Kind of Science. Wolfram Media Inc. (2002)

17. Xenakis, I.: Formalized music: thought and mathematics in composition. Pendragon Press (1992)


Full Text

internal file

Sonstige Links