Tabu Search Case Study

Good Essays
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

Related Documents

  • Decent Essays

    PICT Case Study

    • 1546 Words
    • 7 Pages

    Test parameter and parameter value was insert into CTWeb in two ways, manually or upload the value file. CTWeb also support constraints and weight where the value can be defined by CTWeb user. Another additional features of CTWeb is its ability to set base test suite where a list of test case was used as base for PROW algorithm. Having all information needed, CTWeb execute PROW algorithm for the second times to reduce pairs obtained from the first execution. Then, the result will be sorted according to the weight of each pairs.…

    • 1546 Words
    • 7 Pages
    Decent Essays
  • Decent Essays

    Serial Correlation Essay

    • 1588 Words
    • 6 Pages

    Several methods exist for dealing with serial correlation. Here, we will deal exclusively with batch means, replication/deletion, and the Mean Squared Error Reduction (MSER) technique. The goal of these methods is to produce valid confidence intervals (CI’s) in the presence of serial correlation. In our analysis, we will use the lag k autocorrelation to find a point at which the observations are…

    • 1588 Words
    • 6 Pages
    Decent Essays
  • Decent Essays

    Which is not a characteristic or benefit of BI? a) helps eliminate blindspots b) integrates data silos c) presents data in visual displays d) implemented by end-users 17. An advantage of __________ is that they are a way to access a particular view of data or to analyze what’s happening. a) OLAP b) data mining c) predictive analytics d) queries 18. Three core functions of __________ are query, reporting, and analytics.…

    • 1819 Words
    • 8 Pages
    Decent Essays
  • Decent Essays

    Instruction set and functional unit set are characterizing for doing Instruction scheduling. Processors are designated for performing different sets of tasks. Genetic programming has been evolved from Genetic algorithm which is used in applications for machine learning. It uses algorithms and randomly generated remainders to find the expression fitness and compiles the program. Here the important step in GP is to identify required functions and useful terminals and find a way to combine them to get an effective strategically program.…

    • 814 Words
    • 4 Pages
    Decent Essays
  • Decent Essays

    Tartan Case Study

    • 969 Words
    • 4 Pages

    More specifically, in incremental models, we are sure about what the system-to-be is, and then we divide the system-to-be into smaller functions, and then design, implement, and test those functions. However, in iterative models, just like Walton said, “iterative development emphasizes constant feedback, and quicker, smaller releases”[3], we build up our understanding of final products by going through many development cycles. One example would be a web login function. If we implement this login function by using incremental models, we might divide it into front-end, database, and login mechanisms, such as Facebook login. Then we go through design, coding, and testing phase for each function.…

    • 969 Words
    • 4 Pages
    Decent Essays
  • Decent Essays

    Best-First Search Paper

    • 1346 Words
    • 6 Pages

    To solve the memory requirements issue associated with Best-First algorithm, a constraint can be imposed, called a beam width B that specifies a number for the set of nodes that are selected for expansion and stored during each level of the search. This is called Beam search. Beam search uses a heuristics function to determine which nodes are closest to the goal node and only the best B nodes are stored and expanded further at each level. The rest are…

    • 1346 Words
    • 6 Pages
    Decent Essays
  • Decent Essays

    SVM And Genetic Algorithm

    • 985 Words
    • 4 Pages

    In SVM, the commonly used core function is RBF, at this point we just cram the RBF parameter optimization. Generalization C includes the optimized parameters. Another optimization path be headed to estimate the simplification ability of SVM utilizing a slope drop calculation over the arrangement of parameters. The SVM model prefers the parameters with esteem to the maximum generalization capability. However, this process normally time overriding and do not make fine, we represent a GA-based constraint optimization for…

    • 985 Words
    • 4 Pages
    Decent Essays
  • Decent Essays

    A/B Testing Essay

    • 1473 Words
    • 6 Pages

    Which we can then check whether or not changing the expertise had an optimistic, poor, or no effect on tourist conduct. 3. Importance of A/B Testing A/B trying out allows for individuals, teams, and businesses to make cautious and calculated changes to their site visitors experiences and they go on to collect the information on the results. This permits them to build the hypotheses and to understand much better which factors have an impact on the user experiences and on consumer behavior. Not only just answering a one-off question or settling a disagreement, AB testing is likely used consistently to continually beef up a given experience, bettering a single intention like conversion cost over time.…

    • 1473 Words
    • 6 Pages
    Decent Essays
  • Decent Essays

    Whales Observation Report

    • 1796 Words
    • 8 Pages

    Our proposed WOA–SVR details are illustrated as next: Preprocess: 1.1. Remove non-numerical value from features value to obtained the correct result. 1.2. Data scaling. The major trait of scaling is to bypass attributes in major numeric amplitude dominating those in lesser numeric amplitude.…

    • 1796 Words
    • 8 Pages
    Decent Essays
  • Decent Essays

    This is done because real images have anomalies at some points caused by sensor errors and image deformation caused by errors of the local trajectory and residual scaled differences. The research into which type of restoration approach should be used and the equations presented which will be used was done by (M. Sistiaga, 1998). The selected method was to use Partial Derivative Equations (P.D.E.) as it successfully restored images and replaced linear filtering methods. A scheme that has been developed to restore images is multi-scale morphological analysis proposed by (L. Alvarez, 1992), which was used by (Lucido, 1997), the diffusion is based on an equation in the…

    • 709 Words
    • 3 Pages
    Decent Essays