Tabu list

Iteration Current schedule Current objective Best move Move value Tabu state Tabu list Tabu position Best objective... 

The dumbest of these search methods by some distance is one in which colours are chosen for matching completely at random. In a random search (Fig. 2a) a colour is chosen blindly from the wheel for comparison with the paint chip. If the colours match, the search is over, but if there is no match, another colour is chosen at random and the process is repeated. This kind of search has almost no merit beyond simplicity. Even in the small search space of this problem it is inefficient, while for large spaces the probability of success falls to near zero. Furthermore, the search may revisit points it has already checked, which is unproductive. (This is avoided in a TABU search, in which a tally is kept of points previously visited, but maintaining a TABU list adds computational overhead which becomes increasingly onerous as the search progresses and cannot pretend to rescue what is a very poor method.)... 

The upper level sub-problem decides the locations of DC by the sophisticated tabu search. Tabu search (TS Glover, 1989) is a metaheuristic algorithm on a basis of local search technique with a memory structure. The TS repeats the local search iteratively to move from a current solution jr to a possible and best solution x in the neighbor of a . To avoid the cycling of the solution, the TS uses the tabu list that prohibits transition to any solutions for a while even if this will improve the current solution. 

Perform tabu list management compute moves (or attributes) to be set tabu and add those to the tabu list. 

Tahu algorithms of Glover and others deal with repeats by keeping list of moves that are temporarily tabu or forbidden. The best improving (or least nonimproving) non-tabu move is adopted at each step of the procedure. For example, in the above case where yj is switched from = 1 to = 0, any move involving yjr might be placed on the tabu list for say the next 5-10 steps and then freed. Solutions can still repeat under tabu, but computational experience has shown promise in a number of applications. 

Consider Fig. 12, where point A has already been searched and the current point is It is more attractive to return to point A than to move to C in the short term, even though C may eventually lead to a higher reward, as it could direct the search toward D. Tabu search attempts to inhibit this kind of behavior by maintaining a tabu list, which is simply a list of previously made moves, or areas of the landscape which have already been searched, and therefore should not be revisited (are considered taboo). 

When moving from one solution 5" to another solution s tabu search generates a set of possible moves known as the neighborhood of 5". The move that gives the greatest reward is taken and then entered into the tabu list to ensure that the same move will not be made again. The exact form of the tabu list varies. Sometimes the actual solutions themselves... 

Tabu search can be looked upon as a search with a shortterm memory, as the last number of moves are remembered. There is a limit to the number remembered, as it is generally not practical to store every move. Using this implementation, however, tabu search can be too restrictive quite often there may only be a relatively small number of moves leading away from a particular position. Once all of these are in the tabu list, it is possible for the search to become trapped. 

To prevent this from happenning, an aspiration function is often employed. An aspiration function permits a move that is in the tabu list if this move gives a better score than all others found. This is sometimes necessary because some level of backtracking is often needed. The probability of the aspiration function permitting a move from the tabu list to be made often varies with time. 

---