"We then analyze an "idealized" genetic algorithm (IGA) that is signi cantly faster than RMHC and that gives a lower bound for GA speed. We identify the features of the IGA that give rise to this speedup, and discuss how these features can be incorporated into a real GA."
"As can be seen, the time to reach level one is comparable for the two algorithms, but the GA is much faster at reaching levels 2 and 3. Further, the GA discovers level 3 approximately twice as often as RMHC."
"We have presented analyses of two algorithms, RMHC and the IGA, and have used the analyses to identify some general principles of when and how a genetic algorithm will out-
perform hill climbing."
I'm not sure this paper says what you're claiming that it says.
Note that the "IGA" is not a real algorithm. Knowledge of the solution is encoded into the algorithm. It's no surprise that it outperforms an algorithm that does not have the privilege of knowing the solution before it starts.
Second, to get a result where a GA outperformed hill climbing they did the following:
1. They started with a problem that was DESIGNED to be very well suited to GAs and not so well suited to hill climbing. It turned out that when you do hill climbing in a non ridiculous way that GAs lose big time (by a factor of 10).
2. Through several steps they further modified the artificial problem to give a disadvantage to hill climbing and an advantage to GAs.
3. They tuned the GA's parameters and did not tune the hill climber's parameters.
4. They compared the performance by number of fitness function evaluations. This is unfair to hill climbing because GAs have bigger overheads elsewhere.
After these steps the GA outperformed hill climbing by about a factor of 2. So it is not clear that the GA would still win if you tuned the hill climber. Even if it did, this is a problem explicitly designed to give GAs an advantage. The fact that they had to go through so much effort to design such a problem doesn't instill much confidence that there exists a real world problem where GAs work.
I have tried to replicate their results and do the tuning of the hill climber, but unfortunately the paper is so vague on what the problem is that the algorithms are actually supposed to solve, so that I was not able to do this. If anybody knows a study of a problem (preferably real world) where GAs are shown to outperform reasonable forms of hill climbing I'd be very happy to hear it.
"If anybody knows a study of a problem (preferably real world) where GAs are shown to outperform reasonable forms of hill climbing I'd be very happy to hear it."
GA (specially pseudo-boolean GA) is not a "Golden Algorihtm" that solves every problem as most people think, rather it is a "idea" that was pioneered by Hollad in the sixties, now it's sole purpose is to explain the theoretical aspects of other GA-offshoot Evolutionary Optimization techniques like GP(Genetic Programming), EA (Evolutionary Algorithm), DE(Differential Evolution), ES(Evolutionary Strategy) etc, etc.
I think GP has much more impact in attacking real world problems, GECCO Humies award list has many interesting results where RMHC's may not be suitable -- http://www.genetic-programming.org/combined.html
"Even if it did, this is a problem explicitly designed to give GAs an advantage."
Well, yeah, you'd want to use GAs on problems for which they were well-suited. That's not at all the same as "clearly shows that GAs are NOT a good way to solve any problem".
Sure. The point is the effort they had to find such a problem. That indicates that it is very unlikely that any given practical problem is suitable for GAs. Again, if you are aware of any real problem where GAs work better than hill climbing, please do share. Note that this is not a very high bar. For example the same applied to quicksort vs insertion sort is "find any real example where quicksort outperforms insertion sort". If you couldn't find such an example and had to go to great lengths to artificially construct such an example then I'd call quicksort a failure, given that it's more complicated than insertion sort. Why GAs were/are as hyped as they are is a mystery to me.
But I agree, that they are not a silver bullet for any kind of problem and for most problems there is almost always a way smarter and more efficient algorithm.
I did not hold this presentation to show that GAs were the best solution for any problem. My intention was to teach sth. that I myself liked in university. Especially I thought that the way we were taught GAs in university was too complicated and complex.
"As can be seen, the time to reach level one is comparable for the two algorithms, but the GA is much faster at reaching levels 2 and 3. Further, the GA discovers level 3 approximately twice as often as RMHC."
"We have presented analyses of two algorithms, RMHC and the IGA, and have used the analyses to identify some general principles of when and how a genetic algorithm will out- perform hill climbing."
I'm not sure this paper says what you're claiming that it says.