A learning-based path relinking algorithm for the bandwidth coloring problem. (June 2016)

• Record Type: Journal Article
• Authors: Lai, Xiangjing; Hao, Jin-Kao; Lü, Zhipeng; Glover, Fred
• Is Part Of: Engineering applications of artificial intelligence. Volume 52(2016:Apr.)
• Page Start: 81
• Page End: 91
• Publication Date: 2016-06
• Subjects: Path relinking and tabu search -- Learning mechanism -- Bandwidth and graph coloring problems -- Population-based computing; Engineering -- Data processing -- Periodicals; Artificial intelligence -- Periodicals; Expert systems (Computer science) -- Periodicals; Ingénierie -- Informatique -- Périodiques; Intelligence artificielle -- Périodiques; Systèmes experts (Informatique) -- Périodiques; Artificial intelligence; Engineering -- Data processing; Expert systems (Computer science); Periodicals; 620.00285
• DOI: 10.1016/j.engappai.2016.02.008
• Languages: English
• ISSNs: 0952-1976

Abstract

Abstract: This paper proposes a learning-based path relinking algorithm (LPR) for solving the bandwidth coloring problem and the bandwidth multicoloring problem. Based on the population path-relinking framework, the proposed algorithm integrates a learning-driven tabu optimization procedure and a path-relinking operator. LPR is assessed on two sets of 66 common benchmark instances, and achieves highly competitive results in terms of both solution quality and computational efficiency compared to the state-of-the-art algorithms in the literature. Specifically, the algorithm establishes 7 new upper bounds while matching the best known results for 56 cases. The impacts of the learning mechanism and the path relinking operators are investigated, confirming their critical role to the success of the proposed algorithm.