Tabu Search (TS) is a single solution meta-heuristic based on the utilization of its search history. It was introduced by Glover in 1986, and is a first method being referred to as \textit{meta-heuristic} \cite{glover1986}.
However, 10 years earlier many of basic TS elements were already suggested by
Glover as a part of specific oriented heuristic for solving nonlinear covering problem \cite{glover1977,osman1996}. The TS meta-heuristics is mostly applied to combinatorial optimization problems. TS can be viewed as an extension of classical (steepest) local search method in order to overcome local optima with including various types of memory structures (classical being
\textit{short-term memory}) \cite{gendreau2010b}. \iffalse In this way the …show more content…
On the other side a search can be released by means of short-term memory functions. This is achieved by incorporation of an \textit{aspiration level function} $A(s,x)$ used to provide flexibility by overriding the tabu status of a move if the aspiration level is attained \cite{glover1989}.
Tabu Search is a single-solution method, constructed as an iterative algorithm.
The basic version of the TS is presented in pseudo-code of TS in
Fig.~\ref{fig:TS}. The algorithm starts with generation of an initial solution.
At each iteration a whole neighborhood of the initial solution is searched in a deterministic manner \cite{talbi2009metaheuristics}. When a new solution leads to improvement, TS replaces current solution with the new found. In case that all examined neighbor solutions do not lead to an improvement (TS reached local optima), TS will move to the best admissible neighbor even if this causes the objective function to deteriorate. This kind of admission criterion may lead to cycling, that is, returning to solutions already visited \cite{osman1996}. To avoid cycles TS memorizes attributes\footnote{In order to decrease memory used for storing already visited solutions, smaller set of informations can be …show more content…
The first version of the meta-heuristic method inspired with ants behavior was proposed by Dorigo as an Ant System method (AS) in 1992 for solving of TSP problem with up to 75 cities \cite{dorigo1992,dorigo2010}. As AS didn't show up to be competitive with up to that time specific oriented algorithms designed for dealing with TSP, next years were devoted to development of better version, known today as ACO. Ant Colony Optimization uses artificial ants to construct solutions by incrementally adding new components
\cite{dorigo2010}. In the analogy to the biological example, the communication between artificial ants is indirect and uses pheromones as a communication medium. The pheromone trails in ACO serve as a distributed, numerical information, which the ants use to probabilistically construct solutions to the problem being solved. Moreover, the ants adapt this information during the algorithms execution to reflect their search experience.
A general outline of the ACO meta-heuristic according to \cite{dorigo2010} is given in Fig.~\ref{ACO-code}. After initializing parameters and
However, 10 years earlier many of basic TS elements were already suggested by
Glover as a part of specific oriented heuristic for solving nonlinear covering problem \cite{glover1977,osman1996}. The TS meta-heuristics is mostly applied to combinatorial optimization problems. TS can be viewed as an extension of classical (steepest) local search method in order to overcome local optima with including various types of memory structures (classical being
\textit{short-term memory}) \cite{gendreau2010b}. \iffalse In this way the …show more content…
On the other side a search can be released by means of short-term memory functions. This is achieved by incorporation of an \textit{aspiration level function} $A(s,x)$ used to provide flexibility by overriding the tabu status of a move if the aspiration level is attained \cite{glover1989}.
Tabu Search is a single-solution method, constructed as an iterative algorithm.
The basic version of the TS is presented in pseudo-code of TS in
Fig.~\ref{fig:TS}. The algorithm starts with generation of an initial solution.
At each iteration a whole neighborhood of the initial solution is searched in a deterministic manner \cite{talbi2009metaheuristics}. When a new solution leads to improvement, TS replaces current solution with the new found. In case that all examined neighbor solutions do not lead to an improvement (TS reached local optima), TS will move to the best admissible neighbor even if this causes the objective function to deteriorate. This kind of admission criterion may lead to cycling, that is, returning to solutions already visited \cite{osman1996}. To avoid cycles TS memorizes attributes\footnote{In order to decrease memory used for storing already visited solutions, smaller set of informations can be …show more content…
The first version of the meta-heuristic method inspired with ants behavior was proposed by Dorigo as an Ant System method (AS) in 1992 for solving of TSP problem with up to 75 cities \cite{dorigo1992,dorigo2010}. As AS didn't show up to be competitive with up to that time specific oriented algorithms designed for dealing with TSP, next years were devoted to development of better version, known today as ACO. Ant Colony Optimization uses artificial ants to construct solutions by incrementally adding new components
\cite{dorigo2010}. In the analogy to the biological example, the communication between artificial ants is indirect and uses pheromones as a communication medium. The pheromone trails in ACO serve as a distributed, numerical information, which the ants use to probabilistically construct solutions to the problem being solved. Moreover, the ants adapt this information during the algorithms execution to reflect their search experience.
A general outline of the ACO meta-heuristic according to \cite{dorigo2010} is given in Fig.~\ref{ACO-code}. After initializing parameters and