Ant Colony Optimization with Hill Climbing for the Bandwidth Minimization Problem
In this work, the problem of reducing the bandwidth of sparse matrices by permuting rows and columns is addressed and solved using a hybrid ant system to generate high-quality renumbering which is refined by a hill climbing local search heuristic. Computational experiments compare the algorithm with...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | text |
| Language: | English |
| Published: |
Institutional Knowledge at Singapore Management University
2006
|
| Subjects: | |
| Online Access: | https://ink.library.smu.edu.sg/lkcsb_research/2619 https://doi.org/10.1016/j.asoc.2005.01.001 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | Singapore Management University |
| Language: | English |
| Summary: | In this work, the problem of reducing the bandwidth of sparse matrices by permuting rows and columns is addressed and solved using a hybrid ant system to generate high-quality renumbering which is refined by a hill climbing local search heuristic. Computational experiments compare the algorithm with the well-known GPS algorithm, as well as recently proposed methods. These show the new approach to be as good as current best algorithms. In addition, an algorithm to randomly generate matrices with known optimal bandwidth is developed and used to evaluate results. Comparisons show that the new algorithm was able to find either the optimal solution or a solution very close to the optimal for most instances. |
|---|