Ant colony optimisation with local search for the bandwidth minimisation problem on graphs. (9th September 2019)

• Record Type: Journal Article
• Authors: Guan, Jian; Lin, Geng; Feng, Hui-Bin
• Is Part Of: International journal of intelligent information and database systems. Volume 12:Number 1/2(2019)
• Page Start: 65
• Page End: 78
• Publication Date: 2019-09-09
• Subjects: metaheuristics -- ant colony optimisation -- bandwidth minimisation problem -- local search -- intelligent algorithm; Database management -- Computer programs -- Periodicals; Information retrieval -- Computer programs -- Periodicals; Information storage and retrieval systems -- Computer programs -- Periodicals; Artificial intelligence -- Periodicals; Expert systems (Computer science) -- Periodicals; Intelligent agents (Computer software) -- Periodicals; 006.33
• Languages: English
• ISSNs: 1751-5858

Abstract

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.