Parallel Search for Combinatorial Optimization: Genetic Algorithms, Simulated Annealing, Tabu Search and GRASP

In this paper, we review parallel search techniques for approximating the global optimal solution of combinatorial optimization problems. Recent developments on parallel implementation of genetic algorithms, simulated annealing, tabu search, and greedy randomized adaptive search procedures (GRASP) are discussed. Key words: Parallel Search, Heuristics, Genetic Algorithms, Simulated Annealing, Tabu Search, GRASP, Parallel Computing. 1 Introduction Search techniques are fundamental problem-solving methods in computer science and operations research. Search algorithms have been used to solve many classes of problems, including path-finding problems, two-player games and constraint satisfaction problems. Classical examples of path-finding problems include many combinatorial optimization problems (e.g. integer programming) and puzzles (e.g. Rubic's cube, Eight Puzzle). Chess, backgammon, and othello Invited paper to appear in Proceedings of the Workshop on Parallel Algorithms for Irregul..