4 ms·

This is the type of non-obvious optimization that genetic algorithms excel at. This is not true. GA search is a hill climbing algorithm which is prone to findi

by codexon 16y ago

This is the type of non-obvious optimization that genetic algorithms excel at. This is not true. GA search is a hill climbing algorithm which is prone to finding local maxima. The less obvious a strategy is, the more likely it is that GA will miss it.

richcollins 16y ago
GAs are less likely than other learning techniques to get stuck at a local maxima because mutations and crossover can cause to them to search entirely new areas in the space (unlike ANNs for example).
henning 16y ago
> GA search is a hill climbing algorithm which is prone to finding local maxima GAs are not pure hill climbers. Variation operators introduce new solutions into the population at random. As long as premature convergence is prevented, GAs will probably explore the search space well. There's always a tradeoff between exploration and exploitation. > The less obvious a strategy is, the more likely it is that GA will miss it. This is a tautology that states "the harder a problem it is, the harder it is."
- codexon 16y ago
  GAs are not pure hill climbers. Variation operators introduce new solutions into the population at random. In searching for non-obvious solutions a GA is no better, probably even worse than an exhaustive search. You are essentially gambling to find the absolute maxima by increasing the mutation rate and population variance. GA is merely a heuristic to speed up searches by assuming the global solution is close to your randomly seeded population, something which is unlikely to be true in non-obvious solutions. Let's say you increase the mutation rate to the point where you are guaranteed find the "non-obvious solution". Well then you've essentially just created an insanely inefficient exhaustive search. This is a tautology that states "the harder a problem it is, the harder it is. No. For example in an exhaustive search, the obviousness of a strategy has no bearing on whether or not it would more likely be found.
  - henning 16y ago
    How convenient to ignore the fact that exhaustive search is completely computationally infeasible in most practical situations. Genetic algorithms are heuristics, yes. There is no guarantee they will work. That doesn't mean they haven't been successfully applied in a very wide variety of domains. The facts of their successes clearly mean nothing to you, though. "Not guaranteed to work" is not the same as "not useful as evidenced by hundreds of papers describing real-world applications." It takes a special kind of boorish ignorance to respond to a post where the guy comes up with a Starcraft 2 build that is "non-obvious" and pretty strong and whine about how a metaheuristic doesn't work/didn't work when you tried it.
    - codexon 16y ago
      I find your tone very disturbing. The point which keeps going over your head is that GA approaches a exhaustive search in which you randomly select cases to test until you've either tried them all (and wasted many cpu cycles along the way with repeated mutations) or luckily stumbled across the global maximum early (in which case you would never know if it was global). The reason why people use it instead of exhaustive searches is because they don't care about a global maximum, or in this case "obviousness". But to say that non-obvious solutions are a strong suit of GA is wrong, and that is what I had an issue with. If you knew the solution was non-obvious, you'd have better luck randomly testing solutions without the overhead of cross-over and mutations. I also doubt that an exhaustive search to find this 7 roach build is infeasible when today's chess engines are able to brute-force 10 steps in a matter of minutes on standard hardware. I also never "whine"d about how GA didn't work for me, so I don't know what to say about that except that it is now obvious you are trolling.

by codexon 16y ago

richcollins 16y ago

GAs are less likely than other learning techniques to get stuck at a local maxima because mutations and crossover can cause to them to search entirely new areas in the space (unlike ANNs for example).

henning 16y ago

> GA search is a hill climbing algorithm which is prone to finding local maxima GAs are not pure hill climbers. Variation operators introduce new solutions into the population at random. As long as premature convergence is prevented, GAs will probably explore the search space well. There's always a tradeoff between exploration and exploitation. > The less obvious a strategy is, the more likely it is that GA will miss it. This is a tautology that states "the harder a problem it is, the harder it is."

codexon 16y ago
GAs are not pure hill climbers. Variation operators introduce new solutions into the population at random. In searching for non-obvious solutions a GA is no better, probably even worse than an exhaustive search. You are essentially gambling to find the absolute maxima by increasing the mutation rate and population variance. GA is merely a heuristic to speed up searches by assuming the global solution is close to your randomly seeded population, something which is unlikely to be true in non-obvious solutions. Let's say you increase the mutation rate to the point where you are guaranteed find the "non-obvious solution". Well then you've essentially just created an insanely inefficient exhaustive search. This is a tautology that states "the harder a problem it is, the harder it is. No. For example in an exhaustive search, the obviousness of a strategy has no bearing on whether or not it would more likely be found.
- henning 16y ago
  How convenient to ignore the fact that exhaustive search is completely computationally infeasible in most practical situations. Genetic algorithms are heuristics, yes. There is no guarantee they will work. That doesn't mean they haven't been successfully applied in a very wide variety of domains. The facts of their successes clearly mean nothing to you, though. "Not guaranteed to work" is not the same as "not useful as evidenced by hundreds of papers describing real-world applications." It takes a special kind of boorish ignorance to respond to a post where the guy comes up with a Starcraft 2 build that is "non-obvious" and pretty strong and whine about how a metaheuristic doesn't work/didn't work when you tried it.
  - codexon 16y ago
    I find your tone very disturbing. The point which keeps going over your head is that GA approaches a exhaustive search in which you randomly select cases to test until you've either tried them all (and wasted many cpu cycles along the way with repeated mutations) or luckily stumbled across the global maximum early (in which case you would never know if it was global). The reason why people use it instead of exhaustive searches is because they don't care about a global maximum, or in this case "obviousness". But to say that non-obvious solutions are a strong suit of GA is wrong, and that is what I had an issue with. If you knew the solution was non-obvious, you'd have better luck randomly testing solutions without the overhead of cross-over and mutations. I also doubt that an exhaustive search to find this 7 roach build is infeasible when today's chess engines are able to brute-force 10 steps in a matter of minutes on standard hardware. I also never "whine"d about how GA didn't work for me, so I don't know what to say about that except that it is now obvious you are trolling.