Chose the Right Mutation Rate for Better Evolve Combinational Logic Circuits

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.




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.