/***********************************************************************
* Adaptive Simulated Annealing (ASA)
* Lester Ingber <ingber@ingber.com>
* Copyright (c) 1993-2007 Lester Ingber.  All Rights Reserved.
* The ASA-LICENSE file must be included with ASA code.
***********************************************************************/

$Id: ASA-NOTES,v 26.23 2007/01/31 20:13:25 ingber Exp ingber $

========================================================================
			CONTENTS (Search on these words)

NOTE:  I have attempted to specifically date sections where some
updates in other files might give conflicting references.

@@SOME USER FRIENDLY ISSUES
	@@Original ASA Comments
	@@Some Reflections After a Score of Years
@@SOME SA/ASA COMMENTS
	@@General Comments
	@@Parameter-Temperature Scales
	@@Equality Constraints
	@@Number of Generated States Required
@@TUNING FOR SOME SYSTEMS
	@@Tuning
	@@Some Tuning Guidelines
	@@Quenching
	@@Options for Large Spaces
	@@Shunting to Local Codes
	@@Judging Importance-Sampling
@@SPECIAL COMPILATIONS/CODE
	@@Tsallis Statistics
	@@Dynamic Hill Climbing (DHC)
	@@FORTRAN Issues
	@@Specific Machines/Architectures

========================================================================
========================================================================
@@SOME USER FRIENDLY ISSUES

========================================================================
	@@Original ASA Comments

I do not give out any info I receive from users unless they
specifically permit me to do so; that way many people do ask questions
and give me info/feedback on the code they might not give otherwise.
In order to get maximum feedback without unduly bothering researchers,
I also have decided not to make the ASA_list an open forum, but rather
an efficient moderated medium to gather information.

While I agree the code should become more user friendly, my first
priority for the time I have is to make the code more powerful.  I
figure that such algorithms are usually most useful only for really
hard problems, and if a group can't enough help from me via e-mail,
well then they might have to consult an expert.  I think the best
answer is to someday get someone to work to produce a graphical user
interface, embedding knowledge gained by helping many people, into some
menu-driven program that can guide a user at various stages of the
search.

In ASA, I have broken out all user OPTIONS into plain view.  Many of
these are counterparts to parameters "hidden" in other codes.  The
downside of having this control is that it can be bewildering at
first.  The upside is that people have been able to solve hard problems
they could not solve any other way.

The easiest way for many users to quickly use ASA likely is to invoke
the COST_FILE OPTIONS (the default), illustrated in the section Use of
COST_FILE on Shubert Problem below.  The ASA-README files give further
instructions on alternative ways of compiling the code.

========================================================================
	@@Some Reflections After a Score of Years

In response to:

Andreas Schuldei 9/25/2006 6:55 AM:
> Hi!
> 
> I used your ASA code about 10-6 years ago with good results and
> want to thank you for providing it.
> 
> however even back then i noticed that it was in urgent need of a
> good refactoration. 
> 
> http://en.wikipedia.org/wiki/Refactor
> 
> I encourage you to go over your code and split it up in more
> readable chunks. todays compilers are pretty good at optimizing
> the result so it will not impact your programs performance.
> 
> In the meantime i also became more involved in free software. I
> think you would get more contributions (e.g. doing this
> refactoration) from other people if you used the GPL as a
> license. 
> 
> Again, thank you very much for your excellt program.
> 
> /andreas

Andreas:

Hi.

I agree about the refactoration, but I don't agree about the GPL license:

When I first wrote the code it was in broken into multiple files which
were easy to take care of.  I made the decision, which feedback has
shown to be a good one, to make the code look less formidable to many
users by aggregating the code into just a few files.   The code is used
widely across many disciplines, but often by expert people or groups
without computer science skills, and often tuning can be accomplished by
tweaking the parameter file and not having to deal with the .c files
very much.

Even if I choose to keep just a few files, I just do not have the time
to rewrite the code into better code similar to how I write code now,
20 years later (I first wrote the VFSR code in 1987).  However, for me
at least, the structure of the code makes it very easy to maintain, and
I been able to be responsive to any major changes that might come up.
The ASA-CHANGES files reflects this.

I have led teams of extremely bright and competent math-physics and
computer-science people in several disciplines over the years, and I
have also seen how code that may be written in exemplary languages,
whether C, Java, C++, python, etc., nonetheless can be rotten to
maintain if it is not written in a "functional" manner that better
reflects the underlying algebra or physical process, e.g., as most
people would program in an algebraic language like Macsyma/Maxima,
Maple, etc.  In many of these projects, we had no problem using ASA.
This does not excuse the a lot of the clumsy writing in ASA, but it does
reflect on the difference between code that is just well-written but not
flexible and robust to maintain.

By now, ASA represents a lot of feedback from thousands of users.  A
major strength of the code is that it has well over 100 tuning OPTIONS,
albeit in many case only a few are usually required.  This is the nature
of sampling algorithms, and I have broken our all such code-specific
parameters into a top-level meta-language that is easy for an end-user
to handle.  Other very good sampling algorithms do not give such robust
tuning, and too often do not work on some complex systems for some users
just for this reason.  This also has added a lot of weight to the code,
but since most of these ASA OPTIONS are chosen at pre-compile time, this
does not affect the executables in typical use.  I have had at least
half a dozen exceptional coders start to rewrite the code into another
language, e.g., C++, Java, Matlab, etc., but they gave up when faced
with integrating all the ASA OPTIONS.  (There is no way I could
influence them to start or stop such projects.)  I think all these
OPTIONS are indeed necessary for such a generic code.

