Abstract
The Bandwidth Minimization Problem (BMP) is a graph layout problem which is known to be NP-complete. Since 1960, a considerable number of algorithms have been developed for addressing the BMP. At present, meta-heuristics (such as evolutionary algorithms and tabu search) are popular and successful approaches to the BMP. In such algorithms, the design of the fitness function (i.e. the metric that attempts to guide the search towards highquality solutions) plays a key role in performance; the fitness function, along with the operators, induce the 'search landscape', and careful attention to these issues may lead to landscapes that are more amenable to successful search. For example, rather than simply use the most obvious quality measure (in this case, the bandwidth itself), it is often helpful to design a more informative measure, indicating not only a solutions quality, but also encapsulating (for example) an indication of how distant this particular solution is from even better solutions. In this paper, a new fitness function and an associated new mutation operator are presented for BMP. These are incorporated within a simple Evolutionary Algorithm (EA), and evaluated on a set of 27 instances of the BMP (from the Harwell-Boeing sparse matrix collection). The results of this EA are compared with results obtained by using the standard fitness function (used in almost all previous researches on metaheuristics applied to the BMP). The results indicate clearly that the new fitness function and operator performed provide significantly superior results in the reduction of bandwidth. © 2009 American Institute of Physics.
Original language | English |
---|---|
Title of host publication | BICS 2008 - Proceedings of the 1st International Conference: Bio-Inspired Computational Methods Used for Solving Difficult Problems-Development of Intelligent and Complex Systems |
Pages | 21-28 |
Number of pages | 8 |
Volume | 1117 |
DOIs | |
Publication status | Published - 2009 |
Event | 1st International Conference on Bio-Inspired Computational Methods Used for Solving Difficult Problems-Development of Intelligent and Complex Systems - Tirgu Mures, Romania Duration: 5 Nov 2008 → 7 Nov 2008 |
Conference
Conference | 1st International Conference on Bio-Inspired Computational Methods Used for Solving Difficult Problems-Development of Intelligent and Complex Systems |
---|---|
Abbreviated title | BICS 2008 |
Country/Territory | Romania |
City | Tirgu Mures |
Period | 5/11/08 → 7/11/08 |
Keywords
- Bandwidth Minimization
- Evolutionary Algorithm
- Graph
- Profile
- Sparse Matrices