On the Use of Clonal Selection Principle in Cartesian Genetic Programming for Designing Combinational Logic Circuits

• José Eduardo H. da Silva UFJF
• Luciana N. S. Prachedes UFJF
• Heder S. Bernardino UFJF
• José J. Camata UFJF
• Itamar L. de Oliveira UFJF

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

Resumo

Evolutionary techniques have been used in the design and optimization of combinational logic circuits. This procedure is called evolvable hardware and Cartesian Genetic Programming (CGP) is the evolutionary technique with the best performance in this context. Despite the good results obtained by CGP techniques, its search procedure usually evolves a single candidate solution by an evolution strategy and this approach tends to be trapped in local optima. On the other hand, clonal selection techniques in general, and CLONALG in particular, were designed to avoid converging to a low-quality local optimum. Thus, we propose here using the representation of CGP with the search procedure of a Clonal Selection Algorithm to minimize the number of transistors of combinational logic circuits. Furthermore, a parameter sensitivity analysis is performed. The results are assessed considering a benchmark from the literature and showed a reduction in the number of transistors when compared to the baseline ESPRESSO.

Referências

Barbosa, H. J., Bernardino, H. S., and Barreto, A. M. (2010). Using performance profiles to analyze the results of the 2006 cec constrained optimization competition. In Evolutionary Computation (CEC), 2010 IEEE Congress on, pages 1-8. IEEE.

Bernardino, H. S. and Barbosa, H. J. (2009a). Artificial immune systems for optimization. In Nature-Inspired Algorithms for Optimisation, pages 389-411. Springer.

Bernardino, H. S. and Barbosa, H. J. C. (2009b). Nature-Inspired Algorithms for Optimisation, chapter Artificial Immune Systems for Optimization, pages 389-411. Springer Berlin / Heidelberg.

Bernardino, H. S. and Barbosa, H. J. C. (2011). Grammar-based immune programming. Nat. Comput., 10(1):209-241.

Coello, C., Aguirre, A., and Buckles, B. (2000). Evolutionary multiobjective design of combinational logic circuits. In Proceedings. The Second NASA/DoD Workshop on Evolvable Hardware, pages 161-170. IEEE.

da Silva, J. E. and Bernardino, H. S. (2018). Cartesian genetic programming with crossover for designing combinational logic circuits. In 2018 7th Brazilian Conference on Intelligent Systems (BRACIS), pages 145-150. IEEE.

da Silva, J. E. H., Manfrini, F. A., Bernardino, H. S., and Barbosa, H. J. (2018). Biased mutation and tournament selection approaches for designing combinational logic circuits via cartesian genetic programming. In Anais do XV Encontro Nacional de Inteligência Artificial e Computacional, pages 835-846. SBC.

de Castro, L. N. and von Zuben, F. J. (2002). Learning and optimization using the clonal selection principle. IEEE Trans. Evo. Comp., 6(3):239-251.

de Souza, L. A. M., da Silva, J. E. H., Chaves, L. J., and Bernardino, H. S. (2020). A benchmark suite for designing combinational logic circuits via metaheuristics. Applied Soft Computing, 91:106246.

Deb, K. (2000). An efficient constraint handling method for genetic algorithms. Computer Methods in Applied Mechanics and Engineering, 186(2):311-338.

Delves, P. J. and Roitt, I. M. (2000). The immune system. New England journal of medicine, 343(1):37-49.

Dolan, E. D. and Moré, J. J. (2002). Benchmarking optimization software with performance profiles. Mathematical Program., 91(2):201-213.

Fan, X., Sayers, W., Zhang, S., Han, Z., Ren, L., and Chizari, H. (2020). Review and classification of bio-inspired algorithms and their applications. Journal of Bionic Engineering, 17(3):611-631.

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

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

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

Haddow, P. C. and Tyrrell, A. M. (2018). Evolvable hardware challenges: Past, present and the path to a promising future. Inspired by Nature, pages 3-37.

Hatata, A. Y., Osman, M. G., and Aladl, M. M. (2017). A review of the clonal selection algorithm as an optimization method. Leonardo Journal of Sciences, 16(30):1-14.

Hodan, D., Mrazek, V., and Vasicek, Z. (2021). Semantically-oriented mutation operator in cartesian genetic programming for evolutionary circuit design. Genetic Programming and Evolvable Machines, 22(4):539-572.

Husa, J. and Kalkreuth, R. (2018). A comparative study on crossover in cartesian genetic programming. In European Conference on GP, pages 203-219. Springer.

Ji, Z. and Dasgupta, D. (2007). Revisiting negative selection algorithms. Evolutionary computation, 15(2):223-251.

Manfrini, F. A., Bernardino, H. S., and Barbosa, H. J. (2016). A novel efficient mutation for evolutionary design of combinational logic circuits. In International Conference on Parallel Problem Solving from Nature, pages 665-674. Springer.

Miller, J. F. (2011). Cartesian genetic programming. In Cartesian genetic programming, pages 17-34. Springer.

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

Vasicek, Z. (2015). Cartesian gp in optimization of combinational circuits with hundreds of inputs and thousands of gates. In European Conference on Genetic Programming, pages 139-150. Springer.

Walker, J. A., Miller, J. F., and Cavill, R. (2006). A multi-chromosome approach to standard and embedded cartesian genetic programming. In Proceedings of the 8th annual conference on Genetic and evolutionary computation, pages 903-910. ACM.

Wang, J., Chen, Q. S., and Lee, C. H. (2008). Design and implementation of a virtual reconfigurable architecture for different applications of intrinsic evolvable hardware. IET Computers & Digital Techniques, 2(5):386-400.

Zhang, W., Yen, G. G., and He, Z. (2013). Constrained optimization via artificial immune system. IEEE Transactions on Cybernetics, 44(2):185-198.