Award Date

5-1-2014

Degree Type

Thesis

Degree Name

Master of Science in Computer Science

Department

Computer Science

First Committee Member

Wolfgang Bein

Second Committee Member

Ajoy K Datta

Third Committee Member

Juyeon Jo

Fourth Committee Member

Venkatesan Muthukumar

Fifth Committee Member

Kathryn Hausbek Korgan

Number of Pages

66

Abstract

Tabu search is a Meta heuristic loosely connected to evolutionary computing. It has been used to tackle hard problems, especially combinatorial optimization problems. Tabu search is designed to overcome difficult regions of a search space by imposing restrictions. Various methods for diversification and intensification are applied depending on the particular problem type and on what type of solutions (within the set of good solutions) are sought. Tabu search uses memory - short term, long term and intermediate - to achieve diversification and intensification. Furthermore, aspiration criteria may be used to tune the optimization process.

Thus the Tabu search Meta heuristic is very general. Different variants of the Tabu search Meta heuristic are presented in the context of combinatorial optimization. Problems discussed include the travelling salesman problem, various graph problems, and scheduling.

Keywords

Combinatorial optimization; Computer algorithms; Heuristic algorithms; Memory--Data processing; Search theory

Disciplines

Computer Sciences

Language

English


Share

COinS