Soutenance de th
Forum 'Annonces' - Sujet créé le 2005-06-07
Matthieu Basseur vous invite à sa soutenance de thèse intitulée "Conception d'algorithmes coopératifs pour l'optimisation multi-objectif : Application aux problèmes d'ordonnancement de type Flow-shop" qui aura lieu le Mardi 21 Juin à 14 heures au Bâtiment des thèses à l'Université de Lille 1 (métro Cité Scientifique).
Le jury est composé de :
Directeur de Thèse : El-Ghazali TALBI , Professeur, Université de Lille I
Rapporteurs : Jin-Kao HAO, Professeur, Université d'Angers
Patrick SIARRY, Professeur, Université de Paris XII
Membres : Arnaud FREVILLE, Professeur, Université de Valenciennes
Kenneth SORENSEN, Assistant Professor, Université d'Anvers
Jacques TEGHEM, Professeur, Faculté Polytechnique de Mons
Philippe MATHIEU, Professeur, Université de Lille I
Résumé :
Les problèmes " difficiles " de l'optimisation combinatoire, sont généralement résolus de manière heuristique, afin de procurer de bonnes solutions en un temps " raisonnable ", les méthodes de résolution exacte étant inapplicables aux grandes instances. Actuellement, un nombre croissant d'approches coopératives entre ces méthodes voient le jour.
Dans un premier temps, une classification des approches coopératives de la littérature à été réalisé. A partir de ces travaux, nous présentons différents schémas de coopération typiques, en se focalisant spécialement sur les coopérations entre méthodes de résolution exacte et heuristique.
Dans un deuxième temps, nous proposons d'effectuer différentes coopérations pour résoudre un problème de Flow-shop bi-objectif. Pour la résolution approchée de ce problème, l'algorithme AGA (Algorithme Génétique Adaptatif) a été défini pour servir de base aux méthodes coopératives. Deux mécanismes sont proposés pour renforcer l'adaptabilité et la capacité d'exploration des algorithmes génétiques multi-objectif. Le premier mécanisme permet d'utiliser, dans le même programme, plusieurs opérateurs de mutation, et de favoriser automatiquement ceux qui s'avèrent plus efficaces. Le second mécanisme consiste à adapter en ligne un paramètre de la diversification, de sorte à obtenir une répartition harmonieuse des solutions le long du front de Pareto.
Ensuite, nous proposons de faire coopérer AGA avec des méthodes dédiées à l'intensification de la recherche. Nous proposons un premier type de coopération avec PLS (Recherche Locale Pareto) en proposant différents algorithmes de type recherche mimétique. Les tests effectués sur les différentes coopérations montrent l'intérêt d'utiliser un algorithme d'exploration (AGA), ainsi que l'efficacité des coopérations adaptives entre différents algorithmes.
Puis, nous proposons une coopération originale avec l'algorithme MOPR (Path Relinking Multi-Objectif). Pour cela nous avons défini différents mécanismes pour adapter les algorithmes de path-relinking au cas multi-objectif. Ce type d'approche est très prometteur.
Enfin, les approches coopératives avec la méthode exacte bi-objectif TPM (Méthode Deux Phases) ont été énvisagées. Trois approches ont été proposées, une exacte et deux heuristique. Les expérimentations ont permis d'améliorer sensiblement les meilleures solutions obtenues.
Les différentes approches testées montrent l'intérêt des mécanismes de transition adaptative entre algorithmes, ainsi que l'apport réalisé par l'utilisation de méthodes d'optimisation très différentes, dans le cadre de l'optimisation multi-objectif.
Le jury est composé de :
Directeur de Thèse : El-Ghazali TALBI , Professeur, Université de Lille I
Rapporteurs : Jin-Kao HAO, Professeur, Université d'Angers
Patrick SIARRY, Professeur, Université de Paris XII
Membres : Arnaud FREVILLE, Professeur, Université de Valenciennes
Kenneth SORENSEN, Assistant Professor, Université d'Anvers
Jacques TEGHEM, Professeur, Faculté Polytechnique de Mons
Philippe MATHIEU, Professeur, Université de Lille I
Résumé :
Les problèmes " difficiles " de l'optimisation combinatoire, sont généralement résolus de manière heuristique, afin de procurer de bonnes solutions en un temps " raisonnable ", les méthodes de résolution exacte étant inapplicables aux grandes instances. Actuellement, un nombre croissant d'approches coopératives entre ces méthodes voient le jour.
Dans un premier temps, une classification des approches coopératives de la littérature à été réalisé. A partir de ces travaux, nous présentons différents schémas de coopération typiques, en se focalisant spécialement sur les coopérations entre méthodes de résolution exacte et heuristique.
Dans un deuxième temps, nous proposons d'effectuer différentes coopérations pour résoudre un problème de Flow-shop bi-objectif. Pour la résolution approchée de ce problème, l'algorithme AGA (Algorithme Génétique Adaptatif) a été défini pour servir de base aux méthodes coopératives. Deux mécanismes sont proposés pour renforcer l'adaptabilité et la capacité d'exploration des algorithmes génétiques multi-objectif. Le premier mécanisme permet d'utiliser, dans le même programme, plusieurs opérateurs de mutation, et de favoriser automatiquement ceux qui s'avèrent plus efficaces. Le second mécanisme consiste à adapter en ligne un paramètre de la diversification, de sorte à obtenir une répartition harmonieuse des solutions le long du front de Pareto.
Ensuite, nous proposons de faire coopérer AGA avec des méthodes dédiées à l'intensification de la recherche. Nous proposons un premier type de coopération avec PLS (Recherche Locale Pareto) en proposant différents algorithmes de type recherche mimétique. Les tests effectués sur les différentes coopérations montrent l'intérêt d'utiliser un algorithme d'exploration (AGA), ainsi que l'efficacité des coopérations adaptives entre différents algorithmes.
Puis, nous proposons une coopération originale avec l'algorithme MOPR (Path Relinking Multi-Objectif). Pour cela nous avons défini différents mécanismes pour adapter les algorithmes de path-relinking au cas multi-objectif. Ce type d'approche est très prometteur.
Enfin, les approches coopératives avec la méthode exacte bi-objectif TPM (Méthode Deux Phases) ont été énvisagées. Trois approches ont été proposées, une exacte et deux heuristique. Les expérimentations ont permis d'améliorer sensiblement les meilleures solutions obtenues.
Les différentes approches testées montrent l'intérêt des mécanismes de transition adaptative entre algorithmes, ainsi que l'apport réalisé par l'utilisation de méthodes d'optimisation très différentes, dans le cadre de l'optimisation multi-objectif.