INCREMENTAL EVOLUTION OF CELLULAR AUTOMATA FOR RANDOM NUMBER GENERATION

Sheng-Uei Guan () and Shu Zhang ()
Additional contact information
Sheng-Uei Guan: Department of Electrical and Computer Engineering, National University of Singapore, 10 Kent Ridge Crescents, Singapore 119260, Singapore
Shu Zhang: Department of Electrical and Computer Engineering, National University of Singapore, 10 Kent Ridge Crescents, Singapore 119260, Singapore

International Journal of Modern Physics C (IJMPC), 2003, vol. 14, issue 07, 881-896

Abstract: 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 (1D) CA and compete with two-dimensional (2D) CA. Yet the structural complexity of CCA is higher than that of 1D 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 1D CA. Furthermore, the methodology developed could be used to evolve other CA or serve as a yardstick to compare different types of CA.

Keywords: Controllable cellular automata; pseudorandom number generation; multi-objective optimization; incremental evolution (search for similar items in EconPapers)
Date: 2003
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0129183103005017
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:ijmpcx:v:14:y:2003:i:07:n:s0129183103005017

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0129183103005017

Access Statistics for this article

International Journal of Modern Physics C (IJMPC) is currently edited by H. J. Herrmann

More articles in International Journal of Modern Physics C (IJMPC) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().