×

zbMATH — the first resource for mathematics

The continuous reactive tabu search: Blending combinatorial optimization and stochastic search for global optimization. (English) Zbl 0851.90093
Summary: A novel algorithm for the global optimization of functions (C-RTS) is presented, in which a combinatorial optimization method cooperates with a stochastic local minimizer. The combinatorial optimization component, based on the reactive tabu search recently proposed by the authors, locates the most promising “boxes”, in which starting points for the local minimizer are generated. In order to cover a wide spectrum of possible applications without user intervention, the method is designed with adaptive mechanisms: the box size is adapted to the local structure of the function to be optimized, the search parameters are adapted to obtain a proper balance of diversification and intensification. The algorithm is compared with some existing algorithms, and the experimental results are presented for a variety of benchmark tasks.

MSC:
90C27 Combinatorial optimization
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] D.H. Ballard, C.A. Jelinek and R. Schinzinger, An algorithm for the solution of constrained generalized polynomial programming problems, Comp. J. 17(1974)261–266. · Zbl 0284.65053
[2] R. Battiti and G. Tecchiolli, Parallel biased search for combinatorial optimization: genetic algorithms and TABU, Microproc. Microsyst. 16(1992)351–367.
[3] R. Battiti and G. Tecchiolli, The reactive tabu search, ORSA J. Comp. 6(1994)126–140. · Zbl 0807.90094
[4] R. Battiti and G. Tecchiolli, Learning with first, second and no derivatives: A case study in high energy physics, Neurocomp. 6(1994)181–206. · Zbl 0812.68067
[5] R. Battiti and G. Tecchiolli, Training neural nets with the reactive tabu search, IEEE Trans. Neural Networks 6(1995)1185–1200. · Zbl 0843.90094
[6] R. Battiti, The reactive tabu search for machine learning, in:Proc. GAA ’93, Giornate dei Gruppi di Lavoro AI*AI, Apprendimento Automatico, Milan (1993).
[7] R. Battiti and G. Tecchiolli, Local search with memory: Benchmarking RTS, Preprint UTM, University of Trento, Italy (October, 1993), submitted. · Zbl 0843.90094
[8] R. Battiti and G. Tecchiolli, Simulated annealing and tabu search in the long run: A comparison on QAP tasks, Comp. Math. Appl. 28(6) (1994) 1–8. · Zbl 0812.68067
[9] G.L. Bilbro and W.E. Snyder, Optimization of functions with many minima, IEEE Trans. Syst., Man, Cybern. SMC-21(1991)840–849.
[10] C.G.E. Boender and A.H.G. Rinnooy Kan, Bayesian stopping rules for multistart global optimization methods, Math. Progr. 37(1987)59–80. · Zbl 0626.90079
[11] F.H. Branin, Jr., Widely convergent method for finding multiple-solutions of simultaneous nonlinear equations, IBM J. Res. Develop. (September 1992) 504–522. · Zbl 0271.65034
[12] R. Brunelli and G. Tecchiolli, On random minimization of functions, Biol. Cybern. 65(1991)501–506.
[13] R. Brunelli and G. Tecchiolli, Stochastic minimization with adaptive memory, J. Comp. Appl. Math. 57(1995)329–343. · Zbl 0823.65057
[14] R. Brunelli, On training neural nets through stochastic minimization, Neural Networks (1994).
[15] L.C.W. Dixon and G.P. Szego (eds.),Towards Global Optimization 2 (North-Holland, 1978).
[16] S. Fanelli and A. Ramponi, Computational experience with a multistart algorithm for global optimization based on new Bayesian stopping rules, in:Proc. 14th Symp. A.M.A.S.E.S., Pescara (September 1990).
[17] M.R. Garey and D.S. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, 1979). · Zbl 0411.68039
[18] F. Glover, Tabu search – Part I, ORSA J. Comp. 1(1989)190–206.
[19] F. Glover, Tabu search – Part II, ORSA J. Comp. 2(1990)4–32.
[20] A.A. Goldstein and I.F. Price, On descent from local minima, Math. Comp. 25 (July 1971). · Zbl 0223.65020
[21] G.H. Golub and C.F. Van Loan,Matrix Computations, 2nd ed. (The Johns Hopkins University Press, 1990). · Zbl 1118.65316
[22] E. Hansen,Global Optimization Using Interval Analysis (Marcel Dekker, 1992). · Zbl 0762.90069
[23] J.K. Hartman, Technical Report NP55HH72051A, Naval Postgraduate School, Monterey, CA (1972).
[24] J.H. Holland,Adaptation in Natural and Artificial Systems. An Introductory Analysis with Applications to Biology, Control, Artificial Intelligence (University of Michigan Press, 1975). · Zbl 0317.68006
[25] A.V. Levy, A. Montalvo, S. Gomez and A. Galderon,Topics in Global Optimization, Lecture Notes in Mathematics No. 909 (Springer, 1981).
[26] A.V. Levy and S. Gomez, The tunneling method applied to global optimization, in:Numerical Optimization 1984, ed. P.T. Boggs, R.H. Bryd and R.B. Schnabel (SIAM Publications, 1985) pp. 213–244.
[27] S. Kirkpatrick, C.D. Gelatt and M.P. Vecchi, Optimization by simulated annealing, Science 220(1983)671–680. · Zbl 1225.90162
[28] D.E. Knuth,The Art of Computer Programming, Vol. 3:Sorting and Searching (Addison-Wesley, 1973). · Zbl 0191.17903
[29] H.J. Kushner, A new method of locating the maximum of an arbitrary multipeak curve in the presence of noise, in:Proc. Joint Automatic Control Conf. (1963).
[30] W.L. Price, Global optimization by controlled random search, J. Optim. Theory Appl. 40(1983)333–348. · Zbl 0494.90063
[31] W.L. Price, Global optimization algorithms for a CAD workstation, J. Optim. Theory Appl. 55(1987)133–146. · Zbl 0622.90073
[32] F.J. Solis and R.J-B Wets, Minimization by random search techniques, Math. Oper. Res. 6(1981)19–30. · Zbl 0502.90070
[33] R.G. Strongin and Y.D. Sergeyev, Global multidimensional optimization on parallel computers, Parallel Comp. 18(1992)1259–1273. · Zbl 0766.65052
[34] B.E. Stuckman, A global search method for optimizing nonlinear systems, IEEE Trans. Syst., Man, Cybern., SMC-18(1988)965–977. · Zbl 0673.65034
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.