Incremental evolution of cellular automata for random number generation

Sheng Uei Guan*, Shu Zhang

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

7 Citations (Scopus)


Cellular automata (CA) have been used in pseudorandom number generation for over a decade. Recent studies show that controllable CA (CCA) can generate better random sequences than conventional one-dimensional (ID) CA and compete with two-dimensional (2D) CA. Yet the structural complexity of CCA is higher than that of ID programmable cellular automata (PCA). It would be good if CCA can attain a good randomness quality with the least structural complexity. In this paper, we evolve PCA/CCA to their lowest complexity level using genetic algorithms (GAs). Meanwhile, the randomness quality and output efficiency of PCA/CCA are also evolved. The evolution process involves two algorithms - a multi-objective genetic algorithm (MOGA) and an algorithm for incremental evolution. A set of PCA/CCA are evolved and compared in randomness, complexity, and efficiency. The results show that without any spacing, the CCA could generate good random number sequences that could pass DIEHARD. To obtain the same randomness quality, the structural complexity of the CCA is not higher than that of ID CA. Furthermore, the methodology developed could be used to evolve other CA or serve as a yardstick to compare different types of CA.

Original languageEnglish
Pages (from-to)881-896
Number of pages16
JournalInternational Journal of Modern Physics C
Issue number7
Publication statusPublished - Sept 2003
Externally publishedYes


  • Controllable cellular automata
  • Incremental evolution
  • Multi-objective optimization
  • Pseudorandom number generation

Cite this