Example – Tabu SearchFlowchart of a Standard Tabu Search Algorithm [7]Example – Tabu SearchExampleExampleExampleExamplePros and ConsSome Convergence Results1Example – Tabu Search–Minimum spanning tree problem with constraints.–Objective: Connects all nodes with minimum costsABDC E20 3015 4010525CostsLi, Liu, Lu UW Spring 2005 INDE 516 2Flowchart of a Standard Tabu Search Algorithm [7]Initial solution (i in S)Create a candidate list of solutionsEvaluate solutionsChoose the best admissible solutionStopping conditions satisfied ?Update Tabu & AspirationConditionsFinal solutionNoYes3Example – Tabu Search–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.)4Example 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.)5Example* 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*CE60+100=16095+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.)6Add25Example* 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.)7ExampleOptimal SolutionCost = 70Additional iterations only find inferior solutionsABDC E20 3015 40105258Pros 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 best solutions previously found by other approaches [1].•Cons:–Too many parameters to be determined–Number of iterations could be very large–Global optimum may not be found, depends on parameter settings9Some Convergence Results•Memory Tabu Search converges to the global optimum with probability one if randomly generated vectors (x) follows Gaussian or uniform distribution.•Convergent Tabu Search converges to the global optimum with probability
View Full Document
Unlocking...