Ant colony optimisation with local search for the bandwidth minimisation problem on graphs

被引：0
作者：
Guan J. [1 ]
Lin G. [2 ]
Feng H.-B. [3 ]
机构：
[1] Modern Educational Technology Center, Minjiang University, Fuzhou
[2] College of Mathematics and Data Science, Minjiang University, Fuzhou
[3] College of Computer and Control Engineering, Minjiang University, Fuzhou
来源：
International Journal of Intelligent Information and Database Systems | 2019年 / 12卷 / 1-2期
基金：
中国国家自然科学基金;
关键词：
Ant colony optimisation; Bandwidth minimisation problem; Intelligent algorithm; Local search; Metaheuristics;
D O I：
10.1504/IJIIDS.2019.102327
中图分类号：
学科分类号：
摘要：
The bandwidth minimisation problem on graphs (BMPG) is an NP-complete problem, which consists of labelling the vertices of a graph with the integers from 1 to n (n is the number of vertices) such that the maximum absolute difference between labels of adjacent vertices is as small as possible. In this paper, an application of the ant colony optimisation with local search is presented to solve the bandwidth minimisation problem. The main novelty of the proposed approach is an efficient local search combined with first improvement and best improvement strategies. A fast incremental evaluation technique is employed to avoid excessive fitness evaluations of moves in local search. Computational experiments on 56 benchmark instances show that the proposed algorithm is able to achieve competitive results. Copyright © 2019 Inderscience Enterprises Ltd.
引用
收藏
页码：65 / 78
页数：13
相关论文
共 35 条
  • [1] Berry M., Et al., Sparse matrix reordering schemes for browsing hypertext, Lectures in Applied Mathematics, 32, pp. 99-123, (1996)
  • [2] Bhatt S.N., Leighton F.T., A framework for solving VLSI graph layout problems, Journal of Computer & System Sciences, 28, 2, pp. 300-343, (1984)
  • [3] Campos V., Et al., Adaptive memory programming for matrix bandwidth minimization, Annals of Operations Research, 183, 1, pp. 7-23, (2011)
  • [4] Caprara A., Salazar-Gonzalez J.J., Laying out sparse graphs with provably minimum bandwidth, INFORMS Journal on Computing, 17, 3, pp. 356-373, (2005)
  • [5] Crisan G.C., Pintea C.M., A hybrid technique for a matrix bandwidth problem, Scientific Studies and Research, 21, 1, pp. 113-120, (2011)
  • [6] Cuthill E., McKee J., Reducing the bandwidth of sparse symmetric matrices, Proceedings of the 1969 24th National Conference, pp. 157-172, (1969)
  • [7] Cygan M., Pilipczuk M., Even faster exact bandwidth, ACM Transactions on Algorithms (TALG), 8, 1, pp. 1-11, (2012)
  • [8] De Oliveira S.L.G., Et al., An evaluation of low-cost heuristics for matrix bandwidth and profile reductions, Computational and Applied Mathematics, 37, 2, pp. 1412-1471, (2018)
  • [9] Del Corso G.M., Manzini G., Finding exact solutions to the bandwidth minimization problem, Computing, 62, 3, pp. 189-203, (1999)
  • [10] Doss L.J.T., Arathi P., A constructive bandwidth reduction algorithm - A variant of GPS algorithm, AKCE International Journal of Graphs and Combinatorics, 13, 3, pp. 241-254, (2016)
1234