Integrated Genetic Algorithm with Hill Climbing for Bandwidth Minimization Problem

Andrew Lim¹, Brian Rodrigues², and Fei Xiao³

¹Department of Industrial Engineering and Engineering Management
Hong Kong University of Science and Technology
Clear Water Bay, Hong Kong
iealim@ust.hk

²School of Business
Singapore Management University
469 Bukit Timah Road
Singapore 259756
br@smu.edu.sg

³Department of Computer Science
National University of Singapore
3 Science Drive 2
Singapore 117543
xiaofei@comp.nus.edu.sg

Abstract. In this paper, we propose an integrated Genetic Algorithm with Hill Climbing to solve the matrix bandwidth minimization problem, which is to reduce bandwidth by permuting rows and columns resulting in the nonzero elements residing in a band as close as possible to the diagonal. Experiments show that this approach achieves the best solution quality when compared with the GPS [1] algorithm, Tabu Search [3], and the GRASP with Path Relinking methods [4], while being faster than the latter two newly-developed heuristics.

LNCS 2724, p. 1594 ff.

Full article in PDF

lncs@springer.de
© Springer-Verlag Berlin Heidelberg 2003