An experimental analysis of a GP hyperheuristic approach for evolving low-cost heuristics for profile reductions
Resumo
Researchers used graph-theory approaches to design the state-of-theart low-cost heuristics for profile reduction. This paper evolves and selects four low-cost heuristics for profile reduction using a genetic programming hyperheuristic approach. This paper evaluates the resulting heuristics for profile reduction from the genetic programming hyperheuristic approach in two application areas against the low-cost heuristics for solving the problem. The results obtained on a set of standard benchmark matrices taken from the SuiteSparse sparse matrix collection indicate that the resulting heuristics from the genetic programming hyperheuristic approach does not compare favorably with a high-quality heuristics for profile reduction.
Palavras-chave:
graph-theory, heuristics, genetic programming, profile reduction
Referências
Barnard, S. T., Pothen, A., and Simon, H. D. (1993). A spectral algorithm for envelope reduction of sparse matrices. In Proceedings of the 1993 ACM/IEEE conference on Supercomputing, pages 493–502, Portland, OR. ACM.
Bernardes, J. A. B. and Gonzaga de Oliveira, S. L. (2015). A systematic review of heuris- tics for profile reduction of symmetric matrices. Procedia Computer Science, 51:221– 230.
Davis, T. A. and Hu, Y. (2011). The University of Florida sparse matrix collection. ACM Transactions on Mathematical Software, 38(1):1–25.
George, A. (1971). Computer implementation of the finite element method. PhD thesis, Stanford University, Stanford, USA.
Gibbs, N. (1976). A hybrid profile reduction algorithm. ACM Transactions on Mathema- tical Software, 2(4):378–387.
Gonzaga de Oliveira, S. L., Bernardes, J. A. B., and Chagas, G. O. (2018a). An evaluation of low-cost heuristics for matrix bandwidth and profile reductions. Computational & Applied Mathematics, 37(2):1412–1471.
Gonzaga de Oliveira, S. L., Bernardes, J. A. B., and Chagas, G. O. (2018b). An evaluation of reordering algorithms to reduce the computational cost of the incomplete cholesky- conjugate gradient method. Computational & Applied Mathematics, 37(3):2965–3004.
Gonzaga de Oliveira, S. L., Osthoff, C., and Henderson, L. N. (2019). An Experimen- tal Analysis of Heuristics for Profile Reduction. In Proceedings of 18th International Conference on Computational Science and Its Applications, ICCSA. Lecture Notes in Computer Science book series (LNCS) vol. 11619, pages 25–36, Saint Petersburg, Rus- sia. Springer International Publishing.
Hager, W. W. (2002). Minimizing the profile for a symmetric matrix. SIAM Journal on Scientific Computing, 23(5):1799–1816.
Hu, Y. and Scott, J. A. (2001). A multilevel algorithm for wavefront reduction. SIAM Journal on Scientific Computing, 23(4):1352–1375.
Koohestani, B. and Poli, R. (2015a). Addressing the envelope reduction of sparse matrices using a genetic programming system. Computational Optimization and Applications, 60(3):789–814.
Koohestani, B. and Poli, R. (2015b). Evolving an improved algorithm for envelope re- duction using a hyper-heuristic approach. IEEE Transactions on Evolutionary Compu- tation, 18(4):543–558.
Koza, J. R. (1992). Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, Cambridge, MA, USA.
Kumfert, G. and Pothen, A. (1997). Two improved algorithms for envelope and wavefront reduction. BIT Numerical Mathematics, 37(3):559–590.
Lewis, J. G. (1982). Implementation of the Gibbs-Poole-Stockmeyer and Gibbs-King algorithms. ACM Transactions on Mathematical Software, 8(2):180–189.
Lin, Y. X. and Yuan, J. J. (1994). Profile minimization problem for matrices and graphs. Acta Mathematicae Applicatae Sinica, 10(1):107–122.
Medeiros, S. R. P., Pimenta, P. M., and Goldenberg, P. (1993). Algorithm for profile and wavefront reduction of sparse matrices with a symmetric structure. Engineering Computations, 10(3):257–266.
Reid, J. K. and Scott, J. A. (1999). Ordering symmetric sparse matrices for small pro- file and wavefront. International Journal for Numerical Methods in Engineering, 45(12):1737–1755.
Reid, J. K. and Scott, J. A. (2002). Implementing Hager’s exchange methods for matrix profile reduction. ACM Trans. Math. Softw., 28(4):377–391.
Sloan, S. W. (1989). A Fortran program for profile and wavefront reduction. International Journal for Numerical Methods in Engineering, 28(11):2651–2679.
STFC (Accessed: December, 2018). The Science and Technology Facilities Council. HSL. A collection of Fortran codes for large scale scientific computation. http: //www.hsl.rl.ac.uk.
Bernardes, J. A. B. and Gonzaga de Oliveira, S. L. (2015). A systematic review of heuris- tics for profile reduction of symmetric matrices. Procedia Computer Science, 51:221– 230.
Davis, T. A. and Hu, Y. (2011). The University of Florida sparse matrix collection. ACM Transactions on Mathematical Software, 38(1):1–25.
George, A. (1971). Computer implementation of the finite element method. PhD thesis, Stanford University, Stanford, USA.
Gibbs, N. (1976). A hybrid profile reduction algorithm. ACM Transactions on Mathema- tical Software, 2(4):378–387.
Gonzaga de Oliveira, S. L., Bernardes, J. A. B., and Chagas, G. O. (2018a). An evaluation of low-cost heuristics for matrix bandwidth and profile reductions. Computational & Applied Mathematics, 37(2):1412–1471.
Gonzaga de Oliveira, S. L., Bernardes, J. A. B., and Chagas, G. O. (2018b). An evaluation of reordering algorithms to reduce the computational cost of the incomplete cholesky- conjugate gradient method. Computational & Applied Mathematics, 37(3):2965–3004.
Gonzaga de Oliveira, S. L., Osthoff, C., and Henderson, L. N. (2019). An Experimen- tal Analysis of Heuristics for Profile Reduction. In Proceedings of 18th International Conference on Computational Science and Its Applications, ICCSA. Lecture Notes in Computer Science book series (LNCS) vol. 11619, pages 25–36, Saint Petersburg, Rus- sia. Springer International Publishing.
Hager, W. W. (2002). Minimizing the profile for a symmetric matrix. SIAM Journal on Scientific Computing, 23(5):1799–1816.
Hu, Y. and Scott, J. A. (2001). A multilevel algorithm for wavefront reduction. SIAM Journal on Scientific Computing, 23(4):1352–1375.
Koohestani, B. and Poli, R. (2015a). Addressing the envelope reduction of sparse matrices using a genetic programming system. Computational Optimization and Applications, 60(3):789–814.
Koohestani, B. and Poli, R. (2015b). Evolving an improved algorithm for envelope re- duction using a hyper-heuristic approach. IEEE Transactions on Evolutionary Compu- tation, 18(4):543–558.
Koza, J. R. (1992). Genetic Programming: On the Programming of Computers by Means of Natural Selection. MIT Press, Cambridge, MA, USA.
Kumfert, G. and Pothen, A. (1997). Two improved algorithms for envelope and wavefront reduction. BIT Numerical Mathematics, 37(3):559–590.
Lewis, J. G. (1982). Implementation of the Gibbs-Poole-Stockmeyer and Gibbs-King algorithms. ACM Transactions on Mathematical Software, 8(2):180–189.
Lin, Y. X. and Yuan, J. J. (1994). Profile minimization problem for matrices and graphs. Acta Mathematicae Applicatae Sinica, 10(1):107–122.
Medeiros, S. R. P., Pimenta, P. M., and Goldenberg, P. (1993). Algorithm for profile and wavefront reduction of sparse matrices with a symmetric structure. Engineering Computations, 10(3):257–266.
Reid, J. K. and Scott, J. A. (1999). Ordering symmetric sparse matrices for small pro- file and wavefront. International Journal for Numerical Methods in Engineering, 45(12):1737–1755.
Reid, J. K. and Scott, J. A. (2002). Implementing Hager’s exchange methods for matrix profile reduction. ACM Trans. Math. Softw., 28(4):377–391.
Sloan, S. W. (1989). A Fortran program for profile and wavefront reduction. International Journal for Numerical Methods in Engineering, 28(11):2651–2679.
STFC (Accessed: December, 2018). The Science and Technology Facilities Council. HSL. A collection of Fortran codes for large scale scientific computation. http: //www.hsl.rl.ac.uk.
Publicado
30/06/2020
Como Citar
SILVA, Libério; DE OLIVEIRA, Sanderson Gonzaga.
An experimental analysis of a GP hyperheuristic approach for evolving low-cost heuristics for profile reductions. In: SEMINÁRIO INTEGRADO DE SOFTWARE E HARDWARE (SEMISH), 47. , 2020, Cuiabá.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2020
.
p. 128-138.
ISSN 2595-6205.
DOI: https://doi.org/10.5753/semish.2020.11323.
