État de l'art des méthodes “d'optimisation globale”

Gérard Berthiau; Patrick Siarry

RAIRO - Operations Research (2010)

  • Volume: 35, Issue: 3, page 329-365
  • ISSN: 0399-0559

Abstract

top
We present a review of the main “global optimization" methods. The paper comprises one introduction and two parts. In the introduction, we recall some generalities about non linear constraint-less optimization and we list some classifications which have been proposed for the global optimization methods. We then describe, in the first part, various “classical" global optimization methods, most of which available long before the appearance of Simulated Annealing (a key event in this field). There exists plenty of papers and books dealing with these methods, and studying in particular their convergence properties. The second part of the paper is devoted to more recent or atypical methods, mostly issued from combinatorial optimization. The three main methods are “metaheuristics": Simulated Annealing (and derived techniques), Tabu Search and Genetic Algorithms; we also describe three other less known methods. For these methods, theoretical studies of convergence are less abundant in the literature, and the use of convergence results is by far more limited in practice. However, the fitting of some of these techniques to continuous variables problems gave very promising results; that question is not discussed in detail in the paper, but useful references allowing to deepen the subject are given.

How to cite

top

Berthiau, Gérard, and Siarry, Patrick. "État de l'art des méthodes “d'optimisation globale” ." RAIRO - Operations Research 35.3 (2010): 329-365. <http://eudml.org/doc/116597>.

