×

Reducing the bandwidth of a sparse matrix with a genetic algorithm. (English) Zbl 1305.65136

Summary: The matrix bandwidth minimization problem (MBMP) consists in finding a permutation of the lines and columns of a given sparse matrix in order to keep the non-zero elements in a band that is as close as possible to the main diagonal. Equivalently in terms of graph theory, MBMP is defined as the problem of finding a labelling of the vertices of a given graph G such that its bandwidth is minimized. In this paper, we propose an improved genetic algorithm (GA)-based heuristic for solving the matrix bandwidth minimization problem, motivated by its robustness and efficiency in a wide area of optimization problems. Extensively computational results are reported for an often used set of benchmark instances. The obtained results on the different instances investigated show improvement of the quality of the solutions and demonstrate the efficiency of our GA compared to the existing methods in the literature.

MSC:

65F50 Computational methods for sparse matrices
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
68T05 Learning and adaptive systems in artificial intelligence
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] DOI: 10.1007/BF02280884 · Zbl 0321.65019 · doi:10.1007/BF02280884
[2] DOI: 10.1002/(SICI)1097-0118(199906)31:2<75::AID-JGT1>3.0.CO;2-S · Zbl 0924.05058 · doi:10.1002/(SICI)1097-0118(199906)31:2<75::AID-JGT1>3.0.CO;2-S
[3] DOI: 10.1007/s006070050002 · Zbl 0946.65030 · doi:10.1007/s006070050002
[4] Dueck GH, J. Comb. Math. Comb. Comput 18 pp 97– (1995)
[5] Esposito A, LNCS 1184 pp 239– (1996)
[6] DOI: 10.1016/S0377-2217(00)00325-8 · Zbl 1051.90031 · doi:10.1016/S0377-2217(00)00325-8
[7] DOI: 10.1016/S0377-2217(02)00715-4 · Zbl 1053.90057 · doi:10.1016/S0377-2217(02)00715-4
[8] DOI: 10.1016/j.ejor.2005.02.066 · Zbl 1116.90118 · doi:10.1016/j.ejor.2005.02.066
[9] DOI: 10.1016/j.asoc.2005.01.001 · Zbl 05391293 · doi:10.1016/j.asoc.2005.01.001
[10] DOI: 10.1007/s10489-006-0019-x · Zbl 1189.65085 · doi:10.1007/s10489-006-0019-x
[11] DOI: 10.1016/j.ejor.2005.12.052 · Zbl 1146.90518 · doi:10.1016/j.ejor.2005.12.052
[12] DOI: 10.1016/j.ejor.2008.12.015 · Zbl 1188.90217 · doi:10.1016/j.ejor.2008.12.015
[13] Holland J, Adaptation in natural and artificial systems (1975)
[14] DOI: 10.1023/A:1009642825198 · Zbl 0972.68630 · doi:10.1023/A:1009642825198
[15] Bäck T. Evolutionary algorithms in theory and practice: evolution Strategies, evolutionary programming, genetic algorithms. Oxford (UK): Oxford University Press; 1996. · Zbl 0877.68060
[16] Safro I, ACM J. Exper. Algorith 13 pp 1.4:1– (2009)
[17] DOI: 10.1016/j.ejor.2007.02.004 · Zbl 1138.90037 · doi:10.1016/j.ejor.2007.02.004
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.