5 ms·

Sadly, it's three editions and AIMA is still hopeless regarding stochastic optimization (genetic algorithms, simulated annealing, ant colony optimization, hill

Sadly, it's three editions and AIMA is still hopeless regarding stochastic optimization (genetic algorithms, simulated annealing, ant colony optimization, hill climbing, and the like), and gradient-based optimization. It seems they don't want to be bothered about the significant difference between search and optimization. So they stick all the stochastic optimization stuff into a section called "local search and optimization", and place it underneath the Search chapter (it's not search, and almost none of it is local). And then separate out optimization methods like gradient descent etc., placing them under "local search in continuous spaces", as if (1) they were search and (2) stochastic optimization wasn't applied to continuous spaces. And if this wasn't muddled enough, their recommended books for stochastic optimization aren't under the Search chapter at all -- they've been placed under the Machine Learning chapter. And it's a strange collection. I'm pretty disappointed with AIMA's seemingly poor understanding of this area. Well, I guess at least it's better than their cursory treatment of multiagent systems.

leoc 16y ago
Could you recommend a better introductory text for these topics?
- notaddicted 16y ago
  I believe he did so yesterday: http://news.ycombinator.com/item?id=2464591 http://news.ycombinator.com/item?id=2464591
bpodgursky 16y ago
How is optimization not a form of search? It's a search through the solution space which tries to find a global minima or maxima. Also, of the techniques you list, simulated annealing, hill climbing and gradient-based optimization are all local search methods (genetic algorithms may or may not be, depending on your emphasis on mutation vs recombination.)
- Dn_Ab 16y ago
  I agree with you, most of those methods are local and optimization is a form of search typically used for continuous and usually differentiable spaces. One can also say search is a form of optimization. But Based on my readings genetic algorithms are more known to be susceptible to local minima, while simulated annealing in theory is a global method. --- As for genetic algorithms - for optimization I prefer Differential Evolution. For Exploration maybe genetic algorithms are more fruitfull although I think Genetic programming and Learning Classifier Systems be slept on. Speaking of slept on - another under appreciated but much more used method is stochastic gradient descent. Global optimums might be overrated.
  - SeanLuke 16y ago
    > But Based on my readings genetic algorithms are more known to be susceptible to local minima, while simulated annealing in theory is a global method. Both simulated annealing and genetic algorithms are global methods, and both can get caught in local minima. The same goes for pretty much every other global stochastic optimization method out there. Simulated annealing got this "special" reputation among engineers back in the '80s because the Metropolis algorithm had a formal proof of global guarantees -- run it long enough and it's guaranteed to find the global optimum. But nowadays most every algorithm in this category has similar guarantees. It's relatively easy to make such a guarantee as it turns out. I like differential evolution too, though it's pretty exploitative.
- SeanLuke 16y ago
  "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.

leoc 16y ago

Could you recommend a better introductory text for these topics?

notaddicted 16y ago
I believe he did so yesterday: http://news.ycombinator.com/item?id=2464591 http://news.ycombinator.com/item?id=2464591

bpodgursky 16y ago

How is optimization not a form of search? It's a search through the solution space which tries to find a global minima or maxima. Also, of the techniques you list, simulated annealing, hill climbing and gradient-based optimization are all local search methods (genetic algorithms may or may not be, depending on your emphasis on mutation vs recombination.)

Dn_Ab 16y ago
I agree with you, most of those methods are local and optimization is a form of search typically used for continuous and usually differentiable spaces. One can also say search is a form of optimization. But Based on my readings genetic algorithms are more known to be susceptible to local minima, while simulated annealing in theory is a global method. --- As for genetic algorithms - for optimization I prefer Differential Evolution. For Exploration maybe genetic algorithms are more fruitfull although I think Genetic programming and Learning Classifier Systems be slept on. Speaking of slept on - another under appreciated but much more used method is stochastic gradient descent. Global optimums might be overrated.
- SeanLuke 16y ago
  > But Based on my readings genetic algorithms are more known to be susceptible to local minima, while simulated annealing in theory is a global method. Both simulated annealing and genetic algorithms are global methods, and both can get caught in local minima. The same goes for pretty much every other global stochastic optimization method out there. Simulated annealing got this "special" reputation among engineers back in the '80s because the Metropolis algorithm had a formal proof of global guarantees -- run it long enough and it's guaranteed to find the global optimum. But nowadays most every algorithm in this category has similar guarantees. It's relatively easy to make such a guarantee as it turns out. I like differential evolution too, though it's pretty exploitative.
SeanLuke 16y ago
"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.