Comparative study of serial and parallel heuristics used to design combinational logic circuits. (English) Zbl 1134.94410
Summary: We perform a comparative study of different heuristics used to design combinational logic circuits. This study mainly emphasizes the use of local search hybridized with a genetic algorithm (GA) and the impact of introducing parallelism. Our results indicate that a hybridization of a GA with a local search algorithm (simulated annealing) is beneficial and that the use of parallelism not only introduces a speedup in the algorithms compared (as expected) but also allows us to improve the quality of the solutions found.
MSC:
| 94C30 | Applications of design theory to circuits and networks |
Keywords:
combinational logic circuits; genetic algorithms; metaheuristics; simulated annealing; parallelization; hybridizationReferences:
| [1] | Karnaugh M., Transactions of the AIEE, Communications and Electronics pp 593– (1953) |
| [2] | Veitch, E. W. A chart method for simplifying boolean functions. Proceedings of the ACM. pp.127–133. New York: ACM Press. |
| [3] | McCluskey E. J., Bell Systems Technical Journal 35 pp 1417– (1956) |
| [4] | DOI: 10.2307/2307285 · Zbl 0068.24209 · doi:10.2307/2307285 |
| [5] | Coello Coello C. A., International Journal of Smart Engineering System Design 2 pp 299– (2000) · Zbl 1066.01025 |
| [6] | DOI: 10.1023/A:1010016313373 · Zbl 1006.68633 · doi:10.1023/A:1010016313373 |
| [7] | DOI: 10.1080/0305215031000091569 · doi:10.1080/0305215031000091569 |
| [8] | Miller, J., Kalganova, T., Lipnitskaya, N. and Job, D. The genetic algorithm as a discovery engine: strange circuits and new principles. Proceedings of the AISB Symposium on Creative Evolutionary Systems (CES’99). Edinburgh, UK: The University of Edinburgh. |
| [9] | Coello Coello, C. A., Christiansen, A. D. and Hernández Aguirre, A. Automated design of combinational logic circuits using genetic algorithms. Proceedings of the International Conference on Artificial Neural Nets and Genetic Algorithms, Edited by: Smith, D. G., Steele, N. C. and Albrecht, R. F. pp.335–338. Springer-Verlag. · Zbl 1006.68579 |
| [10] | Louis, S. J. 1993. ”Genetic algorithms as a computational tool for design”. Indiana University. PhD thesis, Department of Computer Science |
| [11] | Louis, S. J. and Rawlins, G. J. 1991. ”Using genetic algorithms to design structures”. Bloomington, Indiana: Indiana University. Technical Report 326, Computer Science Department |
| [12] | Miller J. F., Genetic Algorithms and Evolution Strategy in Engineering and Computer Science pp 105– (1998) |
| [13] | Banzhaf W., Genetic Programming. An Introduction. On the Automatic Evolution of Computer Programs and Its Applications (1998) · Zbl 0893.68117 |
| [14] | Al-Saiari, U. S. 2003. ”Digital circuit design through simulated evolution”. Dhahran, Saudi Arabia: King Fahd University of Petroleum and Minerals. Master’s thesis |
| [15] | Slowik, A. and Bialko., M. Design and optimization of combinational digital circuits using modified evolutionary algorithm. 7th International Conference in Artificial Intelligence and Soft Computing–ICAISC 2004. Edited by: Rutkowski, L., Siekmann, J. H., Tadeusiewicz, R. and Zadeh, L. A. Vol. 3070, June. pp.468–473. Zakopane, Poland: Springer-Verlag. Lecture Notes in Computer Science |
| [16] | Vassilev, V. K., Miller, J. F. and Fogarty, T. C. Digital circuit evolution and fitness landscapes. 1999. Congress on Evolutionary Computation. Vol. 2, July. pp.1299–1306. Washington, DC: IEEE Service Center. |
| [17] | DOI: 10.1023/A:1010066330916 · Zbl 1035.68640 · doi:10.1023/A:1010066330916 |
| [18] | DOI: 10.1162/106365600568095 · doi:10.1162/106365600568095 |
| [19] | Abd-El-Barr, M., Sait, S. M., Sarif, B. A.B and Al-Saiari, U. A modified ant colony algorithm for evolutionary design of digital circuits. Proceedings of the 2003 Congress on Evolutionary Computation (CEC’2003). pp.708–715. Canberra: IEEE Press. |
| [20] | DOI: 10.1007/3-540-46406-9_3 · doi:10.1007/3-540-46406-9_3 |
| [21] | Coello Coello, C. A., Hernández, Luna E. and Hernández, Aguirre A. Use of particle swarm optimization to design combinational logic circuits. 5th International Conference in Evolvable Systems: From Biology to Lecture Notes in Computer Science. Edited by: Haddow, P. C., Tyrell, A. M. and Torresen, J. Vol. 2606, pp.398–409. Trondheim, Norway: Springer-Verlag. · Zbl 1034.68591 |
| [22] | Gudise, V. G. and Venayagamoorthy, G. K. Evolving digital circuits using particle swarm. Proceedings of the INNS-IEEE International Joint Conference on Neural Networks. pp.468–472. Porland, OR: IEEE Service Center. |
| [23] | Gordon, T. G.W. and Bentley, P. J. 2003. ”On evolvable hardware”. Edited by: Ovaska, S. and Sztandera, L. 279–323. Heidelberg, Germany: Physica-Verlag. Soft Computing in Industrial Electronics |
| [24] | Goldberg D. E., Genetic Algorithms in Search, Optimization and Machine Learning (1989) · Zbl 0721.68056 |
| [25] | Holland J. H., Adaptation in Natural and Artificial Systems (1975) |
| [26] | DOI: 10.1002/(SICI)1099-0526(199903/04)4:4<31::AID-CPLX5>3.0.CO;2-4 · doi:10.1002/(SICI)1099-0526(199903/04)4:4<31::AID-CPLX5>3.0.CO;2-4 |
| [27] | Davis L., Handbook of Genetic Algorithms (1991) |
| [28] | Eshelman L. J., Foundations of Genetic Algorithms (FOGA) pp 265– (1991) |
| [29] | DOI: 10.1126/science.220.4598.671 · Zbl 1225.90162 · doi:10.1126/science.220.4598.671 |
| [30] | Aarts E., Essays and Surveys un Metaheuristics (2002) |
| [31] | Laarhoven P. J.M., Simulated Annealing: Theory and Applications (1987) |
| [32] | DOI: 10.1109/TEVC.2002.800880 · doi:10.1109/TEVC.2002.800880 |
| [33] | DOI: 10.1016/S0377-2217(99)00255-6 · Zbl 0961.90037 · doi:10.1016/S0377-2217(99)00255-6 |
| [34] | DOI: 10.1080/0305215041000168521 · doi:10.1080/0305215041000168521 |
| [35] | DOI: 10.1080/1055678021000030084 · Zbl 1065.90081 · doi:10.1080/1055678021000030084 |
| [36] | DOI: 10.1080/10556780310001645189 · Zbl 1059.90149 · doi:10.1080/10556780310001645189 |
| [37] | DOI: 10.1016/S0169-7439(97)00071-3 · doi:10.1016/S0169-7439(97)00071-3 |
| [38] | Coello Coello, C. A., Hernández Aguirre, A. and Buckles, B. P. Evolutionary multiobjective design of combinational logic circuits. Proceedings of the Second NASA/DoD Workshop on Evolvable Hardware. Edited by: Lohn, J., Stoica, A., Keymeulen, D. and Colombano, S. pp.161–170. Los Alamitos, CA: IEEE Computer Society. · Zbl 1042.68741 |
| [39] | Sasao T., Logic Synthesis and Optimization (1993) · Zbl 0937.94017 · doi:10.1007/978-1-4615-3154-8 |
| [40] | Coello Coello C. A., Artificial Intelligence for Engineering, Design, Analysis and Manufacture 16 pp 39– (2002) · Zbl 1026.74056 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
