Hacker News Reader

Comment by jules | Hacker News Reader

Hill climbing is far simpler and virtually always works better. In fact I've yet to see a practical case where GAs work better than simple randomized hill climbing.

View on HN

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.)

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.

Have you tried automatic programming? For one heuristic optimization project, I automatically derived arithmetic expressions to match an unknown function, using a wide variety of methods including hill-climbing. Many methods started out more efficient than genetic algorithms - at one hundred thousand evaluations or so, simulated annealing was doing best. But by one million, all other contenders had levelled out, while the genetic algorithm was still doggedly finding better answers. The fact that it maintains a population and exchanges working code between its members turns out to be extremely effective for hard problems.

Yes, I have tried automatic programming in the past, but my results were the opposite. Hill climbing universally does better. Of course you need to be reasonable and restart the search once it gets stuck in a local maximum. If you don't do that then GAs obviously do better since they start off with a whole population rather than one candidate. So the reason GAs do better has nothing whatsoever to do with its essential difference to hill climbing (the crossover). In fact if you just take an ordinary GA and disable crossover, and you let each individual in the population have exactly 1 offspring, it will usually work better! This is because crossover & the breeding rules of GA tend to remove diversity in the population.

By the way, in my automatic programming programming experiments hill climbing hardly did better than just brute force search. It fails for all but the smallest examples. So that's another one of those things that doesn't really work in practice.

My reading of genetic programming disagrees with you. In fact many have found that mutation doesn't actually help. Pure crossover with a random population seemed to work just fine (for genetic programming.)

The biggest problem is that the search space isn't smooth and even crossover is very mutative on discrete, arbitrary graphs.

> Hill climbing is far simpler and virtually always works better. In fact I've yet to see a practical case where GAs work better than simple randomized hill climbing.

Thank you for saying this.

Realizing this is sort of similar to the time when I first learned about how standard error-backprop neural networks really work, and I realized that they're "just" a stochastic optimization algo and not really actually "smart like a brain" that can learn everything (I was young :) ).

About, a "practical case" where GAs work better, I'm going to go with (generative/digital) art projects. The fact that a GA is sort of based on a simulation of a biological process lends extra flavour to an art piece that is somehow crafted using a GA, more so than if it had used hill-climbing or brute force. It'll help ask questions like "who is the artist here?" and "what is creativity" and "can a computer be alive?" etc etc.

Reply on news.ycombinator.com