Newsgroups: comp.parallel From: Chen Loon-Been Subject:Simulate Annealing Date: Sat, 5 Nov 1994 15:23:04 GMT Message-ID:<39a1sa$srs@news.csie.nctu.edu.tw> Is their any guarantee of approximate solution found by Simulated Annealing Algorithm ? Chen Loon-Been ---------------------------------------------------------------------------- Newsgroups: comp.parallel From: grwy0@cc.usu.edu (Fu-Hsieng A. Lee, X2845, EE, USU) Subject: RE: Simulated Annealing Organization: Utah State University Date: Wed, 9 Nov 1994 20:55:41 GMT Hi There: Yes, SA does quarantee something! The probability of resulting in the minimal solution set is reversely proportional to the total number of iterations performed to the power of a constant. Prob[Xn not in Emin] follows (1/n)^k , Xn = result after n iter, Emin = min set, k = a constant Ref: R. Azencott, Simulated Annealing: Parallelization Technique, John Wiley & Sons, Inc. 1992. F. H. Lee, G. S. Stiles, and V. Swaminathan, "Parallel Annealing on Distributed Memory Systems", Proc. 2nd Int'l Conf. on Software for Multiprocessors and Supercomputers: Theory, Practice, Experience, Moscow, 09, 1994. F. H. Lee fhl@multi.ee.usu.edu ---------------------------------------------------------------------------- Newsgroups: comp.parallel From: Jan Vorbrueggen Subject: Re: Simulate Annealing In-Reply-To: 's message of Sat, 5 Nov 1994 15:23:04 GMT Organization: Institut fuer Neuroinformatik, Ruhr-Universitaet Bochum, Germany Date: Tue, 8 Nov 1994 02:50:15 GMT In article <39a1sa$srs@news.csie.nctu.edu.tw> writes: > Is their any guarantee of approximate solution found by Simulated > Annealing Algorithm ? Yes. If you cool infinitely slowly from an infinite startin temperature, you're guaranteed to find the global minimum of your goal function. Noce theoretically, but not very useful in practice...proper setting of parameters to get both decent performance and results remains a black art. Jan ---------------------------------------------------------------------------- Newsgroups: comp.parallel From: Lester Ingber Subject: Re: Simulate Annealing Organization: California Institute of Technology, Alumni Association Date: Tue, 8 Nov 1994 02:46:25 GMT In article <39a1sa$srs@news.csie.nctu.edu.tw>, wrote: > Is their any guarantee of approximate solution found by Simulated > Annealing Algorithm ? > Chen Loon-Been Yes, but _only_ if proper annealing is performed consistent with the "proof" accompanying the particular algorithm. For example, the annealing proper for the standard Boltzmann algorithm requires a temperature schedule that is lowered logarithmically. This is so slow that in practice most users actually "quench" by using schedules that diminish at polynomial or even exponential rates. This leads to just another kind of "greedy" algorithm, but one that may compete well with other quasi-Newton algorithms for _some_ systems; however, there no longer is any statistical guarantee of convergence to the global optimal point. ASA has a proof that permits exponential schedules. The code and some papers can be obtained using instructions below. A 1993 paper also discusses annealing vs quenching, and how quenching sometimes can perform quite well: asa93_sapvt.ps.Z %A L. Ingber %T Simulated annealing: Practice versus theory %J Mathl. Comput. Modelling %V 18 %N 11 %D 1993 %P 29-57 ASA also now has "hooks" to insert parallel code, using some properties of the algorithm discussed in: smni92_mnn.ps.Z %A L. Ingber %T Generic mesoscopic neural networks based on statistical mechanics of neocortical interactions %J Phys. Rev. A %V 45 %N 4 %P R2183-R2186 %D 1992 ======================================================================== Adaptive Simulated Annealing (ASA) ________________________________________________________________________ General Information The latest Adaptive Simulated Annealing (ASA) code and some related (p)reprints can be retrieved via anonymous ftp from ftp.alumni.caltech.edu [131.215.139.234] in the /pub/ingber directory. This archive also can be accessed via WWW path http://alumni.caltech.edu/~ingber/ or ftp://ftp.alumni.caltech.edu/pub/ingber/ Interactively [brackets signify machine prompts]: [your_machine%] ftp ftp.alumni.caltech.edu [Name (...):] anonymous [Password:] your_e-mail_address [ftp>] cd pub/ingber [ftp>] binary [ftp>] ls [ftp>] get file_of_interest [ftp>] quit The 00index file contains an index of the other files and information on getting gzip and unshar for DOS, MAC, UNIX, and VMS systems. The latest version of ASA, ASA-x.y (x and y are version numbers), can be obtained in several formats. ASA-shar.Z is a compress'd shar'd file of the current code. For the convenience of users who do not have any uncompress/gunzip utility, there is a file ASA-shar which is an uncompress'd copy of ASA-shar.Z; if you do not have sh or shar, you still can delete the first-column X's and separate the files at the END_OF_FILE locations. There are tar'd versions in compress and gzip format, ASA.tar.Z and ASA.tar.gz, respectively. There also is a current zip'd version, ASA.zip, in which all files have been processed through unix2dos. Directory /pub/ingber/0lower.dir contains links to these files for some PC users who may have difficulty with upper case. If you do not have ftp access, get information on the FTPmail service by: mail ftpmail@decwrl.dec.com, and send only the word "help" in the body of the message. If any of the above are not possible, and if your mailer can handle large files (please test this first), the code or papers you require can be sent as uuencoded compressed files via electronic mail. If you have gzip, resulting in smaller files, please state this. Sorry, I cannot assume the task of mailing out hardcopies of code or papers. My volunteer time assisting people with their queries on my codes and papers must be limited to electronic mail correspondence. To get on or off the ASA_list e-mailings, just send an e-mail to asa-request@alumni.caltech.edu with your request. Update notices are sent to the ASA_list about every month or two, more frequently if warranted, e.g., in cases of important bug fixes; these notices are the only e-mail sent to the ASA_list. +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Parallelizing ASA and PATHINT Project (PAPP) See the file parallel.txt in /pub/ingber/MISC.DIR +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ Lester -- [[ Prof. Lester Ingber ]] [[ Lester Ingber Research E-Mail: ingber@alumni.caltech.edu ]] [[ P.O. Box 857 WWW: http://alumni.caltech.edu/~ingber/ ]] [[ McLean, VA 22101 Archive: ftp.alumni.caltech.edu:/pub/ingber/ ]] ----------------------------------------------------------------------------