Focal distance tabu search

作     者：Fred GLOVER Zhipeng Lü Fred GLOVER;Zhipeng L(U)

作者机构：Meta-AnalyticsInc. School of Computer Science and Technology Huazhong University of Science and Technology 

出 版 物：《Science China(Information Sciences)》 (中国科学:信息科学(英文版))

年 卷 期：2021年第64卷第5期

页      面：5-16页

核心收录：

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 081104[工学-模式识别与智能系统] 08[工学] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：We are grateful to the anonymous reviewers for their valuable comments which helped us to improve the paper 

主　　题：tabu search diversification strategic oscillation adaptive partitioning metaheuristics 

摘      要：Focal distance tabu search modifies a standard tabu search algorithm for binary optimization by augmenting a periodic diversification step that drives the search away from a current best(or elite) solution until the objective function deteriorates beyond a specified threshold or until attaining a lower bound on the distance from the originating solution. The new augmented algorithm combines the threshold and lower bound approaches by introducing an initial focal distance for the lower bound which is updated when the diversification step is completed. However, rather than terminating the diversification step at the customary completion point, focal distance tabu search(TS) retains the focal distance bound through additional search phases designed to improve the objective function, drawing on a strategy proposed with strategic *** algorithm realizes this strategy by partitioning the variables into two sets which are managed together with an abbreviated tabu search process. An advanced version of the approach drives the search away from a collection of solutions rather than a single originating solution, introducing the concept of a signature solution to guide the search. The method can be employed to augment a variety of other metaheuristic algorithms such as those using threshold procedures, late acceptance hill climbing, iterated local search, breakout local search, GRASP, and path relinking.