×
Chelouah, Rachid; Siarry, Patrick

Genetic and Nelder–Mead algorithms hybridized for a more accurate global optimization of continuous multiminima functions. (English) Zbl 1035.90062

Eur. J. Oper. Res. 148, No. 2, 335-348 (2003).
Summary: A hybrid method combining two algorithms is proposed for the global optimization of multiminima functions. To localize a “promising area”, likely to contain a global minimum, it is necessary to well “explore” the whole search domain. When a promising area is detected, the appropriate tools must be used to “exploit” this area and obtain the optimum as accurately and quickly as possible. Both tasks are hardly performed through only one method. We propose an algorithm using two processes, each one devoted to one task. Global metaheuristics, such as simulated annealing, tabu search, and genetic algorithms (GAs) are efficient to localize the “best” areas. On the other hand, local search methods are classically available: in particular the hill climbing (e.g. the quasi-Newton method), and the Nelder-Mead simplex search. Therefore we worked out an hybrid method, called continuous hybrid algorithm (CHA), performing the exploration with a GA, and the exploitation with a Nelder-Mead SS. To evaluate the efficiency of CHA, we implemented a set of benchmark functions, and compared our results to the ones supplied by other competitive methods.

Cited in 39 Documents

MSC:

90C26 Nonconvex programming, global optimization
90C59 Approximation methods and heuristics in mathematical programming

Keywords:

Genetic algorithm; Simplex search; Global optimization; Continuous variables; Multiminima functions

Software:

GAToolBox
Cite Review PDF
Full Text: DOI

References:

