Soutenance de Thèse Peio Loubiere

Amélioration des métaheuristiques d'optimisation à l'aide de l'analyse de sensibilité

Peio Loubiere

 

Peio LOUBIERE, enseignant-chercheur du département informatique de l'EISTI, a soutenu avec succès sa thèse "Amélioration des métaheuristiques d'optimisation à l'aide de l'analyse de sensibilité".

La soutenance s'est déroulée lundi 21 novembre 2016 à l'Université Paris-Est Créteil (UPEC)  devant un jury composé de :

  • Directeurs de thèse : Patrick SIARRY (Professeur UPEC) et Rachid CHELOUAH (Directeur de la Recherche en Informatique EISTI)
  • Rapporteur : Stéphane CANU (Professeur INSA Rouen) et André ROSSI (Professeur Université d'Angers)
  • Examinateurs : Laurent DUMAS (Professeur Université de Versailles), Astrid JOURDAN (Enseignante-chercheuse EISTI) et Nicolas MONMARCHE (Maître de conférences Université de Tours).

L'équipe enseignante et administrative de l'EISTI lui adresse toutes ses félicitations.

Résumé

L'optimisation difficile représente une classe de problèmes dont la résolution ne peut être obtenue par une méthode exacte en un temps polynomial.

Trouver une solution en un temps raisonnable oblige à trouver un compromis quant à son exactitude.

Les métaheuristiques sont une classe d'algorithmes permettant de résoudre de tels problèmes, de manière générique et efficiente (i.e. trouver une solution satisfaisante selon des critères définis: temps, erreur, etc.).

Le premier chapitre de cette thèse est notamment consacré à la description de cette problématique et à l'étude détaillée de deux familles de métaheuristiques à population, les algorithmes évolutionnaires et les algorithmes d'intelligence en essaim. Afin de proposer une approche innovante dans le domaine des métaheuristiques, ce premier chapitre présente également la notion d'analyse de sensibilité. L'analyse de sensibilité permet d'évaluer l'influence des paramètres d'une fonction sur son résultat.

Son étude caractérise globalement le comportement de la fonction à optimiser (linéarité, influence, corrélation, etc.) sur son espace de recherche. L'incorporation d'une méthode d'analyse de sensibilité au sein d'une métaheuristique permet d'orienter sa recherche le long des dimensions les plus prometteuses.

Deux algorithmes réunissant ces notions sont proposés aux deuxième et troisième chapitres. Pour le premier algorithme, ABC-Morris, la méthode de Morris est introduite dans la métaheuristique de colonie d'abeilles artificielles (ABC). Cette inclusion est dédiée, les méthodes reposant sur deux équations similaires.

Afin de généraliser l'approche, une nouvelle méthode, NN-LCC, est ensuite développée et son intégration générique est illustrée sur deux métaheuristiques, ABC avec taux de modification et évolution différentielle. L'efficacité des approches proposées est testée sur le jeu de données de la conférence CEC 2013. L'étude se réalise en deux parties: une analyse classique de la méthode vis-à-vis de plusieurs algorithmes de la littérature, puis vis-à-vis de l'algorithme d'origine en désactivant un ensemble de dimensions, provoquant une forte disparité des influences.