A Genetic Programming Approach to the Matrix Bandwidth-Minimization Problem
Created by W.Langdon from
gp-bibliography.bib Revision:1.7975
- @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