|
|
|
|
|
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. |
|
|
|
|
|
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. |
|
|
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. 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. |
|
|
|
|
|
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. |
|
|
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 :
|