http://www.npac.syr.edu/users/paulc/lectures/montecarlo/node148.html


Like simulated annealing but faster. The idea is to ignore the physical analogy. All we need is a way to approach ideal solutions, without getting stuck in local minima.

The Metropolis schedule (as it is known) cools like a real crystal, it starts off fast and then gets slower and slower, till it's creeping along for little gain. The 'temperature' affects the amount of perturbation.

For my version, instead I went back to the specification. Right, hillclimbing, well that's easy. Randomly perturb the network a little bit and see if it is 'better'. I actually perturb my network in the direction I know I want to go. This corresponds to following the local slope (of the partial derivative) at any particular node. This is usually known (for these problems).

Then there's jumping out of local minima. I allow a solution that is worse than the last one, some of the time, though I save the best solution for later.

Then there's the scanning of the solution space. I run the simulation lots of times from random (but satisfying the constraints) initial positions.

Guess what? Better results quicker. Totally annihilated the best genetic algorithms for both speed and accuracy. Also better results than Metropolis (or ordinary quenching) since I could run a million simulations in the same time it took to run four or five. It also beat hill-climbing-only algorithms and a number of other quenching algorithms (including the ones in the referred paper).

The particular problem-space I was looking at (smooth functions of many variables with validity constraints) turns out to be the typical one. Genetic algorithms have a problem with constrained networks.

If you watch it work. It tends to zoom into the big minima, then creeps about, very occasionally updating its 'best' value. Hillclimbing is biased to be around 90% of processing. Reversing about 10%. The amount of perturbation is reduced according to need. If the 'best' has remained 'best' for some time (say 10 attempts), then reduce the 'temperature'. If the 'best' has remained 'best' for, say 1000 attempts, with near-zero perturbation, then take the result and start a new run. I usually do a tiny incremental hill-climb at the end, on the best solution, just in case it isn't in its local minimum.

--RichardHenderson.

Have you tried the simpler approach of just climbing hills until convergence, starting in random places? 
(Or, probably better: hill-climb for some modest number
of iterations, starting in random places; choose the
best result you see and then hill-climb to convergence.)

''Yup, that's what I meant by 'It also beat hill-climbing-only'. I just set the reversal proportion to zero. Simple hill-climbers are very dumb. They also tend to follow very predictable paths which can structure them away from good solutions.''

One difficulty with constrained optimization problems
that you obviously don't have is that it can be rather
hard just ''generating'' random feasible points. (The
constraints may cut off most of the search space.)

''I agree with you. Finding initial good points can be a real pain. Constraints tend to be hard or soft. Soft constraints are range limitations on the variables. Hard constraints specify how the values must relate. So far I have got away with initially ignoring the soft constraints and successively constraining the system by adding random values appropriately. In theory, the order in which this is done may make a difference, and sensitive systems tend to blow up. If so, then just use any solution available and allow 100% reversals for a while. The soft constraints will cause rapid convergence since I use a directed perturbation. Out of range values are given high energies, so should only occur as a result of a reversal. If the 'best' solution cannot settle down to an in-range value then it may not exist. You can get a 'nearest approach' though. I think all algorithms suffer from this. It is exactly why naive genetic algorithms are so poor in this class of problem. They fall off the equation and can't get back on it easily.''