Mutation Rate for Evolvable Hardware

Authors: Emanuele Stomeo, Tatiana Kalganova, Cyrille Lambert

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.

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

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] 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.