Résumé : On a assisté ces dernières années à une prolifération de "nouvelles" méta-heuristiques. Si l'on considère les principes à la base de ces techniques, on se rend souvent compte qu'il s'agit de variations de concepts précédemment proposés, lorsque ce n'est pas simplement une présentation d'une méthode existante mais en utilisant une terminologie associées à une autre métaphore. Cet exposé présentera sous une forme unifiée un certain nombre de méta-heuristiques. Une seconde partie se penchera sur la manière de comparer des méthodes itératives non déterministes. En effet, les méthodes mises au point en se basant sur des méta-heuristiques sont très souvent non déterministes et itératives. Or, dans la littérature on voit encore très souvent des comparaison de ces méthodes sous la forme de tableaux qui donnent, pour un effort de calcul arbitraire, la qualité moyenne obtenue par quelques méthodes. Ce type de tableaux donne des informations très partielles et peu lisibles. On fera donc quelques propositions pour comparer de manière plus complète et plus scientifique des méthodes basées sur des méta-heuristiques.

Résumé : La plupart des métaheuristiques ont été conçues, à l'origine, pour la résolution des problèmes d' " optimisation difficile " de nature discrète. Cependant, les ingénieurs sont souvent confrontés à des problèmes d' optimisation à variables continues : amélioration des performances d'un circuit électronique, identification des paramètres d'un modèle de gisement d'hydrocarbures, apprentissage d'un réseau de neurones ou d'une base de règles floues. De tels problèmes peuvent être également " difficiles ", dans un sens différent de celui consacré par la théorie de la complexité : fonction objectif non connue analytiquement ou bruitée, variables corrélées ou évoluant dans des gammes très diverses, présence de non-linéarités, etc. Les métaheuristiques offrent, dans ce cadre, un avantage précieux : elles n'exploitent pas les gradients de la fonction objectif. Ces techniques doivent cependant être adaptées au cas continu ; nous décrirons dans cet exposé quelques approches pour quatre métaheuristiques : le recuit simulé, la recherche tabou, les algorithmes génétiques et les algorithmes de colonies de fourmis.

Résumé : Dans cet exposé nous nous intéressons aux voisinages de taille exponentielle, pouvant être néanmoins explorés en temps polynomial, pour plusieurs problèmes d'optimisation combinatoire. Après avoir dressé un bref panorama des résultats existants, nous montrons que l'approche dynasearch développée par Congram, Potts et van de Velde peut être étendue aux cas de problèmes d'optimisation "dynamiques" et multicritère. Comme exemples nous considérons un problème d'ordonnancement monocritère dont la durée de chaque tâche est fonction de sa date d'exécution et le problème du voyageur de commerce bicritère. Pour ces deux problèmes nous présentons des résultats expérimentaux montrant l'intérêt de cet approche par rapport aux voisinages classiques de petite taille.

Résumé : Apres une brève introduction aux algorithmes évolutionnaires - algorithmes d'optimisation stochastiques s'inspirant grossierement de l'évolution darwinienne des populations biologiques - dont les plus connus sont les algorithmes génétiques, nous présenterons un bref historique des applications de ces algorithmes a l'optimisation combinatoire, avec en particulier l'apparition récente des algorithmes dits "memetiques". Puis nous donnerons un exemple d'application particulier dans le domaine du contrôle aérien.

Résumé : Le système des colonies de fourmis (ACS) est un algorithme évolutif qui s'inspire du comportement des véritables fourmis. Cette méthode se caractérise par la combinaison d'une approche constructive et de mécanismes d'apprentissage fondés sur la mémorisation. Elle a été introduite par Marco Dorigo (1992) et a été appliquée avec succès au problème du voyageur de commerce. Il s'agit dans cette présentation : a) de décrire le principe et l'intérêt de la méthode et comment elle peut être appliquée dans un contexte de programmation par contraintes; b) de comparer les résultats obtenus sur le problème de tournées de véhicules (VRP) et sur une variante de ce problème, le Pickup and Delivery Problem (PDP), avec d'autres approches connues; c) de décrire les différentes implémentations possibles et les avantages de chacune d'elle.