I've seen hype about genetic algorithms, but no actual examples of problems where they are useful. Based on reading the threads here, it looks like the requirement for a GA to be useful is
* Problem is noisy and complex enough to make other algorithms fail
* Problem is understood well enough to determine good mutation and crossover operators.
But it seems to me like the requirements are somewhat contradictory. If you know a lot about a problem, surely there's a better method than just randomly moving population of search points around and praying for emergent behavior? Are there any concrete examples where genetic algorithms are actually useful?
when are genetic algorithms useful?
I've seen hype about genetic algorithms, but no actual examples of problems where they are useful. Based on reading the threads here, it looks like the requirement for a GA to be useful is
* Problem is noisy and complex enough to make other algorithms fail
* Problem is understood well enough to determine good mutation and crossover operators.
But it seems to me like the requirements are somewhat contradictory. If you know a lot about a problem, surely there's a better method than just randomly moving population of search points around and praying for emergent behavior? Are there any concrete examples where genetic algorithms are actually useful?
In general there are better solutions, GAs however are easy to implement and can be used to optimize almost any process or design (If you can assign a relative fitness to the result then a GA will work reasonably well), It basically trades the need for human expertise for a need of computing power.
Making machines do "creative" work is interesting and even if they suck at it they will work 24/7 without complaining, they never ask for a raise(unless the cost of power goes up) and you can chain them all in the basement without having the authorities come after you, does it really matter if its practical ?
That said however there are tons of papers around discussing practical applications of GAs that you could take a look at and it has been used in the real world in fields like medical research for example.
I feel that GAs are a solution in search of a problem. Just like Artificial Neural Networks, they have a very sexy name and they promise a solution to almost anything, so every generation will find them fascinating for a little while. But then you find that for most problems there are better ways to do things.
In particular these two techniques have virtually no application to AI in games.
In particular these two techniques have virtually no application to AI in games.
I agree with alvaro. I've taken a class in GA at uni and can say that they aren't very useful(IMHO).
All the toy problems we have seen were solvable(sometimes barely) with a GA but I don't see a reason to use it an not a hand crafted algorithm.
They are easy to implement and most of the code is reusable ( you need to change only a few operators), and maybe for a simple problem they might be a good choice
if you've already got a framework running and don't have the time to invest in an ad hoc algorithm. Also fine-tuning all the parameters can take more time than actually writing the whole thing.
In general the idea is nice but I personally haven't come across a problem where GA was a good solution.
All the toy problems we have seen were solvable(sometimes barely) with a GA but I don't see a reason to use it an not a hand crafted algorithm.
They are easy to implement and most of the code is reusable ( you need to change only a few operators), and maybe for a simple problem they might be a good choice
if you've already got a framework running and don't have the time to invest in an ad hoc algorithm. Also fine-tuning all the parameters can take more time than actually writing the whole thing.
In general the idea is nice but I personally haven't come across a problem where GA was a good solution.
In particular these two techniques have virtually no application to AI in games.
GAs have been used to find strong build orders for the opening stages of Starcraft 2. (I'm not saying this is evidence for anything more general, just seems relevant to the OP.)
I've seen an AI player for the board game Puerto Rico (written in excel no less) using a GA which is almost unbeatable. It can be found on the Puerto Rico page of BoardGameGeek.
There's many of applications of GA and ANN solving real-world physics, engineering, and computing problems.
http://en.wikipedia.org/wiki/List_of_genetic_algorithm_applications
http://en.wikipedia.org/wiki/Neural_network#Applications_of_natural_and_of_artificial_neural_networks
Most of them have nothing to do with game AI. There are a few games that use them though:
- Forza (ANN drivers)
- Colin McRae (ANN drivers)
- Black and White (some type of learning?)
- Creatures (not sure ...)
http://en.wikipedia.org/wiki/List_of_genetic_algorithm_applications
http://en.wikipedia.org/wiki/Neural_network#Applications_of_natural_and_of_artificial_neural_networks
Most of them have nothing to do with game AI. There are a few games that use them though:
- Forza (ANN drivers)
- Colin McRae (ANN drivers)
- Black and White (some type of learning?)
- Creatures (not sure ...)
The reason for using a GA to train an ANN is that multilayer ANNs are hideous. The mapping from weights to training error is an ugly nonconvex mess. Since there's not much you can do, you throw a sample-based optimizer like an ANN at it.
But remember that the reason you were stuck using a GA was your choice of ANNs in the first place. Had you just stuck with a linear architecture -- a sum of basis functions -- you'd have gotten a standard linear least squares problem that you could have solved quickly with QR factorization or the conjugate gradient method. So why didn't you just choose that from the outset?
Good question.
But remember that the reason you were stuck using a GA was your choice of ANNs in the first place. Had you just stuck with a linear architecture -- a sum of basis functions -- you'd have gotten a standard linear least squares problem that you could have solved quickly with QR factorization or the conjugate gradient method. So why didn't you just choose that from the outset?
Good question.
But it seems to me like the requirements are somewhat contradictory. If you know a lot about a problem, surely there's a better method than just randomly moving population of search points around and praying for emergent behavior? Are there any concrete examples where genetic algorithms are actually useful?
Avlaro kind of summed it up. I've used GA's before, with some success, but there have always been better alternatives and I was just 'playing'.
Their strength is that they are not problem specific, and in theory could be used to 'solve' just about any problem given enough computing time.
In reality this is mostely pointless. GAs, and ANNs, were dreamt up in a time when processing power (and raw data) was very limited. These days it's feasible to do a somewhat exhaustive search of a space using millions of data samples, so....
As far as games go, I can think of a few uses, but so far haven't seen anyone use them.
- Black and White (some type of learning?)
- Creatures (not sure ...)
Black & White simply used reinforcement learning. All that does is tweak weight coefficients.
Creatures used a GA for the actual genetics (so not really a GA per se... just a gene sequence that was combined and mutated from parents). They also used a form of NN for the learning, iirc. Not really typical gameplay, however. Again, both of these were, as Alvaro said, the algorithms looking for problems and finding them.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
