Evolutionary synthesis of cellular automata

被引:0
作者
Zupanc J. [1 ]
Filipič B. [2 ]
机构
[1] Faculty of Computer and Information Science, University of Ljubljana, SI-1000 Ljubljana
[2] Department of Intelligent Systems, Jožef Stefan Institute, Ljubljana
关键词
Cellular automata; Cellular programming algorithm; Density classification task; Evolutionary computing; Genetic algorithm;
D O I
10.2498/cit.1001419
中图分类号
学科分类号
摘要
Synthesis of cellular automata is an important area of modeling and describing complex systems. Large amounts of combinations and candidate solutions render the usage of deterministic approaches impractical and thus nondeterministic optimization methods have to be employed. Two of the typical evolutionary approaches to synthesizing cellular automata are the evolution of a single automaton and a genetic algorithm that evolves a population of automata. The first approach, with addition of some heuristics, is known as the cellular programming algorithm. In this paper we address the second approach and develop a genetic algorithm that evolves a population of cellular automata. We test both approaches on the density classification task, which is one of the most widely studied computational problems in the context of evolving cellular automata. Comparison of the synthesized cellular automata demonstrates unexpected similarity of the evolved rules and comparable classification accuracy performance of both approaches.
引用
收藏
页码:105 / 112
页数:7
相关论文
共 13 条
[1]  
von Neumann J., Theory of Self-reproducing Automata, (1966)
[2]  
Capcarerre M.S., Sipper M.M.T., Two-state, r=1 cellular automaton that classifies density, Physical Review Letters, 77, 24, pp. 4969-4971, (1996)
[3]  
Ermentrout G.B., Edelstein-Keshet L., Cellular automata approaches to biological modeling, Journal of Theoretical Biology, 160, pp. 97-133, (1993)
[4]  
Nandi S., Kar B.K., Chaudhuri P., Theory and applications of cellular automata in cryptography, IEEE Transactions on Computers, 43, 12, pp. 1346-1357, (1994)
[5]  
Guoqing G., Poming H., Binghong W., Shiqiang D., Two-dimensional cellular automaton traffic model with randomly switching traffic lights, Applied Mathematics and Mechanics, 19, 9, pp. 807-813, (1998)
[6]  
Sipper M., Evolution of Parallel Cellular Machines - The Cellular Programming Approach, (1997)
[7]  
Sipper M., Evolution of ParallelCellularMachines, (2004)
[8]  
Gacs P., Kurdyumov G.L., Levin L.A., One dimensional uniform arrays that wash out finite islands, Problemy Peredachi Informatsii, 12, pp. 92-98, (1978)
[9]  
Das R., Crutchfield J.P., Mitchell M., Hanson J.E., Evolving globally synchronized cellular automata, Proceedings of The Sixth International Conference on Genetic Algorithms, pp. 336-343, (1995)
[10]  
Holland J.H., Adaptation in Natural and Artificial Systems, (1975)