×

zbMATH — the first resource for mathematics

Comparison of partition evaluation measures in an adaptive partitioning algorithm for global optimization. (English) Zbl 0976.90124
Summary: An adaptive partitioning algorithm with random search is proposed to locate the global optimum of multimodal functions. Partitioning algorithms divide the feasible region into nonoverlapping partitions in order to restrict and direct the search to the most promising region expected to contain the global optimum. In such a scheme a partition evaluation measure is required to assess sub-regions in order to re-partition the most promising sub-region and intensify the search within that area. This study provides computational results on several classes of partition evaluation measures used in the assessment of samples taken from all partitions. Among the partition evaluation classes used in our comparison are fuzzy, statistical, and deterministic interval estimation measures. Performance in terms of solution quality is reported on an extensive set of 77 test functions collected from the literature.

MSC:
90C70 Fuzzy and other nonstochastic uncertainty mathematical programming
90C26 Nonconvex programming, global optimization
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ali, M.M.; Storey, C., Topographical multi-level single-linkage, J. global optim., 5, 349-358, (1994) · Zbl 0814.90102
[2] Aluffi-Pentini, F.; Parisi, V.; Zirilli, F., Global optimization and stochastic differential equations, J. optim. theory appl., 47, 1-16, (1985) · Zbl 0549.65038
[3] Archetti, F.; Betro, B., A probabilistic algorithm for global optimization, Calcolo, 16, 335-343, (1979) · Zbl 0428.90064
[4] L. Özdamar, M. Demirhan, Computational experiments with probabilistic search methods in global optimization, Working Paper, Istanbul Kültür University, Dept. of Computer Engineering, Istanbul, 1997.
[5] C.G.E. Boender, The generalized multinomial distribution: a Bayesian analysis and applications, Ph.D. Dissertation, Erasmus University, Rotterdam, 1984.
[6] Botsaris, C.A., A curvilinear optimization method based upon iterative estimation of the eigensystem of the Hessian matrix, J. math. anal. appl., 63, 396-411, (1978) · Zbl 0383.49024
[7] Breiman, L.; Cutler, A., A deterministic algorithm for global optimization, Math. programming, 58, 179-199, (1993) · Zbl 0807.90103
[8] Corana, A.; Marchesi, M.; Marini, C.; Ridella, S., Minimizing multimodal functions of continuous variables with the simulated annealing algorithm, ACM trans. math. software, 13, 262-279, (1987) · Zbl 0632.65075
[9] Y.M. Danilin, S.A. Piyavskii, On an algorithm for finding the absolute minimum, Theory of Optimal Solutions, Institute of Cybernetics, Kiev, 1967, pp. 25-37.
[10] K. De Jong, An analysis of the behaviour of a class of genetic adaptive systems, Ph.D. Thesis, University of Michigan, Ann Arbor, 1975.
[11] Dekkers, A.; Aarts, E., Global optimization and simulated annealing, Math. programming, 50, 367-393, (1991) · Zbl 0753.90060
[12] Deluca, A.; Termini, S., A definition of nonprobabilistic entropy in the setting of fuzzy sets theory, Inform. and control, 20, 301-312, (1972) · Zbl 0239.94028
[13] M. Demirhan, L. Özdamar, A note on the use of fuzzy measures in adaptive partitioning algorithms for global optimization, Working Paper, Istanbul Kültür University, Dept. of Computer Engineering, 1997.
[14] M. Demirhan, L. Özdamar, Ş.İ. Birbil, L. Helvacıoğlu, A fractal partitioning algorithm (with fuzzy measures) for optimization, Proc. EUFIT ‘97, Aachen, Germany, 1997. · Zbl 0961.90081
[15] E. Easom, A survey of global optimization techniques, Thesis, University of Louisville, Louisville, KY, 1990.
[16] Goldberg, D., Genetic algorithms in search, optimization and machine learning, (1989), Addison-Wesley Reading, MA · Zbl 0721.68056
[17] Horst, R.; Tuy, H., Global optimization-deterministic approaches, (1996), Springer Berlin · Zbl 0867.90105
[18] L. Ingber, Adaptive simulated annealing (ASA) Lessons learned, Control Cybernet. (Polish Journal) (1995). · Zbl 0860.93035
[19] Kan Rinnooy, A.H.G.; Timmer, G.T., Stochastic methods for global optimization, Amer. J. math. management sci., 4, 7-40, (1984) · Zbl 0556.90073
[20] Kaufmann, A., Introduction to the theory of fuzzy subsets, vol. 1, (1975), Academic New York · Zbl 0332.02063
[21] Kearfott, B., An efficient degree-computation method for a generalized method of bisection, Numer. math., 32, 109-127, (1979) · Zbl 0386.65016
[22] Kushner, H.J., A new method of locating the maximum point of an arbitrary multi-peak curve in the presence of noise, Trans. ASME, ser. D, J. basic eng., 86, 97-105, (1964)
[23] A.V. Levy, A. Montalvo, S. Gomez, A. Calderon, Topics in Global Optimization, Lecture Notes in Mathematics, No. 909, Springer, Berlin, 1981. · Zbl 0473.65037
[24] Michalewicz, Z., Genetic algorithms+data structures=evolution programs, (1994), Springer Berlin · Zbl 0818.68017
[25] Mockus, J.B.; Thiesis, V.; Zilinskas, A., The application of Bayesian methods for seeking the extremum, (), 117-129
[26] R.E. Moore, Automatic error analysis in digital computation, Technical Report LMSD-48421, Lockheed Missiles and Space Division, Sunnyvale, CA, 1959.
[27] Moore, R.E., Methods and applications of interval analysis, (1979), SIAM Philadelphia · Zbl 0417.65022
[28] Moore, R.E.; Ratschek, H., Inclusion functions and global optimization II, Math. programming, 41, 341-356, (1988) · Zbl 0644.90074
[29] More, B.J.; Garbow, B.S.; Hillstrom, K.E., Testing unconstrained optimization, ACM trans. math. software, 7, 17-41, (1981) · Zbl 0454.65049
[30] Pal, N.R.; Bezdek, J.C., Measuring fuzzy uncertainty, IEEE trans. fuzzy systems, 2, 107-118, (1994)
[31] N.R. Pal, S.K. Pal, Object-background segmentation using new definitions of entropy, IEE Proc. 136, pt. E (1989) 284-295.
[32] Pinter, J., Convergence qualification of adaptive partitioning algorithms in global optimization, Math. programming, 56, 343-360, (1992) · Zbl 0762.90071
[33] Pinter, J., Continuous global optimization softwarea brief review, Optima, the newsletter of the mathematical programming society, 52, 1-8, (1996)
[34] Press, W.H.; Teukolsky, S.A.; Vetterling, W.T.; Flannery, B.P., Numerical recipes, the art of scientific computing, (1992), Cambridge University Press New York · Zbl 0778.65002
[35] Price, W.L., A controlled random search procedure for global optimization, () · Zbl 0394.90092
[36] B. Ratz, T. Csendes, 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
[37] H.H. Rosenbrock, State-Space and Multivariable Theory, Nelson, London, 1970. · Zbl 0246.93010
[38] J.D. Schaffer, A study of control parameters affecting online performance of genetic algorithms for function optimization, Proc. of the 3rd Int. Conf. on Genetic Algorithms, 1989, pp. 51-60.
[39] Schubert, B.O., A sequential method seeking the global maximum of a function, SIAM J. numer. anal., 9, 379-388, (1972) · Zbl 0251.65052
[40] Schwefel, H., Numerical optimization of computer models, (1991), Wiley New York
[41] Srinivas, M.; Patnaik, L.M., Adaptive probabilities of crossover and mutation in genetic algorithms, IEEE trans. systems man cybernet., 24, 656-667, (1994)
[42] Stenger, F., Computing the topological degree of a mapping in \(R\^{}\{n\}\), Numer. math., 25, 23-38, (1975) · Zbl 0316.55007
[43] Strongin, R.G., Numerical methods for multiextremal problems, (1978), Nauka Moscow · Zbl 0458.65062
[44] Tang, Z.B., Adaptive partitioned random search to global optimization, IEEE trans. automat. control, 39, 2235-2244, (1994) · Zbl 0846.90102
[45] Törn, A., A search clustering approach to global optimization, () · Zbl 0392.90073
[46] Törn, A.; Viitanen, S., Topographical global optimization using pre-sampled points, J. global optim., 5, 267-276, (1994) · Zbl 0813.90108
[47] A. Törn, A. Zilinskas, Global Optimization, Lecture Notes in Computer Science, Springer, Berlin, 1989.
[48] Wingo, D.R., Estimating the location of the Cauchy distribution by numerical global optimization, Comm. statist. part B. simulation comput., 12, 201-212, (1983)
[49] Zilinskas, A., Two algorithms for one-dimensional multimodal minimization, Optimization, 12, 53-63, (1981) · Zbl 0467.90058
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.