<div>
	APPLICATION OF THE DIRECTED MUTATION TO CELLULAR AUTOMATA GENERATION PROCESS</div>

Tikhomirov Andrey V, Shalyto Anatoly A.

2014 , VOLUME 14, NUMBER 2 ( MARCH-APRIL )

ISSN 2226-1494 (print), ISSN 2500-0373 (online)

Publications

Editor-in-Chief

Nikiforov
Vladimir O.
D.Sc., Prof.

Partners

APPLICATION OF THE DIRECTED MUTATION TO CELLULAR AUTOMATA GENERATION PROCESS

A. V. Tikhomirov, A. A. Shalyto

Read the full article

Article in Russian

Abstract

Cellular automata are widely used for the simulation of discrete systems. However, in most cases creation of controlling cellular automata is done manually, empirically or by exhaustive search. A number of papers describe methods for automatic generation of finite automata and cellular automata using genetic programming. However, relatively simple genetic operators are used in these issues not taking into account the current test patterns and the population state that makes strong impact on the performance and convergence of these methods. This paper deals with the classical mutation operator applied to the process of cellular automata generation and directed mutation operator, designed to eliminate the above shortcomings. Both described operators are used in the adaptive genetic algorithm. The operator of directed mutation performs the analysis of the current chromosome, test pattern, and offers an optimal variant of mutation on the basis of the information received. The main differences and advantages as compared with the standard mutation operator are described. Testing on several training examples is performed; data about the resulting performance for genetic algorithm is presented.

Keywords: cellular automata, genetic algorithms

References

1. Frisch U., d'Humières, D., Hasslacher B., Lallemand P., Pomeau Y., Rivet J.-P. Latticegas hydrodynamics in two and three dimensions. Complex Systems, 1987, vol. 1, no. 4, pp. 649–707.

2. Wolfram S. Cellular automation fluids 1: Basic theory. Journal of Statistical Physics, 1986, vol. 45, no. 3-4, pp. 471–526. doi: 10.1007/BF01021083

3. Vose M.D., Wright A.H. Simple genetic algorithms with linear fitness. Evolutionary Computation, 1994, vol. 2, no. 4, pp. 347-368. doi: 10.1162/evco.1994.2.4.347

4. Vose M.D. A Critical Examination of the Schema Theorem. Technical Report UT-CS-93212. University of Tennessee, 1993. Available at: http://citeseer.ist.psu.edu/129900.html (accessed 20.02.2014).

5. Vose M.D., Wright A.H. The simple genetic algorithm and the Walsh transform. Part I. Theory. Evolutionary Computation, 1998, vol. 6, no. 3, pp. 253-273. doi: 10.1162/evco.1998.6.3.253

6. Das R., Crutchfield J.P., Mitchell M., Hanson J.E. Evolving globally synchronized cellular automata. Proceedings of the Sixth International Conference on Genetic Algorithms. San Francisco, USA, 1995, pp. 336–343.

7. Psakhie S.G., Horie Y., Ostermeyer G.P., Korostelev S.Yu., Smolin A.Yu., Shilko E.V., Dmitriev A.I., Blatnik S., Spegel M., Zavsek S. Movable cellar automata method for simulating materials with mesostructure. TheoreticalandAppliedFractureMechanics, 2001, vol. 37, pp. 311-334. doi: 10.1016/S0167-8442(01)00079-9

8. SkakovP.S. Klassifikatsiyapovedeniyaodnomernykhkletochnykhavtomatov. Magisterskaya dissertatsiya[Classification of one-dimensional cellular automata behavior. Master's thesis]. SPbSU ITMO, 2007. Available at:http://is.ifmo.ru/papers/_skakov_master.pdf(accessed 20.02.2014).

9. Panchenko E.V., Ul’yantsev V.I. Primenenie metodov resheniya zadachi o vypolnimosti kvantifitsirovannoi bulevoi funktsii dlya postroeniya upravlyayushchikh konechnykh avtomatov po stsenariyam raboty i temporal’nym svoistvam [Quantified Boolean function satisfiability solving methods application to extended finite-state machine creation based on scenarios and temporal properties]. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2013, no. 4 (86), pp. 151–153.

10. Bedny Yu.D. Primenenie geneticheskikh algoritmov dlya postroeniya kletochnykh avtomatov [Application of genetic algorithms for the construction of cellular automata]. Available at: http://is.ifmo.ru/papers/genalgcelaut.pdf (accessed 20.02.2014).

11. Tsarev F.N., Shalyto A.A. Primenenie geneticheskogo programmirovaniya dlya generatsii avtomata v zadache ob “umnom murav’e” [Application of genetic programming for generation of a control system in “Artificial Ant” problem]. Available at: http://is.ifmo.ru/genalg/_ant_ga.pdf (accessed 20.02.2014).

12. Tikhomirov A.V., Shalyto A.A. Primenenie adaptivnogo geneticheskogo algoritma dlya generatsii kletochnykh avtomatov [Genetic programming application for cellular automata generation]. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2012, no. 1 (77), pp. 100–105.

13. Tikhomirov A.V., Shalyto A.A. Primenenie geneticheskogo podkhoda dlya generatsii kletochnykh avtomatov [Genetic approach for cellular automata generation]. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2011, no. 2 (72), pp. 62–66.

14. Toffoli T., Margolus N. Cellular automata machines: a new environment for modeling. Cambridge: MIT Press, 1987.

15. von Neumann J. Theory of self-reproducing automata. Urbana and London, University of Illinois Press, 1966, 403 p.

16. Naumov L.A. Metod vvedeniya obobshchennykh koordinat i instrumental’noe sredstvo dlya avtomatizatsii proektirovaniya programmnogo obespecheniya vychislitel’nykh eksperimentov s ispol’zovaniem kletochnykh avtomatov. Diss. kand.tekhn. nauk [The method of generalized coordinates leading and tool for software design automation for computational experiments using cellular automata. PhD eng. sci. diss] St. Petersburg, 2007, 283 p.

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License