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.8081

@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