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 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.
Bandwidth minimization, Ant colony optimization, Hill climbing
Operations and Supply Chain Management
Applied Soft Computing
LIM, Andrew; LIN, Jing; RODRIGUES, Brian; and XIAO, Fei.
Ant Colony Optimization with Hill Climbing for the Bandwidth Minimization Problem. (2006). Applied Soft Computing. 6, (2), 180-188. Research Collection Lee Kong Chian School Of Business.
Available at: http://ink.library.smu.edu.sg/lkcsb_research/2619