A Tabu Search with a Double Neighborhood Strategy

Paula Amaral, Ana Mendes, J. Miguel Espinosa

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

Tabu Search (TS) is a well known and very successful method heuristic approach for hard optimization problems, linear or nonlinear. It is known to produce very good solutions, optimal or close to optimal for some hard combinatorial optimization problems. The drawback is that we have in general no optimality certificate, but this is the price to be paid for problems where the exact methods are too costly in terms of time and computational memory. One of the drawbacks of TS is that the strategies must be studied and refined for every instance. Many proposals exist to enhance the efficiency of this method heuristic. TS is particularly fragile in cases where there are many local optima of the problem. TS may be slow in the process of escaping a region of attraction of a local optima. If the strategy for evaluating the solutions in the neighborhood takes time to move away from the local optimum then it may compromise the search efficiency. In this paper we propose a double neighborhood strategy with opposite optimization directions (minimization and maximization). While one search for the best solution in the neighborhood the second search for the worse, and two parallel process develop switching from the minimization to maximization and vice-versa, when in consecutive iterations there is no improvement in solution. With this proposal, it is intended that the research can escape the attraction zone of a local optimum, more quickly allowing the research space to be better explored. We present an application to a Knapsack problem.

Original languageEnglish
Title of host publicationComputational Science and Its Applications – ICCSA 2022 Workshops
Subtitle of host publicationMalaga, Spain, July 4–7, 2022, Proceedings, Part II
EditorsOsvaldo Gervasi, Beniamino Murgante, Sanjay Misra, Ana Maria Rocha, Chiara Garau
Place of PublicationCham
PublisherSpringer
Pages219-230
Number of pages12
ISBN (Electronic)978-3-031-10562-3
ISBN (Print)978-3-031-10561-6
DOIs
Publication statusPublished - Aug 2022
Event22nd International Conference on Computational Science and Its Applications , ICCSA 2022 - Malaga, Spain
Duration: 4 Jul 20227 Jul 2022

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherSpringer
Volume13378
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference22nd International Conference on Computational Science and Its Applications , ICCSA 2022
Country/TerritorySpain
CityMalaga
Period4/07/227/07/22

Keywords

  • Double neighborhood
  • Neighborhood search
  • Tabu Search

Fingerprint

Dive into the research topics of 'A Tabu Search with a Double Neighborhood Strategy'. Together they form a unique fingerprint.

Cite this