Evolving co-adapted subcomponents in assembler encoding

Praczyk, T.

International Journal of Applied Mathematics and Computer Science, Tome 17 (2007) no. 4, pp. 549-563.

Résumé

The paper presents a new Artificial Neural Network (ANN) encoding method called Assembler Encoding (AE). It assumes that the ANN is encoded in the form of a program (Assembler Encoding Program, AEP) of a linear organization and of a structure similar to the structure of a simple assembler program. The task of the AEP is to create a Connectivity Matrix (CM) which can be transformed into the ANN of any architecture. To create AEPs, and in consequence ANNs, genetic algorithms (GAs) are used. In addition to the outline of AE, the paper also presents a new AEP encoding method, i.e., the method used to represent the AEP in the form of a chromosome or a set of chromosomes. The proposed method assumes the evolution of individual components of AEPs, i.e., operations and data, in separate populations. To test the method, experiments in two areas were carried out, i.e., in optimization and in a predator-prey problem. In the first case, the task of AE was to create matrices which constituted a solution to the optimization problem. In the second case, AE was responsible for constructing neural controllers used to control artificial predators whose task was to capture a fast-moving prey.

Détail

Keywords: neural networks, evolution, neuroevolution
Mots-clés : sieci neuronowe, ewolucja, neuroewolucja

Bibliographie

[1] Cangelosi A., Parisi D. and Nolfi S. (1994): Cell division and migration in a genotype for neural networks. Network: Computation in Neural Systems, Vol. 5, No. 4, pp. 497-515.

[2] Curran D. and O'Riordan C. (2002): Applying evolutionary computation to designing networks: A study of the state of the art. Technical Report NUIG-IT-111002, National University of Ireland.

[3] Floreano D. and Urzelai J. (2000): Evolutionary robots with online self-organization and behavioral fitness. Neural Networks Vol. 13, No. 13, pp. 431-443.

[4] Gruau F. (1994): Neural network synthesis using cellular encoding and the genetic algorithm. Ph.D. thesis, Ecole Normale Supērieure de Lyon.

[5] Gruau F. (1995): Automatic definition of modular neural networks. Adaptive Behavior Vol. 3, No. 2., pp. 151-183.

[6] Gruau F., Whitley D. and Pyeatt L. (1996): A comparison between cellular encoding and direct encoding for genetic neural networks. In: Genetic Programming: Proceedings of the First Annual Conference (J. R. Koza, D. E. Goldberg, D. B. Fogel, R. L. Riolo, Eds.), Stanford University, CA, USA, MIT Press. 81-89.

[7] Kitano H. (1990): Designing neural networks using genetic algorithms with graph generation system. Complex Systems. Vol. 4, pp. 461-476.

[8] Krawiec, K. and Bhanu, B. (2005): Visual learning by coevolutionary feature synthesis. IEEE Transactions on Systems, Man, and Cybernetics, Part B: Cybernetics. Vol. 35, pp. 409-425.

[9] Luke S. and Spector L. (1996): Evolving graphs and networks with edge encoding: Preliminary report. In: Late Breaking Papers at the Genetic Programming 1996 Conference, (J. R. Koza, Ed.), Stanford University, CA: Stanford Bookstore, pp. 117-124.

[10] Mandischer M. (1993): Representation and evolution of neural networks. In: Artificial Neural Nets and Genetic Algorithms, (Albrecht R. F., Reeves, C. R., Steele U. C., Eds.), 643-649, Springer Verlag, New York.

[11] Miller G.F., Todd P.M. and Hegde S.U. (1989): Designing neural networks using genetic algorithms. Proceedings of the 3rd International Conference on Genetic Algorithms. San Mateo, CA, USA, 379-384.

[12] Moriarty D. E. and Miikkulainen R., (1998): Forming neural networks through efficient and adaptive coevolution. Evolutionary Computation, Vol. 5, No. 4, pp. 373-399.

[13] Moriarty D. E. (1997): Symbiotic evolution of neural networks in sequential ddecision tasks. Ph.D. thesis, The University of Texas at Austin, TR UT-AI97-257.

[14] Nolfi S. and Parisi D. (1992): Growing neural networks. In: Artificial Life IIII (C. G. Langton, Ed.) Reading, MA: Addison-Wesley.

[15] Nordin P., Banzhaf W. and Francone F. (1999): Efficient evolution of machine code for CISC architectures using blocks and homologous crossover. In: Advances in Genetic Programming III (L. Spector andW. Langdon and U. O'Reilly and P. Angeline Eds.), MIT Press, Cambridge, MA, USA, pp. 275-299.

[16] Potter M. (1997):The design andanalysis of a computational model of cooperative coevolution. Ph.D. thesis, George Mason University, Fairfax, VA.

[17] Potter M. and De Jong K. A. (1995): Evolving neural networks with collaborative species. In: Proceedings of the 1995 Summer Computer Simulation Conference, (T. I. Oren, L. G. Birta, Eds.), Ottawa, Canada, The Society of Computer Simulation, pp. 340-345.

[18] Potter M. A. and De Jong K. A. (1994): A cooperative coevolutionary approach to function optimization. In: The Third Parallel Problem Solving from Nature, Berlin: Springer-Verlag, pp. 249-257.

[19] Potter M. A. and De Jong K. A. (2000): Cooperative coevolution: An architecture for evolving coadapted subcomponents. Evolutionary Computation. Vol. 8, No. 1, pp. 1-29.

[20] Praczyk T. (2007) Application of assembler encoding to optimization problem. (submitted)

[21] Whitley D., Gruau F. and Pyeatt L. (1995): Cellular encoding applied to neurocontrol. Proceedings of the 6-th International Conference on Genetic Algorithms, San Francisco, CA, USA, pp. 460-467.