Article

An efficient selection strategy for digital circuit evolution

Authors:

Lukáš SekaninaAuthors Info & Claims

ICES'10: Proceedings of the 9th international conference on Evolvable systems: from biology to hardware

Pages 13 - 24

Published: 06 September 2010 Publication History

Abstract

In this paper, we propose a new modification of Cartesian Genetic Programming (CGP) that enables to optimize digital circuits more significantly than standard CGP. We argue that considering fully functional but not necessarily smallest-discovered individual as the parent for new population can decrease the number of harmful mutations and so improve the search space exploration. This phenomenon was confirmed on common benchmarks such as combinational multipliers and the LGSynth91 circuits.

References

[1]

Miller, J.F., Job, D., Vassilev, V.K.: Principles in the Evolutionary Design of Digital Circuits - Part I. Genetic Programming and Evolvable Machines 1(1), 8-35 (2000).

Digital Library

[2]

Vassilev, V., Job, D., Miller, J.: Towards the Automatic Design of More Efficient Digital Circuits. In: Proc. of the 2nd NASA/DoD Workshop on Evolvable Hardware, pp. 151-160. IEEE Computer Society, Los Alamitos (2000).

Digital Library

[3]

Kalganova, T., Miller, J.F.: Evolving more efficient digital circuits by allowing circuit layout evolution and multi-objective fitness. In: The First NASA/DoD Workshop on Evolvable Hardware, pp. 54-63. IEEE Computer Society, Los Alamitos (1999).

Digital Library

[4]

Gajda, Z., Sekanina, L.: Reducing the number of transistors in digital circuits using gate-level evolutionary design. In: 2007 Genetic and Evolutionary Computation Conference, pp. 245-252. ACM, New York (2007).

Digital Library

[5]

Gajda, Z., Sekanina, L.: When does cartesian genetic programming minimize the phenotype size implicitly? In: Genetic and Evolutionary Computation Conference. ACM, New York (2010) (accepted).

Digital Library

[6]

Vassilev, V.K., Miller, J.F.: The advantages of landscape neutrality in digital circuit evolution. In: Miller, J.F., Thompson, A., Thompson, P., Fogarty, T.C. (eds.) ICES 2000. LNCS, vol. 1801, pp. 252-263. Springer, Heidelberg (2000).

Digital Library

[7]

Miller, J.F., Smith, S.L.: Redundancy and Computational Efficiency in Cartesian Genetic Programming. IEEE Transactions on Evolutionary Computation 10(2), 167-174 (2006).

Digital Library

[8]

Miller, J.F., Job, D., Vassilev, V.K.: Principles in the Evolutionary Design of Digital Circuits - Part II. Genetic Programming and Evolvable Machines 1(3), 259-288 (2000).

Digital Library

[9]

Miller, J., Thomson, P.: Cartesian Genetic Programming. In: Poli, R., Banzhaf, W., Langdon, W.B., Miller, J., Nordin, P., Fogarty, T.C. (eds.) EuroGP 2000. LNCS, vol. 1802, pp. 121-132. Springer, Heidelberg (2000).

Digital Library

[10]

Yu, T., Miller, J.F.: Neutrality and the evolvability of boolean function landscape. In: Miller, J., Tomassini, M., Lanzi, P.L., Ryan, C., Tetamanzi, A.G.B., Langdon, W.B. (eds.) EuroGP 2001. LNCS, vol. 2038, pp. 204-217. Springer, Heidelberg (2001).

Digital Library

[11]

Collins, M.: Finding needles in haystacks is harder with neutrality. In: GECCO 2005: Proceedings of the 2005 conference on Genetic and evolutionary computation, pp. 1613-1618. ACM, New York (2005).

Digital Library

[12]

Miller, J.: What bloat? cartesian genetic programming on boolean problems. In: 2001 Genetic and Evolutionary Computation Conference Late Breaking Papers, pp. 295-302 (2001).

[13]

Yang, S.: Logic Synthesis and Optimization Bechmarks User Guide, Version 3.0 (1991).

[14]

Berkley Logic Synthesis and Verification Group (ABC: A System for Sequential Synthesis and verification).

[15]

Weste, N., Harris, D.: CMOS VLSI Design: A Circuits and Systems Perspective, 3rd edn. Addison-Wesley, Reading (2004).

Cited By

Manazir ARaza K(2019)Recent Developments in Cartesian Genetic Programming and its VariantsACM Computing Surveys10.1145/327551851:6(1-29)Online publication date: 28-Jan-2019
https://dl.acm.org/doi/10.1145/3275518
Bremner PSamie MDragffy GPipe1 ALiu Y(2011)Evolving cell array configurations using CGPProceedings of the 14th European conference on Genetic programming10.5555/2008307.2008315(73-84)Online publication date: 27-Apr-2011
https://dl.acm.org/doi/10.5555/2008307.2008315
Sekanina LLanzi P(2011)Evolution of digital circuitsProceedings of the 13th annual conference companion on Genetic and evolutionary computation10.1145/2001858.2002140(1343-1360)Online publication date: 12-Jul-2011
https://dl.acm.org/doi/10.1145/2001858.2002140

An efficient selection strategy for digital circuit evolution
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies

Recommendations

Scalability Problems of Digital Circuit Evolution: Evolvability and Efficient Designs
EH '00: Proceedings of the 2nd NASA/DoD workshop on Evolvable Hardware

A major problem in the evolutionary design of combinational circuits is the problem of scale. This refers to the design of electronic circuits in which the number of gates required to implement the optimal circuit is too high to search the space of all ...
The Advantages of Landscape Neutrality in Digital Circuit Evolution
ICES '00: Proceedings of the Third International Conference on Evolvable Systems: From Biology to Hardware

The paper studies the role of neutrality in the fitness landscapes associated with the evolutionary design of digital circuits and particularly the three-bit binary multiplier. For the purpose of the study, digital circuits are evolved extrinsically on ...
Self-adaptive differential evolution algorithm with improved mutation strategy

Different mutation strategies and control parameters settings directly affect the performance of differential evolution (DE) algorithm. In this paper, a self-adaptive differential evolution algorithm with improved mutation strategy (IMSaDE) is proposed ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

ICES'10: Proceedings of the 9th international conference on Evolvable systems: from biology to hardware

September 2010

394 pages

ISBN:3642153224

Editors:
Gianluca Tempesti
University of York, Department of Electronics, Intelligent Systems Group, York, UK
,
Andy M. Tyrrell
University of York, Department of Electronics, Intelligent Systems Group, York, UK
,
Julian F. Miller
University of York, Department of Electronics, Intelligent Systems Group, York, UK

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 06 September 2010

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Manazir ARaza K(2019)Recent Developments in Cartesian Genetic Programming and its VariantsACM Computing Surveys10.1145/327551851:6(1-29)Online publication date: 28-Jan-2019
https://dl.acm.org/doi/10.1145/3275518
Bremner PSamie MDragffy GPipe1 ALiu Y(2011)Evolving cell array configurations using CGPProceedings of the 14th European conference on Genetic programming10.5555/2008307.2008315(73-84)Online publication date: 27-Apr-2011
https://dl.acm.org/doi/10.5555/2008307.2008315
Sekanina LLanzi P(2011)Evolution of digital circuitsProceedings of the 13th annual conference companion on Genetic and evolutionary computation10.1145/2001858.2002140(1343-1360)Online publication date: 12-Jul-2011
https://dl.acm.org/doi/10.1145/2001858.2002140

View Options

View options

Figures

Tables

Media

View Table of Conten