A Neuro-Genetic Framework for Pattern Recognition in Complex Systems

• Autorzy: Bandini S. , Vanneschi L. , Wuensche A. , Bahgat Shehata A.
• Języki publikacji: EN

Abstrakty

EN

This paper presents a general framework to automatically generate rules that produce given spatial patterns in complex systems. The proposed framework integrates Genetic Algorithms with Artificial Neural Networks or Support Vector Machines. Here, it is tested on a well known 3-values, 6-neighbors, k-totalistic cellular automata rule called the "burning paper" rule. Results are encouraging and should pave the way for the use of the proposed framework in real-life complex systems models.

Słowa kluczowe

EN

complex systems; cellular automata; pattern recognition; automatic rule generation; machine learning; genetic algorithm; artificial neutral networks; support vector machine (SVM)

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2008
• Tom: Vol. 87, nr 2
• Strony: 207--226
• Opis fizyczny: bibliogr. 47 poz., tab., wykr.

Twórcy

autor

Bandini S.

autor

Vanneschi L.

autor

Wuensche A.

autor

Bahgat Shehata A.

• Complex Systems and Artificial Intelligence (C.S.A.I.) research Center Dept. of Informatics, Systems and Communication (D.I.S.Co.), university of Milano-Bicocca, 20126 Milan, Italy,

Bibliografia

