Abstract
We introduce a method, based on a genetic algorithm (GA) approach, to design combinational logic circuits. This problem is quite difficult for a traditional GA, but we have overcome these difficulties and have implemented a computer program that can automatically generate high-quality circuit designs. We describe the important issues to consider when solving this circuit design problem: the importance of the representation scheme, the encoding function, and the definition of the fitness function. We present several circuits derived by our system under various assumed constraints, such as the maximum number of allowable gates and the types of available gates. We compare the solutions produced by our system against those generated by a human designer. We also show that our representation approach, when compared to a standard binary encoding, produces better performance both in terms of quality of solution and in terms of speed of convergence.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
R.K. Brayton, G.D. Hachtel, C.T. McMullen, and A.L. Sangiovanni-Vincentelli. Logic Minimization Algorithms for VLSI Synthesis. Kluwer Academic Publishers, 1984.
R.K. Brayton, R. Rudell, A. Sangiovanni-Vincentelli, and A.R. Wang. Mis: A multiple-level logic optimization system. IEEE Transactions on Computer-Aided Design, CAD-6(6):1062–1081, November 1987.
David E. Goldberg. Genetic Algorithms in Search, Optimization and Machine Learning. Reading, Mass.: Addison-Wesley Publishing Co., 1989.
J.H. Holland. Adaptation in Natural and Artificial Systems. An Introductory Analysis with Applications to Biology, Control and Artificial Intelligence. MIT Press, Cambridge, Massachusetts, 1992.
M. Karnaugh. A map method for synthesis of combinational logic circuits. Transactions of the AIEE, Communications and Electronics, 72(I): 593–599, November 1953.
J.R. Koza. Genetic Programming. On the Programming of Computers by Means of Natural Selection. The MIT Press, 1992.
S.J. Louis and G.J. Rawlins. Using genetic algorithms to design structures. Technical Report 326, Computer Science Department, Indiana University, Bloomington, Indiana, feb 1991.
S.J. Louis. Genetic Algorithms as a Computational Tool for Design. PhD thesis, Department of Computer Science, Indiana University, aug 1993.
E.J. McCluskey. Minimization of boolean functions. Bell Systems Technical journal, 35(5):1417–1444, November 1956.
W.V. Quine. A way to simplify truth functions. American Mathematical Monthly, 62(9):627–631, 1955.
C.H. Roth, Jr. Fundamentals of Logic Design (4th Edition). West Publishing Company, 1992.
C.E. Shannon. A symbolic analysis of relay and switching circuits. Transactions of the AIEE, 57:713–723, 1938.
E.W. Veitch. A chart method for simplifying boolean functions. Proceedings of the ACM, pages 127–133, May 1952.
Author information
Authors and Affiliations
Rights and permissions
Copyright information
© 1998 Springer-Verlag Wien
About this paper
Cite this paper
Coello Coello, C.A., Christiansen, A.D., Aguirre, A.H. (1998). Automated Design of Combinational Logic Circuits by Genetic Algorithms. In: Artificial Neural Nets and Genetic Algorithms. Springer, Vienna. https://doi.org/10.1007/978-3-7091-6492-1_73
Download citation
DOI: https://doi.org/10.1007/978-3-7091-6492-1_73
Publisher Name: Springer, Vienna
Print ISBN: 978-3-211-83087-1
Online ISBN: 978-3-7091-6492-1
eBook Packages: Springer Book Archive