James Tauber

journeyman of some

blog > 2005 > 11 > 29 >

Devin Kilminster Has Been Annealing

Devin Kilminster has taken the lead in category III of my ongoing programming competition. Unlike Mark Ellison, who used a deterministic algorithm, Devin used simulated annealing like I did.

I'm starting to put together a second edition of the programming competition that will involve more complex relationships between prerequisites. I don't think that will make the problem any harder for simulated annealing approaches (it will just involve changing the scoring function) but it will probably require quite different deterministic approaches than the current competition. I might have two divisions to keep it fair between the 'annealers' and the 'deterministas'.

Categories:
prev « programming_competition » next

Comments (4)

Bob Hutchison on Nov. 29, 2005:

I don't know if you should separate them. If the 'deterministas' were really doing an exact solution, then *nothing* can beat their solutions -- only get poorer solutions (much) faster. If they don't have the best solution then you are really talking about implementations of specialised heuristics. Simulated Annealing is just one kind of general purpose heuristic. The specialised heuristics should be able to outperform the general purpose ones. On top of that, how are you going to tell them apart? I think that all you can do is include a time component, but that is impractical.

Perhaps you mean to separate them by their use of a random number generator? Not sure about that either... most good heuristics at some point or other 'toss a coin'.

Hmm. What do you mean by 'deterministic' anyway?

Bob Hutchison on Nov. 29, 2005:

I don't know if you should separate them. If the 'deterministas' were really doing an exact solution, then *nothing* can beat their solutions -- only get poorer solutions (much) faster. If they don't have the best solution then you are really talking about implementations of specialised heuristics. Simulated Annealing is just one kind of general purpose heuristic. The specialised heuristics should be able to outperform the general purpose ones. On top of that, how are you going to tell them apart? I think that all you can do is include a time component, but that is impractical.

Perhaps you mean to separate them by their use of a random number generator? Not sure about that either... most good heuristics at some point or other 'toss a coin'.

Hmm. What do you mean by 'deterministic' anyway?

James Tauber on Nov. 30, 2005:

I don't think exact solutions are going to be possible for anything but the smallest of texts---the problem can be embedded in the traveling salesman problem.

But you're right that lumping the non-annealing approaches together as "deterministic" might not really make that much sense. Some of the "deterministic" approaches that have done well have involved fine tweaking of parameters so are like annealing in that regard.

As far as I know, however, only annealing-based submissions have so far involved tossing a coin. That was my criterion for being (non-)deterministic.

Also, as far as I know, no one has hand-optimized the results after running their program even though that's perfectly acceptable under the rules.

Bob Hutchison on Nov. 30, 2005:

It seems to me that any of the SA (and variants), GA, or some of the stranger general purpose heuristics will at some point resort to a random number generator. Even Lagrange relaxation techniques will eventually toss a coin. I suppose, at a stretch, you might say that tossing a coin to break a tie is somehow, at least seems to be, qualitatively different that using randomness as an integral part of the decision process in the heuristic. But I don't know about that, it might be illusion (and based on some work I did a decade ago I'd be thinking illusion, but that's just me).

Anyway, the phrase 'toss a coin' is often used in the operations research literature to mean break a tie randomly. It turns out that the heuristics get in weird traps if you don't actually use a random number (i.e. the same tie may come up more than once -- and they for sure do in Lagrange relaxation techniques -- and if you don't 'explore' the ties you may get a less than optimal local minima).

But I don't do that stuff anymore :-)

BTW, how did that comment I made get in there twice. I hope I didn't do anything stupid.

Add a Comment

Created: Nov. 29, 2005
Last Modified: Nov. 29, 2005
Author: jtauber