An Improved Fitness Function and Mutation Operator for Metaheuristic Approaches to the Bandwidth Minimization Problem.

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 high-quality 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. [ABSTRACT FROM AUTHOR]