Tabu SearchIntroductionOverview of Tabu SearchSlide 4Tabu Search StrategyParameters of Tabu SearchBasic Ingredients of Tabu SearchBasic Tabu Search AlgorithmTabu Search Stopping ConditionsExampleSlide 11Slide 12Slide 13Slide 14Pros and ConsReferencesTabu Search22c:145Artificial Intelligence2Introduction•Tabu – socially or culturally proscribed: forbidden to be used, mentioned, or approached because of social or cultural rather than legal prohibitions. (http://encarta.msn.com/dictionary_1861698691/taboo.html)•Glover, F. 1986. Future Paths for Integer Programming and Links to Artificial Intelligence. Computers and Operations Research. Vol. 13, pp. 533-549.3Overview of Tabu Search•Tabu search is based on introducing flexible memory structures in conjunction with strategic restrictions and aspiration levels as a means for exploiting search spaces [1].•Meta-heuristic that guides a local heuristic search procedure to explore the solution space beyond local optimum by use of a Tabu list.4Overview of Tabu Search•Used to solve combinatorial (finite solution set) optimization problems•A dynamic neighborhood search method•Use of a flexible memory to restrict the next solution choice to some subset of neighborhood of current solution5Tabu Search Strategy•3 main strategies:–Forbidding strategy: control what enters the tabu list–Freeing strategy: control what exits the tabu list and when–Short-term strategy: manage interplay between the forbidding strategy and freeing strategy to select trial solutions6Parameters of Tabu Search•Local search procedure•Neighborhood structure•Aspiration conditions•Form of tabu moves•Addition of a tabu move•Maximum size of tabu list•Stopping rule7•A chief way to exploit memory in tabu search is to classify a subset of the moves in a neighborhood as forbidden (or tabu).•A neighborhood is constructed to identify adjacent solutions that can be reached from current solution. •The classification depends on the history of the search, and particularly on the recency or frequency that certain move or solution components, called attributes, have participated in generating past solutions.•A tabu list records forbidden moves, which are referred to as tabu moves.•Tabu restrictions are subject to an important exception. When a tabu move has a sufficiently attractive evaluation where it would result in a solution better than any visited so far, then its tabu classification may be overridden. A condition that allows such an override to occur is called an aspiration criterion.Basic Ingredients of Tabu Search8Basic Tabu Search Algorithm•Step 1: Choose an initial solution i in S. Set i* = i and k=0.•Step 2: Set k=k+1 and generate a subset V of solution in N(i,k) such that either one of the Tabu conditions is violated or at least one of the aspiration conditions holds.•Step 3: Choose a best j in V and set i = j.•Step 4: If f(i) < f(i*) then set i* = i.•Step 5: Update Tabu and aspiration conditions.•Step 6: If a stopping condition is met then stop. Else go to Step 2.9Tabu Search Stopping ConditionsSome immediate stopping conditions could be the following:1. N(i, K+1) = 0. (no feasible solution in the neighborhood of solution i)2. K is larger than the maximum number of iterations allowed.3. The number of iterations since the last improvement of i* is larger than a specified number.4. Evidence can be given than an optimum solution has been obtained.Stopping criterion can, for example, use a fixed number of iterations, a fixed amount of CPU time, or a fixed number of consecutive iterations without an improvement in the best objective function value. Also stop at any iteration where there are no feasible moves into the local neighborhood of the current trial solution.10Example–Minimum spanning tree problem with constraints.–Objective: Connects all nodes with minimum costsABDC E20 3015 4010525ABDC E20 3015 4010525CostsAn optimal solution without considering constraintsConstraints 1: Link AD can be included only if link DE also is included. (penalty:100)Constraints 2: At most one of the three links – AD, CD, and AB – can be included.(Penalty of 100 if selected two of the three, 200 if all three are selected.)11Example New cost = 75 (iteration 2) ( local optimum)ABDC E20 3015 4010525Delete AddIteration 1Cost=50+200 (constraint penalties)Add Delete CostBEBEBECEACAB75+200=27570+200=27060+100=160CDCDADAC60+100=16065+300=365DEDEDECEACAD85+100=18580+100=18075+0=75Constraints 1: Link AD can be included only if link DE also is included. (penalty:100)Constraints 2: At most one of the three links – AD, CD, and AB – can be included.(Penalty of 100 if selected two of the three, 200 if all three are selected.)12Example* A tabu move will be considered only if it would result in a better solution than the best trial solution found previously (Aspiration Condition) Iteration 3 new cost = 85 Escape local optimumABDC E20 3015 4010525TabuDeleteAddTabu list: DEIteration 2 Cost=75Add Delete CostADADADDE*CEACTabu move85+100=18580+100=180BEBEBECEACAB100+0=10095+0=9585+0=85CDCDDE*CETabu move95+100=195Constraints 1: Link AD can be included only if link DE also is included. (penalty:100)Constraints 2: At most one of the three links – AD, CD, and AB – can be included.(Penalty of 100 if selected two of the three, 200 if all three are selected.)13Add25Example* A tabu move will be considered only if it would result in a better solution than the best trial solution found previously (Aspiration Condition)Iteration 4 new cost = 70 Override tabu statusABDC E20 3015 40105TabuTabuDeleteTabu list: DE & BEIteration 3 Cost=85Add Delete CostABABABBE*CEACTabu move100+0=10095+0=95ADADADDE*CEAC60+100=16095+0=9590+0=90 CDCDDE*CE70+0=70 105+0=105Constraints 1: Link AD can be included only if link DE also is included. (penalty:100)Constraints 2: At most one of the three links – AD, CD, and AB – can be included.(Penalty of 100 if selected two of the three, 200 if all three are selected.)14ExampleOptimal SolutionCost = 70Additional iterations only find inferior solutionsABDC E20 3015 401052515Pros and Cons•Pros:–Allows non-improving solution to be accepted in order to escape from a local optimum–The use of Tabu list–Can be applied to both discrete and continuous solution spaces–For larger and more difficult problems (scheduling, quadratic assignment and vehicle routing), tabu search obtains solutions that rival and often surpass the