Quote:Original post by Anonymous Poster
Give simulated annealing a try. I think you will find it easier to implement than a GA. There should be plenty of papers available to point you in the right direction. I remember a lecture given by Rob Rutenbar @ CMU where they had a video of one of their place and route systems solving the exact problem you describe.

Yup, simulated annealing will be much easier to implement, considering its nothing more than a probabilistic hill climber. And of course, like every other probabilistic hill climber, you run into the nasty cooling schedule issue. What most research on simulated annealingdon't show half the time is all the various cooling schedules that are tested before they hit on one that does better. Of course, its the same with GAs as well. So, in the end, you win some and you lose some. It all boils down to heuristics, parameter settings, and the various choices you make during implementation. The crazy world of optimization.

Heck, even hill climbers have various issues involved, like do we do probabilistic restarts or do we do min conflict or something else.

I'm not sure Simulated Annealing (or any other hill climber, including gradient descent and genetic algorithms) will be usefull for this type of problem as the search space isnt in any way smooth. In effect, theres no hills to climb.

To be specific, it is not simple to define a loss function which smoothly indicates how close a solution is to being perfect/acceptable. The obvious loss function here only indicates to what degree the constraints arent satisifed.

In some problems the two values as I described would be one and the same, but for other problems (especialy this one), the number of constraint violations is not an inidcation of how close the solution is to being the correct one.

To be really specific, a solution with 1 peice out of order and 1 constraint violation is indistinguishable from a solution with 10 pieces out of order and 1 constraint violation. The loss function in both cases will indicate 1 constraint violation.

- Joseph Koss

Joseph,

This is still an area of active research and investment: place and route in VLSI, truck/cargo container packing, etcetera. Regardless of the approach taken, whether it is an exhaustive search of the design space, a probablistic search of the design space, or an integer/linear programming approach, a cost function needs to be defined and constraints need to be handled (implicitly or explicitly).

For what is worth, GAs, SA, monte carlo, simple gradient methods with restarts, etc. are all provably identical. If the code is well written it shouldn't be too hard to change the optimizer.


Phil

VLSI, container packing, scheduling, etc. are all problems for which there are clearly functions to minimize (circuit length, space, time, etc.). In these problems, a solution that is not optimal is still usually good enough. For a puzzle, being close to the solution is not good enough, since we actually want the solution. The goal is not to minimize a cost function, it is to find a valid solution.