Chose the Right Mutation Rate for Better Evolve Combinational Logic Circuits

Authors: Emanuele Stomeo, Tatiana Kalganova, Cyrille Lambert

Abstract:

Evolvable hardware (EHW) is a developing field that applies evolutionary algorithm (EA) to automatically design circuits, antennas, robot controllers etc. A lot of research has been done in this area and several different EAs have been introduced to tackle numerous problems, as scalability, evolvability etc. However every time a specific EA is chosen for solving a particular task, 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 the selection of the right parameters for the EA-s components for solving different “test-problems" has been investigated. In this paper the behaviour of mutation rate for designing logic circuits, which has not been done before, has been deeply analyzed. The mutation rate for an EHW system modifies the number of inputs of each logic gates, the functionality (for example from AND to NOR) and the connectivity between logic gates. The behaviour of the mutation has been analyzed based on the number of generations, genotype redundancy and number of logic gates for the evolved circuits. The experimental results found provide the behaviour of the mutation rate during evolution for the design and optimization of simple logic circuits. The experimental results propose the best mutation rate to be used for designing combinational logic circuits. The research presented is particular important for those who would like to implement a dynamic mutation rate inside the evolutionary algorithm for evolving digital circuits. The researches on the mutation rate during the last 40 years are also summarized.

Keywords: Design of logic circuit, evolutionary computation, evolvable hardware, mutation rate.

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

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] H. de Garis. "An Artificial Brain: ATR's CAM-Brain Project Aims to Build/Evolve an Artificial Brain with a Million Neural Net Modules Inside a Trillion Cell Cellular Automata Machine", New Generation Computing J., 12, no. 2, pp. 215 - 221. 1994.
[4] D. E. Goldberg. Genetic algorithm in search, optimization and machine learning. Addison-Wesley Publishing Company, Incorporated, Reading, Massachusetts, 1989.
[5] J. Holland. Adaptation in Natural and Artificial Systems. Ann Arbor, MI: University of Michigan Press, 1975.
[6] M. D. Vose. "The Simple Genetic Algorithm". MA: MIT Press 1999.
[7] J. R Koza. Genetic Programming: On the Programming of Computers by Means of Natural selection. ISBN 0-262-11170-5. MIT Press, 1992.
[8] I. Rechenberg, "Evolution Strategy", in J. Zurada, R. Marks II, and C. Robinson (Eds.), Computational Intelligence: Imitating Life, 1994, pp. 147-159.
[9] 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.
[10] T. Bäck, Evolutionary Algorithms in Theory and Practice. New York: Oxford Univ. Press, 1996.
[11] H.-P. Schwefel, Numerical Optimization of Computer Models. New York: Wiley, 1981.
[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] 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.
[16] 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.
[17] 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.
[18] J. J. Grefenstette, "Optimization of control parameters for genetic algorithms," IEEE Trans. Systems, Man, Cybernetics. Vol. 16, no. 1, pp. 122-128, 1986.
[19] 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.
[20] 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.
[21] 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.
[22] 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.
[23] 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
[24] 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.
[25] 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
[26] 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.
[27] M. Srinivas, L. M. Patnaik; "Genetic algorithms: a survey". IEEE JNL Computer, Volume: 27, Issue: 6, June 1994. Pages:17 - 26
[28] 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
[29] 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.
[30] 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.
[31] 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.
[32] 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.
[33] 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
[34] 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.
[35] 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.
[36] 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.
[37] H. P. Schwefel. Numerical Optimization of Computer Models. John Wiley & Sons, Chichester, UK, 1981.
[38] 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.
[39] A. Stoica, R. Zebulum, D. Keymeulen. "Mixtrinsic Evolution". In Fogarty, T., Miller, J., Thompson, A., Thompson, P. (Eds.), Proceedings of the Third International Conference on Evolvable systems: From Biology to Hardware (ICES2000), April 17-19, 2000, Edinburgh, UK. New York, USA, Springer Verlag, 208-217.
[40] J. Torresen. "Possibilities and Limitations of Applying Evolvable Hardware to Real-World Applications". Proc. of the 10th International Conference on Field Programmable Logic and Applications, Villach, Austria, pp. 230-239. 2000.
[41] P. Andersen P. "Evolvable Hardware: Artificial Evolution of Hardware Circuits in Simulation and Reality", M.Sc. Thesis, University of Aarhus, Denmark. 1998.
[42] Timothy G. W. Gordon and Peter J. Bentley. "On Evolvable Hardware". In Ovaska, S. and Sztandera, L. Soft Computing in Industrial Electronics. Physica-Verlag, Heidelberg, Germany, pp. 279-323. 2002.
[43] A. J. Hirst. "Notes on the Evolution of Adaptive Hardware", Proc. of Adaptive Computing in Engineering Design and Control, Plymouth, U.K., pp. 212-219. 1996.
[44] D. Beasley, D. R. Bull, R. R. Martin. "An Overview of Genetic Algorithms: Part 1, Fundamentals". University Computing, 1993, 15(2) 58-69; ┬®Inter-University Committee on Computing.
[45] E. Stomeo et al. "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.