@article{Berthiau2010,
abstract = { We present a review of the main “global optimization" methods. The paper comprises one introduction and two parts. In the introduction, we recall some generalities about non linear constraint-less optimization and we list some classifications which have been proposed for the global optimization methods. We then describe, in the first part, various “classical" global optimization methods, most of which available long before the appearance of Simulated Annealing (a key event in this field). There exists plenty of papers and books dealing with these methods, and studying in particular their convergence properties. The second part of the paper is devoted to more recent or atypical methods, mostly issued from combinatorial optimization. The three main methods are “metaheuristics": Simulated Annealing (and derived techniques), Tabu Search and Genetic Algorithms; we also describe three other less known methods. For these methods, theoretical studies of convergence are less abundant in the literature, and the use of convergence results is by far more limited in practice. However, the fitting of some of these techniques to continuous variables problems gave very promising results; that question is not discussed in detail in the paper, but useful references allowing to deepen the subject are given. },
author = {Berthiau, Gérard, Siarry, Patrick},
journal = {RAIRO - Operations Research},
keywords = {Global optimization; metaheuristics; convergence; continuous optimization.; continuous optimization; global optimization; simulated annealing; tabu search; genetic algorithms},
language = {fre},
month = {3},
number = {3},
pages = {329-365},
publisher = {EDP Sciences},
title = {État de l'art des méthodes “d'optimisation globale” },
url = {http://eudml.org/doc/116597},
volume = {35},
year = {2010},
}

TY - JOUR
AU - Berthiau, Gérard
AU - Siarry, Patrick
TI - État de l'art des méthodes “d'optimisation globale”
JO - RAIRO - Operations Research
DA - 2010/3//
PB - EDP Sciences
VL - 35
IS - 3
SP - 329
EP - 365
AB - We present a review of the main “global optimization" methods. The paper comprises one introduction and two parts. In the introduction, we recall some generalities about non linear constraint-less optimization and we list some classifications which have been proposed for the global optimization methods. We then describe, in the first part, various “classical" global optimization methods, most of which available long before the appearance of Simulated Annealing (a key event in this field). There exists plenty of papers and books dealing with these methods, and studying in particular their convergence properties. The second part of the paper is devoted to more recent or atypical methods, mostly issued from combinatorial optimization. The three main methods are “metaheuristics": Simulated Annealing (and derived techniques), Tabu Search and Genetic Algorithms; we also describe three other less known methods. For these methods, theoretical studies of convergence are less abundant in the literature, and the use of convergence results is by far more limited in practice. However, the fitting of some of these techniques to continuous variables problems gave very promising results; that question is not discussed in detail in the paper, but useful references allowing to deepen the subject are given.
LA - fre
KW - Global optimization; metaheuristics; convergence; continuous optimization.; continuous optimization; global optimization; simulated annealing; tabu search; genetic algorithms
UR - http://eudml.org/doc/116597
ER -

References

top
  1. E.H.L. Aarts et P.J.M. Van Laarhoven, Simulated annealing: Theory and applications. D. Reidel Publishing Company (1987).  Zbl0643.65028
  2. R.S. Anderssen, Global optimization, édité par R.S. Anderssen, L.S. Jennings et D.M. Ryan. Optimization, Univ. of Queensland Press, St Lucia (1972) 28-48.  
  3. J.P. Barthélémy, G. Cohen et A. Lobstein, Complexité algorithmique et problèmes de communication. Masson, Collection CNET-ENST (1992).  
  4. R. Battiti et G. Tecchiolli, The continuous reactive tabu search: Blending Combinatorial Optimization and Stochastic Search for Global Optimization. Ann. Oper. Res.63 (1996) 53-188.  Zbl0851.90093
  5. R.W. Becker et G.V. Lago, A global optimization algorithm, dans Proc. of the 8th Allerton Conference on Circuits and Systems Theory. Montecillo, Illinois (1970) 3-12.  
  6. M. Bertocchi et C.D. Odoardo, A stochastic algorithm for global optimization based on threshold accepting technique, dans 11th European Congress on Operational Research EURO XI. Aachen, Germany (1991).  
  7. G. Berthiau, La méthode du recuit simulé pour la conception des circuits électroniques : adaptation et comparaison avec d'autres méthodes d'optimisation. Thèse de Doctorat de l'École Centrale de Paris (1994).  
  8. I.O. Bohachevsky, M.E. Johnson et M.L. Stein, Generalized Simulated Annealing for function optimization. Technometrics28 (1986) 209-217.  Zbl0609.65045
  9. F.H. Branin et S.K. Hoo, A method for finding multiple extrema of a function of n variables, édité par F.A. Lootsma, Numerical methods of nonlinear optimization. Academic Press, London (1972).  
  10. S.H. Brooks, A discussion of random methods for seeking maxima. Oper. Res.6 (1958) 244-251.  
  11. D.G. Brooks et W.A. Verdini, Computational experience with Generalized Simulated Annealing over continuous variables. Amer. J. Math. Management Sci.8 (1988) 425-449.  Zbl0684.65061
  12. F. Catthoor, H. De Man et J. Vandewalle, SAMURAI: A general and efficient simulated annealing schedule with fully adaptive annealing parameters. Integration, The VLSI Journal6 (1988) 147-178.  
  13. V. Cerny, Minimization of continuous functions by simulated annealing, Internal Documentation HU-TFT-84-51. Research Institute for Theoretical Physics, University of Helsinki, Siltavuorenpenger 20c, SF-00170, Helsinki 17, Finland (1984).  
  14. V. Cerny, Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm. J. Optim. Theory Appl.45 (1985) 41-51.  Zbl0534.90091
  15. I. Charon et O. Hudry, Le bruitage : une méthode prometteuse d'optimisation combinatoire. ENST, Département d'Informatique, Rapport Interne Télécom Paris 92-D-005 (1992).  
  16. Y. Cherruault et A. Guillez, Une méthode pour la recherche du minimum global d'une fonctionnelle. C. R. Acad. Sci. Paris Sér. I Math.296 (1983) 175-178.  Zbl0525.65047
  17. Y. Cherruault, Mathematical modelling in Biomedicine. D. Reidel Publishing Company (1986).  
  18. Y. Cherruault, A new method for global optimization (Alienor). Kybernetes19 (1989) 19-32.  Zbl0701.90083
  19. A. Corana, M. Marchesi, C. Martini et S. Ridella, Minimizing multimodal functions of continuous variables with the ``simulated annealing'' algorithm. ACM Trans. Math. Software13 (1987) 262-280.  Zbl0632.65075
  20. P. Courrieu, Un algorithme de recherche distribuée pour l'optimisation difficile. Univ. de Provence, Centre de Recherche en Psychologie Cognitive, Rapport Interne TF-9101 (1991).  
  21. M. Creutz, Microcanonical Monte-Carlo simulation. Phys. Rev. Lett.50 (1983) 1411-1414.  
  22. D. Cvijovic et J. Klinowski, Taboo search. An approach to the Multiple Minima Problem. Science667 (1995) 664-666.  Zbl1226.90101
  23. A. Dekkers et E.H.L. Aarts, Global optimization and simulated annealing. Math. Programming50 (1991) 367-393.  Zbl0753.90060
  24. L. Devroye, Progressive global random search of continuous functions. Math. Programming15 (1978) 330-342.  Zbl0387.90083
  25. D. De Werra et A. Hertz, Tabu search techniques: A tutorial and an application to neural networks. OR Spektrum11 (1989) 131-141.  Zbl0672.90089
  26. L.C.W. Dixon et G.P. Szegö, Towards global optimization. North Holland, Amsterdam (1975).  Zbl0309.90052
  27. L.C.W. Dixon et G.P. Szegö, Towards global optimization 2. North Holland, Amsterdam (1978).  
  28. G. Dueck et T. Scheuer, Threshold accepting. IBM Zentrum Heidelberg, Germany (1989).  
  29. G. Dueck, New optimization heuristics, the great deluge and the record-to record travel. J. Comput. Phys.104 (1993) 86-92.  Zbl0773.65042
  30. S. Geman et C.R. Hwang, Diffusions for global optimization. SIAM J. Control Optim.24 (1986) 1031-1043.  Zbl0602.60071
  31. M. Gendreau, A. Hertz et G. Laporte, A Tabu Search Algorithm for the Vehicle Routing Problem. Management Sci.40 (1994) 1276-1290.  Zbl0822.90053
  32. F. Glover, Future paths for integer programming and links to artificial intelligence. Comput. Oper. Res.13 (1986) 533-549.  Zbl0615.90083
  33. F. Glover et H.J. Greenberg, New approaches for heuristic search: A bilateral linkage with artificial intelligence. Eur. J. Oper. Res.39 (1989) 119-130.  Zbl0658.90079
  34. F. Glover, Tabu search fundamentals and uses, Working paper. Graduate School of Business, Box 419, University of Colorado, Boulder, CO (1995).  
  35. F. Glover et M. Laguna, Tabu search. Kluwer Academic Publishers (1997).  Zbl0930.90083
  36. D.E. Goldberg, Genetic algorithms in search, optimization and machine learning. Addison-Wesley, Reading (1989).  Zbl0721.68056
  37. L. Hérault, Réseaux de neurones récursifs pour l'optimisation combinatoire ; Application à la théorie des graphes et à la vision par ordinateur, Thèse de Doctorat de l'Institut National Polytechnique de Grenoble. INPG, Grenoble (1989).  
  38. J.H. Holland, Adaptation in natural and artificial systems. Univ. of Michigan Press, Ann Arbor (1975).  
  39. R. Horst, P.M. Pardalos, Handbook of Global Optimization. Kluwer Academic Publishers (1995).  Zbl0805.00009
  40. N. Hu, Tabu Search method with random moves for globally optimal design. Int. J. Numer. Meth. Eng.35 (1992) 1055-1070.  
  41. R.B. Kearfott, Test results for an interval branch and bound algorithm for equality-constrained optimization, édité par C. Floudas et P.M. Pardalos, State of the Art in Global Optimization: Computational Methods and Applications. Kluwer, Dordrecht, Netherlands (1996) 181-200.  
  42. R.B. Kearfott et V. Kreinovich, Applications of Interval Computations. Kluwer, Dordrecht, Netherlands, Applied Optimization (1996).  Zbl0841.65031
  43. S. Kirkpatrick, C.D. Gelatt et M.P. Vecchi, Optimization by simulated annealing, Research Report RC 9355. IBM, Yorktown Heights, NY (1982).  Zbl1225.90162
  44. S. Kirkpatrick, C.D. Gelatt et M.P. Vecchi, Optimization by simulated annealing. Science220 (1983) 671-680.  Zbl1225.90162
  45. A.V. Levy et S. Gomez, The tunneling algorithm for the global optimization problem of constrained functions, Technical Report 231. Univ. Nat. Auton. de Mexico (1980).  
  46. A.V. Levy et S. Gomez, The tunneling method applied to global optimization, édité par P.T. Boggs, R.H. Byrd et R.B. Schnanel, Numerical Optimization 1984. SIAM Philadelphia (1984).  
  47. A.V. Levy et A. Montalvo, The tunneling algorithm for the global minimization of functions. SIAM J. Sci. Stat. Comp.6 (1985) 15-29.  Zbl0601.65050
  48. M. Lundy et A. Mees, Convergence of an annealing algorithm. Math. Programming34 (1986) 111-124.  Zbl0581.90061
  49. N. Metropolis, A.R. Rosenbluth, M.N. Rosenbluth, A. Teller et E. Teller, Equation of state calculations by fast computing machines. J. Chem. Phys.21 (1953).  
  50. Z. Michalewicz, Genetic algorithms + Data structures = Evolution Programs. Springer (1996).  Zbl0841.68047
  51. M. Minoux, Programmation mathématique - Théorie et algorithmes. Édition Dunod (1983).  Zbl0546.90056
  52. R.E. Moore, On computing the range of values of a rational function of n variables over a bounded region. Computing16 (1976) 1-15.  Zbl0345.65024
  53. R.E. Moore, Methods and applications of interval analysis. SIAM, Philadelphia (1979).  Zbl0417.65022
  54. I. Mrad, La méthode du recuit simulé pour la synthèse automatique d'un schéma électrique équivalent. Application à la modélisation de composant et à l'adaptation à large bande. Thèse de Doctorat de l'École Centrale de Paris (1997).  
  55. J.A. Nelder et R. Mead, A simplex method for function minimization. Comput. J.7 (1965) 308-313.  Zbl0229.65053
  56. C. Poivey, Méthodes d'optimisation globales pour la C.A.O. de circuits intégrés. Interface avec le simulateur SPICE-PAC. Thèse de Doctorat de l'Université de Clermont-Ferrand (1988).  
  57. C.R. Reeves, Modern Heuristic Techniques for Combinatorial Problems. Mc Graw-Hill, Advanced Topics in Comput. Sci. Ser. (1995).  Zbl0942.90500
  58. A.H.G. Rinnooy Kan et G.T. Timmer, Stochastic methods for global optimization. Amer. J. Math. Management Sci.4 (1984) 7-40.  Zbl0556.90073
  59. A.H.G. Rinnooy Kan et G.T. Timmer, Global optimization, Report 8612/A. Erasmus Univ. Rotterdam (1986).  Zbl0649.65034
  60. A.H.G. Rinnooy Kan et G.T. Timmer, Stochastic global optimization methods. Part I: Clustering methods. Math. Programming39 (1987) 27-56.  Zbl0634.90066
  61. A.H.G. Rinnooy Kan et G.T. Timmer, Stochastic global optimization methods. Part II: Multi-level methods. Math. Programming39 (1987) 57-78.  Zbl0634.90067
  62. E. Rolland, A Tabu Search Method for Constrained Real-Number Search: Applications to Portfolio Selection, Working Paper. The A. Gary Anderson Graduate School of Management, University of California, Riverside (1996).  
  63. E. Rolland et H. Johnson, Skewness and the Mean-Variance Frontier: A Tabu Search Approach, Working Paper. The A. Gary Anderson Graduate School of Management, University of California, Riverside (1996).  
  64. G. Rudolph, Convergence analysis of canonical genetic algorithms. IEEE Trans. Neural Networks5 (1994) 96-101.  
  65. K. Schittkowski et W. Hock, Test examples for nonlinear programing codes. Springer-Verlag, Lecture Notes in Econom. and Math. Systems187 (1981).  Zbl0452.90038
  66. K. Schittkowski et W. Hock, More test examples for nonlinear programing codes. Springer-Verlag, Lecture Notes in Econom. and Math. Systems282 (1988).  Zbl0452.90038
  67. P. Siarry, La méthode du recuit simulé : application à la conception de circuits électroniques. Thèse de Doctorat de l'Université Pierre et Marie Curie, Paris 6 (1986).  
  68. P. Siarry et G. Dreyfus, La méthode du recuit simulé : théorie et applications. Éditeur IDSET (1988).  
  69. P. Siarry, La méthode du recuit simulé en électronique : adaptation et accélération. Comparaison avec d'autres méthodes d'optimisation. Application dans d'autres domaines, Rapport d'habilitation à diriger les recherches en sciences. Université de Paris Sud, Centre d'Orsay (1994).  
  70. P. Siarry, G. Berthiau, F. Durbin et J. Haussy, Enhanced Simulated Annealing for globally minimizing functions of many-continuous variables. ACM Trans. Math. Software23 (1997) 209-228.  Zbl0887.65067
  71. P. Siarry et G. Berthiau, Fitting of Tabu Search to optimize functions of continuous variables. Int. J. Numer. Methods Eng.40 (1997) 2449-2457.  Zbl0882.65049
  72. E.G. Talbi, A taxonomy of hybrid meta-heuristics, Rapport AS-183 du Laboratoire d'Informatique Fondamentale de Lille. Université des Sciences et Technologies de Lille (1998).  
  73. A. Törn, A search clustering approach to global optimization, édité par L.C.W. Dixon et G.P. Szegö. North Holland, Amsterdam, Towards Global Optimization2 (1978).  Zbl0392.90073
  74. A. Törn et A. Zilinskas, Global optimization, édité par G. Goos et J. Hartmanis. Springer Verlag, No. 350 (1989).  
  75. D. Vanderbilt et S.G. Louïe, A Monte-Carlo simulated annealing approach to optimization over continuous variables. J. Comput. Phys.56 (1984) 259-271.  Zbl0551.65045

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.