An Evolutionary Approach to Bandwidth Minimization
Conference Proceeding Article
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. Many algorithms for this problem have been developed, including the well-known CM and GPS algorithms. Recently, Marti et al., (2001) used tabu search and Pinana et al. (2002) used GRASP with path relinking, separately, where both approaches outperformed the GPS algorithm. In this work, our approach is to exploit the genetic algorithm technique in global search while using hill climbing for local search. Experiments show that this approach achieves the best solution quality when compared with the GPS algorithm, tabu search, and the GRASP with path relinking methods, while being faster than the latter two newly-developed heuristics.
Operations and Supply Chain Management
CEC 2003: Congress on Evolutionart Computation, 8-12 December 2003, Canberra, Australia
City or Country
LIM, Andrew; XIAO, Fei; and RODRIGUES, Brian.
An Evolutionary Approach to Bandwidth Minimization. (2003). CEC 2003: Congress on Evolutionart Computation, 8-12 December 2003, Canberra, Australia. Research Collection Lee Kong Chian School Of Business.
Available at: http://ink.library.smu.edu.sg/lkcsb_research/2063