Biased Mutation and Tournament Selection Approaches for Designing Combinational Logic Circuits via Cartesian Genetic Programming

• José Eduardo H. da Silva UFJF
• Francisco A. L. Manfrini IFSudesteMG
• Heder S. Bernardino UFJF
• Helio J. C. Barbosa LNCC

DOI: https://doi.org/10.5753/eniac.2018.4471

Resumo

Cartesian Genetic Programming (CGP) is often applied to design combinational logic circuits. However, there is no consensus in the literature regarding the more appropriate objective function when it is desired to minimize the number of logic gates of the circuit. Thus, we analyze here two strategies: the minimization of the number of logic gates and the maximization of the number of wire gates. Additionally, a biased mutation strategy for CGP, which were previously presented and tested only to find a feasible solution, are extended in this paper for the subsequent optimization step. Several configurations were proposed and tested varying objective function and selection schemes. Compu- tational experiments are conducted with some benchmark circuits to relatively compare the proposed methods, and the results obtained are better than those found by the other techniques considered here.

Referências

Brayton, R. K., Hachtel, G. D., McMullen, C., and Sangiovanni-Vincentelli, A. (1984).

Logic minimization algorithms for VLSI synthesis. Springer Science & Business Md.

Coello, C., Aguirre, A., and Buckles, B. (2000a). Evolutionary multiobjective design of combinational logic circuits. In Proc. of the 2nd NASA/DoD Workshop on Evolvable Hardware, pages 161–170. IEEE.

Coello, C. A., Christiansen, A. D., and Aguirre, A. H. (1997). Automated design of combinational logic circuits using genetic algorithms. In Intl. Conf. on Artificial Neural

Nets and Genetic Algorithms, pages 335–338.

Coello, C. A. C. and Aguirre, A. H. (2002). Design of combinational logic circuits through an evolutionary multiobjective optimization approach. AI EDAM, 16(1):39–53.

Coello, C. A. C., Alba, E., and Luque, G. (2003a). Comparing different serial and parallel heuristics to design combinational logic circuits. In Proc. of the 2003 NASA/DoD Conference on Evolvable Hardware, pages 3–12.

Coello, C. A. C., Christiansen, A. D., and Aguirre, A. H. (2000b). Towards automated evolutionary design of combinational circuits. Computers & Electrical Engineering, 27(1):1–28.

Coello, C. A. C., Christiansen, A. D., and Aguirre, A. H. (2000c). Use of evolutionary techniques to automate the design of combinational circuits. Intl. J. of Smart Engineer- ing System Design, 2:299–314.

Coello, C. A. C., Luna, E. H., Aguirre, A. H., et al. (2003b). Use of particle swarm optimization to design combinational logic circuits. In ICES, pages 398–409. Springer.

Coello, C. A. C., Zavala, R. L. G., García, B. M., and Aguirre, A. H. (2000d). Ant colony system for the design of combinational logic circuits. In Intl. Conf. on Evolvable Systems, pages 21–30. Springer.

Coello, C. C., Luna, E. H., and Aguirre, A. H. (2004). A comparative study of encodings to design combinational logic circuits using particle swarm optimization. In Proc. of the 2004 NASA/DoD Conference on Evolvable Hardware, pages 71–78. IEEE.

Damiani, M., Yang, J.-Y., and De Micheli, G. (1995). Optimization of combinational logic circuits based on compatible gates. IEEE Trans. on Computer-Aided Design of Integrated Circuits and Systems, 14(11):1316–1327.

García, B.M. and Coello, C. A. C. (2002). An approach based on the use of the ant system to design combinational logic circuits. Mathware and Soft Comp, 9(2-3):235–250.

Goldman, B. W. and Punch, W. F. (2013). Reducing wasted evaluations in cartesian genetic programming. In European Conf. on GP, pages 61–72. Springer.

Goldman, B. W. and Punch, W. F. (2015). Analysis of cartesian genetic programmings evolutionary mechanisms. IEEE Trans. on Evolutionary Computation, 19(3):359–373.

