A guided Monte Carlo search algorithm for global optimization of multidimensional functions?
UNSPECIFIED (1998) A guided Monte Carlo search algorithm for global optimization of multidimensional functions? In: American-Association-for-the-Advancement-of-Science Annual Meeting and Science Innovation Expo (AMSIE 95), FEB 16-21, 1995, ATLANTA, GA.Full text not available from this repository.
The high efficiency of the Monte Carlo optimization algorithm developed by Pulfer and Waine(14) is due to the discovery of a novel sampler that combines randomized guided step sizes with a random direction search strategy. We modified this algorithm to use a preset number of optimally sequenced steps to bound the randomly chosen step length. This has the effect of both spanning the response surface rapidly and escaping local optima efficiently. Coupled to changes in both sampling strategy and termination criteria, the resulting guided Monte Carlo (GMC) numerical search algorithm is shown to solve the global optimization problem effectively. Fifteen multidimensional benchmark test functions having differing characteristics such as numerous local optima or very sharp optima, very shallow optima, variables with differing influence over the function, and high dimensionality, were used to test the efficacy of the GMC algorithm. It was successful in solving them all, with a majority converging 100% of the time out of 1000 independent runs within highly competitive computer processing times when compared to contemporary efficient algorithms. For example, when the highly intractable five dimensional shekel function was-solved by Fagiuoli:et al.'s(20) sampling algorithm, it required 2514 function evaluations (f.e.) and 7. shekels of computer time to find the global optimum with a success rate of 900 out of 1000 independent runs, whereas the GMC algorithm needed only 519 f.e. and 1.66 shekels to achieve-the same accuracy with the same probability of success. A multirun routine has also been incorporated into the GMC algorithm to enable users to repeatedly test the response surface to achieve almost 100% certainty. Also, the GMC algorithm successfully solved the 100 dimensional cosine mixture test function, known to have numerous shallow local optima and one global optimum. This indicates its potential to solve practical problems such as those associated with protein configuration analysis.
|Item Type:||Conference Item (UNSPECIFIED)|
|Subjects:||Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software
Q Science > QD Chemistry
|Journal or Publication Title:||JOURNAL OF CHEMICAL INFORMATION AND COMPUTER SCIENCES|
|Publisher:||AMER CHEMICAL SOC|
|Number of Pages:||9|
|Page Range:||pp. 1087-1095|
|Title of Event:||American-Association-for-the-Advancement-of-Science Annual Meeting and Science Innovation Expo (AMSIE 95)|
|Location of Event:||ATLANTA, GA|
|Date(s) of Event:||FEB 16-21, 1995|
Actions (login required)