Study on Incorporating Tabu Search Strategies into A Multi-start Metaheuristic

摘要

Meta-RaPS (Meta-heuristic for Randomized Priority Search) is a typical multi-start local search meta-heuristic,rnwhich iteratively constructs feasible initial solutions and improves them by applying local search heuristics. It can bernviewed as a generalized form of several other multi-start heuristics such as the classic random restart and thernGRASP procedure. These heuristics are memoryless in the sense that they do not make use of the information in thernprevious iterations to build new solutions. The adaptive memory in Tabu Search (TS) has been extensively studiedrnin application with transition neighborhoods in local search, however, the little work done to incorporate adaptivernmemory in muti-start heuristics has been restricted to the construction phases. This paper investigates thernincorporation of the Tabu adaptive memory into Meta-RaPS and analyzes its collaboration with systematicrnrandomness in the construction phase and the intensified local search in the improvement phase. This paperrndiscovers several efficient algorithms that maintain a good balance between randomness and memory and can findrnthe optimal solutions for the 45 Set-covering Problem (SCP) test instances from OR-library, while only one otherrnheuristic from the literature can achieve the optimality for these benchmark problems.