Re the GPL license, I instead chose a Berkeley UNIX-type license.  I
felt and still feel, similar to many other people who make code
available at no charge to others, that the GPL license is just too
cumbersome and onerous.  I have made my code available at no charge to
anyone or any company, subject to very simple terms.  If some user
contributions do not quite fit into the code per se, I have put or
referenced their contributions into the asa_contrib.txt or ASA-NOTES
files.  I do not think this has stymied people from contributing to the
code.

I very much appreciate your writing to me.

Lester

========================================================================
========================================================================
@@SOME SA/ASA COMMENTS

========================================================================
	@@General Comments

"Adaptive" in Adaptive Simulated Annealing refers to adaptive options
available to a user to tune the ASA algorithm to optimize the code for
applications to specific systems.  While the default options may
suffice for many applications, this is not intended to imply that the
code will automatically adaptively seek the best tuning options.  (The
SELF_OPTIMIZE OPTIONS theoretically may do well in some cases to
automate this, but it likely is too CPU expensive.)  Rather, the
intention is to recognize that nonlinear systems typically are quite
non-typical, and such tuning is often essential as part of an
interaction between the user and the system as knowledge of the system
is gained by successive stages of applying the algorithm.  The section
Efficiency Versus Necessity in the ASA-README also discusses this.

Simulated annealing (SA) algorithms vary in how fast the temperature
schedule can be implemented to satisfy a (weakly) ergodic search, to
reasonably statistically sample the parameter space.  The Boltzmann SA
algorithm (BA) requires a very slow schedule, so people usually "cheat"
and apply a faster schedule, thereby in practice defining "simulated
quenching" (SQ) rather than SA.  This voids the SA proof, and while it
may work well on some problems, as might some other "greedy"
algorithms, making it a valuable tool on such occasions, it likely
will fail on some other problems that would yield to the proven
temperature schedule.

There are SA algorithms that are proven to statistically sample the
space effectively that are exponentially (fast SA, FSA) and also
exponentially exponentially (adaptive SA, ASA) faster than the standard
BA algorithm.  This usually implies that the rejection rate is higher
to accept new points, but in practice this rate increases only modestly
across problems relative to BA, thus truly taking advantage of the
faster sampling temperature.  Of course, SQ can also be applied to
these SA algorithms, and such accelerations can be useful in large
dimensional spaces.

I think the bottom line is this:  If you don't know anything about your
system, and it is very important to find the global optimal point, then
using SA at least gives you some statistical guarantee that you will
not get stuck at a local optimal point.  This also requires some common
sense.  If you start out a very low temperature, or some equivalent set
of such algorithm parameters, you may make it impractical to get a fit
within any practical time or within practical machine precision.  Thus,
even here, there still may be some "art" required to find a decent set
of starting conditions.  I think this is the nature of nonlinear
systems, that they are often so different, that defies using algorithms
as "black boxes" as can be done for (quasi-)linear systems.

ASA can often do very well in the beginning stages of broad search, as
well as in the end stages of sharpening the precision of the final
answer.  A good way to see this is to plot the log of the number of
generated points versus the log of the value of the cost function or
"cost procedure."  However, some problems do not show such a clean
division, and then ASA can be even more important.

A good way of including constraints is to test them in your cost
function and return a non-valid flag as soon as any are not satisfied.
Then the penalty part of your cost function is not exactly part of the
cost function being minimized.  This often is more efficient than
including penalty functions explicitly as part of the cost function,
which works well with ASA.

Concerning reannealing in ASA, if too radical a reannealing procedure
is taken, i.e., much more radical than the linear rescaling in the
present code, then this can be self-defeating.  For example, consider
how difficult/impossible it might be to say that a given dimension is
the most sensitive one early in a search, when it might turn out to be
the least sensitive one in the end stages of the search.  So, some
compromise seems to be to take a regularly selected moderate approach,
and I chose the acceptance criteria (every set number of accepted
points) to be better at gauging the changing sensitivity of the search
than the generating criteria (number of generated points).

The parameter temperatures determine the "effective" width of the ASA
distribution to select new generated points about the current optimal
point.  When used in conjunction with the proper annealing schedule,
this ensures a statistical covering of the parameter space, as given by
the simple proof in the ASA papers.  (See the section Judging
Importance-Sampling below for more info.)

Most discussions on SA focus on the cost temperature, and the analogy
to metallic cooling/annealing.  They do not properly address the issue
of the annealing schedule, and the necessity of satisfying the guide to
statistical ergodicity.  If they neglect this, then their resulting
algorithm is really "just" another quasi-local algorithm, which belongs
in the class I call "simulated quenching" (SQ), without establishing
any statistical certainty of being able to find the global optimal
point.  That said, SQ techniques still can be very useful and
powerful.

In ASA, one of the most useful control for some people has been
USER_COST_SCHEDULE, which permits just about anything for the cost
temp.  This is possible since the ASA proof of proper sampling just
concerns the parameter temperatures (within reason, as discussed in the
docs and as is sometimes obvious--if you start too focussed, it may
take until your next generation to sample the space, etc.)

You can use an alternative to the Boltzmann using
USER_ACCEPTANCE_TEST.  This can be useful in cases where the form of
your cost function varies with scale, e.g., changing from a power at
coarse scales to an exponential at finer scales.  In the
ASA_TEMPLATE_SAMPLE template in asa_usr.c there is an example of a class
of such modifications.  Note that when USER_ACCEPTANCE_TEST is TRUE,
you also have the option of calculating the acceptance criteria within