ABSTRACT
Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225 7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226 7.2 Branch-and-Bound Algorithms and Interval Analysis Methods . . . . . . . . . . . . . . . . . . . . . . . . 227 7.3 Heuristics and Metaheuristics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231
7.3.1 Local Search and Multistart Local Search Techniques . . . . . . . . . . . . . . . . . . . . . . . . . 232 7.3.1.1 Tunneling Methods for Bounded Constrained Problems . . . . . . . . . . . . . . 234 7.3.1.2 Multistart Local Search for Nonconvex Minimization over Polytopes . 235 7.3.1.3 Grids and Clusters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237 7.3.1.4 Greedy Randomized Adaptive Search Procedure . . . . . . . . . . . . . . . . . . . . . 240
7.3.2 Simulated Annealing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241 7.3.3 Tabu Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243 7.3.4 Controlled Random Search Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246 7.3.5 Evolutionary and Genetic Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 247
7.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249 Acknowledgments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250
Global optimization problems (GOPs) arise in a wide range of real-world problems. They include applications in operations research, engineering, biological sciences, and computer science. The effective use of parallel machines in global optimization is a very promising area of research since, due to inherent difficulty of problems it studies, only instances of limited dimension can be solved in reasonable computer time on conventional machines. However, the use of parallel and distributed processing can substantially increase the possibilities for the success of the global optimization approach in practice. A survey on parallel algorithms proposed for the solution of GOPs is given. A majority of these algorithms belongs to the class of heuristic techniques. This is because such methods easily parallelize according to general principles. Even deterministic optimizing methods, such as branch-and-bound (BB) and interval methods, tend to be excellent candidates for parallel computing, although the effort required to achieve both efficient parallelization and to preserve their convergence properties is certainly greater than in the case of heuristic methods. That is why, until very recently, virtually no work (or a very little) had be done on parallel deterministic methods, although the effective parallelization of the search process appear the only way to make solution of large-scale problems practical.
