Soutenance mémoire
La programmation par contraintes est un paradigme qui permet de résoudre des problèmes d’optimisation combinatoire. Dans ce chapitre nous présentons les concepts de base en programmation par contraintes qui seront utilisés tout au long de ce manuscrit. Après avoir introduit la notion de problème de satisfaction de contraintes, nous aborderons les mécanismes de résolution ou de recherche de solution inhérentes au paradigme.
Notions de base en programmation par contraintes
Cette section introduit d’une part les différentes notions de base en programmation par contraintes et présente d’autre part le mécanisme de résolution des problèmes de satisfaction de contraintes.
Définitions
Définition 1 (Problème de satisfaction de contraintes). Un problème de satisfaction de contraintes noté CSP (pour constraint satisfaction problem en anglais) [RVBW06] est un triplet P = (X, D, C) où :
• X est un tuple de n > 0 variables, X = <x0, x1, . . . , xn−1>.
• D est un tuple de n > 0 domaines, D = <D0, D1, . . . , Dn−1> tel que xi ∈ Di.
• C est un tuple de k > 0 contraintes C = <C0, C1, …, Ck−1>.
Nous définissons à présent ce qu’est une contrainte.
Définition 2 (Contrainte). Soit P = (X, D, C) un problème de satisfaction de contraintes. Une contrainte Ci ∈ C est une paire <Ri, Si> où Si est un sous ensemble de X appelé portée de la contrainte et Ri est une relation sur les éléments de Si . La relation Ri spécifie les tuples de valeurs autorisées dans le produit cartésien des domaines des variables de Si .
Consistance aux bornes
Soit P = (X, D, C) un réseau de contraintes c = hR, Si ∈ C est dite consistante aux bornes (en anglais bound(Z) consistent) [Bes06b] si et seulement si pour toute variable x ∈ S ayant pour domaine dom(x), les valeurs max(dom(x)) et min(dom(x)) ont chacune un support par rapport à la contrainte c. Le réseau de contraintes est alors dit consistant aux bornes si toutes ses contraintes le sont. Ce niveau de consistance garanti l’existence d’une solution faisant intervenir les bornes des variables. Les travaux de cette thèse s’articulant autour de la planification des tâches au sein d’un data center, la consistance aux bornes prend tout son sens.
Heuristiques de recherche
Bien que la propagation de contraintes permette de réduire a priori l’espace de recherche d’un problème de satisfaction de contraintes, il est nécessaire d’éviter de parcourir jusqu’aux feuilles les chemins ne menant pas à une solution. En d’autres termes, on doit stopper l’exploration d’un chemin dans l’arbre de recherche aussitôt qu’une instanciation viole une contrainte du problème. Il existe plusieurs algorithmes qui assurent cette propriété pour le parcours de l’arbre de recherche d’un CSP. Dans les travaux de cette thèse, nous avons utilisé le Forward checking [BMFL02]. Le principe de l’algorithme de parcours en forward checking est de propager chaque instanciation de valeur dans le réseau. Ceci permet à chaque étape de supprimer des domaines des variables non instanciées les valeurs non consistantes avec l’instanciation courante.
Reste maintenant à déterminer l’ordre dans lequel les variables du problème sont choisies puis instanciées, comment est construit l’arbre de recherche. En effet, selon l’ordre dans lequel les variables d’un problème sont instanciées, on peut détecter plus ou moins rapidement un échec. L’objectif étant de détecter un échec le plus tôt possible, on utilise des heuristiques de recherche qui fixent l’ordre dans lequel les variables sont sélectionnées, et l’ordre dans lequel les valeurs des domaines sont attribuées. Il existe deux principaux types d’heuristique, les heuristiques statiques et les heuristiques dynamiques.
Heuristiques statiques
Le but d’une heuristique fixant l’ordre dans lequel les variables d’un problème sont instanciées est de détecter les échecs au plus tôt. C’est le principe fail first introduit par Haralick [HE80]. Ce principe a donné naissance aux heuristiques statiques. Les heuristiques statiques prédéfinissent un ordre sur les variables et les valeurs avant le début de la recherche. La plus simple est l’heuristique lexicographique qui fixe un ordre lexicographique sur les variables. Dans cet esprit de détection de l’échec le plus tôt possible, l’ordre lexicographique n’est pas toujours la solution adéquate. Une alternative couramment utilisée est l’heuristique du degré. L’heuristique du degré fixe l’ordre d’instanciation des variables en fonction du nombre de contraintes les impliquant.
L’usage des heuristiques statiques présente à mon avis un avantage majeur qui n’est pas souvent mentionné dans la littérature. Du fait qu’elles prédéfinissent un ordre avant le début de la recherche, l’arbre de recherche est le même quel que soit l’algorithme de propagation utilisé. Cette propriété permet de comparer deux différents algorithmes de propagation de contraintes sur la résolution d’une même instance de problème.
Heuristiques dynamiques
Les heuristiques dynamiques spécifient de façon dynamique l’ordre d’instanciation des variables à chaque étape. Le principe fail first reste en vigueur. L’heuristique dom est un exemple d’heuristique dynamique, elle ordonne les variables à chaque étape de propagation en fonction du nombres de valeurs consistantes avec l’instanciation partielle courante.
Le problème avec dom est que si à une étape plusieurs variables ont une même taille de domaine, il devient difficile de choisir la prochaine variable. Pour résoudre ce genre de problème autrement qu’avec un choix aléatoire, Forst et Dechter [FD+95] proposent dom + deg. L’heuristique dom + deg fixe l’ordre des variables en fonction de la taille des domaines et en cas d’égalité, elle repose sur le nombre de contraintes impliquant chacune des variables pour les départager.
Apprentissage non supervisé : K-means
Par opposition à l’apprentissage supervisé, nous présentons ici la notion d’apprentissage dit non supervisé. L’apprentissage non supervisé [HTF09] est un ensemble de techniques d’apprentissage qui permettent de faire des inférences à partir d’un ensemble de données non étiquetés. Les méthodes d’apprentissage non supervisés permettent en général d’apprendre un classificateur à partir des données d’apprentissage. Un des algorithmes d’apprentissage non supervisé les plus populaires est le K-means [PM11].
L’algorithme du K-means permet de partitionner un ensemble de données en un nombre k d’ensemble appelés clusters. Pour un ensemble de données (x1, x2, x3, …, xn), le paramètre k(k ≤ n) spécifiant le nombre de clusters à créer, l’algorithme du K-means procède en trois étapes :
1. Déterminer les coordonnées de k centroïdes correspondant aux k clusters.
2. Calculer la distance de chaque objet xi aux k centroïdes
3. Associer chaque objet a un cluster unique de façon à minimiser le diamètre du cluster. Le diamètre d’un cluster étant la distance entre les deux objets du cluster les plus éloignés l’un de l’autre.
|
Table des matières
1 Introduction
I État de l’art
2 Techniques de modélisation et apprentissage machine.
2.1 Notions de base en programmation par contraintes
2.1.1 Définitions
2.1.2 Propagation de contraintes
2.1.3 Consistance d’arc
2.1.4 Consistance aux bornes
2.1.5 Heuristiques de recherche
2.2 Notions de base en apprentissage machine
2.2.1 Apprentissage supervisé : Réseau de neurones
2.2.2 Apprentissage non supervisé : K-means
3 PPC et apprentissage machine pour le cloud computing
3.1 Programmation par contraintes pour le cloud computing
3.1.1 Planification de tâches dans un data center
3.1.2 Gestionnaire de consolidation pour clusters
3.1.3 Les contraintes sur les séries temporelles
3.2 Apprentissage machine pour le cloud computing
II Contributions
4 Contrainte de précédence et d’intersection de tâches.
4.1 Introduction
4.2 Contrainte d’Intersection de Tâches
4.3 Faisabilité de la Contrainte d’Intersection de Tâches
4.3.1 Borne Réalisables pour l’Intersection Totale
4.3.2 Condition Nécessaire et Suffisante pour la Faisabilité
4.4 Algorithme de Filtrage de la Contrainte TASKINTERSECTION
4.4.1 Caractérisation des Valeurs à Filtrer
4.4.2 Caractérisation du Filtrage
4.5 Implémentation
4.6 Évaluation
4.6.1 Évaluation Comparative de la Contrainte TASKINTERSECTION avec sa Reformulation
4.6.2 Évaluation sur des Instances réelles du Problème de Résumé Vidéo
4.7 Conclusion
5 Modèles de génération et de prédiction pour la charge des data centers.
5.1 Introduction
5.2 Présentation des traces de charge réelles utilisées
5.3 Modèles de prédiction de la charge des data centers
5.3.1 Classification des charges de travail
5.3.2 Modèle à base de programmation par contraintes
5.3.3 Apprentissage sur des séries temporelles avec un réseau de neurones
5.4 Génération de traces de la charge d’un data center
5.4.1 Construction du CSP et génération de nouvelles traces
5.4.2 Évaluation du générateur de traces à base de CSP
5.4.3 Générateur de traces à base de réseau de neurones
5.5 Conclusion
6 Planification énergiquement écologique.
6.1 Introduction et travaux connexes
6.2 Description du problème et définitions
6.2.1 Définitions
6.3 Modélisation du problème
6.3.1 La programmation par contraintes pour le problème de planification énergiquement écologique au sein d’un data center virtualisé
6.3.2 Mise en route et extinction d’un serveur
6.3.3 Modélisation des applications
6.3.4 Coûts de migration
6.3.5 Cosommation mémoire et usage CPU
6.3.6 Minimisation de la consommation d’énergie fossile
6.4 Résolution d’un PPEE
6.5 Evaluation
6.5.1 Description des jeux de données
6.5.2 Modèle énergétique
6.6 Conclusion
7 Conclusion
Télécharger le rapport complet
