An improved fitness function and mutation operator for metaheuristic approaches to the bandwidth minimization problem

Behrooz Koohestani, David W. Corne

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Citation (Scopus)

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 languageEnglish
Title of host publicationBICS 2008 - Proceedings of the 1st International Conference: Bio-Inspired Computational Methods Used for Solving Difficult Problems-Development of Intelligent and Complex Systems
Pages21-28
Number of pages8
Volume1117
DOIs
Publication statusPublished - 2009
Event1st International Conference on Bio-Inspired Computational Methods Used for Solving Difficult Problems-Development of Intelligent and Complex Systems - Tirgu Mures, Romania
Duration: 5 Nov 20087 Nov 2008

Conference

Conference1st International Conference on Bio-Inspired Computational Methods Used for Solving Difficult Problems-Development of Intelligent and Complex Systems
Abbreviated titleBICS 2008
CountryRomania
CityTirgu Mures
Period5/11/087/11/08

Keywords

  • Bandwidth Minimization
  • Evolutionary Algorithm
  • Graph
  • Profile
  • Sparse Matrices

Fingerprint Dive into the research topics of 'An improved fitness function and mutation operator for metaheuristic approaches to the bandwidth minimization problem'. Together they form a unique fingerprint.

  • Cite this

    Koohestani, B., & Corne, D. W. (2009). An improved fitness function and mutation operator for metaheuristic approaches to the bandwidth minimization problem. In BICS 2008 - Proceedings of the 1st International Conference: Bio-Inspired Computational Methods Used for Solving Difficult Problems-Development of Intelligent and Complex Systems (Vol. 1117, pp. 21-28) https://doi.org/10.1063/1.3130627