Analysis of Genotype Size for an Evolvable Hardware System
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.
[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.
[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.
@article{"International Journal of Electrical, Electronic and Communication Sciences:64165", author = "Emanuele Stomeo and Tatiana Kalganova and Cyrille Lambert", title = "Analysis of Genotype Size for an Evolvable Hardware System", 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.", volume = "1", number = "7", pages = "1067-6", }
