A Genetic Programming Approach to the Matrix Bandwidth-Minimization Problem

Created by W.Langdon from gp-bibliography.bib Revision:1.8051

@InProceedings{Koohestani:2010:PPSN,

• author = "Behrooz Koohestani and Riccardo Poli",
• title = "A Genetic Programming Approach to the Matrix Bandwidth-Minimization Problem",
• booktitle = "PPSN 2010 11th International Conference on Parallel Problem Solving From Nature",
• year = "2010",
• editor = "Robert Schaefer and Carlos Cotta and Joanna Kolodziej and Guenter Rudolph",
• publisher = "Springer",
• pages = "482--491",
• series = "Lecture Notes in Computer Science",
• address = "Krakow, Poland",
• month = "11-15 " # sep,
• volume = "6239",
• keywords = "genetic algorithms, genetic programming, Bandwidth Minimization Problem, BMP, Graph Labelling, Sparse Matrices, Combinatorial Optimisation",
• DOI = "doi:10.1007/978-3-642-15871-1_49",
• abstract = "The bandwidth of a sparse matrix is the distance from the main diagonal beyond which all elements of the matrix are zero. The bandwidth minimisation problem for a matrix consists of finding the permutation of rows and columns of the matrix which ensures that the non-zero elements are located in as narrow a band as possible along the main diagonal. This problem, which is known to be NP-complete, can also be formulated as a vertex labelling problem for a graph whose edges represent the non-zero elements of the matrix. In this paper, a Genetic Programming approach is proposed and tested against two of the best-known and widely used bandwidth reduction algorithms. Results have been extremely encouraging.",
• notes = "flattened tree GP, C#, tress create permutations (row-column re-ordering) of sparse symmetric matrix adjacency graph. Function set +-*protected division, sin, abs, terminal set: three inputs (one or more required), 100 floating erc. Subtree crossover, point mutation. Each tree run n(graph size) times. Three inputs based on eigenvectors, level structure from other BMP solvers. fitness biased to better areas of search space. math.nist.gov Harwell-Boeing, Compared with Matlab RCMM and Spectral",
• affiliation = "School of Computer Science and Electronic Engineering, University of Essex, CO4 3SQ UK",

}

Genetic Programming entries for Behrooz Koohestani Riccardo Poli

Citations