5 ms·

What techniques are now used in place of GAs?

by istjohn 16y ago

aothman 16y ago
GAs are just a really complex version of a local search algorithm. The problem with them is that they're just too complicated - you're trying to solve some non-linear problem, and your first step is to introduce several more non-linear problems that also need to be solved (picking chromosomes, mixing, population size, etc.)?
- adovenmuehle 16y ago
  I'm kind of interested if you could point us in the direction of specific techniques. I always thought neural nets and genetic algorithms were interesting and I'm curious what other techniques are out there.
  - jerf 16y ago
    Your query is so vague it's hard to know where to even start; you're looking for "artificial intelligence" or "machine learning". Here's a halfway decent start, actually: http://en.wikipedia.org/wiki/Artificial_Intelligence#Tools http://en.wikipedia.org/wiki/Artificial_Intelligence#Tools , it at least arms you with a lot of search terms and introductory overviews. Neural nets and genetic algorithms are plenty interesting, it's just that they're way more interesting than they are useful. (Also note I didn't say useless. Just, not that useful.)
  - aothman 16y ago
    For solving local search problems, I use tabu search (hill climb with a "recently visited" list) or beam search (simultaneous hill search). Both are simple techniques that show remarkable emergent behavior. Many search problems are better phrased in terms of numerical optimization or what have you - if your problems maps a continuous space to a continuous space there's probably a standard numerical technique that solves it better than a local search hack. For Machine Learning type applications, SVMs are very popular. Briefly, both sufficiently deep neural nets and sufficiently dimensional SVMs are arbitrarily expressive, but SVMs give you a better perspective on what is actually happening with your problem. If you're interested in Machine Learning, you should check out Andrew Moore's very well-written tutorials: http://www.autonlab.org/tutorials/list.html http://www.autonlab.org/tutorials/list.html
  - Dn_Ab 16y ago
    There are lots of techniques. Really simple and effective methods are naive bayes and kNN. Other methods include decision trees and logistic regression which seems to be popular at Google from what I can indirectly infer from their papers. More complex methods include bayesian and non bayesian graphical models, kernel methods (SVM, RVM) and not too hard but powerful methods are boosted trees, random forests and ensemble methods in general. Layers of unsupervised learners (clustering) feeding into a supervised learner form a very powerful technique known as deep learning. This technique hasn't found a niche though and can be outperformed by shallower methods for much of where they are used [1]. And due to all this big data mumbo jumbo on-line learning methods are getting to be more important. [1] http://ai.stanford.edu/~ang/papers/nipsdlufl10-AnalysisSingleLayerUnsupervisedFeatureLearning.pdf http://ai.stanford.edu/~ang/papers/nipsdlufl10-AnalysisSingl...
lwat 16y ago
Actual Genetic Algorithms are not really applicable for this (or most other) AI problems.
Dn_Ab 16y ago
Simulated Annealing with restarting is a simpler, less finicky and robust one to use in place of GAs. But since the No Free Lunch theorem for optimization says that the general applicability of any optimization algorithm is as bad as every other and no better than random search the answer is like anything else. Understand your problem and pick the right tools. You can get an overview of the numerous techniques here. http://en.wikipedia.org/wiki/Category:Optimization_algorithms http://en.wikipedia.org/wiki/Category:Optimization_algorithm... * Actually its not quite any since it holds not exactly but to a very very good approximation and there are a few, like Coevolutionary approaches which provide a loophole out of that. So that might be something you want to look at.
- yters 16y ago
  What is the loophole that coevolution provides? I didn't realize there was a loophole to NFLT.
  - Dn_Ab 16y ago
    Well the loophole is not really a loophole more like an escape hatch in that NFLT was shown to not be applicable for certain types of coevolutionary algorithms like say pareto coevolution. The way I understand it is that in essence the no free lunch theorem only applies when candidate solutions are not re-evaluated in terms of relative performance. In coevolution we continually pit a population of candidate solutions 'to play' against each other in order to evolve a champion. Since fitness in this case is relative and not absolute - making performance tricky to measure - NFTL can be wiggled out of. as long as you can evaluate/term your problem within game like heuristics. - http://www.no-free-lunch.org/ http://www.no-free-lunch.org/ - http://cs.calstatela.edu/wiki/images/1/15/Wolpert-Coevolution.pdf http://cs.calstatela.edu/wiki/images/1/15/Wolpert-Coevolutio...

