Abstract
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 oscillation. The 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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Lucas A. Ising formulations of many NP problems. Front Phys, 2014, 2: 5
Kochenberger G, Hao J K, Glover F, et al. The unconstrained binary quadratic programming problem: a survey. J Comb Optim, 2014, 28: 58–81
Glover F, Kochenberger G, Du Y. Quantum bridge analytics I: a tutorial on formulating and using QUBO models. 4OR-Q J Oper Res, 2019, 17: 335–371
Vyskocil T, Pakin S, Djidjev H N. Embedding inequality constraints for quantum annealling optimization. In: Quantum Technology and Optimization Problems. Cham: Springer, 2019. 11413
Glover F. Future paths for integer programming and links to artificial intelligence. Comput Oper Res, 1986, 13: 533–549
Glover F. Heuristics for integer programming using surrogate constraints. Decision Sci, 1977, 8: 156–166
Dueck G, Scheuer T. Threshold accepting: a general purpose optimization algorithm appearing superior to simulated annealing. J Comput Phys, 1990, 90: 161–175
Osman I H. Metastrategy simulated annealing and tabu search algorithms for the vehicle routing problem. Ann Oper Res, 1993, 41: 421–451
Dueck G. New optimization heuristics the great deluge algorithm and the record-to-record travel. J Comput Phys, 1993, 104: 86–92
Glover F. Tabu thresholding: improved search by nonmonotonic trajectories. ORSA J Computing, 1995, 7: 426–442
Glover F, Kochenberger G A. Critical event tabu search for multidimensional knapsack problems. In: Meta-Heuristics: Theory & Applications. Boston: Springer, 1996. 407–427
Battiti R, Tecchiolli G. The reactive tabu search. ORSA J Comput, 1994, 6: 126–140
Kelly J P, Laguna M, Glover F. A study of diversification strategies for the quadratic assignment problem. Comput Oper Res, 1994, 21: 885–893
Woodruff D L, Zemel E. Hashing vectors for tabu search. Ann Oper Res, 1993, 41: 123–137
Glover F, Kochenberger G, Alidaee B, et al. Tabu search with critical event memory: an enhanced application for binary quadratic programs. In: Meta-Heuristics. Boston: Springer, 1998. 83–109
Glover F, Laguna M. Tabu Search. Boston: Springer Academic Publications, 1997
Samorani M, Wang Y, Wang Y, et al. Clustering-driven evolutionary algorithms: an application of path relinking to the quadratic unconstrained binary optimization problem. J Heuristics, 2019, 25: 629–642
Lourenço H R, Martin O C, Stüzle T. Iterated local search: framework and applications. In: Handbook of Metaheuristics. Boston: Springer, 363–397
Coelho V N, Grasas A, Ramalhinho H, et al. An ILS-based algorithm to solve a large-scale real heterogeneous fleet VRP with multi-trips and docking constraints. Eur J Oper Res, 2016, 250: 367–376
Benlic U, Hao J K. Breakout local search for the quadratic assignment problem. Appl Math Comput, 2013, 219: 4800–4815
Fu Z H, Hao J K. Breakout local search for the Steiner tree problem with revenue, budget and hop constraints. Eur J Oper Res, 2014, 232: 209–220
Lu Z, Hao J K, Zhou Y. Stagnation-aware breakout tabu search for the minimum conductance graph partitioning problem. Comput Oper Res, 2019, 111: 43–57
Burke E K, Bykov Y. The late acceptance hill-climbing heuristic. Eur J Oper Res, 2017, 258: 70–78
Namazi M, Sanderson C, Newton M A H, et al. Diversified late acceptance search. In: Advances in Artificial Intelligence. Cham: Springer, 2018, 11320: 299–311
Resende M G C, Ribeiro C C. Greedy randomized adaptive search procedures: advances and extensions. In: Handbook of Metaheuristics. 3rd ed. Cham: Springer, 2019. 169–220
Peng B, Liu D, Su Z, et al. Solving the Incremental Graph Drawing Problem by Solution-based Multiple Neighborhood Tabu Search. Research Report. Chengdu: Southwestern University of Finance and Economics, 2019
Glover F. Analyzing and Exploiting Landscape Patterns in Combinatorial Optimization. School of Engineering and Applied Science, University of Colorado. 2019
Acknowledgements
We are grateful to the anonymous reviewers for their valuable comments which helped us to improve the paper.
Author information
Authors and Affiliations
Corresponding authors
Rights and permissions
About this article
Cite this article
Glover, F., Lü, Z. Focal distance tabu search. Sci. China Inf. Sci. 64, 150101 (2021). https://doi.org/10.1007/s11432-020-3115-5
Received:
Accepted:
Published:
DOI: https://doi.org/10.1007/s11432-020-3115-5