Minimizing multimodal functions of continuous variables with the “simulated annealing” algorithm—Corrigenda for this article is available here

ACM Transactions on Mathematical Software - Tập 13 Số 3 - Trang 262-280 - 1987
Angelo Corana1, Michele Marchesi1, Claudio Martini1, Sandro Ridella1
1Istituto per i Circuiti Elettronici-C.N.R., Genoa, Italy

Tóm tắt

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.

Từ khóa


Tài liệu tham khảo

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 . 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.

DIXON L. C. W. AND SZEGO G. P. (EDS.) Toward Global Optimization. North-Holland Amsterdam 1975. DIXON L. C. W. AND SZEGO G. P. (EDS.) Toward Global Optimization. North-Holland Amsterdam 1975.

DIXON , L. C. W., AND SZEGO , G. e. (EDS.) Toward Global Optimization 2. North-Holland , Amsterdam , 1978 . DIXON, L. C. W., AND SZEGO, G. e. (EDS.) Toward Global Optimization 2. North-Holland, Amsterdam, 1978.

10.1093/comjnl/6.2.163

10.1093/comjnl/7.2.149

10.1145/355759.355760

10.1145/321062.321069

10.1126/science.220.4598.671

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 . 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.1063/1.1699114

10.1093/comjnl/7.4.308

10.1287/mnsc.20.5.845

10.1093/comjnl/20.4.367

10.1016/0378-4754(84)90105-8

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 . 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.

10.1093/comjnl/3.3.175

SHAH , R. V. , BUEHLER , R. J. , AND KEMPTHORNE , O . Some algorithms for minimizing a function of several variables . SIAM J. 12 ( 1964 ), 74 - 92 . SHAH, R. V., BUEHLER, R. J., AND KEMPTHORNE, O. Some algorithms for minimizing a function of several variables. SIAM J. 12 (1964), 74-92.

10.1063/1.34823

Thông tin
Thông tin xuất bản

ACM Transactions on Mathematical Software

Tập 13 Số 3

262-280

Thông tin tác giả