What techniques are now used in place of GAs?

by istjohn 16y ago

What techniques are now used in place of GAs?

GAs are just a really complex version of a local search algorithm. The problem with them is that they're just too complicated - you're trying to solve some non-linear problem, and your first step is to introduce several more non-linear problems that also need to be solved (picking chromosomes, mixing, population size, etc.)?

adovenmuehle 16y ago
I'm kind of interested if you could point us in the direction of specific techniques. I always thought neural nets and genetic algorithms were interesting and I'm curious what other techniques are out there.
- jerf 16y ago
  Your query is so vague it's hard to know where to even start; you're looking for "artificial intelligence" or "machine learning". Here's a halfway decent start, actually: http://en.wikipedia.org/wiki/Artificial_Intelligence#Tools http://en.wikipedia.org/wiki/Artificial_Intelligence#Tools , it at least arms you with a lot of search terms and introductory overviews. Neural nets and genetic algorithms are plenty interesting, it's just that they're way more interesting than they are useful. (Also note I didn't say useless. Just, not that useful.)
- aothman 16y ago
  For solving local search problems, I use tabu search (hill climb with a "recently visited" list) or beam search (simultaneous hill search). Both are simple techniques that show remarkable emergent behavior. Many search problems are better phrased in terms of numerical optimization or what have you - if your problems maps a continuous space to a continuous space there's probably a standard numerical technique that solves it better than a local search hack. For Machine Learning type applications, SVMs are very popular. Briefly, both sufficiently deep neural nets and sufficiently dimensional SVMs are arbitrarily expressive, but SVMs give you a better perspective on what is actually happening with your problem. If you're interested in Machine Learning, you should check out Andrew Moore's very well-written tutorials: http://www.autonlab.org/tutorials/list.html http://www.autonlab.org/tutorials/list.html
- Dn_Ab 16y ago
  There are lots of techniques. Really simple and effective methods are naive bayes and kNN. Other methods include decision trees and logistic regression which seems to be popular at Google from what I can indirectly infer from their papers. More complex methods include bayesian and non bayesian graphical models, kernel methods (SVM, RVM) and not too hard but powerful methods are boosted trees, random forests and ensemble methods in general. Layers of unsupervised learners (clustering) feeding into a supervised learner form a very powerful technique known as deep learning. This technique hasn't found a niche though and can be outperformed by shallower methods for much of where they are used [1]. And due to all this big data mumbo jumbo on-line learning methods are getting to be more important. [1] http://ai.stanford.edu/~ang/papers/nipsdlufl10-AnalysisSingleLayerUnsupervisedFeatureLearning.pdf http://ai.stanford.edu/~ang/papers/nipsdlufl10-AnalysisSingl...

lwat 16y ago

Actual Genetic Algorithms are not really applicable for this (or most other) AI problems.

Dn_Ab 16y ago

Simulated Annealing with restarting is a simpler, less finicky and robust one to use in place of GAs. But since the No Free Lunch theorem for optimization says that the general applicability of any optimization algorithm is as bad as every other and no better than random search the answer is like anything else. Understand your problem and pick the right tools. You can get an overview of the numerous techniques here. http://en.wikipedia.org/wiki/Category:Optimization_algorithms http://en.wikipedia.org/wiki/Category:Optimization_algorithm... * Actually its not quite any since it holds not exactly but to a very very good approximation and there are a few, like Coevolutionary approaches which provide a loophole out of that. So that might be something you want to look at.

yters 16y ago
What is the loophole that coevolution provides? I didn't realize there was a loophole to NFLT.
- Dn_Ab 16y ago
  Well the loophole is not really a loophole more like an escape hatch in that NFLT was shown to not be applicable for certain types of coevolutionary algorithms like say pareto coevolution. The way I understand it is that in essence the no free lunch theorem only applies when candidate solutions are not re-evaluated in terms of relative performance. In coevolution we continually pit a population of candidate solutions 'to play' against each other in order to evolve a champion. Since fitness in this case is relative and not absolute - making performance tricky to measure - NFTL can be wiggled out of. as long as you can evaluate/term your problem within game like heuristics. - http://www.no-free-lunch.org/ http://www.no-free-lunch.org/ - http://cs.calstatela.edu/wiki/images/1/15/Wolpert-Coevolution.pdf http://cs.calstatela.edu/wiki/images/1/15/Wolpert-Coevolutio...