×

zbMATH — the first resource for mathematics

Experiments with new stochastic global optimization search techniques. (English) Zbl 0967.90086
Summary: In this paper several probabilistic search techniques are developed for global optimization under three heuristic classifications: simulated annealing, clustering methods and adaptive partitioning algorithms. The algorithms proposed here combine different methods found in the literature and they are compared with well-established approaches in the corresponding areas. Computational results are obtained on 77 small to moderate size (up to 10 variables) nonlinear test functions with simple bounds and 18 large size test functions (up to 400 variables) collected from literature.

MSC:
90C26 Nonconvex programming, global optimization
90B40 Search theory
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Moré JJ, Wu Z. Global smoothing and continuation for large-scale molecular optimization. Preprint MCS-P539-1095. Argonne National Laboratory, Illinois, 1995.
[2] Schoen, F., A wide class of test functions for global optimization, Journal of global optimization, 3, 133-137, (1993) · Zbl 0772.90072
[3] Gill, P.; Murray, W., Quasi-Newton methods for unconstrained optimization, Journal of institute of mathematics and its applications, 9, 91-108, (1972) · Zbl 0264.49026
[4] Fletcher, R.; Powell, M., A rapidly convergent descent method for minimization, Computer journal, 6, 163-168, (1963) · Zbl 0132.11603
[5] Armijo, L., Minimization of functions having Lipschitz continuous first partial derivatives, Pacific J. of mathematics, 16, 1-3, (1966) · Zbl 0202.46105
[6] Fletcher, R.; Reeves, C., Function minimization by conjugate gradients, Computer journal, 7, 149-154, (1964) · Zbl 0132.11701
[7] Beveridge G, Schechter R. Optimization: theory and practice. New York: Mc-Graw Hill, 1970. · Zbl 0205.21401
[8] Törn A. A search clustering approach to global optimization. In: Dixon LCW, Szegö GP, editors. Towards global optimization 2. Amsterdam: North-Holland, 1978. · Zbl 0392.90073
[9] Price WL. A controlled random search procedure for global optimization. In: Dixon LCW, Szegö GP, editors. Towards global optimization 2. Amsterdam: North-Holland, 1978.
[10] Rinnooy Kan, A.H.G.; Timmer, G.T., Stochastic methods for global optimization, American journal of mathematical management science, 4, 7-40, (1984) · Zbl 0556.90073
[11] Ali, M.M.; Storey, C., Topographical multi level single linkage, Journal of global optimization, 5, 349-358, (1994) · Zbl 0814.90102
[12] Törn, A.; Viitanen, S., Topographical global optimization using pre-sampled points, Journal of global optimization, 5, 267-276, (1994) · Zbl 0813.90108
[13] Kirkpatrick, A.; Gelatt Jr, C.D.; Vechi, M.P., Optimization by simulated annealing., 220, 671-680, (1983) · Zbl 1225.90162
[14] Dekkers, A.; Aarts, E., Global optimization and simulated annealing, Mathematical programming, 50, 367-393, (1991) · Zbl 0753.90060
[15] Ingber, L., Simulated annealing:practice versus theory, Journal of mathematical computer modelling, 18, 11, 29-57, (1994) · Zbl 0819.90080
[16] Frost R. Ensemble based simulated annealing, ftp.sdsc.edu/pub/sdsc/math/Ebsa, La Jolla. CA. University of California, San Diego, 1993.
[17] Wood GR. Multidimensional bisection and global minimization, Working Paper, New Zealand: University of Canterbury, 1985.
[18] Horst, R., A general class of branch and bound mehods in global optimization, with some new approaches for concave minimization, Journal of optimization theory and applications, 51, 271-291, (1986) · Zbl 0581.90073
[19] Csendes, T.; Pinter, J., The impact of accelerating tools on the interval subdivision algorithm for global optimization, European journal of operations research, 65, 314-320, (1993) · Zbl 0768.90068
[20] Caprani, O.; Gothaab, B.; Madsen, K., Use of real-valued local minimum in parallel interval global optimization, Interval computations, 3, 71-82, (1993) · Zbl 0829.65081
[21] Ratz D, Csendes T. On the selection of subdivision directions in interval branch and bound methods. Working Paper, Karlsruhe University, Institut für Angewandte Mathematik, Karlsruhe, Germany, 1994. · Zbl 0841.90116
[22] Streltsov S, Vakili P. Global optimization: Partitioned random search and optimal index policies. Working Paper. Manufacturing Engineering Department. Boston: Boston University, 1995.
[23] Pinter, J., Convergence qualification of adaptive partitioning algorithms in global optimization, Mathematical programming, 56, 343-360, (1992) · Zbl 0762.90071
[24] Kushner, H.J., A new method of locating the maximum point of an arbitrary multi-peak curve in the presence of noise, Transactions of ASME, series D, journal of basic engineering, 86, 97-105, (1964)
[25] Danilin YM, Piyavskii SA. On an algorithm for finding the absolute minimum, In: Theory of optimal solutions. Kiev: Institute of Cybernetics, 1967;25-37.
[26] Schubert, B.O., A sequential method seeking the global maximum of a function, SIAM journal of numerical analysis, 9, 379-388, (1972) · Zbl 0251.65052
[27] Strongin RG, Numerical methods for multiextremal problems. Moscow: Nauka, 1978.
[28] Zilinskas, A., Two algorithms for one-dimensional multimodal minimization, Optimization, 12, 53-63, (1981) · Zbl 0467.90058
[29] Wingo, D.R., Estimating the location of the Cauchy distribution by numerical global optimization, Communications in statistics part B. simulation and computation, 12, 201-212, (1983)
[30] Moore RE. Automatic error analysis in digital computation. Technical Report LMSD-48421, Lockheed Missiles and Space Division, Sunnyvale, CA, 1959.
[31] Moore RE. Methods and applications of interval analysis. Philadelpxhia: SIAM, 1979.
[32] Moore, R.E.; Ratschek, H., Inclusion functions and global optimization II, Mathematical programming, 41, 341-356, (1988) · Zbl 0644.90074
[33] Archetti, F.; Betro, B., A probabilistic algorithm for global optimization, Calcolo, 16, 335-343, (1979) · Zbl 0428.90064
[34] Mockus JB, Thiesis V, Zilinskas A. The application of Bayesian methods for seeking the extremum. In: Dixon LCW, Szego, GP, editors. Towards global optimization, vol. 2. Amsterdam: North-Holland, 1978;117-29.
[35] Boender CGE. The generalized multinomial distribution: a Bayesian analysis and applications, PhD dissertation. Erasmus University, Rotterdam, 1984.
[36] Ingber L. Adaptive simulated annealing (ASA): lessons learned. Control and Cybernetics, (Polish Journal), 1999, to appear. · Zbl 0860.93035
[37] Bilchev G, Parmee I. Inductive search. IEEE Transactions 1996;832-6.
[38] Özdamar L, Bozyel MA. The capacitated lot sizing problem with overtime decisions and setup times. Working Paper, Istanbul Kültür University, Dept of Computer Engineering. Istanbul. Turkey. 1996.
[39] Ozdamar, L.; Bozyel, M.A., Simultaneous lot sizing and loading of product families on parallel facilities of different classes, International journal of production research, 36, 1305-1324, (1998) · Zbl 0946.90549
[40] ”Ozdamar, L.; Birbil, I.S., A hybrid genetic algorithm for the capacitated lot sizing and loading problem, European journal of operational research, 110, 525-547, (1998) · Zbl 0948.90009
[41] Demirhan M, Özdamar L, Helvacioglu L, Birbil IS. A fractal partitioning algorithm (with fuzzy measures) for optimization. EUFIT ’97, September 1997, Aachen, Germany.
[42] Demirhan M, Özdamar L. A note on the use of fuzzy measures in adaptive partitioning algorithms for global optimization. IEEE Transactions on Fuzzy Systems 1999, to appear. · Zbl 0976.90124
[43] Pal, N.R.; Bezdek, J.C., Measuring fuzzy uncertainty., IEEE transactions on fuzzy systems, 2, 107-118, (1994)
[44] Pal NR, Pal, SK. Object-background segmentation using new definitions of entropy IEE Proceedings 136, pt. E. 1989;284-95.
[45] Deluca, A.; Termini, S., A definition of nonprobabilistic entropy in the setting of fuzzy sets theory, Information and control, 20, 301-312, (1972) · Zbl 0239.94028
[46] Ozdamar L, Demirhan M. Comparison of partition evaluation measures in an adaptive partitioning algorithm for global optimization. Fuzzy Sets and Systems 1999, to appear. · Zbl 0976.90124
[47] Press WH, Teukolsky SA, Vetterling WT, Flannery BP. Numerical recipes, The art of scientific computing. New York: Cambridge University Press, 1992.
[48] Androulakis, G.S.; Vrahatis, M.N., OPTAC: a portable software package for analyzing and comparing optimization methos by visualization, Journal of computational and applied mathematics, 72, 41-62, (1996) · Zbl 0857.65066
[49] Stenger, F., Computing the topological degree of a mapping in \(R\^{}\{n\}\), Numerical mathematics, 25, 23-38, (1975) · Zbl 0316.55007
[50] Botsaris, C.A., A curvilinear optimization method based upon iterative estimation of the eigensystem of the Hessian matrix, Journal of mathematical analysis and applications, 63, 396-411, (1978) · Zbl 0383.49024
[51] More, B.J.; Garbow, B.S., Hillstrom, K.E. testing unconstrained optimization, ACM transactions on mathematical software, 7, 17-41, (1981)
[52] Kearfott, B., An efficient degree-computation method for a generalized method of bisection, Numerical mathematics, 32, 109-127, (1979) · Zbl 0386.65016
[53] Schaffer JD. A study of control parameters affecting online performance of genetic algorithms for function optimization. Proceedings of the Third International Conference on Genetic Algorithms, 1989: 51-60.
[54] Srinivas, M.; Patnaik, L.M., Adaptive probabilities of crossover and mutation in genetic algorithms, IEEE transactions on systems, man and cybernetics, 24, 656-667, (1994)
[55] Michalewicz Z. Genetic algorithms − data structures = evolution programs. Berlin: Springer, 1994. · Zbl 0818.68017
[56] Rosenbrock HH. State-space and multivariable theory. London: Nelson, 1970.
[57] Levy AV, Montalvo A, Gomez S, Calderon A. Topics in Global Optimization. Lecture Notes in Mathematics, No. 909. Berlin: Springer, 1981. · Zbl 0473.65037
[58] Jansson C, Knüppel O. Numerical results for a self-validating global optimization method. Working Paper, No. 94.1, Technical University of Hamburg-Harburg, 1994.
[59] Schwefel H. Numerical optimization of computer models. New York: Wiley, 1991.
[60] Törn A, Zilinskas A. Global optimization. Lecture Notes in Computer Science. Berlin: Springer, 1989.
[61] Corana, A.; Marchesi, M.; Marini, C.; Ridella, S., Minimizing multimodal functions of continuous variables with the simulated annealing algorithm, ACM transactions of mathematical software, 13, 262-279, (1987) · Zbl 0632.65075
[62] Aluffi-Pentini, F.; Parisi, V.; Zirilli, F., Global optimization and stochastic differential equations, Journal of optimization theory and applications, 47, 1-16, (1985) · Zbl 0549.65038
[63] Breiman, L.; Cutler, A., A deterministic algorithm for global optimization, Mathematical programming, 58, 179-199, (1993) · Zbl 0807.90103
[64] Easom E. A survey of global optimization techniques. M Eng thesis, University of Louisville, Louisville, KY, 1990.
[65] Stuckman, B.E.; Easom, E.E., A comparison of Bayesian/sampling global optimization techniques, IEEE transactions on systems, man and cybernetics, 22, 1024-1032, (1992) · Zbl 0766.90070
[66] De Jong K. An analysis of the behaviour of a class of genetic adaptive systems. PhD thesis. University of Michigan, Ann Arbor, 1975.
[67] Wodrich M, Bilchev G. Cooperative distributed search: the ant’s way. Working Paper, University of Cape Town, South Africa, 1997. · Zbl 0890.90159
[68] Baluja S. Population-based incremental learning: a method for integrating genetic search based function optimization and competitive learning. Working Paper. CMU-CS-94-163, School of Computer Science, Carnegie Mellon University, 1994.
[69] Griewank, A.O., Generalized descent for global optimization, Journal of optimization theory and applications, 34, 11-39, (1981) · Zbl 0431.49036
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.