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 条
  • [21] Marti R., Et al., Reducing the bandwidth of a sparse matrix with tabu search, European Journal of Operational Research, 135, 2, pp. 450-459, (2001)
  • [22] Marti R., Et al., A branch and bound algorithm for the matrix bandwidth minimization, European Journal of Operational Research, 186, 2, pp. 513-528, (2008)
  • [23] Mladenovic N., Et al., Variable neighbourhood search for bandwidth reduction, European Journal of Operational Research, 200, 1, pp. 14-27, (2010)
  • [24] Papadimitriou C.H., The NP-Completeness of the bandwidth minimization problem, Computing, 16, 3, pp. 263-270, (1976)
  • [25] Pintea C.M., Et al., A hybrid ACO approach to the matrix bandwidth minimization problem, Hybrid Artificial Intelligence Systems, pp. 405-412, (2010)
  • [26] Pinana E., Et al., GRASP and path relinking for the matrix bandwidth minimization, European Journal of Operational Research, 153, 1, pp. 200-210, (2004)
  • [27] Pop P.C., Matei O., An improved heuristic for the bandwidth minimization based on genetic programming, International Conference on Hybrid Artificial Intelligence Systems, pp. 67-74, (2011)
  • [28] Rodrigues T.N., Et al., Parallel Implementations of RCM algorithm for bandwidth reduction of sparse matrices, Tema, 18, 3, pp. 449-465, (2017)
  • [29] Rodriguez-Tello E., Et al., An improved evaluation function for the bandwidth minimization problem, Parallel Problem Solving from Nature-PPSN VIII, pp. 652-661, (2004)
  • [30] Rodriguez-Tello E., Et al., An improved simulated annealing algorithm for bandwidth minimization, European Journal of Operational Research, 185, 3, pp. 1319-1335, (2008)
1234