A quality and distance guided hybrid algorithm for the vertex separator problem. (February 2017)

• Record Type: Journal Article
• Authors: Ding, Junwen; Lü, Zhipeng; Zhou, Taoqing; Xu, Liping
• Is Part Of: Computers & operations research. Volume 78(2017)
• Page Start: 255
• Page End: 266
• Publication Date: 2017-02
• Subjects: Vertex separator problem -- Hybrid metaheuristic algorithm -- Distance and quality guided tabu search -- Diversification mechanism; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2016.09.012
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: This paper presents a quality and distance guided local search (QD-LS) as the diversification strategy for metaheuristics. QD-LS uses an augmented evaluation function which considers both solution quality and distance between the current solution and the best found solution to guide the search towards promising regions of the search space. To evaluate the performance of QD-LS, we propose a quality and distance guided hybrid algorithm (QD-HA) for solving the vertex separator problem. Based on the framework of evolutionary algorithms, QD-HA integrates a basic tabu search procedure with a random greedy recombination operator and QD-LS strategy. Assessed on two sets of 348 common benchmark instances, QD-HA achieves highly competitive results in terms of both solution quality and computational efficiency compared with state-of-the-art algorithms in the literature. Specifically, it improves the previous best known results for 63 out of 244 large instances while matching the best known results for others. The impact of the quality and distance based diversification strategy is also investigated. Abstract : Highlights: A quality and distance guided local search (QD-LS) is presented as the diversification strategy. A quality and distance guided hybrid algorithm (QD-HA) is proposed for solving VSP. QD-HA improves the previous best known results for 63 out of 244 large instances. The impact of the QD-LS strategy is investigated.