Research Repository

Evolving an Improved Algorithm for Envelope Reduction Using a Hyper-Heuristic Approach

Koohestani, Behrooz and Poli, Riccardo (2014) 'Evolving an Improved Algorithm for Envelope Reduction Using a Hyper-Heuristic Approach.' IEEE Transactions on Evolutionary Computation, 18 (4). pp. 543-558. ISSN 1089-778X

Full text not available from this repository.


Large sparse symmetric matrices are typical characteristics of the linear systems found in various scientific and engineering disciplines, such as fluid mechanics, structural engineering, finite element analysis, and network analysis. In all such systems, the performance of solvers crucially depends on the sum of the distance of each matrix element from the matrix's main diagonal. This quantity is known as the envelope. In order to reduce the envelope of a matrix, its rows and columns should be reordered properly. The problem of minimizing the envelope size is exceptionally hard and known to be NP-complete. A considerable number of methods have been developed for reducing the envelope among which the Sloan algorithm offered a substantial improvement over previous algorithms. In this paper, a hyper-heuristic approach based on genetic programming, which we term genetic hyper-heuristic, is introduced for evolving an enhanced version of the Sloan algorithm. We also present a local search algorithm and integrate it with the new algorithm produced by our hyper-heuristic to further improve the quality of the solutions. The new algorithms are evaluated on a large set of standard benchmarks against six state-of-the-art algorithms from the literature. Our algorithms outperform all the methods under testing by a wide margin. © 1997-2012 IEEE.

Item Type: Article
Uncontrolled Keywords: Genetic programming; graph theory; optimization; search methods; sparse matrices
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Divisions: Faculty of Science and Health
Faculty of Science and Health > Computer Science and Electronic Engineering, School of
SWORD Depositor: Elements
Depositing User: Elements
Date Deposited: 05 Dec 2014 10:55
Last Modified: 15 Jan 2022 00:34

Actions (login required)

View Item View Item