Ant Colony Optimisation for Performing Computational Task in Cellular Automata

  • Michal Bidlo IT4Innovations Centre of Excellence, Faculty of Information Technology, Brno University of Technology, Czech Republic https://orcid.org/0000-0002-1217-6711
  • Jakub Korgo IT4Innovations Centre of Excellence, Faculty of Information Technology, Brno University of Technology, Czech Republic
Keywords: ant colony optimisation, MAX-MIN ant system, cellular automaton, transition function, square calculation

Abstract

A method is presented for the design of cellular automata rules by means of ant algorithms. In particular, Elitist Ant System and a~modified MAX-MIN Ant System are applied to search for transition functions of 1D cellular automata that are able to calculate squares of given input values. It will be shown that the proposed MAX-MIN Ant System can perform significantly better than the standard variant of Elitist Ant System. In particular, in the most advanced case study, the ant algorithm showed an ability to design a~complete set of elementary cellular automata rules that fulfil the required square calculations. Some selected results will be presented and their features discussed.

References

Bidlo, M. 2016. On routine evolution of complex cellular automata. IEEE Transactions on Evolutionary Computation 20, 5, pp. 742-754.

Codd, E. F. 1968. Cellular Automata. Academic Press, New York, USA.

Colorni, A., Dorigo, M., and Maniezzo, V. 1991. Distributed optimization by ant colonies. In Proceedings of ECAL91 - European Conference on Artificial Life. Paris, France, pp. 134-142.

Dewdney, A. K. 1990. Computer recreations. Scientic American 262, 1, pp. 146-149.

Dorigo, M. and Gambardella, L. M. 1997. Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation 1, 1, pp. 53-66.

Dorigo, M., Maniezzo, V., and Colorni, A. 1996. Ant system: optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics) 26, 1, pp. 29-41.

Dorigo, M. and Stutzle, T. 2004. Ant Colony Optimization. MIT Press, USA.

Hanin, C., Omary, F., Elbernoussi, S., Achkoun, K., and Echandouri, B. 2018. A new block cipher system using cellular automata and ant colony optimization (bc-caaco). International Journal of Information Security and Privacy (IJISP) 12, 4, pp. 54-67.

Holland, J. H. 1975. Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor, USA.

Ilachinski, A. 2001. Cellular Automata: A Discrete Universe. World Scientic, Singapore.

Koza, J. R. 1992. Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, USA.

Karaboga, D. and Basturk, B. 2007. A powerful and efficient algorithm for numerical function optimization: Artificial bee colony (abc) algorithm. Journal of Global Optimization 39, 3, pp. 459-471.

Kennedy, J. and Eberhart, R. 1995. Particle swarm optimization. In Proceedings of ICNN'95 - International Conference on Neural Networks. IEEE, Vol. 4, pp. 1942-1948.

Liu, X., Li, X., Yeh, A. G. O., He, J., and Tao, J. 2007. Discovery of transition rules for geographical cellular automata by using ant colony optimization. Science in China Series D: Earth Sciences 50, 10, pp. 1578-1588.

Martens, D., De Backer, M., Haesen, R., Vanthienen, J., Snoeck, M., and Baesens, B. 2007. Classification with ant colony optimization. IEEE Transactions on Evolutionary Computation 11, 5, pp. 651-665.

von Neumann, J. 1966. The Theory of Self-Reproducing Automata. A. W. Burks (ed.), University of Illinois Press, USA.

Pourtakdoust, S. H. and Nobahari, H. 2004. An extension of ant colony system to continuous optimization problems. In: Ant Colony Optimization and Swarm Intelligence. Springer, Berlin, Heidelberg, pp. 294-301.

Rechenberg, I. 1973. Evolutionstrategie: Optimierung Technischer Systeme nach Prinzipien der Biologischen Evolution. Frommann-Holzboog, Stuttgart, Germany [in German].

Sipper, M. 1997. Evolution of Parallel Cellular Machines { The Cellular Programming Approach, Lecture Notes in Computer Science, Vol. 1194. Springer, Berlin, Germany.

Stutzle, T. and Hoos, H. H. 2000. Max{min ant system. Future Generation Computer Systems 16, 8, pp. 889-914.

Thilak, K. D. and Amuthan, A. 2018. Cellular automata-based improved ant colony-based optimization algorithm for mitigating ddos attacks in vanets. Future Generation Computer Systems 82, pp. 304-314.

Wolfram, S. 2002. A New Kind of Science. Wolfram Media, Champaign IL, USA.

Zhou, K., Ma, S., Zhu, X., Tang, L., and Feng, X. 2010. Improved ant colony algorithm based on cellular automata for obstacle avoidance in robot soccer. In 2010 3rd International Conference on Computer Science and Information Technology. IEEE, Chengdu, China, vol. 5, pp. 298-302.

Published
2019-06-24
How to Cite
[1]
Bidlo, M. and Korgo, J. 2019. Ant Colony Optimisation for Performing Computational Task in Cellular Automata. MENDEL. 25, 1 (Jun. 2019), 147-156. DOI:https://doi.org/10.13164/mendel.2019.1.147.
Section
Research articles