Hilder, J.,Walker, J. A., and Tyrrell, A. (2010). Use of a multi-objective fitness function to improve cartesian genetic programming circuits. In 2010 NASA/ESA Conf. on Adaptive Hardware and Systems, pages 179–185.

Karakatic, S., Podgorelec, V., and Hericko, M. (2013). Optimization of combinational logic circuits with genetic programming. Elektronika ir Elektrotechnika, 19(7):86–89.

Kazarlis, S., Kalomiros, J., and Kalaitzis, V. (2016). A cartesian genetic programming approach for evolving optimal digital circuits. Journal of Engineering Science & Tech- nology Review, 9(5).

Kazarlis, S., Kalomiros, J., Mastorocostas, P., Petridis, V., Balouktsis, A., Kalaitzis, V., and Valais, A. (2014). A method for simulating digital circuits for evolutionary optimization. In Intl. Joint Conf. on Computer, Information, and Systems Sciences, and Engineering (CISSE).

Manfrini, F. A. L., Bernardino, H. S., and Barbosa, H. J. C. (2016a). A novel efficient mutation for evolutionary design of combinational logic circuits. In Intl. Conf. on Parallel Problem Solving from Nature, pages 665–674. Springer.

Manfrini, F. A. L., Bernardino, H. S., and Barbosa, H. J. C. (2016b). On heuristics for seeding the initial population of cartesian genetic programming applied to combinational logic circuits. In Genetic and Evol. Comp. Conf. (GECCO), pages 105–106.

McCluskey, E. J. (1956). Minimization of boolean functions. Bell Labs Technical Journal, 35(6):1417–1444.

Miller, J. F. (1999). An empirical study of the efficiency of learning boolean functions using a cartesian genetic programming approach. In Proc. of the 1st Annual Conf. on Genetic and Evolutionary Comp. Vol 2, pages 1135–1142. Morgan Kaufmann Pub Inc.

Miller, J. F. (2011a). Cartesian Genetic Programming, volume 09-2011 of Natural Computing Series. Springer, 2011 edition.

Miller, J. F. (2011b). Cgp. Cartesian Genetic Programming, pages 17–34.

Miller, J. F., Job, D., and Vassilev, V. K. (2000). Principles in the evolutionary design of digital circuits, part i. Genetic programming and evolvable machines, 1(1-2):7–35.

Sasao, T. (1993). Logic synthesis and optimization, volume 1. Springer.

Stepney, S. and Adamatzky, A. (2017). Inspired by Nature: Essays Presented to Julian F. Miller on the Occasion of His 60th Birthday, volume 28. Springer.

Stomeo, E., Kalganova, T., Lambert, C., Lipnitsakya, N., and Yatskevich, Y. (2005). On evolution of relatively large combinational logic circuits. In Proc. of the 2005 NASA/DoD Conference on Evolvable Hardware, pages 59–66.

Thompson, A., Harvey, I., and Husbands, P. (1996). Unconstrained evolution and hard consequences. In Towards evolvable hardware, pages 136–165. Springer.

Vasicek, Z. (2015). Cartesian gp in optimization of combinational circuits with hundreds of inputs and thousands of gates. In European Conf. on GP, pages 139–150. Springer.

Vasicek, Z. (2018). Bridging the gap between evolvable hardware and industry using cartesian genetic programming. In Inspired by Nature, pages 39–55. Springer.

Vasicek, Z. and Sekanina, L. (2015). Circuit approximation using single-and multiobjective cartesian gp. In European Conf. on GP, pages 217–229. Springer.

Vassilev, V. K., Job, D., and Miller, J. F. (2000). Towards the automatic design of more efficient digital circuits. In NASA/DoD Workshop on Evol. Hardware, pages 151–160.

Wang, P. (2014). A comprehensive technique for majority/minority logic synthesis with applications in nanotechnology. The University of Toledo.