• [1] Andre, D., Bennett III, F. H., Koza, J. R.: Discovery by genetic programming of a cellular automata rule that is better than any known rule for the majority classification problem, Genetic Programming 1996: Proceedings of the First Annual Conference (J. R. Koza, D. E. Goldberg, D. B. Fogel, R. L. Riolo, Eds.), The MIT Press, Cambridge, MA, 1996.
• [2] Bandini, S., Manzoni, S., Redaelli, S., Vanneschi, L.: Automatic Detection of Go-Based Patterns in CA Model of Vegetable Populations: Experiments on Geta Pattern Recognition, Proceedings of the Seventh International Conference on Cellular Automata for Research and Industry (ACRI 2006) (S. E. Yacoubi, B. Chopard, S. Bandini, Eds.), Lecture Notes in Computer Science, LNCS 4173, Springer, Berlin, Heidelberg, New York, 2006, ISBN 3-540-40929-7.
• [3] Bandini, S., Manzoni, S., Redaelli, S., Vanneschi, L.: Emergent Spatial Patterns in Vegetable Population Dynamics: towards Pattern Detection and Interpretation, Modelling Complex Systems by Cellular Automata (MCSCA 2006), workshop of the 6th International Conference on Computational Science (ICCS 2006) (V. N. A. etal., Ed.), 3, Springer, Berlin, Heidelberg, New York, 2006.
• [4] Bilotta, E., Lafusa, A., Pantano, P.: Is self-replication an embedded characteristic of artificial/living matter?, Artificial Life VIII, 2002, 38-48.
• [5] Bilotta, E., Lafusa, A., Pantano, P.: Searching for complex CA rules with GAs, Complexity, 8(3), 2003, 56-67.
• [6] Boser, B., Guyon, I., Vapnik, V: A training algorithm for optimal margin classifiers, Proceedings of the fifth annual workshop on Computational learning theory, 1992, 144-152.
• [7] Brady, M. L., Raghavan, R., Sławny, J.: Probabilistic Cellular Automata in Pattern Recognition, Proc. Inter. Joint Conf. on Neural Networks, 1989
• [8] Breukelaar, R., Back, T.: Using a genetic algorithm to evolve behavior in multi dimensional cellular automata: emergence of behavior, Genetic and Evolutionary Computation Conference, GECCO 2005, Proceedings (H. G. Beyer, U. M. O'Reilly, Eds.), ACM, Washington DC, USA, 2005.
• [9] Chang, C.-C, Lin, C.-J.: LIBSVM: a library for support vector machines, 2001, Software available at http://www.csie.ntu.edu.tw/~cjlin/libsvm.
• [10] Chopard, B., Droz, M.: Cellular Automata Modeling of Physical Systems, Cambridge University Press, Cambridge, UK, 1998.
• [11] Cortes, C, Vapnik, V.: Support-vector networks, Machine Learning, 20(3), 1995, 273-297.
• [12] Das, R., Crutchfield, J. P., Mitchell, M.: Evolving globally synchronized cellular automata,, Proceedings of the Sixth International Conference on Genetic Algorithms (L. J. Eshelman, Ed.), Morgan Kaufmann, San Francisco, CA, 1995.
• [13] El-Manzalawy, Y., Honavar, V.: WLSVM: Integrating LibSVM into Weka Environment, 2005, Software available at http: //www. cs . iastate. edu/~yasser/wlsvm.
• [14] Ganguly, N., Maji, P., Dhar, S., Sikdar, B., Chaudhuri, P.: Evolving Cellular Automata as Pattern Classifier, Proceedings of Fifth International Conference on Cellular Automata for Research and Industry, ACRI 2002, Switzerland, 2002, 56-68.
• [15] Goldberg, D.: Genetic Algorithms in Search, Optimization and Machine Learning, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, USA, 1989.
• [16] H. Juille, J. B. P.: Coevolutionary learning: a case study, ICML '98 Proceedings of the Fifteenth International Conference on Machine Learning, Morgan Kaufmann, San Francisco, CA, 1998.
• [17] Holland, J.: Adaptation in natural and artificial systems, University of Michigan Press, 1975.
• [18] Hordijk, W: Correlation analysis of the synchronizing-ca landscape, Physica D, 107, 1997, 225-264.
• [19] Hsu, C.-W, Chang, C.-C, Lin, C.-J.: A Practical Guide to Support Vector Classification, available at http: //www.csie.ntu.edu.tw/~cjlin/papers/guide/guide.pdf, 2003.
• [20] Ibarra, O., Palis, M., Kim, S.: Fast parallel language recognition by cellular automata, Theoretical Computer Science, 41(2-3), 1985,231-246.
• [21] J. P. Crutchfield, M. Mitchell, R. D.: Evolutionary design of collective computation in cellular automata, Evolutionary Dynamics: Exploring the Interplay of Selection, Accident, Neutrality, and Function (J. P. Crutchfield, P. Schuster, Eds.), Oxford University Press, Oxford, UK, 2003.
• [22] Koza, J.: Genetic Programming: On the Programming of Computers by Means of Natural Selection, MIT Press, Cambridge, MA, USA, 1992, ISBN 0-262-11170-5.
• [23] Land, M., Belew, R. K.: No perfect two-state cellular automata for density classification exists, Physical Review Letters, 74(25), 1995, 5148-5150.
• [24] Maji, P., Shaw, C, Ganguly, N., Sikdar, B. K., Chaudhuri, P. P.: Theory and application of cellular automata for pattern classification, Fundam. Inf., 58(3-4), 2003, 321-354, ISSN 0169-2968.
• [25] Makatchev, M., Lang, S. Y. T.: On the Complexity of Image Processing and Pattern Recognition Algorithms, Proc. of the Int. Workshop on Image, Speech, Signal Processing and Robotics, 1998.
• [26] Mitchell, M., Crutchfield, J., Das, R.: Evolving cellular automata with genetic algorithms: A review of recent work, Proceedings of the First International Conference on Evolutionary Computation and Its Applications (EvCA96), 1996.
• [27] Mitchell, M., Crutchfield, J. P., Hraber, P. T.: Evolving cellular automata to perform computations: Mechanisms and impediments, Physica D, 75, 1994, 361-391.
• [28] Mitchell, M., Hraber, P. T., Crutchfield, J. P.: Revisiting the edge of chaos: Evolving cellular automata to perform computations, Complex Systems, 7, 1993,89-130.
• [29] Orovas, C: Cellular Associative Neural Networks for Pattern Recognition, Ph.D. thesis, University of York, UK, 1999, Downlodable version at: http://citeseer.ist.psu.edu/orovas99cellular.html.
• [30] Raghavan, R.: Cellular automata in pattern recognition, Information Sciences, 70(1), 1993, 145-177.
• [31] Rumelhart, D., Hinton, G., Williams, R.: Learning internal representations by error propagation, MIT Press Cambridge, MA, USA, 1986.
• [32] Sipper, M.: Non-Uniform Cellular Automata: Evolution in Rule Space and Formation of Complex Structures, Proceedings of the 4th International Workshop on the Synthesis and Simulation of Living Systems (Artificial Life IV) (Brooks, R. A, Maes, Pattie, Eds.), MIT Press, 1994.
• [33] Sipper, M.: Co-evolving non-uniform cellular automata to perform computations, Physica D, 92(3-4), 1996, 193-208.
• [34] Sipper, M.: Evolution of parallel cellular machines: The Cellular Programming Approach, Springer New York, 1997.
• [35] Sipper, M.: The evolution of parallel cellular machines: Toward evolware, BioSystems, 42, 1997, 29-43.
• [36] Sipper, M., Tomassini, M., Capcarrere, M.: Evolving asynchronous and scalable non-uniform cellular automata, Proceedings of International Conference on Artificial Neural Networks and Genetic Algorithms (ICANNGA97), 1997,66-70.
• [37] Smith III, A.: Real-time language recognition by one-dimensional cellular automata, Journal of Computer and System Sciences, 6(3), 1972, 233-253.
• [38] Tzionas, G. P., Tsalides, P. G., Thanailakis, A.: Cellular-automata-based learning network for pattern recognition, Proc. ofSPIE Vol. 1606, 1991.
• [39] Vapnik, V.: Estimation of Dependences Based on Empirical Data [in Russian], Nauka, Moscow, 1979, English translation: Springer Verlag, New York, 1982.
• [40] Verel, S., Collard, P., Tomassini, M., Vanneschi, L.: Fitness Landscape of the Cellular Automata Majority Problem: View from the "Olympus", Theoretical Computer Science, 378(1), 2007, 54-77.
• [41] Witten, I., Frank, E.: Data Mining: Practical Machine Learning Tools and Techniques, 2nd edition, Morgan Kaufmann, San Francisco, 2005.
• [42] Wolfram, S.: Statistical mechanics of cellular automata, Reviews of Modern Physics, 55(3), 1983, 601-644.
• [43] Wolfram, S.: A New Kind of Science, Wolfram Media, 2002.
• [44] Wuensche, A.: Classifying Cellular Automata Automatically, Complexity, 4(3), 1999, 47-66.
• [45] Wuensche, A.: Self-reproduction by glider collisions: the beehive rule, International Journal Pollack et. al, 2004,286-291.
• [46] Wuensche, A.: Discrete Dynamics Lab (DDLab), www.ddlab.com and http://www.cogs.susx.ac.uk/users/andywu/ddlab.html, November 2005
• [47] Wuensche, A., Adamatzky, A.: On Spiral Glider-Guns in Hexagonal Cellular Automata:. Activator-Inhibitor Paradigm, International Journal of Modern Physics C, 17(07), 2006, 1009-1026.