Intrinsic evolution of digital circuits using evolutionary algorithms

ABSTRACT

Currently, the auto-design of electronic and analog circuits is an intensively studied topic in the field of evolvable hardware. In order to improve evolutionary design of logic circuits in efficiency, capability of optimization and safety of on-line evolution, an elitist pool evolutionary algorithm (EPEA) based on novel approaches is proposed. First, an extended matrix encoding method is devised, which can be able to reflect the potential performance of a circuit and reduce the risk of deleting a circuit with a good developing potential during evolution. Then, a novel sub-circuit crossover operator and an adaptive mutation strategy are introduced to improve the local optimization and maintain the diversity of a population in the evolution. At last, a framework of on-line evolution is used to implement EPEA on a field-programmable gate array. Experiments show that our proposed method is able to design valid and novel circuits efficiently.

REFERENCES

• 1: Garis, H. d., Evolvable hardware: Genetic programming of a Darwin machine, Int. Conf. Artif. Neural Nets Genetic Algorithms, 1993:441--449.
• 2: Yao, X. and Higuchi, T., Promises and challenges of evolvable hardware, IEEE Transactions on Systems Man and Cybernetics Part C-Applications and Reviews, 1999, 29(1):87--97.
• 3: Yukari Ishida , Hirotaka Nosato , Eiichi Takahashi , Masahiro Murakawa , Isamu Kajitani , Tatsumi Furuya , Tetsuya Higuchi, Proposal for LDPC Code Design System Using Multi-Objective Optimization and FPGA-Based Emulation, Proceedings of the 8th international conference on Evolvable Systems: From Biology to Hardware, September 21-24, 2008, Prague, Czech Republic [doi>10.1007/978-3-540-85857-7_21]
• 4: Carlos A. Coello Coello , Arturo Hernández Aguirre, Design of combinational logic circuits through an evolutionary multiobjective optimization approach, Artificial Intelligence for Engineering Design, Analysis and Manufacturing, v.16 n.1, p.39-53, January 2002 [doi>10.1017/S0890060401020054]
• 5: Ricardo S. Zebulum , Marley S. Vellasco , Marco Aurélio Pacheco, Variable Length Representation in Evolutionary Electronics, Evolutionary Computation, v.8 n.1, p.93-120, March 2000 [doi>10.1162/106365600568112]
• 6: Kalganova, T. and Miller, J. F., Circuit layout evolution: An evolvable hardware approach, IEE Colloquium (Digest), 1999:11--14.
• 7: Julian F. Miller , Dominic Job , Vesselin K. Vassilev, Principles in the Evolutionary Design of Digital Circuits—Part II, Genetic Programming and Evolvable Machines, v.1 n.3, p.259-288, July 2000 [doi>10.1023/A:1010066330916]
• 8: Michal Bidlo , Zdenek Vašícek, Gate-Level Evolutionary Development Using Cellular Automata, Proceedings of the 2008 NASA/ESA Conference on Adaptive Hardware and Systems, p.11-18, June 22-25, 2008 [doi>10.1109/AHS.2008.31]
• 9: Torresen, J., Evolving Multiplier Circuits by Training Set and Training Vector Partitioning, Evolvable Systems: From Biology to Hardware: 5th International Conference (ICES 2003), 2003:228--237.
• 10: Stomeo, E., Kalganova, T. and Lambert, C., Generalized Disjunction Decomposition for Evolvable Hardware, IEEE Transactions on,Systems, Man and Cybernetics (Part B), 2006, 36(5):1024--1043.
• 11: Adrian Thompson, An Evolved Circuit, Intrinsic in Silicon, Entwined with Physics, Proceedings of the First International Conference on Evolvable Systems: From Biology to Hardware, p.390-405, October 07-08, 1996
• 12: Andres Upegui , Eduardo Sanchez, Evolving Hardware with Self-reconfigurable connectivity in Xilinx FPGAs, Proceedings of the first NASA/ESA conference on Adaptive Hardware and Systems, p.153-162, June 15-18, 2006 [doi>10.1109/AHS.2006.38]
• 13: Blodget, B., Bobda, C., Huebner, M. and Niyonkuru, A.,Partial and Dynamically Reconfiguration of Xilinx Virtex-II FPGAs, The14th International Conference on Field Programmable Logic and Application(FPL2004), Antwerp, Belgium, August,pp:801--810, 2004.
• 14: Blodget, B., James-Roxby, P., Keller, E., McMillan, S. and Sundararajan, P.,A, Self-reconfiguring Platform, The13th International Conference on Field Programmable Logic and Application(FPL2003), Lisbon, Portugal, September,pp:565--574, 2003.
• 15: Sekanina, L. and Friedl, S. On Routine Implementation of Virtual Evolvable Devices Using COMBO6, The 6th NASA /DoD Workshop on Evolvable Hardware (EH 2004), Seattle, WA, USA, June,pp:63--70,2004.
• 16: Pauline C. Haddow , Gunnar Tufte, Bridging The Genotype-Phenotype Mapping For Digital Fpgas, Proceedings of the The 3rd NASA/DoD Workshop on Evolvable Hardware, p.109, July 12-14, 2001
• 17: Louis, S. J., Genetic algorithms as a computational tool for design, 1993, Indiana,USA: Indiana university.
• 18: Adrian Thompson, An Evolved Circuit, Intrinsic in Silicon, Entwined with Physics, Proceedings of the First International Conference on Evolvable Systems: From Biology to Hardware, p.390-405, October 07-08, 1996
• 19: Nadia Nedjah , Luiza de Macedo Mourelle, A comparison of two circuit representations for evolutionary digital circuit design, Proceedings of the 17th international conference on Innovations in applied artificial intelligence, p.594-604, May 17-20, 2004, Ottawa, Canada [doi>10.1007/b97304]
• 20: Coello Coello, C. A., Luna, E. H. and Aguirre, A. H., A comparative study of encodings to design combinational logic circuits using particle swarm optimization, the The 2004 NASA/Dod Conference on Evolvable Hardware, 2004:71--78.
• 21: MOORE, P. W. and VENAYAGMOORTHY, G. K., Evolving digital circuits using hybrid particle swarm optimization and differential evolution, International Journal of neural systems, 2006, 16(3):163--177.

INDEX TERMS

Primary Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Automatic synthesis

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.3 Design Aids
          Subjects: Optimization

General Terms:
Algorithms, Design, Performance

Keywords:
evolutionary algorithm, evolvable hardware, logic circuit