Project: Bandwidth reduction

This post is a follow-up to the problem of bandwidth reduction presented earlier. I've done a small Delphi application that can generate sparse matrices of various sizes and densities (the density of a sparse matrix is the percent of non-zero elements is contains) and that features 3 (well, actually more like 2) bandwidth reduction algorithms. The first algorithm is the original Cuthill-McKee algorithm, the second one is the Reverse Cuthill-Mckee algorithm (both of which have been covered in detail) and the third algorithm I've decided to implement is a genetic algorithm.
.

I must say that I was very curious to see how a genetic algorithm would perform on this problem as the bandwidth reduction problem is basically a combinatorial problem. As it turns out there is a really nice study performed by A. Lim, B. Rodrigues and F. Xiao that covers this exact topic. The three researchers carry on the work of R. Marti and V. Campos in trying to use a metaheurisc approach in order to obtain better results than the classic bandwidth reduction algorithms (RCM and GPS).
.

Although genetic algorithms perform very well in global search, some researchers argue that they are less suitable for highly tuned search. As such, Lim, Rodrigues and Xiao combined their genetic algorithm with a hill climbing approach. The resulting hybrid (memetic) algorithm performs very well and generally produces solutions of better quality than the Reverse Cuthill-McKee algorithm.
.

My implementations of the CutHill-McKee algorithm and of the genetic algorithm are by no means optimal! (the genetic algorithm is also slightly modified). Hence, both algorithms perform relatively poor (in terms of speed) compared with their creators' estimations. However, the main purpose of this project was to show that in the field of NP-complete problem solving, metaheuristic approaches, although considered rather slow, can be expected to produce very high quality results.
.
You cand download a fully working version of the application (source code included) by clicking here or from the Downloads box (BandwidthReduction.zip). Here are two screenshots:

And here is an example of how RCM and the hybrid metaheuristics-based algorithm performed on a 150x150 randomly generated simetric sparse matrix with a density of 3.5% (788 non-zero elements):

1. The initial sparse matrix. (bandwidth = 142)

 
2. The solution obtained using RCM. (bandwidth = 81)

 
3. The solution obtaind using the hybrid genetic + hill climbing algorithm. (bandwidth = 65). This solution was obtained after 15 generations using a mutation rate of 40%.

Application platform: Win32