Minimizing multimodal functions of continuous variables with the “simulated annealing” algorithm

ABSTRACT

A new global optimization algorithm for functions of continuous variables is presented, derived from the “Simulated Annealing” algorithm recently introduced in combinatorial optimization. The algorithm is essentially an iterative random search procedure with adaptive moves along the coordinate directions. It permits uphill moves under the control of a probabilistic criterion, thus tending to avoid the first local minima encountered. The algorithm has been tested against the Nelder and Mead simplex method and against a version of Adaptive Random Search. The test functions were Rosenbrock valleys and multiminima functions in 2,4, and 10 dimensions. The new method proved to be more reliable than the others, being always able to find the optimum, or at least a point very close to it. It is quite costly in term of function evaluations, but its cost can be predicted in advance, depending only slightly on the starting point.

REFERENCES

• 1: BARABINO, G. P,, BARABINO, G. S., BIANCO, B., AND MARCHESI, M. A study on the performances of simplex methods for function minimization. In Proceedings of the IEEE International Conference on Circuits and Computers ICCC 80 IEEE, New York, 1980, 1150-1153.
• 2: DIXON, L. C. W., AND SZEGO, G. P. (EDS.) Toward Global Optimization. North-Holland, Amsterdam, 1975.
• 3: DIXON, L. C. W., AND SZEGO, G. e. (EDS.) Toward Global Optimization 2. North-Holland, Amsterdam, 1978.
• 4: FLETCHER, R., AND POWELL, M. J.D. A rapidly convergent descent method for minimization. Comput. J. 6 (1963), 163-168.
• 5: FLETCHER, R., AND REEVES, C.M. Function minimization by conjugate gradients. Comput. J. (1964), 149-154.
• 6: Kenneth E. Hillstrom, A Simulation Test Approach to the Evaluation of Nonlinear Optimization Algorithms, ACM Transactions on Mathematical Software (TOMS), v.3 n.4, p.305-315, Dec. 1977 [doi>10.1145/355759.355760]
• 7: Robert Hooke , T. A. Jeeves, `` Direct Search'' Solution of Numerical and Statistical Problems, Journal of the ACM (JACM), v.8 n.2, p.212-229, April 1961 [doi>10.1145/321062.321069]
• 8: KIRKPATRICK, S., GELATT, C. D., JR., AND VECCHI, M.P. Optimization by simulated annealing. Science 220, 4598 (May 1983), 671-680.
• 9: MASR}, S. F., BEKEY, G. A., AND SAFFORD, F.B. A global optimization algorithm using adaptive random search. Appl. Math. Comput. 7 (1980), 353-375.
• 10: METROPOLIS, N., ROSENBLUTH, A., ROSENBLUTH, M., TELLER, A., AND TELLER, E. Equation of state calculations by fast computing machines. J. Chem. Phys. 21 (1953), 1087-1090.
• 11: NELDER, J. A., AND MEAD, R. A simplex method for function minimization. Comput. J. 7 (1965), 308-313.
• 12: OREN, S. S. Self-scaling variable metric (SSVM) algorithms, part II: implementation and experiments. Manage. Sci. (Theor.) 20 (1974), 845-862.
• 13: PRICE, W. L. A controlled random search procedure for global optimization. Coraput. J. 20 (1977), 367-370.
• 14: Luc Pronzato , Eric Walter , Alain Venot , Jean-Francois Lebruchec, A general-purpose global optimizer: implementation and applications, Mathematics and Computers in Simulation, v.26 n.5, p.412-422, Oct. 1984 [doi>10.1016/0378-4754(84)90105-8]
• 15: ROMEO, F., SANGIOVANNI VINCENTELL|, A., AND SECHEN, C. Research on simulated annealing at Berkeley. In Proceedings of the IEEE International Conference on Computer Design, ICCD 84, IEEE New York, 1984, 652-657.
• 16: ROSENBROCK, H.H. An automatic method for finding the greatest or least value of a function. Comput. J. 3 (1960), 175-184.
• 17: SHAH, R. V., BUEHLER, R. J., AND KEMPTHORNE, O. Some algorithms for minimizing a function of several variables. SIAM J. 12 (1964), 74-92.
• 18: WHITE, S.R. Concepts of scale in simulated annealing. In Proceedings of the IEEE International Con{erence on Computer Design, ICCD 84, New York 1984, 646-651.

INDEX TERMS

Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Nonlinear programming
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Certification and testing

General Terms:
Algorithms, Performance