Soutenance mémoire
L’optimisation combinatoire est un domaine très actif de la recherche en informatique, car il existe de nombreux problèmes de la vie quotidienne qui peuvent se modéliser comme un problème d’optimisation combinatoire. Résoudre un problème d’optimisation consiste à trouver la meilleure solution possible (ou un ensemble de meilleures solutions dans le cadre multi-objectif ) dans un espace fini de solutions réalisables. Une « meilleure solution » est définie par une fonction objectif qui est soit à minimiser, soit à maximiser. Les problèmes étudiés sont généralement NP-difficiles et les méthodes exactes deviennent inutilisables lorsque les problèmes sont de grandes tailles, car trop coûteuses en temps de calcul. Pour pallier cette difficulté, des méthodes approchées ont été développées : les heuristiques et les métaheuristiques. Ces approches permettent d’obtenir des solutions de bonne qualité, mais sans garantie d’optimalité, en un temps raisonnable. Les heuristiques sont généralement des approches gloutonnes, spécifiques à un problème, qui construisent des solutions très rapidement. Les métaheuristiques, à l’opposé des heuristiques, sont des approches génériques de résolution, c’est-à-dire qu’une même métaheuristique peut-être employée pour résoudre des problèmes bien différents.
Ces méthodes approchées ont cependant aussi des désavantages. Les heuristiques sont très spécifiques à un problème, et construisent une solution itérativement, qui, pour les cas des heuristiques gloutonnes, ne tiennent pas compte des éventuelles améliorations entre les itérations. Ce qui fait que généralement la qualité obtenue par ces approches est bien loin de la qualité optimale. Les métaheuristiques pallient ce problème en proposant des modifications itératives de la solution afin de l’améliorer jusqu’à ce qu’un critère d’arrêt soit atteint (temps, optimum local …). Cependant ces méthodes étant généralistes, elles perdent toute exploitation des données spécifiques à un problème donné. Dans ce mémoire, nous proposons d’utiliser les avantages des deux approches : exploiter la connaissance spécifique au problème utilisé dans les heuristiques et les intégrer dans les métaheuristiques pour combiner la force d’exploration de l’espace de recherche de ces dernières et la connaissance utilisée dans les heuristiques.
L’optimisation combinatoire
L’Optimisation Combinatoire est présent dans de nombreux domaines de l’informatique, ainsi que dans d’autres branches où l’optimisation est nécessaire, telles que la recherche opérationnelle et les mathématiques appliquées. Les problèmes d’optimisation demandent généralement de rechercher des regroupements, des affectations ou un ordonnancement, d’un ensemble discret de caractéristiques et en respectant un certain nombres de contraintes, tout en optimisant une fonction objectif. Une solution d’un problème d’optimisation combinatoire est une affectation de valeurs aux variables de décision qui satisfait les contraintes du problème. La qualité de la solution est définie par une fonction objectif qui peut être à minimiser ou à maximiser. Le but étant de trouver la meilleure solution possible. Afin de simplifier la lecture de ce chapitre, nous allons considérer être dans un contexte de minimisation, les définitions et raisonnements s’appliquant de la même façon dans un contexte de maximisation.
Donnons maintenant une définition plus formelle d’un problème d’optimisation combinatoire : l’optimisation combinatoire consiste à trouver une solution optimale dans un ensemble discret de solutions réalisables. La solution optimale est définie en accord avec une fonction objectif. La fonction objectif peut être minimisée ou maximisée. Ainsi un problème d’optimisation peut être défini par un espace de recherche Ω et une fonction objectif f : Ω → R. Le but étant de trouver, dans un contexte de minimisation de la fonction objectif, s ∗ ∈ Ω tel que :
s∗ = ar gmins∈Ω f (s) (1.1)
Dans un contexte de maximisation, l’équation 1.1 consiste alors à maximiser la fonction f . Dans un problème d’optimisation, la solution optimale s∗ appelée aussi optimum global est définie tel que :
∀s ∈ Ω, f (s∗) ≤ f (s) (1.2)
On définit une instance d’un problème d’optimisation combinatoire comme un ensemble de données particulières d’un problème à résoudre. La plupart des problèmes d’optimisation combinatoire font partie de la classe des problèmes dits NP-difficile. C’est-à-dire qu’il n’existe pas d’algorithme efficace permettant de trouver une solution optimale en un temps raisonnable. De ce fait, on définit deux types de méthodes pour résoudre les problèmes d’optimisation combinatoire : les méthodes exactes et les méthodes approchées.
— Les méthodes exactes garantissent une solution optimale, mais deviennent inutilisables lorsque la taille des instances devient trop grande suite à un coût de calcul trop important.
— Les méthodes approchées permettent de trouver une solution de bonne qualité en un temps raisonnable, mais ne garantissent plus l’optimalité de la solution. Ce sont ces méthodes qui seront abordées dans cette thèse.
Méthodes de résolution approchées
Ces méthodes approchées de résolution de problèmes d’optimisation combinatoire se classent en deux grandes catégories : les heuristiques et les méta-heuristiques.
Les heuristiques
Les heuristiques sont des méthodes qui exploitent la structure d’un problème considéré afin de trouver une solution approchée de bonne qualité en un temps raisonnable, i.e. aussi faible que possible. En d’autres termes, elles permettent généralement de trouver une solution approchée à un problème de classe NP en un temps polynomial. Ces heuristiques peuvent être déterministes ou stochastiques. Les heuristiques les plus simples qu’on retrouve dans la littérature sont les heuristiques gloutonnes (DEVORE et TEMLYAKOV [1996]). Ce type d’heuristique fait une succession de choix en fonction de certaines caractéristiques (Exemple : choisir la ville la plus proche parmi un ensemble de villes encore non parcourues), jusqu’à ce que la solution soit réalisable, et cela, sans retour en arrière possible. Bien que le principe soit assez générique, il doit cependant être adapté en fonction du problème, car ces heuristiques sont généralement guidées par des caractéristiques spécifiques au problème considéré et en sont donc totalement dépendantes.
Les méta-heuristiques
Les méta-heuristiques sont des méthodes généralisées pour la résolution de problèmes NP. Ainsi, à l’inverse des heuristiques, elles sont indépendantes du problème considéré. De plus, des preuves de convergence vers la solution optimale ont été établies (FAIGLE et KERN [1992]) montrant que la probabilité de trouver la solution optimale augmente si on laisse un temps infini. Bien qu’en pratique il n’est pas possible de laisser un temps infini, les méta-heuristiques ont montré de très bonnes performances sur un temps fini. Dans les méta-heuristiques nous retrouvons deux grandes stratégies : l’intensification et la diversification. L’intensification consiste à sélectionner un sous-espace de recherche prometteur et d’intensifier la recherche de solutions dans ce sous-espace. La diversification, quant à elle, permet à la méthode d’identifier des zones de l’espace non encore explorées afin de les intensifier pour trouver d’éventuelles meilleures solutions.
Basées sur ces stratégies, les méta-heuristiques recherchent donc le bon compromis entre l’intensification et la diversification. Nous pouvons donc diviser les métaheuristiques en trois catégories. (i) Les méta-heuristiques évolutionnaires : approche inspirée de la nature qui privilégient la diversification à l’intensification. (i i) Les autres méta-heuristiques inspirées de la nature : compromis entre diversification et intensification. (i i i) Les méta-heuristiques à base de voisinages : privilégient l’intensification à la diversification.
Méta-heuristiques évolutionnaires
Les méta-heuristiques évolutionnaires sont issues de la théorie de l’évolution de Charles Darwin. Le principe sur lequel reposent ces approches est que les individus les mieux adaptés à leur environnement survivent et peuvent se reproduire, alors que les plus faibles disparaissent. L’analogie avec l’optimisation combinatoire se fait facilement : les individus les mieux adaptés à leur environnement sont assimilés à des solutions de bonne qualité. Ainsi, les méthodes évolutionnaires vont faire évoluer un ensemble d’individus (i.e. les solutions) appelé population. Les individus seront représentés par leur génotype (i.e. informations caractérisant un individu) et leur phénotype (i.e. la qualité d’un individu). Cette population va évoluer pendant plusieurs générations afin de créer les meilleurs individus possibles. Une génération est décomposée en plusieurs étapes qui sont les suivantes :
— Évaluation : Le phénotype de chaque individu est évalué à partir de son génotype.
— Reproduction : Une partie des individus est choisie pour générer des enfants (offsprings en anglais). Deux étapes sont alors réalisées :
— Croisement : Les individus choisis donnent chacun une partie de leur génotype pour générer un enfant partageant les gènes de ses parents.
— Mutation : Certains enfants subissent une mutation de leur génotype avec une probabilité généralement faible.
— Sélection : Une sélection est effectuée parmi les parents et les enfants afin de ne garder que les meilleurs pour la prochaine génération. La sélection la plus simple consiste à garder uniquement les meilleurs individus de la population, i.e. ceux avec le meilleur phénotype.
Parmi les approches évolutionnaires, les stratégies les plus connues et les plus répandues sont les algorithmes génétiques initiés par HOLLAND [1992] qui suivent rigoureusement les principes énoncés précédemment. Mais d’autres stratégies existent aussi telles que les algorithmes à évolution différentielle (Differential Evolution) de STORN et PRICE [1997] ou les algorithmes à estimation de distribution (Estimation of Distribution Algorithms ou EDA) proposés par MUHLENBEIN et PAASS [1996].
Autres méta-heuristiques inspirées de la nature
Tout comme les méthodes évolutionnaires, d’autres approches inspirées de la nature existent. La particularité de ces approches est qu’elles utilisent une population d’agents agissant indépendamment des autres au lieu d’une population d’individus évoluant ensemble. Les agents vont évoluer dans un système gouverné par un ensemble de règles nommées système multi-agent par FERBER [1999]. Ce système aboutit à terme vers un comportement pour l’ensemble des agents, où le comportement sera la convergence vers une solution d’un problème d’optimisation. Ainsi ces approches vont commencer par une grande diversification du comportement des agents pour finir par intensifier un comportement en particulier, i.e. intensifier une zone de l’espace de recherche. Les méta-heuristiques inspirées de la nature les plus répandues sont les colonies de fourmis et les essaims de particules.
Les algorithmes de colonie de fourmis (Ant Colony Optimization ou ACO) proposés par DORIGO et GAMBARDELLA [1997] utilise la notion de système multi-agent où chaque agent (solution) est une fourmi. La fourmi construit une solution de manière probabiliste, en sélectionnant les attributs de la solution proportionnellement à la quantité de phéromones déposées sur les différents composants possibles. La fourmi dépose à chaque pas une quantité de phéromones proportionnelle à la qualité de solution. Ainsi plus un chemin a de phéromones et plus ce chemin est attractif pour les autres fourmis. Les phéromones subissent un phénomène d’évaporation à chaque itération, ce qui retire une partie des phéromones présentes dans l’environnement. Ainsi les chemins peu explorés ne sont plus privilégiés au cours de la recherche.
On a donc au début de la recherche, une exploration aléatoire des fourmis qui, au fur et à mesure des itérations avec le phénomène d’évaporation de l’intensification suite au dépôt de phéromones, font que seuls les chemins les plus intéressants seront considérés par les fourmis, et les moins intéressants seront ignorés. Ces algorithmes sont généralement très efficaces sur des problèmes pouvant se représenter sous forme de graphes, comme les problèmes de type voyageur de commerce.
Méta-heuristiques à base de voisinages
Les méta-heuristiques à voisinage, appelées aussi recherches locales ou algorithmes de descente, démarrent d’une solution initiale et l’améliorent itérativement à l’aide d’un opérateur de voisinage. Nous définissons ainsi le voisinage ν d’une solution s comme l’ensemble des solutions voisines de s. De plus, nous définissons aussi la notion d’optimum local comme une solution s ∗ ∈ Ω telle que toutes les solutions présentes dans son voisinage soient de moins bonne qualité. L’équation 1.5 formalise la notion d’optimum local :
∀s ∈ ν(s∗), f (s∗) ≤ f (s) (1.5)
|
Table des matières
Introduction
1 Contexte
1.1 L’optimisation combinatoire
1.2 Méthodes de résolution approchées
1.2.1 Les heuristiques
1.2.2 Les méta-heuristiques
1.2.2.1 Méta-heuristiques évolutionnaires
1.2.2.2 Autres méta-heuristiques inspirées de la nature
1.2.2.3 Méta-heuristiques à base de voisinages
1.3 Problèmes étudiés
1.3.1 Problème du No-wait Flowshop
1.3.1.1 Définition du problème
1.3.1.2 Complexité du No-Wait Flowshop
1.3.1.3 Spécificités du No-Wait Flowshop
1.3.1.4 Jeux de données
1.3.1.5 État de l’art
1.3.2 Problème de sélection d’attributs en classification
1.3.2.1 Définition du problème
1.3.2.2 Approches de résolution
1.3.2.3 Jeux de données
1.3.2.4 État de l’art
1.4 Conclusion
2 Intégration de connaissances : définitions et proposition de taxonomie
2.1 Introduction
2.2 Intégration de connaissances : vue générale
2.2.1 Objectifs
2.2.2 Étapes de l’intégration de connaissances
2.3 Extraction de connaissances
2.3.1 Connaissance à partir d’une instance
2.3.2 Connaissance phénotypique
2.3.3 Connaissance génotypique
2.3.4 Classification de différentes approches de la littérature
2.4 Mémorisation de connaissances
2.4.1 Méthodes de mémorisation
2.4.2 Fréquences de mise à jour de la mémoire
2.5 Exploitation de connaissances
2.5.1 Les mécanismes
2.5.2 Fréquences d’exploitation
2.6 Taxonomie des méthodes d’intégration de connaissances
2.7 Conclusion
3 Intégration de connaissances dans les procédures d’initialisation
3.1 Introduction
3.2 Heuristiques pour le NWFS
3.2.1 Une mesure spécifique au NWFSP : le GAP
3.2.2 Heuristiques pour minimiser le Makespan
3.2.3 Heuristiques pour minimiser le Flowtime
3.3 Une nouvelle heuristique pour minimiser le Makespan : IBI
3.3.1 Analyse de la structure d’une solution optimale
3.3.2 Heuristique constructive utilisant des réinsertions partielles
3.4 Evaluation des performances de l’heuristique IBI
3.4.1 Protocole Expérimental
3.4.2 Expérimentations sur les paramètres d’IBI
3.4.2.1 Tri initial σ
3.4.2.2 Cycle
3.4.3 Comparaison d’IBI avec des heuristiques de la littérature
3.4.4 IBI comme initialisation d’une recherche locale
3.5 Une nouvelle heuristique pour minimiser le Flowtime : Incremental GAP
3.5.1 Analyse du GAP d’une solution optimale
3.5.2 Heuristique constructive utilisant le GAP
3.6 Evaluation des performances des heuristiques IncrGAP et IIGAP
3.6.1 Résultats d’IncrGAP
3.6.2 Résultats de IIGAP
3.7 Conclusion
Conclusion
Télécharger le rapport complet
