×

A hybrid method combining continuous tabu search and Nelder–Mead simplex algorithms for the global optimization of multiminima functions. (English) Zbl 1071.90035

Summary: Tabu search (TS) is a metaheuristic, which proved efficient to solve various combinatorial optimization problems. However, few works deal with its application to the global minimization of functions depending on continuous variables. To perform this task, we propose an hybrid method combining tabu search and simplex search (SS). TS allows to cover widely the solution space, to stimulate the search towards solutions far from the current solution, and to avoid the risk of trapping into a local minimum. SS is used to accelerate the convergence towards a minimum. The Nelder-Mead simplex algorithm is a classical very powerful local descent algorithm, making no use of the objective function derivatives. A “simplex” is a geometrical figure consisting, in \(n\)-dimensions, of \((n+1)\) points. If any point of a simplex is taken as the origin, the \(n\) other points define vector directions that span the \(n\)-dimension vector space. Through a sequence of elementary geometric transformations (reflection, contraction and extension), the initial simplex moves, expands or contracts. To select the appropriate transformation, the method only uses the values of the function to be optimized at the vertices of the simplex considered. After each transformation, the current worst vertex is replaced by a better one. Our algorithm called continuous tabu simplex search (CTSS) implemented in two different forms (CTSS\(_{\text{single}}\), CTSS\(_{\text{multiple}})\) is made up of two steps: first, an adaptation of TS to continuous optimization problems, allowing to localize a “promising area”; then, intensification within this promising area, involving SS. The efficiency of CTSS is extensively tested by using analytical test functions of which global and local minima are known. A comparison is proposed with several variants of tabu search, genetic algorithms and simulated annealing. CTSS is applied to the design of a eddy current sensor aimed at non-destructive control.

MSC:

90C27 Combinatorial optimization
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Battiti, R.; Tecchiolli, G., The continuous reactive tabu search: blending combinatorial optimization and stochastic search for global optimization, Annals of operations research, 63, 53-188, (1996) · Zbl 0851.90093
[2] Bilbro, G.L.; Snyder, W.E., Optimization of functions with many minima, IEEE transactions on systems, man, and cybernetics, 21, 4, 840-849, (1991)
[3] Bland, J.A., Nonlinear optimization of constrained functions using tabu search, International journal of mathematical education, science and technology, 24, 5, 741-747, (1993) · Zbl 0807.90102
[4] Bland, J.A., A derivative-free exploratory tool for function minimization based on tabu search, Advances in engineering software, 19, 91-96, (1994)
[5] Chelouah, R.; Siarry, P., Enhanced continuous tabu search: an algorithm for the global optimization of multiminima functions, (), 49-61, (Chapter 4) · Zbl 1073.90578
[6] Chelouah, R.; Siarry, P., A continuous genetic algorithm designed for the global optimization of multimodal functions, Journal of heuristics, 6, 2, 191-213, (2000) · Zbl 0969.68641
[7] Chelouah, R.; Siarry, P., Genetic and nelder – mead algorithms hybridized for a more accurate global optimization of continuous multiminima functions, European journal of operational research, 148, 335-348, (2003) · Zbl 1035.90062
[8] Cvijovic, D.; Klinowski, J., Taboo search. an approach to the multiple minima problem, Science, 667, 664-666, (1995) · Zbl 1226.90101
[9] Dixon, L.C.W.; Szegö, G.P., Towards global optimization, vol. 2, (1978), North-Holland Amsterdam · Zbl 0385.00011
[10] Glover, F., Tabu search. part I, ORSA journal on computing, 1, 3, 190-206, (1989) · Zbl 0753.90054
[11] Glover, F., Tabu search. part II, ORSA journal on computing, 2, 1, 4-32, (1990) · Zbl 0771.90084
[12] Hu, N., Tabu search method with random moves for globally optimal design, International journal for numerical methods in engineering, 35, 1055-1070, (1992)
[13] Nelder, J.A.; Mead, R., A simplex method for function minimization, The computer journal, 7, 308-313, (1965) · Zbl 0229.65053
[14] Press, W.H.; Flanery, B.P.; Teukolsky, S.A.; Vatterling, W.T., Numerical recipes in C, The art of science computing, (1988), Cambridge University Press New York
[15] Press, W.H.; Teukolsky, S.A., Simulated annealing optimization over continuous spaces, Computer in physics, Jul/Aug, 427-429, (1991)
[16] Renders, J.M.; Flasse, S.P., Hybrid method using genetic algorithms for the global optimization, IEEE transactions on systems, man, and cybernetics, 26, 2, 243-258, (1996)
[17] Schittkowski, K.; Hock, W., Test examples for nonlinear programming codes, Lecture notes in economics math. syst, vol. 187, (1981), Springer-Verlag · Zbl 0452.90038
[18] Schittkowski, K.; Hock, W., More test examples for nonlinear programming codes, Lecture notes in economics math. syst, vol. 282, (1987), Springer-Verlag · Zbl 0393.90072
[19] Siarry, P.; Berthiau, G., Fitting of tabu search to optimize functions of continuous variables, International journal for numerical methods in engineering, 40, 2449-2457, (1997) · Zbl 0882.65049
[20] Siarry, P.; Berthiau, G.; Durbin, F.; Haussy, J., Enhanced simulated annealing for globally minimizing functions of many continuous variables, ACM transactions of mathematical software, 23, 2, 209-228, (1997) · Zbl 0887.65067
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.