Evolvable hardware (EHW) refers to a selfreconfiguration
hardware design, where the configuration is under
the control of an evolutionary algorithm (EA). A lot of research has
been done in this area several different EA have been introduced.
Every time a specific EA is chosen for solving a particular problem,
all its components, such as population size, initialization, selection
mechanism, mutation rate, and genetic operators, should be selected
in order to achieve the best results. In the last three decade a lot of
research has been carried out in order to identify the best parameters
for the EA-s components for different “test-problems". However
different researchers propose different solutions. In this paper the
behaviour of mutation rate on (1+λ) evolution strategy (ES) for
designing logic circuits, which has not been done before, has been
deeply analyzed. The mutation rate for an EHW system modifies
values of the logic cell inputs, the cell type (for example from AND
to NOR) and the circuit output. The behaviour of the mutation has
been analyzed based on the number of generations, genotype
redundancy and number of logic gates used for the evolved circuits.
The experimental results found provide the behaviour of the mutation
rate to be used during evolution for the design and optimization of
logic circuits. The researches on the best mutation rate during the last
40 years are also summarized.
[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] D. E. Goldberg. Genetic algorithm in search, optimization and machine
learning. Addison-Wesley Publishing Company, Incorporated, Reading,
Massachusetts, 1989.
[4] J. Holland. Adaptation in Natural and Artificial Systems. Ann Arbor,
MI: University of Michigan Press, 1975.
[5] M. D. Vose. "The Simple Genetic Algorithm". MA: MIT Press 1999.
[6] J. R Koza. Genetic Programming: On the Programming of Computers by
Means of Natural selection. ISBN 0-262-11170-5. MIT Press, 1992.
[7] I. Rechenberg, "Evolution Strategy", in J. Zurada, R. Marks II, and C.
Robinson (Eds.), Computational Intelligence: Imitating Life, 1994, pp.
147-159.
[8] H. G. Beyer and H. P. Schwefel, "Evolution strategies: A comprehensive
introduction," Natural Computing: an international journal. Volume 1,
Issue. 1, pp. 3-52, 2002.
[9] T. Bäck, Evolutionary Algorithms in Theory and Practice. New York:
Oxford Univ. Press, 1996.
[10] H.-P. Schwefel, Numerical Optimization of Computer Models. New
York: Wiley, 1981.
[11] C. Ryan, J. J. Collins, M. O' Neill; "Grammatical Evolution: Evolving
Programs for an Arbitrary Language". Lecture Notes in Computer
Science 1391. First European Workshop on Genetic Programming
1998.
[12] L. J. Fogel, A. J. Owens, M. J. Walsh. Artificial Intelligence through
Simulated Evolution. New York: Wiley, 1966.
[13] Z. Michalewicz, Genetic Algorithms + Data Structures = Evolution
Programs. Berlin, Germany: Springer-Verlag, 1994.
[14] 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.
[15] H. M├╝hlenbein. "Parallel Genetic Algorithms, Population Genetics and
Combinatorial Optimization". In J.D. Schaffer, editor, Proceedings of
the Third International Conference on Genetic Algorithms, pp 416-421,
San Mateo, 1989. Morgan Kaufman.
[16] Myung-Sook Ko, Tae-Won Kang and Chong-Su Hwang. "Function
optimisation using an adaptive crossover operator based on locality".
Eng. Applic. Artif. Intell. Vol. 10, No 6 pp. 519-524, 1997.
[17] R. C. Eberhart and J. Kennedy, "A new optimizer using particle swarm
theory," in Proc. 6th Symp. MicroMachine and Human Science, Nagoya,
Japan, 1995, pp. 39-43.
[18] K. Y. Chan, M. E. Aydin, T. C. Fogarty; "Parameterisation of mutation
in evolutionary algorithms using the estimated main effect of genes"
Congress on Evolutionary Computatio. CEC2004. ,Volume: 2 , 19-23
June 2004 Pages:1972 - 1979.
[19] K. Y. Chan, M. E. Aydin, T. C. Fogarty; "An epistasis measure based on
the analysis of variance for the real-coded representation in genetic
algorithms" Congress on Evolutionary Computation. CEC '03. Vol.: 1 ,
8-12 Dec. 2003 Pages:297 - 304.
[20] J. J. Grefenstette, "Optimization of control parameters for genetic
algorithms," IEEE Trans. Systems, Man, Cybernetics. Vol. 16, no. 1, pp.
122-128, 1986.
[21] K. De Jong, "The analysis of the behavior of a class of genetic adaptive
systems." Ph.D. dissertation, Dept. Computer Science, University of
Michigan, Ann Arbor, 1975.
[22] A. E. Eiben, R. Hinterding, Z. Michalewicz; "Parameter control in
evolutionary algorithms" IEEE Transactions on Evolutionary
Computation, Volume: 3, Issue: 2, July 1999 Pages:124 - 141.
[23] J. D. Schaffer, R. Caruana, L. Eshelman and R. Das, "A study of control
parameters affecting online performance of genetic algorithms for
function optimization." Proceedings of the Third International
Conference on Genetic Algorithms, ed. J. D. Schaffer, Los Altos, CA:
Morgan Kaufmann, June 4-7, 1989, pp. 51-60.
[24] H. M├╝hlenbein. "How genetic algorithms really work: I.Mutation and
Hillclimbing," in Parallel Problem Solving from Nature- PPSN II, R.
Männer and B. Manderick, Eds., Amsterdam, The Netherlands, 1992,
pp. 15-25.
[25] M. Srinivas, L. M. Patnaik. "Adaptive probabilities of crossover and
mutation in genetic algorithms". IEEE Transactions on Systems, Man
and Cybernetics, Volume 24, Issue 4, April 1994 Page(s):656 - 667
[26] T. Niwa, M. Tanaka. "On the mean convergence time for simple genetic
algorithms". IEEE International Conference on Evolutionary
Computation. Volume 1, 29 Nov.-1 Dec. 1995 Page(s):373.
[27] R. L. Haupt. "Optimum population size and mutation rate for a simple
real genetic algorithm that optimizes array factors". IEEE International
Symposium Antennas and Propagation Society. Volume: 2, 16-21 July
2000. Pages:1034 - 1037
[28] S. Nijssen, T. Back; "An analysis of the behaviour of simplified
evolutionary algorithms on trap functions". IEEE Transactions on
Evolutionary Computation. Volume: 7, Issue: 1, Feb. 2003. Pages:11 -
22.
[29] M. Srinivas, L. M. Patnaik; "Genetic algorithms: a survey". IEEE JNL
Computer, Volume: 27, Issue: 6, June 1994. Pages:17 - 26
[30] T. Kalganova, J. Miller, "Evolving more efficient digital circuits by
allowing circuit layout evolution and multi-objective fitness". Proc. of
the First NASA/DoD Workshop on Evolvable Hardware. IEEE
Computer Society, Pages 54-63. July 1999
[31] T. Kalganova; "Bidirectional incremental evolution in extrinsic
evolvable hardware". Proc. of the Second NASA/DoD Workshop on
Evolvable Hardware. IEEE Computer Society, 13-15 July 2000.
Pages:65 - 74
[32] E. H. Luna, C.A. Coello Coello, A.H. Aguirre. "On the use of a
population-based particle swarm optimizer to design combinational logic
circuits". Proceedings of the 2004 NASA/DoD Conference on Evolvable
Hardware, 24-26 June 2004. Pages:183 - 190.
[33] S. Balkir, G. Diindar, G. Alpaydin,; "Evolution based synthesis of
analog integrated circuits and systems" Proceedings of the 2004
NASA/DoD Conference on Evolvable Hardware, 24-26 June 2004
Pages:26 - 29.
[34] M. Oltean, C. Grosan; "Evolving digital circuits using multi expression
programming" Proceedings of the 2004 NASA/DoD Conference on
Evolvable Hardware, 24-26 June 2004 Pages:87 - 94.
[35] Yang Zhang, S.L. Smith, A.M. Tyrrell;"Digital circuit design using
intrinsic evolvable hardware" Proceedings of the 2004 NASA/DoD
Conference on Evolvable Hardware, 24-26 June 2004 Pages:55 - 62
[36] J.C. Gallagher, S. Vigraham, G. Kramer; "A family of compact genetic
algorithms for intrinsic evolvable hardware". IEEE Transactions on
Evolutionary Computation, Volume: 8 , Issue: 2 , April 2004 Pages:111
- 126.
[37] 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.
[38] T. Bäck, F. Hoffmeister, H. P. Schwefel. "A survey of evolutionary
strategies". In R. Belew and L. Booker, editors, Proceedings of the 4th
International Conference on Genetic Algorithms, pages 2-9, San
Francisco, CA, 1991. Morgan Kaufmann.
[39] H. P. Schwefel. Numerical Optimization of Computer Models. John
Wiley & Sons, Chichester, UK, 1981.
[40] 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, pp.
439-444.
[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] D. E. Goldberg. Genetic algorithm in search, optimization and machine
learning. Addison-Wesley Publishing Company, Incorporated, Reading,
Massachusetts, 1989.
[4] J. Holland. Adaptation in Natural and Artificial Systems. Ann Arbor,
MI: University of Michigan Press, 1975.
[5] M. D. Vose. "The Simple Genetic Algorithm". MA: MIT Press 1999.
[6] J. R Koza. Genetic Programming: On the Programming of Computers by
Means of Natural selection. ISBN 0-262-11170-5. MIT Press, 1992.
[7] I. Rechenberg, "Evolution Strategy", in J. Zurada, R. Marks II, and C.
Robinson (Eds.), Computational Intelligence: Imitating Life, 1994, pp.
147-159.
[8] H. G. Beyer and H. P. Schwefel, "Evolution strategies: A comprehensive
introduction," Natural Computing: an international journal. Volume 1,
Issue. 1, pp. 3-52, 2002.
[9] T. Bäck, Evolutionary Algorithms in Theory and Practice. New York:
Oxford Univ. Press, 1996.
[10] H.-P. Schwefel, Numerical Optimization of Computer Models. New
York: Wiley, 1981.
[11] C. Ryan, J. J. Collins, M. O' Neill; "Grammatical Evolution: Evolving
Programs for an Arbitrary Language". Lecture Notes in Computer
Science 1391. First European Workshop on Genetic Programming
1998.
[12] L. J. Fogel, A. J. Owens, M. J. Walsh. Artificial Intelligence through
Simulated Evolution. New York: Wiley, 1966.
[13] Z. Michalewicz, Genetic Algorithms + Data Structures = Evolution
Programs. Berlin, Germany: Springer-Verlag, 1994.
[14] 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.
[15] H. M├╝hlenbein. "Parallel Genetic Algorithms, Population Genetics and
Combinatorial Optimization". In J.D. Schaffer, editor, Proceedings of
the Third International Conference on Genetic Algorithms, pp 416-421,
San Mateo, 1989. Morgan Kaufman.
[16] Myung-Sook Ko, Tae-Won Kang and Chong-Su Hwang. "Function
optimisation using an adaptive crossover operator based on locality".
Eng. Applic. Artif. Intell. Vol. 10, No 6 pp. 519-524, 1997.
[17] R. C. Eberhart and J. Kennedy, "A new optimizer using particle swarm
theory," in Proc. 6th Symp. MicroMachine and Human Science, Nagoya,
Japan, 1995, pp. 39-43.
[18] K. Y. Chan, M. E. Aydin, T. C. Fogarty; "Parameterisation of mutation
in evolutionary algorithms using the estimated main effect of genes"
Congress on Evolutionary Computatio. CEC2004. ,Volume: 2 , 19-23
June 2004 Pages:1972 - 1979.
[19] K. Y. Chan, M. E. Aydin, T. C. Fogarty; "An epistasis measure based on
the analysis of variance for the real-coded representation in genetic
algorithms" Congress on Evolutionary Computation. CEC '03. Vol.: 1 ,
8-12 Dec. 2003 Pages:297 - 304.
[20] J. J. Grefenstette, "Optimization of control parameters for genetic
algorithms," IEEE Trans. Systems, Man, Cybernetics. Vol. 16, no. 1, pp.
122-128, 1986.
[21] K. De Jong, "The analysis of the behavior of a class of genetic adaptive
systems." Ph.D. dissertation, Dept. Computer Science, University of
Michigan, Ann Arbor, 1975.
[22] A. E. Eiben, R. Hinterding, Z. Michalewicz; "Parameter control in
evolutionary algorithms" IEEE Transactions on Evolutionary
Computation, Volume: 3, Issue: 2, July 1999 Pages:124 - 141.
[23] J. D. Schaffer, R. Caruana, L. Eshelman and R. Das, "A study of control
parameters affecting online performance of genetic algorithms for
function optimization." Proceedings of the Third International
Conference on Genetic Algorithms, ed. J. D. Schaffer, Los Altos, CA:
Morgan Kaufmann, June 4-7, 1989, pp. 51-60.
[24] H. M├╝hlenbein. "How genetic algorithms really work: I.Mutation and
Hillclimbing," in Parallel Problem Solving from Nature- PPSN II, R.
Männer and B. Manderick, Eds., Amsterdam, The Netherlands, 1992,
pp. 15-25.
[25] M. Srinivas, L. M. Patnaik. "Adaptive probabilities of crossover and
mutation in genetic algorithms". IEEE Transactions on Systems, Man
and Cybernetics, Volume 24, Issue 4, April 1994 Page(s):656 - 667
[26] T. Niwa, M. Tanaka. "On the mean convergence time for simple genetic
algorithms". IEEE International Conference on Evolutionary
Computation. Volume 1, 29 Nov.-1 Dec. 1995 Page(s):373.
[27] R. L. Haupt. "Optimum population size and mutation rate for a simple
real genetic algorithm that optimizes array factors". IEEE International
Symposium Antennas and Propagation Society. Volume: 2, 16-21 July
2000. Pages:1034 - 1037
[28] S. Nijssen, T. Back; "An analysis of the behaviour of simplified
evolutionary algorithms on trap functions". IEEE Transactions on
Evolutionary Computation. Volume: 7, Issue: 1, Feb. 2003. Pages:11 -
22.
[29] M. Srinivas, L. M. Patnaik; "Genetic algorithms: a survey". IEEE JNL
Computer, Volume: 27, Issue: 6, June 1994. Pages:17 - 26
[30] T. Kalganova, J. Miller, "Evolving more efficient digital circuits by
allowing circuit layout evolution and multi-objective fitness". Proc. of
the First NASA/DoD Workshop on Evolvable Hardware. IEEE
Computer Society, Pages 54-63. July 1999
[31] T. Kalganova; "Bidirectional incremental evolution in extrinsic
evolvable hardware". Proc. of the Second NASA/DoD Workshop on
Evolvable Hardware. IEEE Computer Society, 13-15 July 2000.
Pages:65 - 74
[32] E. H. Luna, C.A. Coello Coello, A.H. Aguirre. "On the use of a
population-based particle swarm optimizer to design combinational logic
circuits". Proceedings of the 2004 NASA/DoD Conference on Evolvable
Hardware, 24-26 June 2004. Pages:183 - 190.
[33] S. Balkir, G. Diindar, G. Alpaydin,; "Evolution based synthesis of
analog integrated circuits and systems" Proceedings of the 2004
NASA/DoD Conference on Evolvable Hardware, 24-26 June 2004
Pages:26 - 29.
[34] M. Oltean, C. Grosan; "Evolving digital circuits using multi expression
programming" Proceedings of the 2004 NASA/DoD Conference on
Evolvable Hardware, 24-26 June 2004 Pages:87 - 94.
[35] Yang Zhang, S.L. Smith, A.M. Tyrrell;"Digital circuit design using
intrinsic evolvable hardware" Proceedings of the 2004 NASA/DoD
Conference on Evolvable Hardware, 24-26 June 2004 Pages:55 - 62
[36] J.C. Gallagher, S. Vigraham, G. Kramer; "A family of compact genetic
algorithms for intrinsic evolvable hardware". IEEE Transactions on
Evolutionary Computation, Volume: 8 , Issue: 2 , April 2004 Pages:111
- 126.
[37] 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.
[38] T. Bäck, F. Hoffmeister, H. P. Schwefel. "A survey of evolutionary
strategies". In R. Belew and L. Booker, editors, Proceedings of the 4th
International Conference on Genetic Algorithms, pages 2-9, San
Francisco, CA, 1991. Morgan Kaufmann.
[39] H. P. Schwefel. Numerical Optimization of Computer Models. John
Wiley & Sons, Chichester, UK, 1981.
[40] 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, pp.
439-444.
@article{"International Journal of Electrical, Electronic and Communication Sciences:55283", author = "Emanuele Stomeo and Tatiana Kalganova and Cyrille Lambert", title = "Mutation Rate for Evolvable Hardware", abstract = "Evolvable hardware (EHW) refers to a selfreconfiguration
hardware design, where the configuration is under
the control of an evolutionary algorithm (EA). A lot of research has
been done in this area several different EA have been introduced.
Every time a specific EA is chosen for solving a particular problem,
all its components, such as population size, initialization, selection
mechanism, mutation rate, and genetic operators, should be selected
in order to achieve the best results. In the last three decade a lot of
research has been carried out in order to identify the best parameters
for the EA-s components for different “test-problems". However
different researchers propose different solutions. In this paper the
behaviour of mutation rate on (1+λ) evolution strategy (ES) for
designing logic circuits, which has not been done before, has been
deeply analyzed. The mutation rate for an EHW system modifies
values of the logic cell inputs, the cell type (for example from AND
to NOR) and the circuit output. The behaviour of the mutation has
been analyzed based on the number of generations, genotype
redundancy and number of logic gates used for the evolved circuits.
The experimental results found provide the behaviour of the mutation
rate to be used during evolution for the design and optimization of
logic circuits. The researches on the best mutation rate during the last
40 years are also summarized.", keywords = "Evolvable hardware, mutation rate, evolutionarycomputation, design of logic circuit.", volume = "1", number = "7", pages = "999-8", }
