A Genetic Programming Approach to the Matrix Bandwidth-Minimization Problem

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

@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