IDEAS home Printed from https://ideas.repec.org/a/wsi/ijmpcx/v14y2003i07ns0129183103005017.html
   My bibliography  Save this article

Incremental Evolution Of Cellular Automata For Random Number Generation

Author

Listed:
  • 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)

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.

Suggested Citation

  • Sheng-Uei Guan & Shu Zhang, 2003. "Incremental Evolution Of Cellular Automata For Random Number Generation," International Journal of Modern Physics C (IJMPC), World Scientific Publishing Co. Pte. Ltd., vol. 14(07), pages 881-896.
    • Handle: RePEc:wsi:ijmpcx:v:14:y:2003:i:07:n:s0129183103005017
    DOI: 10.1142/S0129183103005017
    as

    Download full text from publisher

    File URL: http://www.worldscientific.com/doi/abs/10.1142/S0129183103005017
    Download Restriction: Access to full text is restricted to subscribers
    File URL: https://libkey.io/10.1142/S0129183103005017?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:wsi:ijmpcx:v:14:y:2003:i:07:n:s0129183103005017. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    We have no bibliographic references for this item. You can help adding them by using this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Tai Tone Lim (email available below). General contact details of provider: http://www.worldscinet.com/ijmpc/ijmpc.shtml .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.