Analysis of Genotype Size for an Evolvable Hardware System

Authors: Emanuele Stomeo, Tatiana Kalganova, Cyrille Lambert

Abstract:

The evolution of logic circuits, which falls under the heading of evolvable hardware, is carried out by evolutionary algorithms. These algorithms are able to automatically configure reconfigurable devices. One of main difficulties in developing evolvable hardware with the ability to design functional electrical circuits is to choose the most favourable EA features such as fitness function, chromosome representations, population size, genetic operators and individual selection. Until now several researchers from the evolvable hardware community have used and tuned these parameters and various rules on how to select the value of a particular parameter have been proposed. However, to date, no one has presented a study regarding the size of the chromosome representation (circuit layout) to be used as a platform for the evolution in order to increase the evolvability, reduce the number of generations and optimize the digital logic circuits through reducing the number of logic gates. In this paper this topic has been thoroughly investigated and the optimal parameters for these EA features have been proposed. The evolution of logic circuits has been carried out by an extrinsic evolvable hardware system which uses (1+λ) evolution strategy as the core of the evolution.

Keywords: Evolvable hardware, genotype size, computational intelligence, design of logic circuits.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1084514

References:

[1] X. Yao, T. Higuchi; "Promises and challenges of evolvable hardware" IEEE Trans. Systems, Man and Cybernetics, Part C, volume 29, pp. 87 - 97, February 1999.
[2] H. de Garis. "Evolvable Hardware: Principles and Practice". Communications of the Association for Computer Machinery (CACM Journal). August 1997.
[3] J.D. Lohn, D.S. Linden, G.S. Hornby, W.F. Kraus, A. Rodriguez- Arroyo, S.E. Seufert. "Evolutionary design of an X-band antenna for NASA's space technology 5 mission". NASA/DoD Conference on Evolvable Hardware, 2003.Page(s):155 - 163.
[4] S. V. Hum, M. Okoniewski, R. J. Davies. "An Evolvable Antenna Platform Based on Reconfigurable Reflectarrays". The 2005 NASA/DoD Conference on Evolvable Hardware. June 29 - July 1, 2005, Washington DC, USA. IEEE Computer Society. Pages 139 - 146.
[5] E. Stomeo and T. Kalganova. "Improving EHW performance introducing a new decomposition strategy". 2004 IEEE Conference on Cybernetics and Intelligent Systems. Singapore 1-3 December 2004. Publisher IEEE Inc., New York, NY 10016-5997, United States. Pages 439-444.
[6] E. Stomeo, T. Kalganova, C. Lambert, N. Lipnitsakya, Y. Yatskevich. "On Evolution of Relatively Large Combinational Logic Circuits". The 2005 NASA/DoD Conference on Evolvable Hardware. June 29 - July 1, 2005, Washington DC, USA. IEEE Computer Society. Pages 59 - 66.
[7] S.Zhao, L. Jiao, Y. Wang. "Evolutionary Design of Analog Circuits with a Uniform Design Based Multi-Objective Adaptive Genetic Algorithm". The 2005 NASA/DoD Conference on Evolvable Hardware. June 29 - July 1, 2005, Washington DC, USA. IEEE Computer Society. Pages 26 - 29.
[8] A.H. Aguirre, R. Zebulum, C. Coello Coello. "Evolutionary multiobjective design targeting a Field Programmable Transistor Array". NASA/DoD Conference on Evolvable Hardware, 2004. 24-26 June 2004 Page(s):199 - 205.
[9] A. Stoica, D. Keymeulen, T. Arslan, Vu Duong, R. Zebulum, I. Ferguson, Xin Guo "Circuit self-recovery experiments in extreme environments". NASA/DoD Conference on Evolvable Hardware, 2004. 24-26 June 2004 Page(s):142 - 145.
[10] A. M. Tyrrell, R. A. Krohling and Y. Zhou. "Evolutionary algorithm for the promotion of evolvable hardware". Computers and Digital Techniques, IEE Proceedings- Volume 151, Issue 4, 18 July 2004 Page(s):267 - 275.
[11] D. E. Goldberg. Genetic algorithm in search, optimization and machine learning. Addison-Wesley Publishing Company, Incorporated, Reading, Massachusetts, 1989.
[12] J. Holland. Adaptation in Natural and Artificial Systems. Ann Arbor, MI: University of Michigan Press, 1975.
[13] M. D. Vose. "The Simple Genetic Algorithm". MA: MIT Press 1999.
[14] Jim Torresen. "Two-Step Incremental Evolution of a Prosthetic Hand Controller Based on Digital Logic Gates". 4th Int. Conf. on Evolvable Hardware (ICES2001), October 2001, Tokyo, Japan.
[15] P. Andersen. Evolvable Hardware: Artificial Evolution of Hardware Circuits in Simulation and Reality, M.Sc. Thesis, University of Aarhus, Denmark.
[16] Timothy G. W. Gordon and Peter J. Bentley. "On Evolvable Hardware". In Ovaska, S. and Sztandera, L. (Ed.) Soft Computing in Industrial Electronics. Physica-Verlag, Heidelberg, Germany, pp. 279-323.
[17] A. Stoica, R. Zebulum, and D. Keymeulen, "Mixtrinsic evolution," in International Conference on Evolvable Systems, Edinburgh, U.K., Apr. 2000, pp. 208-217.
[18] T. Kalganova and J. Miller. "Evolving more efficient digital circuits by allowing circuit layout evolution and multi-objective fitness". Proceedings of the First NASA/DoD Workshop on Evolvable Hardware, 19-21 July 1999 Page(s):54 - 63.
[19] Jim Torresen. "Evolving Multiplier Circuits by Training Set and Training Vector Partitioning". In proc. of Fifth International Conference on Evolvable Hardware (ICES03), Springer LNCS 2606, pp. 228-237, March 2003, Trondheim, Norway.
[20] Higuchi, T.; Iwata, M.; Keymeulen, D.; Sakanashi, H.; Murakawa, M.; Kajitani, I.; Takahashi, E.; Toda, K.; Salami, N.; Kajihara, N.; Otsu, N.; "Real-world applications of analog and digital evolvable hardware" IEEE Transactions on Evolutionary Computation , Vol.: 3 Issue: 3 , Sept. 1999 Page(s): 220 -235.
[21] J. Miller. "An empirical study of the efficiency of learning Boolean functions using a Cartesian genetic programming approach" In Proc. of the Genetic and Evolutionary Computation Conference, volume 1, pp. 1135-1142, Orlando, USA, July 1999.
[22] J. F. Miller and P. Thomson. "Cartesian genetic programming". In Riccardo Poli, Wolfgan Banzhaf, William B. Langdon, Julian F. Miller, Peter Nordin and Terence C. Forgaty, editors. Genetic Programming, Proceedings of EuroGP 2000. Vol. 1802 of LNCS, pages 121-132, Edinburg, 16 April 2000. Springer-Verlag.