Comparisons between severl Tabu search variants.md

original tabu Search

1. determine the next move
2. add the move into tabu list with a specified tabu iteration count in order to avoid cycling.
3. aspiration strategy allowed if a move, despite in tabu, generates a better result than ever been.

robust tabu search

I. (seemingly) slight differences in general tactics

newly introduced definitions

if a move is tabu until a specified later iteration, call this later iteration the eligible iteration for a given move.

1. if the current iteration is less than or equal to the eligible iteration, the move is ineligible.
2. if the current iteration is greater than the eligible iteration, the move is authorized.
3. if the current iteration minus an aspiration constant is greater than the eligible iteration the move is aspired.

rules for determining the next move [multi-level aspiration actually]

1. if a move which decreases the lowest cost found so far is available, the move which most decreases this total cost is chosen, independent of whether the move is ineligible, authorized or aspired.
2. if no move meets criterion 1, the aspired move, if one is available, which most decreases the current total cost is chosen.
3. if no moves meet criteria 1 or 2, the lowest cost authorized move is chosen.

II. dynamic tabu list size

propose to change list size randomly during the search.

and practically, list size s will be chosen between $s_{min}$ and $s_{max} = s_{min} + \Delta$ and frequently changed for a specified iterations, e.g., $2\cdot s_{max}$ iterations.

multi-start tabu search

in general, execute multiple times from different initial settings.

2-phase strategy
(1). constructive mehtod: create a new solution.
(2). improvement method: improve solution by local iterative search.

intensification: restricts the search to regions that are known to be part of high quality solutions

diversification: discover new region

alter search trajectory in some manner when an undesirable, prespecified amount of stagnation occurs: perform diversification then reset allowable failures, aka, previously mentioned prespecifiedly undesirable amount of stagnation.