"Local Search" is an unfortunate term -- it's optimization, though the term "local search" is historically common in the hill-climbing community. But I don't think many people would place Genetic Algorithms (GA) in anything other than the "global" category nowadays. Ant Colony Optimization, Particle Swarm Optimization, Genetic Algorithms, Evolution Strategies, Estimation of Distribution Algorithms, Simulated Annealing, etc.: these things are global stochastic optimization techniques.
The terms "search" and "optimization" are often conflated, mostly because "search" was used by two different communities early on to mean two different things back in the 1970s. You still see echoes of it in the optimization community, particularly in single-solution techniques like stochastic hillclimbing, or old terms like "beam search".
So here's how I define them. I believe that "search" typically is applied to problems where you have something to search for. A state or point in space which meets a certain criterion. The most common examples of this are state-space search problems, where the path you took to get there matters, and constraint satisfaction search problems, where the path doesn't matter, only the result. It's also applied in simpler fashions: tree search, binary search, etc.
Optimization, on the other hand, applies to problems where you are trying to find a point which is optimal with regard to some criterion. Unlike search, where it's a find-it-or-not proposition, in optimization you do not necessarily expect to find the globally optimal criterion ever, and in fact you don't necessarily even know that one exists (it could just keep going up and up). You're just trying to find the best thing you can given the time and resources you have.
Optimization algorithms are usually more general, and weaker, than search algorithms. Thus you can typically cast a search problem into an optimization problem -- for example, use your heuristic as the optimization criterion -- but optimization algorithms were designed for a more general class of problems and thus are expected to be outperformed by a custom-designed search algorithm (this fact is a general rule of thumb for pretty much everything in optimization, particularly stochastic optimization -- it's a last-ditch approach). Similarly you can use an optimization algorithm to find a decision tree solution: but I'd get smacked around by colleagues in the machine learning community for calling PSO a machine learning algorithm.
So interesting question: is Alpha-Beta Pruning a search algorithm or an optimization algorithm?
At any rate -- Russell and Norvig are entirely muddled about this. They admit (p. 121) exactly what I state above, yet go on to lump the two together without any further explanation, and then make the strange case that local search is global if it is "complete" -- a very logician way of stating it, but not a term in the field so far as I know.
Very well explained. Thanks. And its how I understand it. I see search as having to do with combinatorial exploration and optimization as having to do with exploring vector spaces. You switch to heuristics in search when the space is too big or complex. But I also think that for suitable generalizations of the term one can view search as optimization or vice versa for reasoning purposes. I think there is something philosophical to be said about the fact that metaheuristics work as well as they do.
The terms "search" and "optimization" are often conflated, mostly because "search" was used by two different communities early on to mean two different things back in the 1970s. You still see echoes of it in the optimization community, particularly in single-solution techniques like stochastic hillclimbing, or old terms like "beam search".
So here's how I define them. I believe that "search" typically is applied to problems where you have something to search for. A state or point in space which meets a certain criterion. The most common examples of this are state-space search problems, where the path you took to get there matters, and constraint satisfaction search problems, where the path doesn't matter, only the result. It's also applied in simpler fashions: tree search, binary search, etc.
Optimization, on the other hand, applies to problems where you are trying to find a point which is optimal with regard to some criterion. Unlike search, where it's a find-it-or-not proposition, in optimization you do not necessarily expect to find the globally optimal criterion ever, and in fact you don't necessarily even know that one exists (it could just keep going up and up). You're just trying to find the best thing you can given the time and resources you have.
Optimization algorithms are usually more general, and weaker, than search algorithms. Thus you can typically cast a search problem into an optimization problem -- for example, use your heuristic as the optimization criterion -- but optimization algorithms were designed for a more general class of problems and thus are expected to be outperformed by a custom-designed search algorithm (this fact is a general rule of thumb for pretty much everything in optimization, particularly stochastic optimization -- it's a last-ditch approach). Similarly you can use an optimization algorithm to find a decision tree solution: but I'd get smacked around by colleagues in the machine learning community for calling PSO a machine learning algorithm.
So interesting question: is Alpha-Beta Pruning a search algorithm or an optimization algorithm?
At any rate -- Russell and Norvig are entirely muddled about this. They admit (p. 121) exactly what I state above, yet go on to lump the two together without any further explanation, and then make the strange case that local search is global if it is "complete" -- a very logician way of stating it, but not a term in the field so far as I know.