[1] Baker, J. E., Reducing bias and inefficiency in the selection algorithm, (Proceedings of the Second International Conference on Genetic Algorithms and their Applications, New Jersey, USA (1985))
[2] 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
[3] Berthiau, G.; Siarry, P., A genetic algorithm for globally minimizing functions of several continuous variables, (Second International Conference on Meta-heuristics, Sophia-Antipolis, France (July 1997)) · Zbl 0882.65049
[4] Bilbro, G. L.; Snyder, W. E., Optimization of functions with many minima, IEEE Transactions on Systems, Man, and Cybernetics, 21, 4, 840-849 (1991)
[5] Chelouah, R.; Siarry, P., Tabu search applied to global optimization, European Journal of Operational Research, 123/2, 30-44 (2000), Special issue on combinatorial optimization · Zbl 0969.68641
[6] Chelouah, R.; Siarry, P., A continuous genetic algorithm designed for the global optimization of multimodal functions, Journal of Heuristics, 6, 191-213 (2000) · Zbl 0969.68641
[7] Chelouah, R.; Siarry, P.; Berthiau, G.; DeBarmon, B., An optimization method fitted for model inversion in non-destructive control by eddy currents, European Physical Journal Applied Physics, 12, 231-238 (2000)
[8] A.J. Chipperfield, P.J. Fleming, H. Pohlheim, C.M. Fonseca, Genetic Algorithm Toolbox User’s Guide, ACSE Research Report No. 512, University of Sheffield, 1994; A.J. Chipperfield, P.J. Fleming, H. Pohlheim, C.M. Fonseca, Genetic Algorithm Toolbox User’s Guide, ACSE Research Report No. 512, University of Sheffield, 1994
[9] Cvijovic, D.; Klinowski, J., Taboo search. An approach to the multiple minima problem, Science, 667, 664-666 (1995) · Zbl 1226.90101
[10] K.A. De Jong, An analysis of the behavior of a class of genetic adaptive systems, University of Michigan, Ann Arbor, MI, Ph.D. thesis, 1975; K.A. De Jong, An analysis of the behavior of a class of genetic adaptive systems, University of Michigan, Ann Arbor, MI, Ph.D. thesis, 1975
[11] Durand, N.; Alliot, J. M., A combined Nelder-Mead simplex and genetic algorithm, (Banzhaf, W.; Daida, J.; Eiben, A. E.; Garzon, M. H.; Honavar, V.; Jakiela, M.; Smith, R. E., Proceedings of the Genetic and Evolutionary Computation Conference GECCO’99 (1999), Morgan Kaufmann: Morgan Kaufmann Orlando, FL, USA), 1-7
[12] Goldberg, D. E., Genetic Algorithms in Search, Optimization, and Machine learning (1989), Addison-Wesley · Zbl 0721.68056
[13] Holland, J. H., Outline for logical theory of adaptive systems, Journal of ACM, 3, 297-314 (1962) · Zbl 0225.68044
[14] J.H. Holland, Adaptation in natural and artificial systems, University of Michigan Press, Ann Arbor, MI, Internal report, 1975; J.H. Holland, Adaptation in natural and artificial systems, University of Michigan Press, Ann Arbor, MI, Internal report, 1975 · Zbl 0317.68006
[15] J.A. Joines, M.G. Kay, R.E. King, A hybrid-genetic algorithm for manufacturing cell design. Technical Report NCSU-IE, Department of Industrial Engineering, North Carolina State University, Box 7906 Raleigh, NC 27695-7906, February 1997; J.A. Joines, M.G. Kay, R.E. King, A hybrid-genetic algorithm for manufacturing cell design. Technical Report NCSU-IE, Department of Industrial Engineering, North Carolina State University, Box 7906 Raleigh, NC 27695-7906, February 1997
[16] Michalewicz, Z., Genetic \(Algorithms+ DataStructures= Evolution\) Programs (1996), Springer-Verlag: Springer-Verlag Heidelberg · Zbl 0841.68047
[17] Mühlenbein, H., Evolution in time and space-the parallel genetic algorithm, (Rawlins, G., Foundations of Genetic Algorithms (1991), Morgan-Kaufman), 316-337
[18] Mühlenbein, H.; Schomish, M.; Born, J., The Parallel Genetic Algorithm as function optimizer, (Proceedings of the Fourth International Conference on Genetic Algorithms, San Diego, CA (1991)), 271-278 · Zbl 0735.65040
[19] H. Mühlenbein, D. Schlierkamp-Voosen, Analysis of Selection, Mutation and Recombination in Genetic Algorithms, Technical Report 93/94, GMD, 1993; H. Mühlenbein, D. Schlierkamp-Voosen, Analysis of Selection, Mutation and Recombination in Genetic Algorithms, Technical Report 93/94, GMD, 1993
[20] Nelder, J. A.; Mead, R., A simplex method for function minimization, The Computer Journal, 7, 308-313 (1965) · Zbl 0229.65053
[21] Press, W. H.; Flanery, B. P.; Teukolsky, S. A.; Vatterling, W. T., Numerical Recipes in C, The Art of Science Computing (1988), Cambridge UP: Cambridge UP New York · Zbl 0661.65001
[22] (Reeves, C. R., Modern Heuristic Techniques for Combinatorial Problems Advanced Topics in Computer Science (1995), McGraw-Hill), Chapter 4
[23] 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)
[24] K. Schittkowski, W. Hock, Test examples for nonlinear programming codes, Lecture Notes in Economics Math. Syst., vol. 187, Springer-Verlag, 1981; K. Schittkowski, W. Hock, Test examples for nonlinear programming codes, Lecture Notes in Economics Math. Syst., vol. 187, Springer-Verlag, 1981 · Zbl 0452.90038
[25] 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
[26] Siarry, P.; Berthiau, G.; Durbin, F.; Haussy, J., Enhanced simulated annealing for globally minimizing functions of many continuous variables, ACM Transactions on Mathematical Software, 23, 2, 209-228 (1997) · Zbl 0887.65067
[27] Törn, A. A.; Zilinskas, A., Global optimization, (Goos, G.; Hartmanis, J., Lecture Notes in Computer Science, vol. 350 (1989), Springer-Verlag) · Zbl 0752.90075
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.