A Quality and Distance Guided Metaheuristic Algorithm for Vertex Separation Problem

作者：Ding, Junwen; Zhou, Taoqing; Lu, Zhipeng^*; Yuan, Yujin

来源：IEEE Access, 2017, 5: 19248-19258.

DOI：10.1109/ACCESS.2017.2740418

• Vertex separation problem
• hybrid metaheuristic algorithm
• quality and distance guided local search

This paper presents a quality and distance guided metaheuristic algorithm (QD-ILS) for solving the vertex separation problem. QD-ILS integrates a basic local search procedure with QD-LS strategy, which uses an augmented evaluation function that considers both solution quality and distance between the current solution and the best found solution to guide the search to explore promising regions of the search space. Assessed on two sets of 162 common benchmark instances, QD-ILS achieves highly competitive results in terms of both solution quality and computational efficiency compared with the state-of-the-art algorithms in the literature. Specifically, it improves the previous best known results for 33 out of 162 benchmark instances and matches the best known results on all except four of the remaining instances compared with the state-of-the-art algorithms in the literature. The impact of the distance and quality-based diversification strategy is also investigated.

• 出版日期2017
• 单位华中科技大学