Une nouvelle métaheuristique pour l'optimisation difficile : la méthode des essaims particulaires

¹ France Télécom R&D, 12 av. de Chevêne, F-74988 Annecy, France.
² Université de Paris 12 Val-de-Marne, LERISS (E.A. 412), 61 av. du Général de Gaulle, F-94010 Créteil, France

Auteur de correspondance : siarry@univ-paris12.fr

Résumé

Nous présentons d'abord dans cet article le cadre général des métaheuristiques, qui sont apparues au début des années 1980 avec une ambition commune : résoudre au mieux les problèmes dits d'optimisation difficile. Nous essayons de cerner le domaine de l'optimisation difficile, tant pour les problèmes discrets que pour les problèmes à variables continues. Puis nous dégageons quelques caractéristiques communes à nombre de métaheuristiques, et nous passons en revue les principales extensions de ces méthodes. Nous présentons ensuite une métaheuristique apparue dernièrement : la méthode d'optimisation par essaim particulaire (OEP). L'OEP est une technique encore peu connue en France, fondée sur la notion de coopération entre des agents (les particules) qui peuvent être vus comme des “ animaux ” aux capacités assez limitées (peu de mémoire et de facultés de raisonnement). L'échange d'information entre eux fait que, globalement, ils arrivent néanmoins à résoudre des problèmes difficiles, comme c'est le cas, par exemple, chez les abeilles vivant en essaim (exploitation de sources de nourriture, construction de rayons, etc.). Après une présentation succincte des origines, l'article propose une description informelle de l'OEP, puis en dégage les principales caractéristiques. Simple à comprendre, à programmer et à utiliser, l'OEP se révèle particulièrement efficace pour les problèmes d'optimisation non linéaire, à variables continues, entières ou mixtes. L'article se termine par un résumé des exposés présentés lors du premier séminaire francophone sur le sujet (OEP'2003, Paris, octobre 2003).