[Some typos corrected -- djr 1999/01 ] ============================================================================== Newsgroups: sci.math,sci.math.num-analysis,sci.math.research From: ingber@alumni.caltech.edu (Lester Ingber) Subject: Re: How to find significant maxima? Date: Mon, 17 Apr 1995 11:51:28 GMT Keywords: significant, maxima In article <1995Apr16.132534.23310@aristo.tau.ac.il>, Kup Konstantin wrote: : Hi, I am trying to get a references related :to the following 'vaguely defined' problems: :for a given real function f(x), x \in [a,b] : :(1) to find n the most significant maxima of f() ; :(n is a 'small' natural number) ; :(2) to find all significant maxima of f(). : :Any pointers to articles would be greatly appreciated. : :------------------------ :Konstantin Kupeev :e-mail : kup@math.tau.ac.il While the question is vague, it does arise quite often in many disciplines. If really not much at all is known about the function/process f, then I do not see much choice but to try some importance-sampling algorithm. Any global optimiation method applied to -f should be able to provide such sampling information. E.g., check out http://www.skypoint.com/subscribers/ashbury/nonlinear-programming-faq.html In ASA, there is an ASA_SAMPLE OPTIONS to collect all the biases and to effect such a sampling. However, as noted in the code, to sample lesser optima, the annealing schedules must be reduced to spend some time gathering information in these local minima. At least simulated annealing has an associated statistical proof that it will importance-sample your space, so that you should be able to get reasonably close to your goal of getting all maxima of f. After you have run such an algorithm for awhile, it would make sense to sit back and examine your data, with the hope of ascertaining/intuiting some knowledge of the nature of f, and then perhaps using some other algorithm more tailored to such a system. Lester ======================================================================== Adaptive Simulated Annealing ASA-7.4 ________________________________________________________________________ General Information Adaptive Simulated Annealing (ASA) is one of the most powerful optimization algorithms for nonlinear and stochastic systems. The latest 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. 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. 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. Lester ======================================================================== -- /* RESEARCH E-Mail: ingber@alumni.caltech.edu * * INGBER WWW: http://alumni.caltech.edu/~ingber * * LESTER Archive: ftp.alumni.caltech.edu:/pub/ingber * * Prof. Lester Ingber _ P.O. Box 857 _ McLean, VA 22101 _ 1.800.L.INGBER */ &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& From: engrand@clt13kk.phr () Newsgroups: sci.math.num-analysis Subject: Re: Simulated Annealing Date: 18 May 1995 09:23:02 GMT In article DLv@lut.ac.uk, R.Sheikhan@lut.ac.uk (R.Sheikhan) writes: > > Hi, > > Can anybody describe Simulated Annealing for Optimisatin please? > Let's minimize y=f(x) x in R^n, y in R Initialize x0, y0=f(x0) step n : Randomly go from xn to xn+1 Calculate yn+1=f(xn+1) If yn+1 < yn then Accept xn+1 If yn+1 > yn then Accept xn+1 with probability p=Exp(-(yn+1-yn)/T) where T is a temperature that you decrease regularly. If yn+1 is accepted, start from xn+1, If not, start again from xn You can see that in beginning of search you accept solutions that increase the objective function, and at the end, you only accept solutions that decrease it. Therefore you won't be caught in a local minima. This method is very efficient especially if f is non-linear. --- _________________________________________________________________ | Philippe Ch't' Engrand - EDF / DER / Physique des Reacteurs | | | | 'Tu bois cette merde ? Fais gouter.' - Breves de Comptoir | |_______________________________________________________________| &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&& From: Dennis Suchta Newsgroups: sci.math Subject: Re: simulated annealing Date: Tue, 17 Nov 1998 07:24:43 -0800 The general problem is to optimize a function. Choose a starting point, evaluate the function. Randomly change the point, reevaluate the function. If the function moves in the desired direction, accept the new point. If it doesnt, accept the new point with a probability dependent on the incremental change. The additional structure imposed is in the random change and the probability function. Generally you choose a sequence of neighborhoods that grow smaller as time progresses for the random change. The probability function started out to be the Boltzman distribution but can be any function with a time parameter that sharpens the function - as time progresses it becomes increasingly unlikely to choose a non-improving random step. This algorithm seems to have been replaced by Genetic Algorithms, which has a large literature. Dennis John McCarthy wrote: > Can anyone tell me or direct me to a paper or resources to educate me on > simulated annealing and how it could be used in the traveling salesman type > of problem. I hear the it is very fast and efficient. > > TIA > john-mccarthy@worldnet.att.net ============================================================================== From: graham_fyffe@hotmail.com Newsgroups: sci.math Subject: Re: simulated annealing Date: Tue, 17 Nov 1998 23:42:46 GMT In article <3651953B.BCE140C2@msn.com>, Dennis Suchta wrote: [quote of previous article deleted -- djr] Another way of doing it is like so: 1 - choose an initial point P and sample it 2 - choose an initial search radius R (usually somewhat larger than the radius of the search space you're interested in) 3 - sample a point Q selected randomly from a gaussian distribution centered around P with standard deviation R 4 - if Q did better than P, set P to Q 5 - decrease R a little bit using some time-dependant function as mentioned above 6 - repeat steps 3-6 until you're happy with the smallness of R, or you're happy with the current best value achieved. Too speed it up for simple cases, if you like, you can add step 4.5 which is to do a simple local minimum search using a quick gradient descent algorithm. You might use a probability function that starts at 100% and decreases with time for choosing whether or not to do this step, since it can interfere with the rest of the algorithm in complex cases. Note that this doesn't do well on really nastily discontinuous problems. Genetic algorithms might suit you better for those. - Graham -----------== Posted via Deja News, The Discussion Network ==---------- http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own ============================================================================== From: Lester Ingber Newsgroups: sci.math Subject: Re: simulated annealing Date: 18 Nov 1998 12:42:55 GMT In article <72ps4i$jf2@bgtnsc01.worldnet.att.net>, John McCarthy wrote: :Can anyone tell me or direct me to a paper or resources to educate me on :simulated annealing and how it could be used in the traveling salesman type :of problem. I hear the it is very fast and efficient. : :TIA :john-mccarthy@worldnet.att.net There are several variants of simulated annealing and some similar techniques. Try http://www.skypoint.com/subscribers/ashbury/nonlinear-programming-faq.html and http://plato.la.asu.edu/guide.html and http://solon.cma.univie.ac.at/~neum/glopt.html Code and reprints on Adpative Simulated Annealing (ASA) can be accessed via my homepage. ======================================================================== ASA is one of the most powerful optimization algorithms for nonlinear and stochastic systems. The latest code can be retrieved using these instructions. Interactively Via WWW The ASA archive can be accessed via WWW path http://www.ingber.com/ http://www.alumni.caltech.edu/~ingber/ [mirror homepage] Interactively Via Anonymous FTP Code and reprints can be 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 00index file contains an index of the other files. Files have the same WWW and FTP paths under the main / directory; e.g., http://www.ingber.com/MISC.DIR/00index_misc and ftp://ftp.ingber.com/MISC.DIR/00index_misc reference the same file. 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. ASA_list To get on or off the ASA_list send your request to either asa-request@ingber.com asa-request@alumni.caltech.edu 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. Additional Information Lester Ingber Research (LIR) develops projects in areas of expertise documented in the ingber.com InterNet archive. 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. Lester ======================================================================== -- /* Lester Ingber http://www.ingber.com/ ftp://ftp.ingber.com * * ingber@ingber.com ingber@alumni.caltech.edu ingber@drwtrading.com * * PO Box 06440 Wacker Dr PO Sears Tower Chicago IL 60606-0440 */