Shuffled complex evolution approach for effective and efficient global minimization. (English) Zbl 0792.90065

Duan, Q. Y.; Gupta, V. K.; Sorooshian, S.

J. Optimization Theory Appl. 76, No. 3, 501-521 (1993).

Summary: The degree of difficulty in solving a global optimization problem is in general dependent on the dimensionality of the problem and certain characteristics of the objective function. This paper discusses five of these characteristics and presents a strategy for function optimization called the shuffled complex evolution (SCE) method, which promises to be robust, effective, and efficient for a broad class of problems. The SCE method is based on a synthesis of four concepts that have proved successful for global optimization: (a) combination of probabilistic and deterministic approaches; (b) clustering; (c) systematic evolution of a complex of points spanning the space, in the direction of global improvement; and (d) competitive evolution. Two algorithms based on the SCE method are presented. These algorithms are tested by running 100 randomly initiated trials on eight test problems of differing difficulty. The performance of the two algorithms is compared to that of the controlled random search CRS2 method presented by W. L. Price [J. Optimization Theory Appl. 40, 333-348 (1983; Zbl 0513.90070); ibid. 55, 133-146 (1987; Zbl 0622.90073)] and to a multistart algorithm based on the simplex method presented by J. A. Nelder and R. Mead [Computer J. 7, 308-313 (1965; Zbl 0229.65053)].

MSC:

90C30

Nonlinear programming

Keywords:

numerical optimization; global search; efficiency; effectiveness; complex of points; random search; global optimization; shuffled complex evolution; clustering; competitive evolution

References:

[1]	Dixon, L. C. W., andSzegö, G. P., Editors,Toward Global Optimization 2, North-Holland, Amsterdam, Holland, 1978.
[2]	Dixon, L. C. W., andSzegö, G. P.,The Global Optimization Problem: An Introduction, Toward Global Optimization 2, Edited by L. C. W. Dixon and G. P. Szegö, North-Holland, Amsterdam, Holland, pp. 1-15, 1978.
[3]	Torn, A., andZilinskas, A.,Global Optimization, Springer-Verlag, Berlin, Germany, 1989.
[4]	Sorooshian, S., Gupta, V. K., andFulton, J. L.,Evaluation of Maximum-Likelihood Parameter Estimation Techniques for Conceptual Rainfall-Runoff Models: Influence of Calibration Data Variability and Length on Model Credibility, Water Resources Research, Vol. 19, pp. 251-259, 1983. · doi:10.1029/WR019i001p00251
[5]	Gupta, V. K., andSorooshian, S.,Uniqueness and Observability of Conceptual Rainfall-Runoff Model Parameters: The Percolation Process Examined, Water Resources Research, Vol. 19, pp. 269-276, 1983. · doi:10.1029/WR019i001p00269
[6]	Gupta, V. K., andSorooshian, S.,The Automatic Calibration of Conceptual Catchment Models Using Derivative-Based Optimization Algorithms, Water Resources Research, Vol. 21, pp. 473-486, 1985. · doi:10.1029/WR021i004p00473
[7]	Duan, Q., Sorooshian, S., andGupta, V. K.,Effective and Efficient Global Optimization for Conceptual Rainfall-Runoff Models, Water Resources Research, Vol. 28, pp. 1015-1031, 1992. · doi:10.1029/91WR02985
[8]	Gomulka, J.,Deterministic Versus Probabilistic Approaches to Global Optimization, Toward Global Optimization 2, Edited by L. C. W. Dixon and G. P. Szegö, North-Holland, Amsterdam, Holland, pp. 19-29, 1978. · Zbl 0401.90087
[9]	Becker, R. W., andLago, G. V.,A Global Optimization Algorithm, Proceedings of the 8th Allerton Conference on Circuits and Systems Theory, Monticello, Illinois, pp. 3-12, 1970.
[10]	Törn, A.,A Search Clustering Approach to Global Optimization, Toward Global Optimization 2, Edited by L. C. W. Dixon and G. P. Szegö, North-Holland, Amsterdam, Holland, pp. 49-62, 1978.
[11]	Rinnooy-Kan, A. H. G., andTimmer, G. T.,Stochastic Global Optimization Methods, Part 1: Clustering Methods, Mathematical Programming, Vol. 39, pp. 27-56, 1987. · Zbl 0634.90066 · doi:10.1007/BF02592070
[12]	Price, W. L.,A Controlled Random Search Procedure for Global Optimization, Toward Global Optimization 2, Edited by L. C. W. Dixon and G. P. Szegö, North-Holland, Amsterdam, Holland, pp. 71-84, 1978.
[13]	Price, W. L.,Global Optimization by Controlled Random Search, Journal of Optimization Theory and Applications, Vol. 40, pp. 333-348, 1983. · Zbl 0494.90063 · doi:10.1007/BF00933504
[14]	Price, W. L.,Global Optimization Algorithms for a CAD Workstation, Journal of Optimization Theory and Applications, Vol. 55, pp. 133-146, 1987. · Zbl 0622.90073 · doi:10.1007/BF00939049
[15]	Holland, J. H.,Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor, Michigan, 1975. · Zbl 0317.68006
[16]	Nelder, J. A., andMead, R.,A Simplex Method for Function Minimization, Computer Journal, Vol. 7, pp. 308-313, 1965. · Zbl 0229.65053