Hacker News Reader

Comment by Houshalter | Hacker News Reader

Hill climbing by it's very nature is going to be faster (unless you can parallelize the GA) because you are only evaluating 1 solution at a time rather than a whole population. The problem is it's "greedy" and prone to getting stuck in local optima. GAs explore around a wide territory before converging and so generally get a better result (especially with crossover which the one from this post didn't use.)

View on HN

That's what people always say but it's false. You do hill climbing until you reach a local maximum, then you restart to a random state and repeat. The difference between hill climbing an GAs is that in GAs you do crossover. So in order to argue that GAs do better you have to show that crossover is beneficial. In all the cases that I have tested, GAs actually do worse because unlike with randomized hill climbing, GAs waste a lot of resources because the population usually isn't 100% diverse.

There is also a paper by the co authored by the inventor of genetic algorithms, where they try to come up with a toy problem where GAs beat hill climbing. They start off with a toy problem that is designed to be an example where GAs shine, but they show that hill climbing actually works (far) better. Then they modify the toy problem in several steps, yet they only succeed barely in coming up with a toy problem where GAs beat hill climbing. Keep in mind that this is an extremely contrived toy problem. Suffice it to say that if coming up with a toy problem is that hard, it's unlikely that you will see a real world problem where GAs do better.

Every field has its dark areas, like chemistry has had alchemists and their quest to create gold. GAs are one of the dark areas of computer science, where a lot of papers have been published but it ultimately turned out to be all bullshit.

What if you GA the algorithm itself? Such that GA converges on hill climbing (or something better, if it exists) as the best technique to use.

I suppose you're talking about genetic programming? That is wildly optimistic. Genetic programming can't find anything except the most trivial programs.

That's been tried before. It's theoretically possible, but unless you have a ton of computing power and example problems to work on, it'd probably just overfit to the specific problems you train it on.

And as the other comment pointed out, genetic programming is far too weak to achieve anything this complex. You need to simplify the problem tremendously by hand and then have the computer optimize the last few bits. Though seeding existing metaheuristics to start with might work.

Well, crossover is extremely powerfull and makes genetic algorithms very genereic. You are right that it's probably overkill for most problems we solve with computers, but only because we solve very simple problems nowadays.

Anyway, my experience with automatic programming is completely oposite to yours, and in line with comicjk. I've always had better results with GA than with hill climbing* or simulated annealing. I have the same experience for resource scheduling. Of course, your experience will vary a lot depending on the data you want to fit/schedule.

Also, nothing is stopping you from including hill climbing as a kind of mutation...

* Last time I used it, I didn't even have a well behaved gradient to climb, it was zero at a huge number of places, and I knew it beforehand. Automatic programming applies to all kinds of crazy domains.

You should publish a paper on the problem you solved with GA. It will be a huge breakthrough, since so far here is only 1 problem known to work better with GAs than hill climbing, and it's a toy problem specifically crafted for this purpose.

I'm not very inclined to share it.

I was trying to fit a potential field, that I knew consisted of a map of 12 dimensions into 1. I could approximate it pointwise, but only with a very slow procedure, and needed both a faster one and a derivative.

Many stochastic methods get around the local optima problem with various techniques. The simplest one is just to pick another random place to start climbing.

Reply on news.ycombinator.com