ADAPTIVE SIMULATED ANNEALING (ASA) (C) Lester Ingber ingber@ingber.com ingber@alumni.caltech.edu Adaptive Simulated Annealing (ASA) is a C-language code developed to statistically find the best global fit of a nonlinear constrained non-convex cost-function over a D-dimensional space. This algorithm permits an annealing schedule for "temperature" T decreasing exponentially in annealing-time k, T = T_0 exp(-c k^1/D). The introduction of re-annealing also permits adaptation to changing sensitivities in the multi-dimensional parameter-space. This annealing schedule is faster than fast Cauchy annealing, where T = T_0/k, and much faster than Boltzmann annealing, where T = T_0/ln k. ASA has over 100 OPTIONS to provide robust tuning over many classes of nonlinear stochastic systems. ----------- /****************************************************************** * Adaptive Simulated Annealing (ASA) * Lester Ingber * Copyright (C) 1987-2008 Lester Ingber. All Rights Reserved. * The ASA-LICENSE file must be included with ASA code. ******************************************************************/ $Id: ASA-README.ms,v 26.30 2008/04/24 20:05:23 ingber Exp ingber $ Adaptive Simulated Annealing (ASA) Lester Ingber 1. ASA-LICENSE This Adaptive Simulated Annealing (ASA) code is being made available under conditions specified in the ASA-LICENSE file that comes with this code, and is owned by Lester Ingber[1]. Reference is properly given to the internet archive that first published the code. Please read the copy of the public ASA-LICENSE contained in the ASA directory. Its intent is to protect the integrity of the algorithm, promote widespread usage, and require reference to current source code. The ASA-LICENSE is so short it is repeated here: Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met: CONDITIONS 1. Redistributions of ASA source code must retain the above copyright notice, this list of conditions, and the following disclaimer. 2. Redistributions in binary form must contain the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution. 3. All modifications to the source code must be clearly marked as such. Binary redistributions based on modified source code must be clearly marked as modified versions in the documentation and/or other materials provided with the distribution. 4. Notice must be given of the location of the availability of the unmodified current source code, e.g., http://www.ingber.com/ or ftp://ftp.ingber.com in the documentation and/or other materials provided with the distribution. ASA also is listed at http://alumni.caltech.edu/~ingber http://asa-caltech.sourceforge.net 5. All advertising and published materials mentioning features or use of this software must display the following acknowledgment: "This product includes software developed by Lester Ingber and other contributors." 6. The name of Lester Ingber may not be used to endorse or promote products derived from this software without specific prior written permission. - 1 - Adaptive Simulated Annealing (ASA) Lester Ingber DISCLAIMER This software is provided by Lester Ingber and contributors "as is" and any expressed or implied warranties, including, but not limited to, the implied warranties of merchantability and fitness for a particular purpose are disclaimed. In no event shall Lester Ingber or contributors be liable for any direct, indirect, incidental, special, exemplary, or consequential damages (including, but not limited to, procurement of substitute goods or services; loss of use, data, or profits; or business interruption) however caused and on any theory of liability, whether in contract, strict liability, or tort (including negligence or otherwise) arising in any way out of the use of this software, even if advised of the possibility of such damage. 2. Lester Ingber Research Terms of Use Lester Ingber Research (LIR) develops projects in several areas of expertise documented in the ingber.com InterNet archive, e.g., this ASA code. Information on terms of use is in the file http://www.ingber.com/ingber_terms.html under WWW or ftp://ftp.ingber.com/ingber_terms.txt under FTP. There is no charge for downloading and using codes or files in the ingber.com archive. In general, I have retained all rights such as copyrights to these codes and files, but they may be freely used by any person or group independent of affiliations, e.g., independent of academic or commercial affiliation. Limited help assisting people with queries on my codes and papers is available only by electronic mail correspondence. Sorry, I cannot mail out hardcopies of code or papers. 3. Documentation Note that most URL references to files in the ingber.com archive have the same WWW and FTP paths under the main http://www.ingber.com/ directory (all .html, .gif and .jpg files are in or under the http://www.ingber.com/ directory). 3.1. Table of Contents/Index A compilation of the three levels of headers with their page numbers may be used as a Table of Contents placed after the first title page (as is done for ASA-README.ps, ASA-README.pdf and ASA-README.html below), or left at the end for quick reference (as is done for ASA-README.txt below). 3.2. ASA-README.ms and ASA-README The ASA-README.ms file is used to prepare other documentation files using UNIX(R) MS macros. - 2 - Adaptive Simulated Annealing (ASA) Lester Ingber 3.2.1. ASA-README.txt and ASA-README+.txt ASA-README.txt is an ASCII file that can be previewed on your screen or sent to an ASCII lineprinter. ASA-README+.txt is ASA-README.txt without any filters to strip off underlining and bold enhancements. 3.2.2. asa.[13nl] Manpage The ASA-README.txt or ASA-README+.txt file can be copied to a file named asa.[l3], and asa.[13] can be installed as MANPATH/cat1/asa.1 or MANPATH/cat3/asa.3, where MANPATH is the place your man directory is located. If you do not have any cat[13] directories on your system, then installing a copy of ASA-README.txt or ASA-README+.txt as MANPATH/man[13nl]/asa.[13nl], choosing one of the suffixes in [13nl] for your choice of directory and asa file name, should work fine on most machines. However, passing this asa.[13nl] through man may strip out additional "back-slash" characters, leading to missing words or unintended formatting. If such a file looks strange, compare it to the raw ASA-README.ms file to determine the true intended content. You likely can avoid some further undesirable formatting by man by placing '.nf' on the first line of this file. 3.2.3. ASA-README.ps and ASA-README.pdf ASA-README.ps is a PostScript(R) formatted file which may be previewed on your screen if you have the proper software, or it may be sent to a PostScript(R) printer to produce hardcopy. A PDF version ASA-README.pdf is prepared from ASA-README.ps. 3.2.4. ASA-README.html ASA-README.html is an HTML version which enables easier access to subsections of this file. Cross-references have been kept local to this file, so you may view it under a local browser if you download the HTML source file. The background image file asa_back.jpg referenced in ASA-README.html can be downloaded as http://www.ingber.com/asa_back.jpg from the ASA archive. 3.3. Additional Documentation ASA-CHANGES is a terse record of major changes made in the ASA code. It has three sections, CHANGES, CONTRIBUTORS, and VERSION DATES. ASA-NOTES is a collection of recommended enhancements, modifications, comments, caveats, etc., that might be of interest. There is a CONTENTS of sections headers that can be used to search on topics in your browser or editor. - 3 - Adaptive Simulated Annealing (ASA) Lester Ingber There are three files in the ASA archive that should be considered as appendices to the ASA-NOTES file: http://www.ingber.com/asa_contrib.txt, http://www.ingber.com/asa_examples.txt, and http://www.ingber.com/asa_papers.html under WWW. The file http://www.ingber.com/asa_contrib.txt in the ASA archive contains some code contributed by users. For example, references are giving to MATLAB and RLaB gateway routines to ASA (which include many important parts of the ASA user module), and to function support for ASA_PARALLEL. There is a CONTENTS of sections headers that can be used to search on topics in your browser or editor. In this file I have included the first 1987 VFSR code, the precursor to the ASA code, as used on a specific project, including the RATFOR vfsr.r and vfsr_com.r code, subsequently compiled into FORTRAN to run on a Lawrence Livermore supercomputer. I do not support this old RATFOR code. The file http://www.ingber.com/asa_examples.txt in the ASA archive contains some example problems using ASA. There is a CONTENTS of sections headers that can be used to search on topics in your browser or editor. This file contains some "toy" problems optimized using ASA, which can provide immediate examples on how you can optimize your own problem. The file http://www.ingber.com/asa_papers.html is an addendum to the ASA-NOTES file in the ASA code, containing references to some patents and papers using ASA or its precursor VFSR. The file asa_new.txt in the ASA archive is a list of major changes in ASA. The files ASA-README.txt, ASA-README.ps and ASA-README.pdf included with the code also are available independently as http://www.ingber.com/ASA-README.txt, http://www.ingber.com/ASA-README.ps.gz, http://www.ingber.com/ASA-README.html, http://www.ingber.com/ASA-README.pdf. There is a set of ASA_TEMPLATE's available in the ASA-Makefile and in the user module (some also in the asa module) to illustrate use of particular OPTIONS, as listed under ASA_TEMPLATE below. You can search on these ASA_TEMPLATE's in your browser or editor to see how these are implemented. Note that some OPTIONS require your input, as described below, and code may fail until you add your own code. Once you have determined the most common set of DEFINE_OPTIONS you are likely to use, you might place these in your own TEMPLATE at the top of asa_usr_asa.h at the location specified, e.g., #if MY_TEMPLATE /* MY_TEMPLATE_asa_user */ /* you can add your own set of #define here */ #define ... TRUE #define ... 100 #endif - 4 - Adaptive Simulated Annealing (ASA) Lester Ingber See http://www.ingber.com/utils_file_formats.txt for some links to information on gzip, PostScript, PDF, tar, and shar utilities. The file utils_code.txt in that directory gives short statements describing these files, which may be accessed as http://www.ingber.com/utils_code.html under WWW. 3.4. Use of Documentation for Tuning I'm often asked how how I can help someone tune their system, and they send me their cost function or a list of the ASA OPTIONS they are using. Most often, the best help I can provide is based on my own experience that nonlinear systems typically are non-typical. In practice, that means that trying to figure out the nature of the cost function under sampling in order to tune ASA (or likely to similarly tune a hard problem under any sampling algorithm), by examining just the cost function, likely will not be as productive as generating more intermediate printout, e.g., setting ASA_PRINT_MORE to TRUE, and looking at this output as a "grey box" of insight into your optimization problem. Larger files with more information is provided by setting ASA_PIPE_FILE to TRUE. Treat the output of ASA as a simulation in the ASA parameter space, which usually is quite a different space than the variable space of your system. For example, you should be able to see where and how your solution might be getting stuck in a local minima for a very long time, or where the last saved state is still fluctuating across a wide portion of your state space. These observations should suggest how you might try speeding up or slowing down annealing/quenching of the parameter space and/or tightening or loosening the acceptance criteria at different stages by modifying the OPTIONS, e.g., starting with the OPTIONS that can be easily adjusted using the asa_opt file. The ASA-NOTES file that comes with the ASA code provides some guidelines for tuning that may provide some insights, especially the section Some Tuning Guidelines. An especially important guide is to examine the output of ASA at several stages of sampling, to see if changes in parameter and temperatures are reasonably correlated to changes in the cost function. Examples of useful OPTIONS that often give quick changes in tuning in some "toy" problems are in the file http://www.ingber.com/asa_examples.txt under WWW. Some of the reprint files of published papers in the ingber.com provide other examples in harder systems, and perhaps you might find some examples of harder systems using ASA similar to your own in http://www.ingber.com/asa_papers.html under WWW. This is the best way to add some Art to the Science of annealing. While the upside of using ASA is that is has many OPTIONS available for tuning, derived in large part from feedback from many users over many years, making it extremely robust across many systems, the downside is that the learning curve can be steep especially if the default settings or simple tweaking in asa_opt do not work very well for your particular system, and you then must turn to using more ASA OPTIONS. Most of these OPTIONS have useful guides in the - 5 - Adaptive Simulated Annealing (ASA) Lester Ingber ASA_TEMPLATEs in asa_usr.c, as well as being documented here. If you really get stuck, you may consider working with someone else who already has climbed this learning curve and whose experience might offer quick help. Tuning is an essential aspect of any sampling algorithm if it is to be applied to many classes of systems. It just doesn't make sense to compare sampling algorithms unless you are prepared to properly tune each algorithm to each system being optimized or sampled. 4. Availability of ASA Code 4.1. ingber.com The latest Adaptive Simulated Annealing (ASA) code and some related papers can be accessed from the home page http://www.ingber.com/ under WWW, or retrieved via anonymous ftp from ftp.ingber.com. Interactively [brackets signify machine prompts]: [your_machine%] ftp ftp.ingber.com [Name (...):] anonymous [Password:] your_e-mail_address [ftp>] binary [ftp>] ls [ftp>] get file_of_interest [ftp>] quit The home page http://www.ingber.com/ under WWW, and the ASCII version 00index.txt, contain an index of the other files. The latest version of ASA, ASA-x.y (x and y are version numbers), can be obtained in two formats: http://www.ingber.com/ASA.tar.gz and http://www.ingber.com/ASA.zip. The tar'd versions is compressed in gzip format, and ASA.tar.gz. In the zip'd version, ASA.zip, all files have been processed for DOS format. Patches ASA-diff-x1.y1-x2.y2 up to the present version can be prepared if a good case for doing so is presented, e.g. to facilitate updating your own modified codes. These may be concatenated as required before applying. If you require a specific patch, contact ingber@ingber.com. 4.2. Electronic Mail If you do not have WWW or FTP access, get the Guide to Offline Internet Access, returned by sending an e-mail to mail-server@rtfm.mit.edu with only the words "send usenet/news.answers/internet-services/access-via-email" in the body of the message. The guide gives information on using e-mail to access just about all InterNet information and documents. You will receive the information in utils_access-via-email.txt in the ASA archive. - 6 - Adaptive Simulated Annealing (ASA) Lester Ingber 5. Background 5.1. Context Too often the management of complex systems is ill-served by not utilizing the best tools available. For example, requirements set by decision-makers often are not formulated in the same language as constructs formulated by powerful mathematical formalisms, and so the products of analyses are not properly or maximally utilized, even if and when they come close to faithfully representing the powerful intuitions they are supposed to model. In turn, even powerful mathematical constructs are ill-served, especially when dealing with multivariate nonlinear complex systems, when these formalisms are butchered into quasi-linear approximations to satisfy constraints of numerical algorithms familiar to particular analysts, but which tend to destroy the power of the intuitive constructs developed by decision-makers. In order to deal with fitting parameters or exploring sensitivities of variables, as models of systems have become more sophisticated in describing complex behavior, it has become increasingly important to retain and respect the nonlinearities inherent in these models, as they are indeed present in the complex systems they model. ASA can help to handle these fits of nonlinear models of real-world data. It helps to visualize the problems presented by such complex systems as a geographical terrain. For example, consider a mountain range, with two "parameters," e.g., along the North-South and East-West directions. We wish to find the lowest valley in this terrain. ASA approaches this problem similar to using a bouncing ball that can bounce over mountains from valley to valley. We start at a high "temperature," where the temperature is an ASA parameter that mimics the effect of a fast moving particle in a hot object like a hot molten metal, thereby permitting the ball to make very high bounces and being able to bounce over any mountain to access any valley, given enough bounces. As the temperature is made relatively colder, the ball cannot bounce so high, and it also can settle to become trapped in relatively smaller ranges of valleys. We imagine that our mountain range is aptly described by a "cost function." We define probability distributions of the two directional parameters, called generating distributions since they generate possible valleys or states we are to explore. We define another distribution, called the acceptance distribution, which depends on the difference of cost functions of the present generated valley we are to explore and the last saved lowest valley. The acceptance distribution decides probabilistically whether to stay in a new lower valley or to bounce out of it. All the generating and acceptance distributions depend on temperatures. - 7 - Adaptive Simulated Annealing (ASA) Lester Ingber The ASA code was first developed in 1987 as Very Fast Simulated Reannealing (VFSR) to deal with the necessity of performing adaptive global optimization on multivariate nonlinear stochastic systems[2]. The first published use of VFSR for a complex systems was in combat analysis, using a model of combat first developed in 1986, and then applied to exercise and simulation data in a series of papers that spanned 1988-1993[3]. The first applications to combat analysis used code written in RATFOR and converted into FORTRAN. Other applications since then have used new code written in C. (The ASA-NOTES file contains some comments on interfacing ASA with FORTRAN codes.) In November 1992, the VFSR C-code was rewritten, e.g., changing to the use of long descriptive names, and made publicly available as version 6.35 under a "copyleft" GNU General Public License (GPL)[4], and copies were placed in NETLIB and STATLIB. Beginning in January 93, many adaptive features were developed, largely in response to users' requests, leading to this ASA code. Until 1996, ASA was located at http://www.alumni.caltech.edu/~ingber/. Pointers were placed in NETLIB and STATLIB to this location. ASA versions 1.1 through 5.13 retained the GPL, but subsequent versions through this one have incorporated a simpler ASA-LICENSE, based in part on a University of California license, that protects the integrity of the algorithm, promotes widespread usage, and requires reference to current source code. As the archive grew, more room and maintenance was required, and in February 1996 the site was moved to the present ingber.com location. Pointers were placed in the Caltech site to this location. http://alumni.caltech.edu/~ingber is the mirror homepage for the ASA site. Beginning in January 2007, ASA also is listed at http://asa-caltech.sourceforge.net (http://asa- caltech.sf.net). ASA has been examined in the context of a review of methods of simulated annealing using annealing versus quenching (faster temperature schedules than permitted by basic heuristic proof of ergodicity)[5]. A paper has indicated how this technique can be enhanced by combining it with some other powerful algorithms, e.g., to produce an algorithm for parallel computation[6]. ASA is now used world-wide across many disciplines[7,8,9,10], including specific disciplines such as finance[11,12,13,14,15,16], neuroscience[17,18,19,20,21], and combat analyses[22,23,24,25,26,27]. Some papers illustrate the combined use of ASA for optimization and sampling[28,29,30,31]. The http://www.ingber.com/asa_papers.html file in the ASA archive contains references to some patents and papers using ASA and VFSR. 5.2. Outline of ASA Algorithm Details of the ASA algorithm are best obtained from the published papers. There are three parts to its basic structure. - 8 - Adaptive Simulated Annealing (ASA) Lester Ingber 5.2.1. Generating Probability Density Function In a D-dimensional parameter space with parameters p^i having ranges [A_i, B_i], about the k'th last saved point (e.g, a local optima), p_k^i, a new point is generated using a distribution defined by the product of distributions for each parameter, g^i(y^i; T_i), in terms of random variables y^i in [-1, 1], where p_k+1^i = p_k^i + y^i(B_i - A_i), and "temperatures" T_i, g^i(y^i; T_i) = 1/[2(|y^i| + T_i)(1 + 1/T_i)]. The DEFINE_OPTIONS USER_GENERATING_FUNCTION permits using an alternative to this ASA distribution function. 5.2.2. Acceptance Probability Density Function The cost functions, C(p_k+1) - C(p_k), are compared using a uniform random generator, U in [0, 1), in a "Boltzmann" test: If exp[-(C(p_k+1) - C(p_k))/T_cost] > U, where T_cost is the "temperature" used for this test, then the new point is accepted as the new saved point for the next iteration. Otherwise, the last saved point is retained. The DEFINE_OPTIONS USER_ACCEPT_ASYMP_EXP or USER_ACCEPT_THRESHOLD permit using alternatives to this Boltzmann distribution function. 5.2.3. Reannealing Temperature Schedule The annealing schedule for each parameter temperature, T_i, from a starting temperature T_i0, is T_i(k_i) = T_0i exp(-c_i k_i^(1/D)). This is discussed further below. The annealing schedule for the cost temperature is developed similarly to the parameter temperatures. However, the index for reannealing the cost function, k_cost, is determined by the number of accepted points, instead of the number of generated points as used for the parameters. This choice was made because the Boltzmann acceptance criteria uses an exponential distribution which is not as fat-tailed as the ASA distribution used for the parameters. This schedule can be modified using several OPTIONS. In particular, the Pre-Compile DEFINE_OPTIONS USER_COST_SCHEDULE permits quite arbitrary functional modifications for this annealing schedule, and the Pre-Compile DEFINE_OPTIONS As determined by the Program Options selected, the parameter "temperatures" may be periodically adaptively reannealed, or increased relative to their previous values, using their relative first derivatives with respect to the cost function, to guide the search "fairly" among the parameters. As determined by the Program Options selected, the reannealing of the cost temperature resets the scale of the the annealing of the cost acceptance criteria as T_cost(k_cost) = T_0cost exp(-c_cost k_cost^(1/D)). The new T_0cost is taken to be the minimum of the current initial cost - 9 - Adaptive Simulated Annealing (ASA) Lester Ingber temperature and the maximum of the absolute values of the best and last cost functions and their difference. The new k_cost is calculated taking T_cost as the maximum of the current value and the absolute value of the difference between the last and best saved minima of the cost function, constrained not to exceed the current initial cost temperature. This procedure essentially resets the scale of the annealing of the cost temperature within the scale of the current best or last saved minimum. This default algorithm for reannealing the cost temperature, taking advantage of the ASA importance sampling that relates most specifically to the parameter temperatures, while often is quite efficient for some systems, may lead to problems in dwelling too long in local minima for other systems. In such case, the user may also experiment with alternative algorithms effected using the Reanneal_Cost OPTIONS, discussed below. For example, ASA provides an alternative calculation for the cost temperature, when Reanneal_Cost < -1 or > 1, that periodically calculates the initial and current cost temperatures or just the initial cost temperature, resp., as a deviation over a sample of cost functions. These reannealing algorithms can be changed adaptively by the user as described below in the sections USER_REANNEAL_COST and USER_REANNEAL_PARAMETERS. 5.3. Efficiency Versus Necessity ASA is not necessarily an "efficient" code. For example, if you know that your cost function to be optimized is something close to a parabola, then a simple gradient Newton search method most likely would be faster than ASA. ASA is believed to be faster and more robust than other simulated annealing techniques for most complex problems with multiple local optima; again, be careful to note that some problems are best treated by other algorithms. If you do not know much about the structure of your system, and especially if it has complex constraints, and you need to search for a global optimum, then this ASA code is heartily recommended to you. In the context of efficiency and necessity, the user should be alert to recognize that any sampling or optimization program generally should be considered as complementary, not as a substitute, to gaining knowledge of a particular system. Unlike relatively "canned" codes that exist for (quasi-)linear systems, nonlinear systems typically are non-typical. Often some homework must be done to understand the system, and tuning often is required of numerical algorithms such as ASA. For example, while principal component analyses (PCA) often suffices to generate good (quasi-)orthogonal or (quasi-)independent sets of parameters, this is not true for general nonlinear systems. While such innovations as reannealing take good advantage of ASA which offers independent distributions for each parameter, this generally may not be a good substitute for a user-defined front-end, e.g., before the call to asa () or even embedded within the cost_function (), to interpret and define relevant parameters. - 10 - Adaptive Simulated Annealing (ASA) Lester Ingber The ASA-NOTES file contains the sections @@Number of Generated States Required and @@Judging Importance-Sampling, recommending use of log-log plots to extrapolate the number of generated states required to attain a global minimum, possibly as a function of selected OPTIONS. 6. Outline of Use Set up the ASA interface: Your program should be divided into two basic modules. (1) The user calling procedure, containing the cost function to be minimized (or its negative if you require a global maximum), is contained in asa_usr.c, asa_usr.h and asa_usr_cst.c. (2) The ASA optimization procedure, is contained in asa.c and asa.h. The file asa_usr_asa.h contains definitions and macros common to both asa.h and asa_usr.h. Furthermore, there are some options to explore/read below. It is assumed there will be no confusion over the standard uses of the term "parameter" in different contexts, e.g., as an element passed by a subroutine or as a physical coefficient in a cost function. ASA has been run successfully on many machines under many compilers. To check out your own system, you can run `make` (or the equivalent set of commands in the ASA-Makefile), and compare your asa_out and asa_usr_out files to the asa_test_asa and asa_test_usr files, respectively, provided with this code. No attempt was made to optimize any compiler, so that the test runs do not really signify any testing of compilers or architectures; rather they are meant to be used as a guide to determine what you might expect on your own machine. The major sections below describe the compilation procedures, the Program Options available to you to control the code, the use of templates to set up your user module and interface to the asa module, and how to submit bug reports. If you already have your own cost function defined, you can insert it into asa_usr_cst.c. If you wish to insert more OPTIONS, as a quick guide to get started, you can search through asa_usr.c and the ASA-Makefile for all occurrences of "MY_TEMPLATE_" to insert the necessary definitions required to run ASA. If you use both OPTIONS_FILE and OPTIONS_FILE_DATA set to TRUE, then usually most such information can be placed in the asa_opt file, and then only the cost_function () must be inserted. The place to insert the cost_function () is marked by "MY_TEMPLATE_cost." 7. ASA-Makefile/Compilation Procedures The ASA-Makefile is intended to be a template for your own Makefile. For quick use, just copy this file to Makefile, which will be recognized by any standard make tool. The PostScript(R) ASA-README.ps and ASCII ASA-README.txt and ASA-README+.txt files were generated using `make doc`. The - 11 - Adaptive Simulated Annealing (ASA) Lester Ingber ASA-Makefile describes some options for formatting these files differently. Use `make` or `make all` to compile and run asa_run, the executable prepared for the test function. Examine the ASA-Makefile to determine the "clean" options available. Since complex problems by their nature are often quite unique, it is unlikely that the default parameters are just right for your problem. However, experience has shown that if you a priori do not have any reason to determine your own parameters, then you might do just fine using these defaults, and these are recommended as a first-order guess. These defaults can be changed simply by adding to the DEFINE_OPTIONS line in the ASA-Makefile, by passing options on your command line, and by changing structure elements in the user or asa module as described below. Depending on how you integrate ASA into your own user modules, you may wish to modify this ASA-Makefile or at least use some of these options in your own compilation procedures. Note that the ASA-Makefile is just a convenience, not a necessity, to use ASA. E.g., on systems which do not support this utility, you may simply compile the files following the guidelines in the ASA-Makefile, taking care to pass the correct DEFINE_OPTIONS to your compilation commands at your shell prompt. Still another way, albeit not as convenient, is to make the desired changes in the asa_usr_asa.h, and asa.h or asa_usr.h files as required. Since the ASA-Makefile contains comments giving short descriptions of some options, it should be considered as an extension of this documentation file. For convenience, most of this information is repeated below. However, to see how they can be used in compilations, please read through the ASA-Makefile. For example, to run the ASA test problem using the gcc compiler, you could just type at your "%" prompt: % cp ASA-Makefile Makefile % gcc -g -DASA_TEST=TRUE -o asa_run asa_usr.c asa_usr_cst.c asa.c -lm % asa_run If you have defined your own cost function in asa_usr_cst.c or within the "MY_TEMPLATE_" guides in asa_usr.c, then ASA_TEST should be set to FALSE (the default if ASA_TEST is not defined in your compilation lines or in the ASA-Makefile). The code for ASA_TEST=TRUE is given just above these guides as a template to use for your own cost function. The easiest way for many users to quickly use ASA likely is to invoke the COST_FILE, OPTIONS_FILE, and OPTIONS_FILE_DATA OPTIONS (the default), using the files asa_usr_cst.c and asa_opt as templates. This is further described below and illustrated in the http://www.ingber.com/asa_examples.txt file in the section Use of COST_FILE on Shubert Problem. - 12 - Adaptive Simulated Annealing (ASA) Lester Ingber 7.1. DLL ASA-Makefile Under Cygwin (cygwin.com), set ASA_LIB to TRUE and INCL_STDOUT to FALSE (OPTIONS described below), with the command % make asadll to produce a DLL to call asa_main() as a DLL function under windows. (Ignore any undefined references to _WinMain.) Note that per instructions given in the ASA-Makefile, -mno-cygwin -mrtd should be included in CFLAGS. If paths are used to access files in code, under Windows use absolute paths with "\\" (double back slash) to separate folders/directories, instead of relative paths with "/" (single forward slash) separators as on other Unix platforms. 8. Generic ASA Interfaces The sections above describe how to quickly adapt ASA for use in many problems. However, complex projects often require sophisticated use of multiple languages to handle data and multiple algorithms. ASA has many OPTIONS that enable users to interface ASA with such complex projects. ASA should compile under C++ as well as under C compilers. For example, I regularly test this by running projects under both gcc and g++. This can be very useful when ASA is called from other C++ programs, e.g., when using ASA_LIB set to TRUE. I have led many projects that required ASA to interface with Java, Maple, Matlab, MySQL, etc. The approach briefly described below can be applied to any language that permits a simple interface to C code. This definitely requires some expert experience in C, so you may have to find a local C guru, since I cannot help you with your specific project. Some specific interfaces have been prepared by other people, and I have included some of them in the asa_contrib.txt file. The tradeoff for their simple use is that these approaches are limited to using just a few ASA OPTIONS as they typically have trimmed down the ASA code. The generic approach is to utilize at least the OPTIONS ASA_LIB and OPTIONAL_DATA_PTR, setting them to TRUE. ASA_LIB permits the entire ASA code to be called as a simple function. Its sole parameter can be a struct defined by OPTIONAL_PTR_TYPE, e.g., OPTIONAL_PTR_TYPE PROJECT, defined in asa_usr_asa.h. A small include file common to asa_usr_asa.h and to the larger complex project, e.g., project.h, is used to define the constituents of the the PROJECT struct. As described above in the DLL ASA-Makefile sub-Section of Section 7, ASA_LIB can be used to create a DLL to be called by Windows programs. A small C function, e.g., project.c, is to be used for the interface between ASA and the other language. Similarly, another small function - 13 - Adaptive Simulated Annealing (ASA) Lester Ingber also may be used to interface the project to handle the interface, e.g., project.m, project.java, project.mpl, etc. Inversely, the interface may (also) be between the cost function, e.g., in asa_usr_cst.c or asa_usr.c, and the project. Then the application below is used to pass information between the cost function and the other language. The other language passes information and data to project.c required by ASA, where it is packed into the struct defined by OPTIONAL_PTR_TYPE. Multiple or recursive calls to ASA can be handled by including a flag in this struct, e.g., to turn on different cost functions. Also added to this struct are placeholders for the output of ASA required by the project. This struct is passed to the ASA code by calling asa_main () defined in asa_usr.c with a parameter PROJECT *Project. In asa_main (), in the section defining properties of OPTIONAL_DATA_PTR, the pointer to Project struct is set to the pointer path to Asa_Data_Ptr. Asa_Data_Ptr is now passed throughout the entire ASA code via the OPTIONS pointer, project parameters can be adaptively changed, etc. See the discussion under Asa_Data_Ptr. After the call to asa () in asa_usr.c, its output can be packed into the project struct, before memory is freed. The pointer Asa_Data_Ptr should be set to NULL instead of freed; see the comment in asa_usr.c at the place Asa_Data_Ptr is freed in the default code. It is wise to create #define PROJECT and #endif pairs wherever changes to any ASA code are made, define PROJECT to TRUE in asa_usr_asa.h, so that it will be easy to modify updated ASA code, etc. Probably several such changes will have to be made in asa_usr.c. Control of OPTIONS likely will best be handled in asa_usr_asa.h than in the ASA-Makefile. 9. User Options Program Options, i.e., the USER_DEFINES typedef on the OPTIONS, USER_OPTIONS, RECUR_USER_OPTIONS, etc., are turned on during the running of asa (). The DEFINE_OPTIONS are compiled in by the use of arguments to the compilation or by setting them in the asa_usr_asa.h file. An example of the former is Reanneal_Parameters, and an example of the latter is ASA_SAMPLE. The basic code is kept small for most users by using the Pre-Compile DEFINE_OPTIONS to pull in additional DEFINE_OPTIONS only if required. The Program Options are intended to be used adaptively and/or to pull in additional code for cases where repeated or recursive use, e.g., when using SELF_OPTIMIZE, might be facilitated by having control of some Program Options at separate levels. Note that even when the DEFINE_OPTIONS or Program Options are used to pull in new code, separate levels of control also can be achieved, albeit usually at the price of incurring some overhead in setting values at some levels of recursion or repeated calls. For example, in cases where new arrays or functions come into play, enough parameters are passed between the asa and user modules to calculate - 14 - Adaptive Simulated Annealing (ASA) Lester Ingber the defaults as well as different values adaptively. In some often used cases, separate DEFINE_OPTIONS are given, e.g., both OPTIONS_FILE and RECUR_OPTIONS_FILE exist. I have tried to strike some reasonable balance between these goals and constraints. The DEFINE_OPTIONS are organized into two groups: Pre-Compile Options and (Pre-Compile) Printing Options. In addition, there are some alternatives to explore under Compiler Choices and Document Formatting. Below are the DEFINE_OPTIONS with their defaults. The Program Options are further discussed in other sections in this document. Note that the Pre-Compile DEFINE_OPTIONS are all in capital letters, and the adaptive Program Options (under structure USER_OPTIONS in the user module and under structure OPTIONS in the asa module) are in capital and lower-case letters. In this file, often just the term OPTIONS may refer to the set of all options when the context is clear. 9.1. Pre-Compile DEFINE_OPTIONS 9.1.1. USER_COST_FUNCTION=cost_function The default name of the cost function is cost_function. This can be changed in asa_usr_asa.h (or the ASA-Makefile) by defining USER_COST_FUNCTION. This of course requires compiling in the new cost function and its prototype. 9.1.2. RECUR_USER_COST_FUNCTION=recur_cost_function When SELF_OPTIMIZE is TRUE, the default name of the recur cost function is recur_cost_function. This can be changed in asa_usr_asa.h (or the ASA-Makefile) by defining RECUR_USER_COST_FUNCTION. This of course requires compiling in the new cost function and its prototype. 9.1.3. OPTIONS_FILE=TRUE You can elect to read in many of the Program Options from asa_opt by setting OPTIONS_FILE=TRUE. OPTIONS_FILE=TRUE can be set in the ASA-Makefile in compilation commands or in asa_usr_asa.h. 9.1.4. OPTIONS_FILE_DATA=TRUE If OPTIONS_FILE is set to TRUE, then setting OPTIONS_FILE_DATA to TRUE permits reading most initialization data from asa_opt, i.e., number of parameters, minimum and maximum ranges, initial values, and integer or real types. This should suffice for most applications, just requiring insertion of the user's cost_function into asa_usr_cst.c or asa_usr.c. If OPTIONS_FILE, OPTIONS_FILE_DATA and QUENCH_COST are TRUE, then *User_Quench_Cost_Scale is read in from asa_opt. If OPTIONS_FILE, - 15 - Adaptive Simulated Annealing (ASA) Lester Ingber OPTIONS_FILE_DATA, QUENCH_COST, and QUENCH_PARAMETERS are TRUE, then *User_Quench_Cost_Scale and User_Quench_Param_Scale [] all are read in from asa_opt. 9.1.5. RECUR_OPTIONS_FILE=FALSE When SELF_OPTIMIZE is TRUE, you can elect to read in many of the Program Options for the top-level program from asa_opt_recur (which you will have to create in the style of asa_opt), by setting RECUR_OPTIONS_FILE=TRUE. 9.1.6. RECUR_OPTIONS_FILE_DATA=FALSE When SELF_OPTIMIZE is TRUE, if RECUR_OPTIONS_FILE is set to TRUE, then setting RECUR_OPTIONS_FILE_DATA to TRUE permits reading most initialization data from asa_opt_recur (which you will have to create in the style of asa_opt), i.e., number of parameters, minimum and maximum ranges, initial values, and integer or real types. If RECUR_OPTIONS_FILE, RECUR_OPTIONS_FILE_DATA and QUENCH_COST are TRUE, then *User_Quench_Cost_Scale is read in from asa_opt_recur. If RECUR_OPTIONS_FILE, RECUR_OPTIONS_FILE_DATA, QUENCH_COST, and QUENCH_PARAMETERS are TRUE, then *User_Quench_Cost_Scale and User_Quench_Param_Scale [] all are read in from asa_opt_recur. 9.1.7. COST_FILE=TRUE If COST_FILE is set to TRUE, then you can use a separate file to define your cost function. When used together with OPTIONS_FILE and OPTIONS_FILE_DATA both set to TRUE, most users may be able to just use their own asa_usr_cst.c file for their cost_function () together with the asa_opt data file, and not have to work through some of the examples and templates contained in asa_usr.c. When COST_FILE is set to TRUE, the file asa_usr_cst.c contains cost_function (). If you wish to change the name of cost_function () in asa_usr_cst.c, then you must also change this name in the call to asa () in asa_usr.c (search under "asa (") and in the prototype listing in asa_usr.h (in the HAVE_ANSI set to TRUE or FALSE section as appropriate). You may wish to copy the appropriate parameter list in asa_usr_cst.c just before the ASA_TEST problem to be sure of using the proper format expected by asa() in asa.c. The http://www.ingber.com/asa_examples.txt file contains a section Use of COST_FILE on Shubert Problem which illustrates the simple modifications of ASA required to use COST_FILE. 9.1.8. ASA_LIB=FALSE Setting ASA_LIB=TRUE will facilitate your running asa () as a library call from another program, calling asa_main () in asa_usr.c. In the templates provided, all initializations and cost function definitions are set up in the user module. For example, you may wish - 16 - Adaptive Simulated Annealing (ASA) Lester Ingber to have some data read in to a module that calls asa_main (), then parses out this information to the arrays in asa_main () and initialize_parameters (and possibly recur_initialize_parameters). In conjunction with setting printout to stdout (see ASA_OUT and USER_ASA_OUT), this can be a convenient way of using the same asa_run executable for many runs. When ASA_LIB is TRUE, another function becomes available in asa_usr.c, asa_seed (), which can be used to change the initial seed used in runs made by asa_main (). If this routine is not called, then the default initial seed is used. An example of using this routine when calling asa_main () is given with ASA_TEMPLATE_LIB, using a main () at the end of the asa_usr.c file. As described in the DLL ASA-Makefile sub-Section of Section 7, the ASA-Makefile and ASA_LIB can be used to create a DLL for Windows programs. 9.1.9. HAVE_ANSI=TRUE Setting HAVE_ANSI=FALSE will permit you to use an older K&R C compiler. This option can be used if you do not have an ANSI compiler, overriding the default HAVE_ANSI=TRUE. If you use HAVE_ANSI=FALSE, change CC and CDEBUGFLAGS as described in the ASA-Makefile. 9.1.10. IO_PROTOTYPES=FALSE Most newer operating systems do not like any other I/O prototyping other than those in their own include files. Other machines, like a Dec-3100 under Ultrix complain that the ANSI I/O prototypes were inconsistent. A Sun under 4.1.x gcc gave warnings if no I/O prototypes were present. The defaults in asa_usr_asa.h use newer system prototypes. IO_PROTOTYPES=TRUE will uncomment out declarations for such items as fprintf, fflush, fclose, exit, and fscanf. 9.1.11. TIME_CALC=FALSE Some systems do not have the time include files used here; others have different scales for time. Setting TIME_CALC=TRUE will permit use of the time routines. 9.1.12. TIME_STD=FALSE Some systems, e.g., hpux and Cygwin (with -mno-cygwin), use other Unix-standard macros to access time. Setting TIME_STD=TRUE when using TIME_CALC=TRUE will use these time routines instead. 9.1.13. TIME_GETRUSAGE=TRUE An additional module for using TIME_CALC set to TRUE, setting TIME_GETRUSAGE to FALSE, is more portable to compile across some - 17 - Adaptive Simulated Annealing (ASA) Lester Ingber platforms, e.g., Cygwin (with -mno-cygwin), but it can require different parameters for timing results. Comments have been placed in the code in asa.c. 9.1.14. INT_LONG=TRUE Some smaller systems choke on 'long int' and this option can be set to INT_LONG=FALSE to turn off warnings and possibly some errors. The cast LONG_INT is used to define 'int' or 'long int' appropriately. 9.1.15. INT_ALLOC=FALSE The cast on *number_parameters is set to ALLOC_INT which defaults to LONG_INT. On some machines, ALLOC_INT might have to be set to int if there is a strict requirement to use an (unsigned) int for calloc, while 'long int' still can be used for other aspects of ASA. If ALLOC_INT is to be set to int, set INT_ALLOC to TRUE. 9.1.16. SMALL_FLOAT=1.0E-18 SMALL_FLOAT is a measure of accuracy permitted in log and divide operations in asa, i.e., which is not precisely equivalent to a given machine's precision. There also are Pre-Compile DEFINE_OPTIONS to separately set constants for minimum and maximum doubles and precision permitted by your machine. Experts who require the very best precision can fine-tune these parameters in the code. Such issues arise because the fat tail of ASA, associated with high parameter temperatures, is very important for searching the breadth of the ranges especially in the initial stages of search. However, the parameter temperatures require small values at the final stages of the search to converge to the best solution, albeit this is reached very quickly given the exponential schedule proven in the referenced publications to be permissible with ASA. Note that the test problem in asa_usr_cst.c and asa_usr.c is a particularly nasty one, with 1E20 local minima and requiring ASA to search over 12 orders of magnitude of the cost function before correctly finding the global minimum. Thus, intermediate values disagree somewhat for SMALL_FLOAT=1.0E-12 from the settings using SMALL_FLOAT=1.0E-18 (the default); they agree if SMALL_FLOAT=1.0E-12 while also setting MIN_DOUBLE=1.0E-18. The results diverge when the parameter temperatures get down to the range of E-12, limiting the accuracy of the SMALL_FLOAT=1.0E-12 run. On some machines that have register variables assigned inconsistently with other doubles, there can arise some numerical differences in some systems. There has been no such problem found on Sun/Solaris 2.x using gcc, but some problems have been noticed on some Intel chips using different gcc optimizations. - 18 - Adaptive Simulated Annealing (ASA) Lester Ingber 9.1.17. MIN_DOUBLE=SMALL_FLOAT You can define your own machine's minimum positive double here if you know it. 9.1.18. MAX_DOUBLE=1.0/SMALL_FLOAT You can define your own machine's maximum double here if you know it. 9.1.19. EPS_DOUBLE=SMALL_FLOAT You can define your own machine's maximum precision here if you know it. 9.1.20. CHECK_EXPONENT=FALSE When CHECK_EXPONENT is set to TRUE, the macro EXPONENT_CHECK(x), defined in asa.h in terms of MIN_DOUBLE and MAX_DOUBLE, checks that an exponent x is within a valid range and, if not, adjusts its magnitude to fit in the range. 9.1.21. NO_PARAM_TEMP_TEST=FALSE If NO_PARAM_TEMP_TEST is set to TRUE, then all parameter temperatures less than EPS_DOUBLE are set to EPS_DOUBLE, and no exit is called. 9.1.22. NO_COST_TEMP_TEST=FALSE If NO_COST_TEMP_TEST is set to TRUE, then a cost temperature less than EPS_DOUBLE is set to EPS_DOUBLE, and no exit is called. 9.1.23. SELF_OPTIMIZE=FALSE The user module contains a template to illustrate how ASA may be used to self-optimize its Program Options. This can be very CPU-expensive and is of course dependent on how you define your recursive cost function (recur_cost_function in the user module). The example given returns from recur_cost_function the number of function evaluations taken to optimization the test cost_function, with the constraint to only accept optimizations of the cost_function that are lower than a specified value. A few lines of code can be uncommented in asa_usr.c to force a fast exit for this demo; search for FAST EXIT. (Note that this also could achieved by using OPTIONS->Immediate_Exit discussed below.) The ASA_TEMPLATE_SELFOPT example uses OPTIONS_FILE=FALSE in the Pre-Compile Options. Note that DEFINE_OPTIONS OPTIONS_FILE=TRUE and OPTIONS_FILE_DATA=TRUE here would take data from asa_opt for the lower-level program using the cost_function (). Both DEFINE_OPTIONS RECUR_OPTIONS_FILE and RECUR_OPTIONS_FILE_DATA would have to be set to TRUE to use asa_opt_recur to read in both the OPTIONS and the - 19 - Adaptive Simulated Annealing (ASA) Lester Ingber recur_cost_parameters data (which you would have to write in the style of asa_opt) for the top-level recur_cost_function (). This can be useful when approaching a new system, and it is suspected that the default ASA Program Options are not at all efficient for this system. It is suggested that a trimmed cost function or data set be used to get a reasonable guess for a good set of Program Options. ASA has demonstrated that it typically is quite robust under a given set of Program Options, so it might not make too much sense to spend lots of resources performing additional fine tuning of the these options. Also, it is possible you might crash the code by permitting ranges of Program Options that cause your particular cost_function to return garbage to asa (). 9.1.24. ASA_TEST=FALSE Setting ASA_TEST to TRUE will permit running the ASA test problem. This has been added to the DEFINE_OPTIONS in the ASA-Makefile so that just running make will run the test problem for the new user. No attempt was made to optimize any OPTIONS for the ASA_TEST problem as it appears in the standard code. 9.1.25. ASA_TEST_POINT=FALSE The code used for the ASA_TEST problem closely follows the reference given in asa_usr.c, and was rewritten from code given to the author in 1992. Other researchers have sent the author different code for this system, and all results agree within round-off errors. However, note that the actual problem stated in the reference in asa_usr.c is harder, requiring the finding of an optimal point and not an optimal region. The code for that problem is given in asa_usr.c when ASA_TEST_POINT is set to TRUE (having the effect of setting COST_FILE to FALSE in asa_usr_asa.h). The http://www.ingber.com/asa_examples.txt file illustrates how that global minimum can be attained. 9.1.26. MY_TEMPLATE=TRUE When MY_TEMPLATE is set to TRUE (the default), locations in asa_usr.c and asa_usr_asa.h become active sites for your own code. Searching asa_usr.c for "MY_TEMPLATE_" provides a guide for additional code to add for your own system. For example, just above the occurrence of the guides for MY_TEMPLATE_cost is the corresponding code for ASA_TEST=TRUE. Keeping the default of ASA_TEST set to FALSE permits such changes without overwriting the test example. 9.1.27. USER_INITIAL_COST_TEMP=FALSE Setting USER_INITIAL_COST_TEMP to TRUE permits you to specify the initial cost temperature in the User_Cost_Temperature [] array. This can be useful in problems where you want to start the search at a specific scale. - 20 - Adaptive Simulated Annealing (ASA) Lester Ingber 9.1.28. RATIO_TEMPERATURE_SCALES=FALSE Different rates of parameter annealing can be set with RATIO_TEMPERATURE_SCALES set to TRUE. This requires initializing the User_Temperature_Ratio [] array in the user module as discussed below. 9.1.29. USER_INITIAL_PARAMETERS_TEMPS=FALSE Setting USER_INITIAL_PARAMETERS_TEMPS to TRUE permits you to specify the initial parameter temperatures in the User_Parameter_Temperature [] array. This can be useful in constrained problems, where greater efficiency can be achieved in focussing the search than might be permitted just by setting upper and lower bounds. 9.1.30. DELTA_PARAMETERS=FALSE Different increments, used during reannealing to set each parameter's numerical derivatives, can be set with DELTA_PARAMETERS set to TRUE. This requires initializing the User_Delta_Parameter [] array in the user module as discussed below. 9.1.31. QUENCH_PARAMETERS=FALSE This DEFINE_OPTIONS permits you to alter the basic algorithm to perform selective "quenching," i.e., faster temperature cooling than permitted by the ASA algorithm. This can be very useful, e.g., to quench the system down to some region of interest, and then to perform proper annealing for the rest of the run. However, note that once you decide to quench rather than to truly anneal, there no longer is any statistical guarantee of finding a global optimum. Once you decide you can quench, there are many more alternative algorithms you might wish to choose for your system, e.g., creating a hybrid global-local adaptive quenching search algorithm, e.g., using USER_REANNEAL_PARAMETERS described below. Note that just using the quenching OPTIONS provided with ASA can be quite powerful, as demonstrated in the http://www.ingber.com/asa_examples.txt file. Setting QUENCH_PARAMETERS to TRUE can be extremely useful in very large parameter dimensions; see the ASA-NOTES file under the section on Quenching. As discussed in the first 1989 VFSR paper, the heuristic statistical proof of finding the global optimum reduces to the following: The parameter temperature schedules must suffice to insure that the product of individual generating distributions, g = PROD_i g^i, taken at all annealing times, indexed by k, of not generating a global optimum, given infinite time, is such that PROD_k (1-g_k) = 0, which is equivalent to SUM_k g_k = infinity. For the ASA temperature schedule, this is satisfied as SUM_k PROD^D 1/k^(1/D) = SUM_k 1/k = infinity. - 21 - Adaptive Simulated Annealing (ASA) Lester Ingber Now, if the temperature schedule above is redefined as T_i(k_i) = T_0i exp(-c_i k_i^(Q/D)), c_i = m_i exp(-n_i Q/D), in terms of the "quenching factor" Q, then the above proof fails if Q > 1 as SUM_k PROD^D 1/k^(Q/D) = SUM_k 1/k^Q < infinity This simple calculation shows how the "curse of dimensionality" arises, and also gives a possible way of living with this disease which will be present in any algorithm that substantially samples the parameter space. In ASA, the influence of large dimensions becomes clearly focussed on the exponential of the power of k being 1/D, as the annealing required to properly sample the space becomes prohibitively slow. So, if we cannot commit resources to properly sample the space ergodically, then for some systems perhaps the next best procedure would be to turn on quenching, whereby Q can become on the order of the size of number of dimensions. In some cases tried, a small system of only a few parameters can be used to determine some reasonable Program Options, and then these can be used for a much larger space scaled up to many parameters. This can work in some cases because of the independence of dimension of the generating functions. If QUENCH_PARAMETERS is TRUE, then User_Quench_Param_Scale [] must be defined as described below. If OPTIONS_FILE_DATA, QUENCH_COST, and QUENCH_PARAMETERS are TRUE, then *User_Quench_Cost_Scale and User_Quench_Param_Scale [] all are read in from asa_opt. If RECUR_OPTIONS_FILE_DATA, QUENCH_COST, and QUENCH_PARAMETERS are TRUE, then *User_Quench_Cost_Scale and User_Quench_Param_Scale [] all are read in from asa_opt_recur. 9.1.32. QUENCH_COST=FALSE If QUENCH_COST is set to TRUE, the scale of the power of 1/D temperature schedule used for the acceptance function can be altered in a similar fashion to that described above when QUENCH_PARAMETERS is set to TRUE. However, note that this OPTIONS does not affect the annealing proof of ASA, and so this may used without damaging the statistical ergodicity of the algorithm. Even greater functional changes can be made using the Pre-Compile DEFINE_OPTIONS USER_COST_SCHEDULE, USER_ACCEPT_ASYMP_EXP, USER_ACCEPT_THRESHOLD, or USER_ACCEPTANCE_TEST. If QUENCH_COST is TRUE, then User_Quench_Cost_Scale [0] must be defined as described below. If OPTIONS_FILE_DATA and QUENCH_COST are TRUE, then User_Quench_Cost_Scale [] is read in from asa_opt. If RECUR_OPTIONS_FILE_DATA and QUENCH_COST are TRUE, then *User_Quench_Cost_Scale is read in from asa_opt_recur. - 22 - Adaptive Simulated Annealing (ASA) Lester Ingber Similarly as noted above for QUENCH_PARAMETERS, setting QUENCH_COST to TRUE can be extremely useful in very large parameter dimensions; see the ASA-NOTES file under the section on Quenching. 9.1.33. QUENCH_PARAMETERS_SCALE=TRUE When QUENCH_PARAMETERS is TRUE, if QUENCH_PARAMETERS_SCALE is TRUE, then the temperature scales and the temperature indexes are affected by User_Quench_Param_Scale []. This can have the effects of User_Quench_Param_Scale [] appear contrary, as the effects on the temperatures from the temperature scales and the temperature indexes can have opposing effects. However, these defaults are perhaps most intuitive when the User_Quench_Param_Scale [] are on the order of the parameter dimension. When QUENCH_PARAMETERS is TRUE, if QUENCH_PARAMETERS_SCALE is FALSE, only the temperature indexes are affected by User_Quench_Param_Scale []. The same effect could be managed by raising Temperature_Anneal_Scale to the appropriate power, but this may not be as convenient. 9.1.34. QUENCH_COST_SCALE=TRUE When QUENCH_COST is TRUE, if QUENCH_COST_SCALE is TRUE, then the temperature scale and the temperature index are affected by User_Quench_Cost_Scale [0]. This can have the effects of User_Quench_Cost_Scale [0] appear contrary, as the effects on the temperature from the temperature scale and the temperature index can have opposing effects. However, these defaults are perhaps most intuitive when User_Quench_Cost_Scale [0] is on the order of the parameter dimension. When QUENCH_COST is TRUE, if QUENCH_COST_SCALE is FALSE, only the temperature index is affected by User_Quench_Cost_Scale [0]. The same effect could be managed by raising Temperature_Anneal_Scale to the appropriate power, but this may not be as convenient. 9.1.35. ASA_TEMPLATE=FALSE There are several templates that come with the ASA code. To permit use of these OPTIONS without having to delete these extra tests, these templates are wrapped with ASA_TEMPLATE's. To use your own cost function, you likely will only have to write cost_function () in asa_usr_cst.c, and use the asa_opt file. If you wish to add more OPTIONS or code, you may need to write relevant portions of cost_function () and initialize_parameters () in asa_usr.c and asa_usr.h. The ASA-Makefile has several examples of DEFINE_OPTIONS that will generate test examples using special ASA_TEMPLATE's set to TRUE. These are {ASA_TEMPLATE_LIB, ASA_TEMPLATE_ASA_OUT_PID, ASA_TEMPLATE_MULTIPLE, ASA_TEMPLATE_SELFOPT, ASA_TEMPLATE_SAMPLE, ASA_TEMPLATE_QUEUE, ASA_TEMPLATE_PARALLEL, ASA_TEMPLATE_SAVE}; the - 23 - Adaptive Simulated Annealing (ASA) Lester Ingber sets of Pre-Compile OPTIONS these use are defined in asa_usr_asa.h. Lines marked off by ASA_TEMPLATE, with no additional suffix, are for specific examples only. ASA_TEMPLATE, with no suffix, should not be set to TRUE, else all groups of these examples will be brought into the code, likely not what is wanted. 9.1.36. OPTIONAL_DATA_DBL=FALSE It can be useful to return/pass additional information to the user module from/through the asa module. When OPTIONAL_DATA_DBL is set to TRUE, an additional Program Option pointer, *Asa_Data_Dbl, and its dimension, Asa_Data_Dim_Dbl, are available in USER_DEFINES *USER_OPTIONS to gather such data. In the ASA_TEMPLATE_SELFOPT example provided (see the set of DEFINE_OPTIONS used in asa_usr_asa.h), OPTIONAL_DATA_DBL is used together with SELF_OPTIMIZE to find the set of ASA parameters giving the (statistically) smallest number of generated points to solve the ASA test problem, assuming this were run several times with different random seeds for randflt in asa_usr.c. Here, Asa_Data_Dbl [0] is used as a flag to print out Asa_Data_Dbl [1] in asa_usr.c, set to *best_number_generated_saved in asa.c. 9.1.37. OPTIONAL_DATA_INT=FALSE It can be useful to return/pass additional integer information to the user module from/through the asa module. When OPTIONAL_DATA_INT is set to TRUE, an additional Program Option pointer, *Asa_Data_Int, and its dimension, Asa_Data_Dim_Int, are available in USER_DEFINES *USER_OPTIONS to gather such data. 9.1.38. OPTIONAL_DATA_PTR=FALSE It can be useful to return/pass additional array or structure information to the user module from/through the asa module (possibly containing other structures, e.g., useful when SELF_OPTIMIZE is TRUE). When OPTIONAL_DATA_PTR is set to TRUE, an additional Program Option pointer, *Asa_Data_Ptr, and its dimension, Asa_Data_Dim_Ptr, are available in USER_DEFINES *USER_OPTIONS to gather such data. The type of *Asa_Data_Dim_Ptr is a pre-compile OPTIONS set by OPTIONAL_PTR_TYPE. See examples under Asa_Data_Dim_Ptr and Asa_Data_Ptr. If OPTIONAL_DATA_PTR is being used for RECUR_USER_OPTIONS as well as for USER_OPTIONS, you need not create (or free) additional memory in recur_cost_function() for Asa_Data_Dim_Ptr and Asa_Data_Ptr to be passed to the inner cost_function(), but rather link pointers to those in RECUR_USER_OPTIONS. In asa_usr.c, there are guidelines to set "#if TRUE" to "#if FALSE" at these points of the code. This is the proper technique to use if ASA_SAVE, ASA_SAVE_OPT, or ASA_SAVE_BACKUP is set to TRUE (since data is saved by asa() depending on the level of recursion).. - 24 - Adaptive Simulated Annealing (ASA) Lester Ingber If ASA_SAVE, ASA_SAVE_OPT, and ASA_SAVE_BACKUP are not set to TRUE, then multiple levels of recursion can each have their own defined information indexed to different elements of the array of structures of size Asa_Data_Dim_Ptr. The http://www.ingber.com/asa_examples.txt file contains some guidance of the use of OPTIONAL_DATA_PTR and Asa_Data_Ptr. 9.1.39. OPTIONAL_PTR_TYPE=USER_TYPE When OPTIONAL_DATA_PTR is set to TRUE, the type of *Asa_Data_Ptr is a pre-compile OPTIONS set by OPTIONAL_PTR_TYPE, e.g., changing the label USER_TYPE in asa_usr_asa.h. Be sure to place any non-standard types, like your own typedef struct, before the #define OPTIONAL_PTR_TYPE at the top of asa_usr_asa.h, e.g., under #if MY_TEMPLATE (since OPTIONAL_PTR_TYPE is tested below in asa_usr_asa.h). See the discussion under Asa_Data_Ptr. 9.1.40. USER_COST_SCHEDULE=FALSE The function used to control the cost_function temperature schedule is of the form test_temperature in asa.c. If the user sets the Pre-Compile DEFINE_OPTIONS USER_COST_SCHEDULE to TRUE, then this function of test_temperature can be controlled, adaptively if desired, in asa_usr.c in Cost_Schedule () (and in recur_Cost_Schedule () if SELF_OPTIMIZE is TRUE) by setting USER_COST_SCHEDULE to TRUE. The names of these functions are set to the relevant pointer in asa_usr.c, and can be changed if desired, i.e., USER_OPTIONS->Cost_Schedule = user_cost_schedule; RECUR_USER_OPTIONS->Cost_Schedule = recur_user_cost_schedule; 9.1.41. USER_ACCEPT_ASYMP_EXP=FALSE When USER_ACCEPT_ASYMP_EXP is TRUE, an asymptotic form of the exponential function as an alternative to the Boltzmann function becomes available for the acceptance test. A parameter OPTIONS->Asymp_Exp_Param becomes available, with a default of 1.0 in asa_usr.c giving the standard Boltzmann function. If you require a more moderate acceptance test, then negative Asymp_Exp_Param may be helpful. 9.1.42. USER_ACCEPT_THRESHOLD=FALSE When USER_ACCEPT_THRESHOLD is TRUE, a simple alternative to the Boltzmann function becomes available for the acceptance test, simply defining the probability of acceptance to be 1 if C(p_k+1) - C(p_k) <= T_cost, and 0 otherwise. 9.1.43. USER_ACCEPTANCE_TEST=FALSE If the Pre-Compile DEFINE_OPTIONS USER_ACCEPTANCE_TEST is set to TRUE, the Boltzmann test probability function used in the acceptance - 25 - Adaptive Simulated Annealing (ASA) Lester Ingber criteria in asa.c can be changed, adaptively if desired, in asa_usr.c in user_acceptance_test () (and in recur_user_acceptance_test () if SELF_OPTIMIZE is TRUE). The names of these functions are set to the relevant pointer in asa_usr.c, and can be changed if desired, i.e., If both USER_ACCEPTANCE_TEST and USER_ACCEPT_ASYMP_EXP are set to TRUE, then the default OPTIONS->Asymp_Exp_Param = 1 can be used in asa_usr.c to duplicate the Boltzmann test in asa.c, e.g., as a template to further develop a new acceptance test. USER_OPTIONS->Acceptance_Test = user_acceptance_test; RECUR_USER_OPTIONS->Acceptance_Test = recur_user_acceptance_test; When USER_ACCEPTANCE_TEST is TRUE, then any random numbers needed for the acceptance criteria are generated in the user module instead of in the asa module. When USER_ACCEPTANCE_TEST is TRUE, additional OPTIONS are available to modify the acceptance criteria, either after the cost function is calculated or during its calculation: USER_OPTIONS->User_Acceptance_Flag USER_OPTIONS->Cost_Acceptance_Flag USER_OPTIONS->Last_Cost USER_OPTIONS->Cost_Temp_Curr USER_OPTIONS->Cost_Temp_Init USER_OPTIONS->Cost_Temp_Scale USER_OPTIONS->Prob_Bias USER_OPTIONS->Random_Seed Failing the acceptance test is not equivalent to dropping generated states from consideration for testing with the acceptance criteria, e.g., if they fail some regional constraints. asa () is designed so that User_Acceptance_Flag is set to TRUE prior to calling the cost function whenever acceptance tests need not be performed, i.e., when using the cost function to generate initial conditions, when being used to calculate derivatives, or when samples are being generated to calculate the cost temperature; otherwise it is set to FALSE. The value of Cost_Acceptance_Flag always is set to FALSE before entering the cost function. When entering the acceptance function, if Cost_Acceptance_Flag is TRUE, then the value of USER_OPTIONS->User_Acceptance_Flag (assuming *valid_state_generated_flag is TRUE) calculated in user_cost_function () determines the value of the acceptance test. Otherwise, USER_OPTIONS->Acceptance_Test () is called to calculate the value of USER_OPTIONS->User_Acceptance_Flag. Note that if the cost function is used to calculate the acceptance criteria, and it is acceptable (e.g., also *valid_state_generated_flag is TRUE), then both USER_OPTIONS->User_Acceptance_Flag and USER_OPTIONS->Cost_Acceptance_Flag must be set to TRUE. For example, this can be useful if during the calculation of the cost function, without having to proceed to the final evaluation, it becomes clear that the acceptance criteria will not be passed. This might occur if the cost function is increasing during its calculation - 26 - Adaptive Simulated Annealing (ASA) Lester Ingber and an acceptance test is carried out using the uniform random number calculated at the top of the cost function. The partially evaluated cost function can be compared to the Last_Cost, using the Boltzmann criteria or whatever criteria is established in USER_OPTIONS->user_acceptance_test (). Then it is clear that the acceptance criteria will not be met (of course after checking that any constraints are met and setting *valid_state_generated_flag to TRUE if so), then USER_OPTIONS->User_Acceptance_Flag can be set to or left at FALSE, and then proceed to return to asa (). However, other information registered in the acceptance function still should be calculated, e.g., updating indices, information used for ASA_SAMPLE and ASA_PARALLEL, etc. 9.1.44. USER_GENERATING_FUNCTION=FALSE The ASA generating probability function in asa.c can be changed if the user sets the Pre-Compile DEFINE_OPTIONS USER_GENERATING_FUNCTION to TRUE; then this function can be changed, adaptively if desired, in asa_usr.c in user_generating_distrib () (and in recur_user_generating_distrib () if SELF_OPTIMIZE is TRUE) by setting USER_GENERATING_FUNCTION to TRUE. The names of these functions are set to the relevant pointer in asa_usr.c, and can be changed if desired, i.e., USER_OPTIONS->Generating_Distrib = user_generating_distrib; RECUR_USER_OPTIONS->Generating_Distrib = recur_user_generating_distrib; The parameters passed to these functions are further described below. Several parameters additional to those required for the ASA distribution are passed to make it easier to install other common distributions. Note that range checks take place at multiple stages of search, so be sure your chosen ranges can take this into account. 9.1.45. USER_REANNEAL_COST=FALSE In asa.c reannealing of the cost temperature is determined by the algorithm described above in the section Reannealing Temperature Schedule. If the user sets the Pre-Compile DEFINE_OPTIONS USER_REANNEAL_COST to TRUE, while Reanneal_Cost is not 0 or -1, then the function controlling the new reannealed cost temperature can be controlled, adaptively if desired using USER_OPTIONS, in asa_usr.c in user_reanneal_cost (), and in recur_user_reanneal_cost () if SELF_OPTIMIZE is TRUE. The names of these functions are set to the relevant pointer in asa_usr.c, and can be changed if desired, i.e., USER_OPTIONS->Reanneal_Cost_Function = user_reanneal_cost; RECUR_USER_OPTIONS->Reanneal_Cost_Function = recur_user_reanneal_cost; In these functions, the variables *current_cost_temperature, *initial_cost_temperature, and the best and last saved cost function can be altered, and the returned integer value of TRUE or FALSE determines whether to use the best saved cost function as the current - 27 - Adaptive Simulated Annealing (ASA) Lester Ingber cost temperature. Since these functions can be called every value of Acceptance_Frequency_Modulus, Generated_Frequency_Modulus, or when the ratio of accepted to generated points is less than Accepted_To_Generated_Ratio, this opportunity also can be used to adaptively change other OPTIONS. This can be very useful for systems where the scales of the acceptance criteria do not simply correlate the cost temperature with the current best value of the cost function. For example, this function could be used when the last saved cost function is so close to zero that the effect would be to set the *initial_cost_temperature to that value, but the best value for the cost function is known to be less than zero. (An alternative moving average example is given in asa_usr.c.) Other alternatives are to use USER_REANNEAL_COST with default FALSE and Reanneal_Cost > 1 or < -1, as described below. 9.1.46. USER_REANNEAL_PARAMETERS=FALSE In asa.h, the macro #define \ FUNCTION_REANNEAL_PARAMS(temperature, tangent, max_tangent) \ (temperature * (max_tangent / tangent)) is used to determine the new temperature, subject to further tests in reanneal (). This is the default if USER_REANNEAL_PARAMETERS is FALSE. If the user sets the Pre-Compile DEFINE_OPTIONS USER_REANNEAL_PARAMETERS to TRUE, then the function controlling the new reannealed temperature can be controlled, adaptively if desired using USER_OPTIONS, in asa_usr.c in user_reanneal_params (), and in recur_user_reanneal_params () if SELF_OPTIMIZE is TRUE. The names of these functions are set to the relevant pointer in asa_usr.c, and can be changed if desired, i.e., USER_OPTIONS->Reanneal_Params_Function = user_reanneal_params; RECUR_USER_OPTIONS->Reanneal_Params_Function = recur_user_reanneal_params; Since FUNCTION_REANNEAL_PARAMS () can be called every value of Acceptance_Frequency_Modulus, Generated_Frequency_Modulus, or when the ratio of accepted to generated points is less than Accepted_To_Generated_Ratio, this opportunity also can be used to adaptively change other OPTIONS. For example, if the QUENCH_PARAMETERS OPTIONS is set to TRUE, as discussed above, it may useful to create a hybrid global-local adaptive quenching search algorithm. 9.1.47. MAXIMUM_REANNEAL_INDEX=50000 The maximum index (number of steps) at which the initial temperature and the index of the temperature are rescaled to avoid losing machine precision. ASA typically is quite insensitive to the - 28 - Adaptive Simulated Annealing (ASA) Lester Ingber value used due to the dual rescaling. 9.1.48. REANNEAL_SCALE=10.0 The reannealing scale used when MAXIMUM_REANNEAL_INDEX is exceeded. 9.1.49. ASA_SAMPLE=FALSE When ASA_SAMPLE is set to TRUE, data is collected by ASA during its global optimization process to importance-sample the user's variables. Four OPTIONS become available to monitor the sampling: Bias_Acceptance, *Bias_Generated, Average_Weights, and Limit_Weights. If Average_Weights exceeds the user's choice of Limit_Weights, then the ASA_OUT file will contain additional detailed information, including temperatures and biases for each current parameter. To facilitate extracting importance-sampled information from the file printed out by the asa module, all relevant lines start with :SAMPLE[ |:|#|+]. A sample () function in asa_usr.c illustrates the use of these tags. Many Monte Carlo sampling techniques require the user to guess an appropriately decreasing "window" to sample the variable space. The fat tail of the ASA generating function, and the decreasing effective range of newly accepted points driven by exponentially decreasing temperature schedules, removes this arbitrary aspect of such sampling. However, note that, albeit local optima are sampled, the efficiency of ASA optimization most often leads to poor sampling in regions whose cost function is far from the optimal point; many such points may be important contributions to algorithms like integrals. Accordingly, ASA_SAMPLE likely is best used to explore new regions and new systems. To increase the sampling rate and thereby to possibly increase the accuracy of this algorithm, use one or a combination of the various OPTIONS available for slowing down the annealing performed by ASA. However, the selected OPTIONS still must yield good convergence if the optimal region is to be properly sampled. 9.1.50. ASA_QUEUE=FALSE When ASA_QUEUE is set to TRUE, a first-in first-out (FIFO) queue, of size USER_OPTIONS->Queue_Size, is used to collect generated states. When a new state is generated, its parameters are tested, within specified resolutions of USER_OPTIONS->Queue_Resolution [] (the absolute values of each of the differences between the parameters of the current generated state and those in the queue). If a previous state is already represented, then the stored values of the cost function and the cost flag are returned, instead of calling the cost function again. Note that the size of the array required to store the queued parameters is Queue_Size times the number of parameters, and - 29 - Adaptive Simulated Annealing (ASA) Lester Ingber this can consume a lot of CPU time as well as storage, so this OPTIONS is only useful for cost functions that are themselves very costly to evaluate. Setting ASA_TEMPLATE_QUEUE to TRUE will run an example using the ASA_TEST problem. The ASA_QUEUE DEFINE_OPTIONS also can be used to coarse-grain a fit, by setting high values of Queue_Resolution []. Note the difference between the operations of this DEFINE_OPTIONS and ASA_RESOLUTION. If ASA_QUEUE is TRUE and ASA_RESOLUTION is FALSE, machine precision is used for type double variables, the queue is created and subsequent variables are tested against this queue. If ASA_RESOLUTION and ASA_QUEUE are both TRUE, then the Coarse_Resolution [] array is used for Queue_Resolution [], ASA_RESOLUTION is enforced from the very first call to the cost function, and the queue is created using these coarse variables. The default in asa.c for the FIFO queue uses a simple search among stored parameter values, under the assumption that for most complex systems for which ASA_QUEUE=TRUE is useful, the bottleneck is in the evaluation of the cost functions. If you think this is not true for you, and you need to conserve CPU time in using lists, the http://www.ingber.com/asa_contrib.txt file gives code that uses doubly-linked and hashed lists. If ASA_QUEUE and ASA_PRINT_MORE are TRUE then, whenever a queued cost function is used, this is recorded in asa_out. 9.1.51. ASA_RESOLUTION=FALSE When ASA_RESOLUTION is set to TRUE, parameters are resolved to a user-defined resolution set in USER_OPTIONS->Coarse_Resolution [], i.e., within plus or minus the values of Coarse_Resolution []. This is performed as soon as candidate values are generated, for each parameter for which Coarse_Resolution [] is greater than zero. Note the difference between the operations of this OPTIONS and ASA_QUEUE. If ASA_QUEUE is TRUE and ASA_RESOLUTION is FALSE, machine precision is used for type double variables, the queue is created and subsequent variables are tested against this queue. If ASA_RESOLUTION and ASA_QUEUE are both TRUE, then the Coarse_Resolution [] array is used for Queue_Resolution [], ASA_RESOLUTION is enforced from the very first call to the cost function, and the queue is created using these coarse variables. When USER_OPTIONS->Coarse_Resolution [] is > 0 and parameter_type [] is > 0 (specifying an integer parameter), ASA_RESOLUTION takes precedence over parameter_type [] when calculating new generated parameters. - 30 - Adaptive Simulated Annealing (ASA) Lester Ingber 9.1.52. FITLOC=FALSE When FITLOC is set to TRUE, three subroutines become active to perform a local fit after leaving asa (). This can be useful to shunt asa () to a local code after the region of the global fit is known with some confidence, which many times is an efficient procedure. Any robust quasi-linear optimization code may work well for this purpose. To illustrate this procedure, the user module contains fitloc () which sets up the calls to simplex (). simplex () calls calcf () which calls cost_function (), and adds USER_OPTIONS->Penalty whenever simplex () asks for parameters out of ranges of the parameters or whenever a constraint in cost_function () is violated. ASA parameters, the OPTIONS, are raised to a high level of view for direct control by the user. However, most optimization codes have their own parameters that may not be apparent to the user. For example, fitloc () calls simplex () which contains parameters such as {tol1, tol2, no_progress, alpha, beta1, beta2, gamma, delta, iters}. Many problems will require tuning of these parameters to achieve good results just from this simplex () algorithm. USER_OPTIONS->Fit_Local is passed to cost_function (). This provides additional flexibility in deciding when to shunt asa () over to fitloc (), e.g., during multiple or recursive optimizations. USER_OPTIONS->Iter_Max determines the maximum iterations of the cost_function () by simplex (). USER_OPTIONS->Penalty determines how to weight violation of constraints, exceeding boundaries, etc. 9.1.53. FITLOC_ROUND=TRUE If FITLOC is set to TRUE and FITLOC_ROUND is TRUE, then each time parameters are passed to or between the local routines, simplex (), calcf (), and fitloc (), they are first processed by rounding integers or respecting rounding according to ASA_RESOLUTION constraints prior to any further calculations. I.e., all values of a parameter within a given resolution are considered to be equivalent for calculating the cost function. 9.1.54. FITLOC_PRINT=TRUE When FITLOC is set to TRUE, if FITLOC_PRINT is TRUE, then intermediate calculations will be printed out from fitloc () and simplex () in the user module. 9.1.55. MULTI_MIN=FALSE When MULTI_MIN is set to TRUE, the lowest USER_OPTIONS->Multi_Number values of the cost function, determined to be the best-generated during the sampling process, of the cost function and their parameters are saved. These can be read out just after asa () returns after its fit. The pre-compile number USER_OPTIONS->Multi_Number and OPTIONS *Multi_Cost, **Multi_Params, - 31 - Adaptive Simulated Annealing (ASA) Lester Ingber *Multi_Grid, and Multi_Specify become available. In asa_usr.c, memory for the arrays USER_OPTIONS->Multi_Cost [USER_OPTIONS->Multi_Number][*parameter_dimension], USER_OPTIONS->Multi_Params [USER_OPTIONS->Multi_Number][*parameter_dimension], and USER_OPTIONS->Multi_Grid [*parameter_dimension] are set. Multi_Grid values must be set by the user, but may be overridden as explained below under USER_OPTIONS->Multi_Grid. If OPTIONS->Curvature_0 is FALSE, all USER_OPTIONS->Multi_Number tangents and curvatures are calculated. This can be useful for some calculations requiring the shapes of the local minima. This procedure selects local minima that statistically have maintained some quasi-stability during sampling. Note that this procedure does not guarantee that the USER_OPTIONS->Multi_Number lowest sampled values of the cost function will be saved, only those that were selected to be the best-generated during the sampling process. If OPTIONS->Multi_Specify is set to 0, the selection of best- generated states includes all sampled instances of the cost functions. If OPTIONS->Multi_Specify is set to 1, the selection of best-generated states is constrained to include only those with different values of the cost function. The http://www.ingber.com/asa_examples.txt file contains some guidance of the use of MULTI_MIN (and Multi_[] OPTIONS). 9.1.56. ASA_PARALLEL=FALSE The parallelization procedure employed here does not destroy the sampling properties of ASA. When ASA_PARALLEL is set to TRUE, parallel blocks of generated states are calculated of number equal to the minimum of USER_OPTIONS->Gener_Block and USER_OPTIONS->Gener_Block_Max. For most systems with complex nonlinear cost functions that require the fat tail of the ASA distribution, leading to high generated to acceptance ratios, this is the most CPU intensive part of ASA that can benefit from parallelization. The actual number calculated is determined by a moving average, determined by USER_OPTIONS->Gener_Mov_Avr, of the previous numbers of USER_OPTIONS->Gener_Block of generated states required to find a new best accepted state. If and when USER_OPTIONS->Gener_Mov_Avr is set to 0, then USER_OPTIONS->Gener_Block is not changed thereafter. Each block of generated states is sorted to permit the lowest cost functions to pass first through the acceptance test. There are hooks in asa.c to spawn off multiple processors. Parallel code should be inserted in asa.c between the lines: /* *** ENTER CODE TO SPAWN OFF PARALLEL GENERATED STATES *** */ - 32 - Adaptive Simulated Annealing (ASA) Lester Ingber ... /* *** EXIT CODE SPAWNING OFF PARALLEL GENERATED STATES *** */ The ASA_TEMPLATE_PARALLEL example given in asa_usr.c illustrates how the run would proceed. Note that since the random number generator is called differently, generating some extra states as described above, the results are not identical to the serial ASA_TEST calculation. 9.1.57. FDLIBM_POW=FALSE When FDLIBM_POW is set to TRUE, a user-defined function s_pow () is used instead of pow (). This may be desirable on some machines when a speed-up can be realized. Some code in http://www.ingber.com/asa_contrib.txt should first be tested with the standard ASA_TEST OPTIONS to see if the resulting asa_out file agrees with the asa_test_asa file. 9.1.58. FDLIBM_LOG=FALSE When FDLIBM_LOG is set to TRUE, a user-defined function s_log () is used instead of log (). This may be desirable on some machines when a speed-up can be realized. Some code in http://www.ingber.com/asa_contrib.txt should first be tested with the standard ASA_TEST OPTIONS to see if the resulting asa_out file agrees with the asa_test_asa file. 9.1.59. FDLIBM_EXP=FALSE When FDLIBM_EXP is set to TRUE, a user-defined function s_exp () is used instead of exp (). This may be desirable on some machines when a speed-up can be realized. Some code in http://www.ingber.com/asa_contrib.txt should first be tested with the standard ASA_TEST OPTIONS to see if the resulting asa_out file agrees with the asa_test_asa file. 9.2. Printing DEFINE_OPTIONS 9.2.1. USER_OUT=\"asa_usr_out\" The name of the output file containing all printing from asa_usr.c. If you wish to attach a process number use USER_OUT=\"asa_usr_out_$$\". (Use USER_OUT=\"asa_usr_out_$$$$\" if this is set in the ASA-Makefile.) If USER_OUT=\"STDOUT\" then asa_usr.c will print to stdout. 9.2.2. INCL_STDOUT=TRUE Some compilers on some systems under some levels of optimization will not compile if "stdout" is present in the code. All instances of "stdout" and "printf" in the user and the asa modules can be commented out by setting INCL_STDOUT to FALSE. Note that this also will - 33 - Adaptive Simulated Annealing (ASA) Lester Ingber suppress some output from such OPTIONS as ASA_PIPE, TIME_CALC, etc. The use of INCL_STDOUT set to FALSE is recommended for creating a DLL as described in the DLL ASA-Makefile sub-Section of Section 7. 9.2.3. ASA_PRINT=TRUE Setting this to FALSE will suppress all printing within asa. 9.2.4. ASA_OUT=\"asa_out\" The name of the output file containing all printing from asa. If you wish to attach a process number use ASA_OUT=\"asa_out_$$\". (Use ASA_OUT=\"asa_out_$$$$\" if this is set in the ASA-Makefile.) If ASA_OUT=\"STDOUT\" then ASA will print to stdout. See the discussion of the use of ASA_TEMPLATE_ASA_OUT_PID in the section USER_ASA_OUT below to obtain multiple output files numbered according to the system pid. 9.2.5. USER_ASA_OUT=FALSE When USER_ASA_OUT is set to TRUE, an additional Program Option pointer, *Asa_Out_File, is used to dynamically set the name(s) of the file(s) printed out by the asa module. (This overrides any ASA_OUT settings.) In asa_usr.c, if USER_OPTIONS->Asa_Out_File = "STDOUT";, then ASA will print to stdout. In the ASA_TEMPLATE_MULTIPLE example provided (see the set of DEFINE_OPTIONS used in asa_usr_asa.h), USER_ASA_OUT is used to generate multiple files of separate ASA runs. (If QUENCH_PARAMETERS and/or QUENCH_COST is set to TRUE, then this example will separate runs with different quenching values.) In the ASA_TEMPLATE_ASA_OUT_PID example provided (see the set of DEFINE_OPTIONS used in asa_usr_asa.h), USER_ASA_OUT is used to generate ASA_OUT files of the form asa_out__x and asa_usr_out_x, where x is the system pid. This can be useful for a series of runs just changing parameters in asa_opt, getting different output files without recompiling. Depending on your system, you may have to change the include file and the prototype of getpid () in asa_usr.h under ASA_TEMPLATE_ASA_OUT_PID, and possibly the int declaration of pid_int in asa_usr.c. 9.2.6. ASA_PRINT_INTERMED=TRUE This option is only effective if ASA_PRINT is TRUE. Setting ASA_PRINT_INTERMED to FALSE will suppress much intermediate printing within asa, especially arrays which can be large when the number of parameters is large. Printing at intermediate stages of testing/reannealing has been turned off when SELF_OPTIMIZE is set to TRUE, since there likely can be quite a bit of data generated; this can be changed by explicitly setting ASA_PRINT_INTERMED to TRUE in the ASA-Makefile or on your compilation command lines. - 34 - Adaptive Simulated Annealing (ASA) Lester Ingber 9.2.7. ASA_PRINT_MORE=FALSE Setting ASA_PRINT_MORE to TRUE will print out more intermediate information, e.g., new parameters whenever a new minimum is reported. As is the case whenever tangents are not calculated by choosing some ASA options, normally the intermediate values of tangents will not be up to date. The section above, Use of Documentation for Tuning, emphasizes the importance of using ASA_PRINT_MORE set to TRUE to help determine optimal tuning of ASA on specific problems. 9.2.8. G_FIELD=12 & G_PRECISION=7 The field width and precision of doubles is specified in asa.c as G_FIELD.G_PRECISION, e.g., as %gG_FIELD.G_PRECISION or %g-G_FIELD.G_PRECISION. These two Printing DEFINE_OPTIONS are available to change the default of 12.7. 9.2.9. ASA_SAVE=FALSE When ASA_SAVE is set to TRUE, asa saves enough information in file asa_save after each newly best accepted state, to restart from the point entering the main annealing loop, continue thereafter from the best accepted state in asa_save. Of course, this use of I/O takes CPU resources, and can appreciably slow down your runs. When SYSTEM_CALL is set to TRUE, for extra protection, e.g., in case the run aborts during a write of asa_save, each time a file asa_save is written, it also is copied to a new file asa_save.old. In order to store the whole block of random numbers used at any time, the number USER USER_OPTIONS->Random_Array_Dim and array USER_OPTIONS->Random_Array are required. These may be changed by the user in asa_usr.c for different random number generators and shuffling algorithms. The default is to use SHUFFLE defined in asa_usr.h for Random_Array_Dim in the default random number generator in asa_usr.c, and the pointer Random_Array is set to the pointer of the static array random_array at the top of asa_usr.c. Just restart the run by executing asa_run. When ASA_SAVE is set to TRUE, the existence of file asa_save is used to determine whether a new run or a rerun is to proceed. Therefore, be sure your ASA directory does not have any old asa_save file present if a new run is to start. The asa_opt file is included just after asa_save files are read into the code. Therefore, any new C code you wish to have override information read in from asa_save can be simply added to the bottom of asa_opt. Be sure you write the names of these variables as they are used in the asa.c file, which can differ from their counterparts in asa_usr.c file. Some example are given at the end of asa_opt before the #endif statement. Each time you add new information to be compiled, be sure to enforce a new recompile of asa.c and asa_run. In - 35 - Adaptive Simulated Annealing (ASA) Lester Ingber most cases this can be done simply by removing asa.o before using a make or recompiling the executable. However, see ASA_SAVE_OPT for changes that may be made without any recompilation. When ASA is run at several levels of recursion, if USER_OPTIONS->Asa_Recursive_Level is properly incremented from 0 at the innermost shell, the outermost shell at level n will create files asa_save_{n}. 9.2.10. ASA_SAVE_OPT=FALSE When ASA_SAVE_OPT is set to TRUE, when asa is restarted, if the file asa_opt_save is present in the same directory as asa_opt, then new values of ASA parameters and OPTIONS are read in after initializing to the point of the last writing of asa_save. No recompilation of the code is necessary, and only warnings are issued if asa_save_opt is not present. The file asa_save_opt should be created as an exact copy of asa_opt before changes in values of parameters and OPTIONS are made. When ASA_SAVE_OPT is TRUE, ASA_SAVE is automatically set to TRUE in asa_usr_asa.h. 9.2.11. ASA_SAVE_BACKUP=FALSE When ASA_SAVE_BACKUP is set to TRUE, asa saves enough information after each newly best accepted state, creating a file asa_save.{N_Accepted}, to enable the user to restart from any previous best accepted state when that asa_save.{best_state} is copied to asa_save. When used with ASA_PIPE and/or ASA_PIPE_FILE, ASA_SAVE_BACKUP permits the user to interactively tune the optimization process without having to start new runs. Read the above ASA_SAVE section on the use of the asa_opt file to modify code before reading in the asa_save file. When ASA_SAVE_BACKUP is TRUE, ASA_SAVE is automatically set to TRUE in asa_usr_asa.h. When ASA is run at several levels of recursion, if USER_OPTIONS->Asa_Recursive_Level is properly incremented from 0 at the innermost shell, the outermost shell at level n will create files asa_save_{n}.{N_Accepted}. 9.2.12. ASA_PIPE=FALSE When ASA_PIPE is set to TRUE, asa prints to STDOUT lines of data after calls to the cost function, which can be used to update databases or graphs in real time. This information is {number of valid generated states, number of accepted states, best cost function, best parameter values, current cost temperature, current parameter temperatures, last cost function}. - 36 - Adaptive Simulated Annealing (ASA) Lester Ingber 9.2.13. ASA_PIPE_FILE=FALSE When ASA_PIPE_FILE is set to TRUE, asa prints to asa_pipe lines of data that can be used to examine run data. This can be used complementary to ASA_PIPE. 9.2.14. SYSTEM_CALL=TRUE When SYSTEM_CALL is set to FALSE, asa avoids popen () commands. This is useful on machines that do not permit these commands. For example, when ASA_SAVE is set to TRUE, asa uses a popen call in asa.c, to copy asa_save to asa_save.old. This also is required to use ASA_SAVE_BACKUP set to TRUE. 9.3. Program OPTIONS typedef struct { LONG_INT Limit_Acceptances; LONG_INT Limit_Generated; int Limit_Invalid_Generated_States; double Accepted_To_Generated_Ratio; double Cost_Precision; int Maximum_Cost_Repeat; int Number_Cost_Samples; double Temperature_Ratio_Scale; double Cost_Parameter_Scale_Ratio; double Temperature_Anneal_Scale; #if USER_INITIAL_COST_TEMP double *User_Cost_Temperature; #endif int Include_Integer_Parameters; int User_Initial_Parameters; ALLOC_INT Sequential_Parameters; double Initial_Parameter_Temperature; #if RATIO_TEMPERATURE_SCALES double *User_Temperature_Ratio; #endif #if USER_INITIAL_PARAMETERS_TEMPS double *User_Parameter_Temperature; #endif int Acceptance_Frequency_Modulus; int Generated_Frequency_Modulus; int Reanneal_Cost; int Reanneal_Parameters; double Delta_X; #if DELTA_PARAMETERS double *User_Delta_Parameter; #endif int User_Tangents; - 37 - Adaptive Simulated Annealing (ASA) Lester Ingber int Curvature_0; #if QUENCH_PARAMETERS double *User_Quench_Param_Scale; #endif #if QUENCH_COST double *User_Quench_Cost_Scale; #endif LONG_INT N_Accepted; LONG_INT N_Generated; int Locate_Cost; int Immediate_Exit; double *Best_Cost; double *Best_Parameters; double *Last_Cost; double *Last_Parameters; #if OPTIONAL_DATA_DBL ALLOC_INT Asa_Data_Dim_Dbl; double *Asa_Data_Dbl; #endif #if OPTIONAL_DATA_INT ALLOC_INT Asa_Data_Dim_Int; double *Asa_Data_Int; #endif #if OPTIONAL_DATA_PTR ALLOC_INT Asa_Data_Dim_Ptr; OPTIONAL_PTR_TYPE *Asa_Data_Ptr; #endif #if USER_ASA_OUT char *Asa_Out_File; #endif #if USER_COST_SCHEDULE double ( *Cost_Schedule ) (); #endif #if USER_ACCEPT_ASYMP_EXP double Asymp_Exp_Param; #endif #if USER_ACCEPTANCE_TEST void ( *Acceptance_Test ) (); int User_Acceptance_Flag; int Cost_Acceptance_Flag; double Last_Cost; double Cost_Temp_Curr; double Cost_Temp_Init; double Cost_Temp_Scale; double Prob_Bias; LONG_INT *Random_Seed; #endif #if USER_GENERATING_FUNCTION double ( *Generating_Distrib ) (); - 38 - Adaptive Simulated Annealing (ASA) Lester Ingber #endif #if USER_REANNEAL_COST int ( *Reanneal_Cost_Function ) (); #endif #if USER_REANNEAL_PARAMETERS double ( *Reanneal_Params_Function ) (); #endif #if ASA_SAMPLE double Bias_Acceptance; double *Bias_Generated; double Average_Weights; double Limit_Weights; #endif #if ASA_QUEUE ALLOC_INT Queue_Size; double *Queue_Resolution; #endif #if ASA_RESOLUTION double *Coarse_Resolution; #endif #if FITLOC int Fit_Local; int Iter_Max; double Penalty; #endif #if MULTI_MIN double *Multi_Cost; double **Multi_Params; double *Multi_Grid; int Multi_Specify; #endif #if ASA_PARALLEL int Gener_Mov_Avr; LONG_INT Gener_Block; LONG_INT Gener_Block_Max; #endif #if ASA_SAVE ALLOC_INT Random_Array_Dim; LONG_INT *Random_Array; #endif int Asa_Recursive_Level; } USER_DEFINES; Note that two ways are maintained for passing the Program Options. Check the comments in the ASA-NOTES file. It may be necessary to change some of the options for some systems. Read the http://www.ingber.com/asa_examples.txt file for some ongoing discussions and suggestions on how to try to optimally set these options. Note the distinction between trying to speed up annealing/quenching versus trying to slow down annealing (which sometimes can speed up the search by avoiding spending too much time in some local optimal regions). Templates are set up in ASA to - 39 - Adaptive Simulated Annealing (ASA) Lester Ingber accommodate all alternatives. Below, the defaults are given in square brackets []. (A) asa_usr.c file When using ASA as part of a large library, it likely is easiest to make these changes within the user module, e.g., using the template placed in asa_usr.c. In the user module, the Program Options are stored in the structure USER_DEFINES *USER_OPTIONS (and in USER_DEFINES *RECUR_USER_OPTIONS if SELF_OPTIMIZE is TRUE). (B) asa_opt file It likely is most efficient to use a separate data file avoiding repeated compilations of the code, to test various combinations of Program Options, e.g., using the file asa_opt when OPTIONS_FILE and OPTIONS_FILE_DATA are set to TRUE in the ASA-Makefile or on your compilation command lines. In the asa module (which can be called recursively) the structure is called USER_DEFINES *OPTIONS. For the rest of this file, where no confusion can reasonably arise, the Program Options will be referred to as USER_DEFINES *OPTIONS. 9.3.1. OPTIONS->Limit_Acceptances[10000] The maximum number of states accepted before quitting. All the templates in ASA have been set to use Limit_Acceptances=1000 to illustrate the way these options can be changed. If Limit_Acceptances is set to 0, then no limit is observed. This can be useful for some systems that cannot handle large integers. 9.3.2. OPTIONS->Limit_Generated[99999] The maximum number of states generated before quitting. If Limit_Generated is set to 0, then no limit is observed. This can be useful for some systems that cannot handle large integers. 9.3.3. OPTIONS->Limit_Invalid_Generated_States[1000] This sets limits of repetitive invalid generated states, e.g., when using this method to include constraints. This also can be useful to quickly exit asa () if this is requested by your cost function: Setting the value of Limit_Invalid_Generated_States to 0 will exit at the next calculation of the cost function (possibly after a few more exiting calls to calculate tangents and curvatures). For example, to exit asa () at a specific number of generated points, set up a counter in your cost function, e.g., similar to the one in the test function in asa_usr.c. For all calls >= the limit of the number of calls to the cost function, terminate by setting OPTIONS->Limit_Invalid_Generated_States = 0 and setting *cost_flag = FALSE. (Note that a quick exit also can be achieved using OPTIONS->Immediate_Exit.) - 40 - Adaptive Simulated Annealing (ASA) Lester Ingber 9.3.4. OPTIONS->Accepted_To_Generated_Ratio[1.0E-6] The least ratio of accepted to generated states. If this value is encountered, then the usual tests, including possible reannealing, are initiated even if the timing does not coincide with Acceptance_Frequency_Modulus or Generated_Frequency_Modulus (defined below). All the templates in ASA have been set to use Accepted_To_Generated_Ratio=1.0E-4 to illustrate the way these options can be changed. 9.3.5. OPTIONS->Cost_Precision[1.0E-18] This sets the precision required of the cost function if exiting because of reaching Maximum_Cost_Repeat, which is effective as long as Maximum_Cost_Repeat > 0. 9.3.6. OPTIONS->Maximum_Cost_Repeat[5] The maximum number of times that the cost function repeats itself, within limits set by Cost_Precision, before quitting. This test is performed only when Acceptance_Frequency_Modulus or Generated_Frequency_Modulus is invoked, or when the ratio of accepted to generated points is less than Accepted_To_Generated_Ratio, in order to help prevent exiting prematurely in a local minimum. If Maximum_Cost_Repeat is 0, this test is bypassed. 9.3.7. OPTIONS->Number_Cost_Samples[5] When Number_Cost_Samples > 0, the initial cost temperature is calculated as the average of the absolute values of Number_Cost_Samples sampled cost functions. When Number_Cost_Samples < -1, the initial cost temperature is calculated as the deviation over a sample of -Number_Cost_Samples number of cost functions, i.e., the square-root of the difference of the second moment and the square of the first moment, normalized by the ratio of -Number_Cost_Samples to -Number_Cost_Samples - 1. When ASA_SAVE is set to TRUE, Number_Cost_Samples is set to 1 after the initial run since all the required information for subsequent runs already has been collected. See Reanneal_Cost for similar treatment of the reannealed cost temperature. 9.3.8. OPTIONS->Temperature_Ratio_Scale[1.0E-5] This scale is a guide to the expected cost temperature of convergence within a small range of the global minimum. As explained in the ASA papers, and as outlined in the ASA-NOTES, this is used to set the rates of annealing. Here is a brief description in terms of the temperature schedule outlined above. - 41 - Adaptive Simulated Annealing (ASA) Lester Ingber As a useful physical guide, the temperature is further parameterized in terms of quantities m_i and n_i, derived from an "expected" final temperature (which is not enforced in ASA), T_fi, T_fi = T_0i exp(-m_i) when k_fi = exp(n_i), c_i = m_i exp(-n_i/D). However, note that since the initial temperatures and generating indices, T_0i and k_i, are independently scaled for each parameter, it usually is reasonable to simply take {c_i, m_i, n_i} to be independent of the index i, i.e., to be {c, m, n} for all i. In asa.c, m = -log(Temperature_Ratio_Scale). This can be overridden if RATIO_TEMPERATURE_SCALES (further discussed below) is set to TRUE, and then values of multipliers of -log(Temperature_Ratio_Scale) are used in asa.c. These multipliers are calculated in the user module as OPTIONS->User_Temperature_Ratio []. Then, m_i = m OPTIONS->User_Temperature_Ratio[i]. For large numbers of parameters, Temperature_Ratio_Scale is a very influential Program Option in determining the scale of parameter annealing. It likely would be best to start with a larger value than the default, to slow down the annealing. The ASA-NOTES contain a section giving a little more explanation on the use of Temperature_Ratio_Scale. 9.3.9. OPTIONS->Cost_Parameter_Scale_Ratio[1.0] This is the ratio of cost:parameter temperature annealing scales. As explained in the ASA papers, and as outlined in the ASA-NOTES, this is used to set the rates of annealing. In terms of the algebraic development given above for the Temperature_Ratio_Scale, in asa.c, c_cost = c Cost_Parameter_Scale_Ratio. Cost_Parameter_Scale_Ratio is a very influential Program Option in determining the scale of annealing of the cost function. 9.3.10. OPTIONS->Temperature_Anneal_Scale[100.0] This scale is a guide to achieve the expected cost temperature sought by Temperature_Ratio_Scale within the limits expected by Limit_Acceptances. As explained in the ASA papers, and as outlined in the ASA-NOTES, this is used to set the rates of annealing. In terms of the algebraic development given above for the Temperature_Ratio_Scale, in asa.c, n = log(Temperature_Anneal_Scale). For large numbers of parameters, Temperature_Anneal_Scale probably should at least initially be set to values greater than - 42 - Adaptive Simulated Annealing (ASA) Lester Ingber *number_parameters, although it will not be as influential as Temperature_Ratio_Scale. 9.3.11. OPTIONS->User_Cost_Temperature If USER_INITIAL_COST_TEMP is TRUE, a pointer, OPTIONS->User_Cost_Temperature, is used to adaptively initialize the cost temperature. If this choice is elected, then User_Cost_Temperature [] must be initialized. 9.3.12. OPTIONS->Include_Integer_Parameters[FALSE] If Include_Integer_Parameters is TRUE, include integer parameters in derivative and reannealing calculations, except those with INTEGER_TYPE (2). This is useful when the parameters can be analytically continued between their integer values, or if you set the parameter increments to integral values by setting ASA_RESOLUTION to TRUE, as discussed further below. 9.3.13. OPTIONS->User_Initial_Parameters[FALSE] ASA always requests that the user guess initial values of starting parameters, since that guess is as good as any random guess the code might make. The default is to use the ASA distribution about this point to generate an initial state of parameters and value of the cost function that satisfy the user's constraints. If User_Initial_Parameters is set to TRUE, then the first user's guess is used to calculate this first state. 9.3.14. OPTIONS->Sequential_Parameters[-1] The ASA default for generating new points in parameter space is to find a new point in the full space, rather than to sample the space one parameter at a time as do most other algorithms. This is in accord with the general philosophy of sampling the space without any prior knowledge of ordering of the parameters. However, if you have reason to believe that at some stage(s) of search there might be some benefit to sampling the parameters sequentially, then set Sequential_Parameters to the parameter number you wish to start your annealing cycle, i.e., ranging from 0 to (*parameter_dimension - 1). Then, ASA will cycle through your parameters in the order you have placed them in all arrays defining their properties, keeping track of which parameter is actively being modified in OPTIONS->Sequential_Parameters, thereby permitting adaptive changes. Any negative value for Sequential_Parameters will use the default ASA algorithm. Upon exiting asa (), Sequential_Parameters is reset back to its initial value. 9.3.15. OPTIONS->Initial_Parameter_Temperature[1.0] The initial temperature for all parameters. This is overridden by use of the USER_INITIAL_PARAMETERS_TEMPS option. - 43 - Adaptive Simulated Annealing (ASA) Lester Ingber 9.3.16. OPTIONS->User_Temperature_Ratio If RATIO_TEMPERATURE_SCALES is TRUE, a pointer, OPTIONS->User_Temperature_Ratio, is used to adaptively set ratios of scales used to anneal the parameters in the cost function. This can be useful when some parameters are not being reannealed, or when setting the initial temperatures (using USER_INITIAL_PARAMETERS_TEMPS set to TRUE) is not sufficient to handle all your parameters properly. This typically is not encountered, so it is advised to look elsewhere at first to improve your search. If this choice is elected, then User_Temperature_Ratio [] must be initialized. 9.3.17. OPTIONS->User_Parameter_Temperature If USER_INITIAL_PARAMETERS_TEMPS is TRUE, a pointer, OPTIONS->User_Parameter_Temperature, is used to adaptively initialize parameters temperatures. If this choice is elected, then User_Parameter_Temperature [] must be initialized. 9.3.18. OPTIONS->Acceptance_Frequency_Modulus[100] The frequency of testing for periodic testing and reannealing, dependent on the number of accepted states. If Acceptance_Frequency_Modulus is set to 0, then this test is not performed. 9.3.19. OPTIONS->Generated_Frequency_Modulus[10000] The frequency of testing for periodic testing and reannealing, dependent on the number of generated states. If Generated_Frequency_Modulus is set to 0, then this test is not performed. 9.3.20. OPTIONS->Reanneal_Cost[1] A value of Reanneal_Cost set to FALSE=0 bypasses reannealing of the cost temperature. This might be done for systems where such reannealing is not useful. Note that the use of USER_REANNEAL_COST permits users to define their own cost temperature reannealing algorithm when Reanneal_Cost is not 0 or -1. A value of Reanneal_Cost = 1 permits the default reannealing of the cost temperature to be part of the fitting process, correlating the cost temperature with the current last and best values of the cost function as described above. If