A Genetic Programming Approach for Evolving Highly-Competitive General Algorithms for Envelope Reduction in Sparse Matrices

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

@InProceedings{conf/ppsn/KoohestaniP12,
  author =       "Behrooz Koohestani and Riccardo Poli",
  title =        "A Genetic Programming Approach for Evolving
                 Highly-Competitive General Algorithms for Envelope
                 Reduction in Sparse Matrices",
  booktitle =    "Parallel Problem Solving from Nature, PPSN XII (part
                 2)",
  year =         "2012",
  editor =       "Carlos A. {Coello Coello} and Vincenzo Cutello and 
                 Kalyanmoy Deb and Stephanie Forrest and 
                 Giuseppe Nicosia and Mario Pavone",
  volume =       "7492",
  series =       "Lecture Notes in Computer Science",
  pages =        "287--296",
  address =      "Taormina, Italy",
  month =        sep # " 1-5",
  publisher =    "Springer",
  keywords =     "genetic algorithms, genetic programming,
                 Hyper-Heuristic, Envelope Reduction Problem, Graph
                 Labelling, Sparse Matrices",
  isbn13 =       "978-3-642-32936-4",
  DOI =          "doi:10.1007/978-3-642-32964-7_29",
  size =         "10 pages",
  abstract =     "Sparse matrices emerge in a number of problems in
                 science and engineering. Typically the efficiency of
                 solvers for such problems depends crucially on the
                 distances between the first non-zero element in each
                 row and the main diagonal of the problem's matrix, a
                 property assessed by a quantity called the size of the
                 envelope of the matrix. This depends on the ordering of
                 the variables (i.e., the order of the rows and columns
                 in the matrix). So, some permutations of the variables
                 may reduce the envelope size which in turn makes a
                 problem easier to solve. However, finding the
                 permutation that minimises the envelope size is an
                 NP-complete problem. In this paper, we introduce a
                 hyper-heuristic approach based on genetic programming
                 for evolving envelope reduction algorithms. We evaluate
                 the best of such evolved algorithms on a large set of
                 standard benchmarks against two state-of-the-art
                 algorithms from the literature and the best algorithm
                 produced by a modified version of a previous
                 hyper-heuristic introduced for a related problem. The
                 new algorithm outperforms these methods by a wide
                 margin, and it is also extremely efficient.",
  bibsource =    "DBLP, http://dblp.uni-trier.de",
  affiliation =  "School of Computer Science and Electronic Engineering,
                 University of Essex, CO4 3SQ UK",
}

Genetic Programming entries for Behrooz Koohestani Riccardo Poli

Citations