Note ABES Extraire et exploiter la connaissance pour mieux optimiser Extract and exploit knowledge for optimization Heuristiques 006.337 Optimisation combinatoire Métaheuristiques Acquisition des connaissances (systèmes experts) Ordonnancement (gestion) Programmation heuristique Exploration de données Les problèmes d’optimisation combinatoire de grandes tailles sont en général difficiles à résoudre de façon optimale due à des temps de calcul trop élevés. Afin de pallier ce problème, des algorithmes d’approximation tels que les heuristiques et les métaheuristiques sont utilisés pour trouver rapidement des solutions approchées de bonne qualité. Les heuristiques sont des approches développées spécifiquement pour un problème et permettent d’obtenir des solutions très rapidement. Les métaheuristiques sont des approches génériques, indépendantes du problème, permettant de trouver des solutions de bonne qualité. Ces approches présentent chacune leurs avantages et inconvénients. Nous proposons dans ce mémoire de tirer parti des avantages de ces deux approches, c’est-à-dire intégrer des connaissances spécifiques à un problème, telles que celles utilisées dans les heuristiques, dans les mécanismes génériques des métaheuristiques, afin de concevoir des nouvelles approches efficaces. Ainsi, dans ce mémoire, nous passons d’abord en revue dans la littérature les approches avec intégration de connaissances afin de proposer une taxonomie de classification de ces approches. Puis nous nous focalisons sur l’intégration de connaissances pour deux problèmes différents : le problème d’ordonnancement de type Flowshop sans temps d’attente, et le problème de sélection d’attributs en classification. Enfin, nous étudions dans ces problèmes l’impact de l’intégration de connaissances dans différents mécanismes des métaheuristiques : l’initialisation, l’opérateur de voisinage et la sélection du voisinage. Large-scale combinatorial optimization problems are generally hard to solve optimally due to expensive computation times. In order to tackle this problem, approximation algorithms such as heuristics and metaheuristics are used to quickly find approximate solutions. Heuristics are problem-specific approaches that provide solutions very quickly. Metaheuristics are generic approaches to finding solutions with good quality for several problems. Each of these approaches has its advantages and disadvantages. We propose in this thesis to use the advantages of these two approaches, that is to say, to integrate specific knowledge associated to a problem as heuristics do, within the mechanisms of metaheuristics in order to design new effective approaches. In this thesis report, we first review knowledge integration approaches in the literature to propose a taxonomy for a classification of these approaches. Then we focus on the integration of knowledge in two different problems: the No-Wait Flowshop Scheduling Problem, and the Feature Selection Problem in a classification context. Finally we study the impact of the integration of knowledge on these problems with different metaheuristic's mechanisms, that is initialization procedure, neighborhood operator and neighborhood selection. Electronic Thesis or Dissertation Text fr PDF 2045113 text/html https://pepite-depot.univ-lille.fr/LIBRE/EDSPI/2018/50376-2018-Mousin.pdf https://theses.fr/2018LILUI091/abes Mousin Lucien Mousin 1991-05-07 FR 242876412 https://theses.fr/2018LILUI091 2018LILUI091 https://doi.org/10.70675/2713982az976fz4a10z84efz732db879786f 2018-11-28 Informatique Université de Lille (2018-2021) 223446556 Doctorat Docteur es non oui Dhaenens Clarisse MADS_DIRECTEUR_DE_THESE_1 050695002 Kessaci Marie-Eléonore MADS_DIRECTEUR_DE_THESE_2 163953791 École doctorale Sciences pour l'ingénieur (Lille ; 1992-2021) MADS_ECOLE_DOCTORALE_1 147297028 Centre de Recherche en Informatique, Signal et Automatique de Lille MADS_PARTENAIRE_DE_RECHERCHE_1 18388695X ddc:004 Dhaenens Clarisse Kessaci Marie-Éléonore École doctorale Sciences pour l'Ingénieur (Lille) Centre de recherche en informatique, signal et automatique de Lille PDF 2045113