A quality and distance guided hybrid algorithm for the vertex separator problem

Autor: Junwen Ding, Liping Xu, Zhipeng Lü, Taoqing Zhou
Rok vydání: 2017
Předmět:
Zdroj: Computers & Operations Research. 78:255-266
ISSN: 0305-0548
DOI: 10.1016/j.cor.2016.09.012
Popis: 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. HighlightsA 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.
Databáze: OpenAIRE
Externí odkaz: