Ant Colony Optimization with Hill Climbing for the Bandwidth Minimization Problem

Publication Type

Journal Article

Publication Date

1-2006

Abstract

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.

Keywords

Bandwidth minimization, Ant colony optimization, Hill climbing

Discipline

Operations and Supply Chain Management

Research Areas

Operations Management

Publication

Applied Soft Computing

Volume

6

Issue

2

First Page

180

Last Page

188

ISSN

1568-4946

Identifier

10.1016/j.asoc.2005.01.001

Publisher

Elsevier

Additional URL

https://doi.org/10.1016/j.asoc.2005.01.001

Link to Full Text

Share

COinS