🚀 go-pugleaf

In article <36404@sdcc12.ucsd.edu> whart@cs.ucsd.edu (Bill Hart) writes:
>andrew@rentec.com (Andrew Mullhaupt) writes:
>
>> You can transform
>>any GA into SA by choosing a funny configuration space topology and annealing
>>schedule

>I do not believe that you can make the transformations between GA's and
>SA's that you indicate.  To transform the GA to an SA, you must first
>note that the GA does not have an annealling aspect which forces it to
>converge.  Any convergence in the GA is forced by the dynamics of
>selection and cross-over.

You can implement the selection in the schedule, and in the definition
of the energy function. Selection is a survival probability, after all.

> Second, I assume that the 'funny
>configuration space topology' would include the mutation and cross-over
>points into the neighborhood used in SA. 

More or less, yes.

>Unfortunately, the
>set of possible cross-over points is dependent on the current population.
>There is no such dependency in SA.  In SA, the neighborhood structure
>is fixed.

Yeah, but it is in GA as well. Suppose for my configuration space for SA
I take a space which comes from putting the "right topology" on finite
sets of the GA "critters". In other words GA is a Markov process which
acts on finite populations of "critters". If it "solves" the problem
(with probability 1) then I assert that it is ergodic. (Else it might
miss an optimum). Now I know that SA will find the optimum with
probability 1, so for problems which GA can do, SA can do too...

You seem to be thinking in terms of the SA having some strong resemblance
to the GA formulation of the problem. I never claimed that.

>It is not clear to me that GA and SA solve the same class of problems.
>Would you explain your reasoning?  The comparisons I have seen between
>GA's and SA's have shown different relative performances on different
>problems. 

Mainly because you're comparing a specific SA and GA for the same problem.
In cases where the GA which occurs to you is close to optimal, then the
SA which you usually pick is sub-optimal. This doesn't mean that there
isn't a good SA for the problem, usually just that you didn't think of it.

Another important point to keep in mind when bashing SA is that most people
do not take advantage of using properly adapted statistical neighborhoods
for the moves. Ingber and Rosen have shown how by controlling the tails
of the move distribution the performance of SA can be improved by orders
of magnitude.

Both techniques are still "exotic" optimizations, and I think we ought
to wait a little longer before we pass judgement on either one. Keep
in mind that a lot of which one "wins" is machine dependent, implementor
dependent, and (dare we say) dependent on the particular axe that the
experimenter is grinding...

Later,
Andrew Mullhaupt