Spelling suggestions: "subject:"heuristique.""
141 |
Energy Conservation for Collaborative Applications in Wireless Sensor Networks / Conservation d'énergie pour les applications collaboratives dans les réseaux de capteurs sans filDemigha, Oualid 29 November 2015 (has links)
Les réseaux de capteurs sans fil est une technologie nouvelle dont les applications s'étendent sur plusieurs domaines: militaire, scientifique, médicale, industriel, etc. La collaboration entre les noeuds capteurs, caractérisés par des capacités minimales en termes de capture, de transmission, de traitement et d'énergie, est une nécessité pour réaliser des tâches aussi complexes que la collecte des données, le pistage des objets mobiles, la surveillance des zones sensibles, etc. La contrainte matérielle sur le développement des ressources énergétiques des noeuds capteurs est persistante. D'où la nécessité de l'optimisation logicielle dans les différentes couches de la pile protocolaire et du système d'exploitation des noeuds. Dans cette thèse, nous approchons le problème d'optimisation d'énergie pour les applications collaboratives via les méthodes de sélection des capteurs basées sur la prédiction et la corrélation des données issues du réseau lui-même. Nous élaborons plusieurs méthodes pour conserver les ressources énergétiques du réseau en utilisant la prédiction comme un moyen pour anticiper les actions des noeuds et leurs rôles afin de minimiser le nombre des noeuds impliqués dans la tâche en question. Nous prenons l'application de pistage d'objets mobiles comme un cas d'étude. Ceci, après avoir dresser un état de l'art des différentes méthodes et approches récentes utilisées dans ce contexte. Nous formalisons le problème à l'aide d'un programme linéaire à variables binaires dans le but de trouver une solution générale exacte. Nous modélisons ainsi le problème de minimisation de la consommation d'énergie des réseaux de capteurs sans fil, déployé pour des applications de collecte de données soumis à la contrainte de précision de données, appelé EMDP. Nous montrons que ce problème est NP-Complet. D'où la nécessité de solutions heuristiques. Comme solution approchée, nous proposons un algorithme de clustering dynamique, appelé CORAD, qui adapte la topologie du réseau à la dynamique des données capturées afin d'optimiser la consommation d'énergie en exploitant la corrélation qui pourrait exister entre les noeuds. Toutes ces méthodes ont été implémentées et testées via des simulations afin de montrer leur efficacité. / Wireless Sensor Networks is an emerging technology enabled by the recent advances in Micro-Electro-Mechanical Systems, that led to design tiny wireless sensor nodes characterized by small capacities of sensing, data processing and communication. To accomplish complex tasks such as target tracking, data collection and zone surveillance, these nodes need to collaborate between each others to overcome the lack of battery capacity. Since the development of the batteries hardware is very slow, the optimization effort should be inevitably focused on the software layers of the protocol stack of the nodes and their operating systems. In this thesis, we investigated the energy problem in the context of collaborative applications and proposed an approach based on node selection using predictions and data correlations, to meet the application requirements in terms of energy-efficiency and quality of data. First, we surveyed almost all the recent approaches proposed in the literature that treat the problem of energy-efficiency of prediction-based target tracking schemes, in order to extract the relevant recommendations. Next, we proposed a dynamic clustering protocol based on an enhanced version of the Distributed Kalman Filter used as a prediction algorithm, to design an energy-efficient target tracking scheme. Our proposed scheme use these predictions to anticipate the actions of the nodes and their roles to minimize their number in the tasks. Based on our findings issued from the simulation data, we generalized our approach to any data collection scheme that uses a geographic-based clustering algorithm. We formulated the problem of energy minimization under data precision constraints using a binary integer linear program to find its exact solution in the general context. We validated the model and proved some of its fundamental properties. Finally and given the complexity of the problem, we proposed and evaluated a heuristic solution consisting of a correlation-based adaptive clustering algorithm for data collection. We showed that, by relaxing some constraints of the problem, our heuristic solution achieves an acceptable level of energy-efficiency while preserving the quality of data.
|
142 |
Recherche et développement du Logiciel Intelligent de Cartographie Inversée, pour l’aide à la compréhension de texte par un public dyslexique / Research and development of the "Logiciel Intelligent de Cartographie Inversée", a tool to help dyslexics with reading comprehension.Laurent, Mario 05 October 2017 (has links)
Les enfants souffrant de troubles du langage, comme la dyslexie, rencontrent de grandes difficultés dans l'apprentissage de la lecture et dans toute tâche de lecture, par la suite. Ces difficultés compromettent grandement l'accès au sens des textes auxquels ils sont confrontés durant leur scolarité, ce qui implique des difficultés d'apprentissage et les entraîne souvent vers une situation d'échec scolaire. Depuis une quinzaine d'années, des outils développés dans le domaine du Traitement Automatique des Langues sont détournés pour être utilisés comme stratégie d'aide et de compensation pour les élèves en difficultés. Parallèlement, l'usage de cartes conceptuelles ou de cartes heuristiques pour aider les enfants dyslexiques à formuler leurs pensées, ou à retenir certaines connaissances, s'est développé. Ce travail de thèse vise à répertorier et croiser, d'une part, les connaissances sur le public dyslexique, sa prise en charge et ses difficultés, d'autre part, les possibilités pédagogiques ouvertes par l'usage de cartes, et enfin, les technologies de résumé automatique et d'extraction de mots-clés. L'objectif est de réaliser un logiciel novateur capable de transformer automatiquement un texte donné en une carte, celle-ci doit faciliter la compréhension du texte tout en comprenant des fonctionnalités adaptées à un public d'adolescents dyslexiques. Ce projet a abouti, premièrement, à la réalisation d'une expérimentation exploratoire, sur l'aide à la compréhension de texte grâce aux cartes heuristiques, qui permet de définir de nouveaux axes de recherche ; deuxièmement, à la réalisation d'un prototype de logiciel de cartographie automatique qui est présenté en fin de thèse / Children with language impairment, such as dyslexia, are often faced with important difficulties when learning to read and during any subsequent reading tasks. These difficulties tend to compromise the understanding of the texts they must read during their time at school. This implies learning difficulties and may lead to academic failure. Over the past fifteen years, general tools developed in the field of Natural Language Processing have been transformed into specific tools for that help with and compensate for language impaired students' difficulties. At the same time, the use of concept maps or heuristic maps to encourage dyslexic children express their thoughts, or retain certain knowledge, has become popular. This thesis aims to identify and explore knowledge about the dyslexic public, how society takes care of them and what difficulties they face; the pedagogical possibilities opened up by the use of maps; and the opportunities created by automatic summarization and Information Retrieval fields. The aim of this doctoral research project was to create an innovative piece of software that automatically transforms a given text into a map. It was important that this piece of software facilitate reading comprehension while including functionalities that are adapted to dyslexic teenagers. The project involved carrying out an exploratory experiment on reading comprehension aid, thanks to heuristic maps, that make the identification of new research topics possible, and implementing an automatic mapping software prototype that is presented at the end of this thesis
|
143 |
Évolution des projets de formation de futurs enseignants du primaire au contact de situations probabilistesRioux, Miranda 06 1900 (has links)
Il semble y avoir des attentes réciproques non comblées en formation initiale à l’enseignement des mathématiques. Cherchant à comprendre la genèse de ces attentes, nous nous sommes intéressée à la vision que les étudiants nourrissent des phénomènes d’enseignement. Ayant postulé que les étudiants ont une vision déterministe de ces phénomènes, et considérant que leur anticipation oriente leur projet de formation, nous nous sommes attaquée au problème de la rencontre des projets des étudiants et des formateurs. Deux objectifs généraux ont été formulés : le premier concerne la description des projets de formation des étudiants tandis que le second concerne l’expérimentation d’une séquence de situations susceptible de faire évoluer leurs projets.
Cette recherche a été menée auprès de 58 étudiants du baccalauréat en enseignement en adaptation scolaire et sociale d’une même université, lesquels entamaient leur formation initiale à l’enseignement des mathématiques. Afin d’explorer les projets qu’ils nourrissent a priori, tous les étudiants ont complété un questionnaire individuel sur leur vision des mathématiques et de leur enseignement et ont participé à une première discussion de groupe sur le sujet. Une séquence de situations probabilistes leur a ensuite été présentée afin d’induire une complexification de leur projet. Enfin, cette expérimentation a été suivie d’une seconde discussion de groupe et complétée par la réalisation de huit entretiens individuels.
Il a été mis en évidence que la majorité des étudiants rencontrés souhaitent avant tout évoluer en tant qu’enseignant, en développant leur capacité à enseigner et à faire apprendre ou comprendre les mathématiques. Bien que certaines visées se situent dans une perspective transmissive, celles-ci ne semblent pas représentatives de l’ensemble des projets "visée". De plus, même si la plupart des étudiants rencontrés projettent de développer des connaissances relatives aux techniques et aux méthodes d’enseignement, la sensibilité à la complexité dont certains projets témoignent ne permet plus de réduire les attentes des étudiants à l’endroit de leur formation à la simple constitution d’un répertoire de techniques d’enseignement réputées efficaces. En ce qui a trait aux modes d’anticipation relevés a priori, nos résultats mettent en relief des anticipations se rattachant d’abord à un mode adaptatif, puis à un mode prévisionnel. Aucune anticipation se rattachant à un mode prospectif n’a été recensée a priori.
La séquence a permis aux étudiants de s’engager dans une dialectique d’action, de formulation et de validation, elle les a incités à recourir à une approche stochastique ainsi qu’à porter un jugement de probabilité qui prenne en compte la complexité de la situation. A posteriori, nous avons observé que les projets "visée" de certains étudiants se sont complexifiés. Nous avons également noté un élargissement de la majorité des projets, lesquels considèrent désormais les autres sommets du triangle didactique. Enfin, des anticipations se rattachant à tous les modes d’anticipation ont été relevées. Des anticipations réalisées grâce à un mode prospectif permettent d’identifier des zones d’incertitude et de liberté sur lesquelles il est possible d’agir afin d’accroître la sensibilité à la complexité des situations professionnelles à l’intérieur desquelles les futurs enseignants devront se situer. / There seems to be unfulfilled reciprocal expectations in mathematical education and initial preparation of teachers. While trying to understand the genesis of their expectations, we were interested in the vision that future teachers have of the educational phenomena. Having postulated that these students have a deterministic view of these phenomena and considering that their anticipation guides their training project, we addressed the problem of the encounter of student and educator projects. Two general objectives were formulated: the first aims at describing student training projects while the second addresses the development of a sequence of situations to help enrich their initial projects.
This research was conducted among 58 undergraduate students in special education at a single university. They were beginning their initial training in teaching mathematics. In order to explore their initial projects, all students completed a questionnaire to inform on their personal vision of mathematics and its teaching. They also participated in an initial group discussion on the subject. A sequence of probabilistic situations was then presented to induce enrichment of their project. Finally, this experiment was followed by a second group discussion and completed with eight interviews.
It was highlighted that the majority of the students met want to evolve primarily as a teacher, developing their ability to teach and stimulate learning and understanding of mathematics. Although some project goals fall into a transmissive perspective, these do not seem representative of the overall goals of the projects. Moreover, although most students want to develop knowledge of techniques and teaching methods, the sensitivity to complexity shown in some projects does not allow to reduce students' expectations regarding their training to the building of a repertoire of teaching techniques deemed effective. Regarding modes of anticipation identified initially, our results highlight anticipations connected with first an adaptive mode and then a forecast mode. We found no initial anticipation connected with a prospective mode.
The sequence has allowed students to engage in a dialectic of action, formulation and validation, it prompted them to use a stochastic approach and to make probability judgment that takes into account the complexity of the situation. Afterwards, we observed that the projects of some students had become more complex. We also noted a widening of the majority of projects which opened to considering other vertices of the didactic triangle. Finally, anticipations relating to all modes of anticipation were identified. Anticipations made through a prospective mode helped identify areas of uncertainty and freedom upon which it appears possible to act, to increase sensitivity to the complexity of the educational situations and the act of teaching.
|
144 |
Gestion adaptative des ressources dans les réseaux maillés sans fil à multiples-radios multiples-canauxRezgui, Jihene 08 1900 (has links)
Depuis quelques années, la recherche dans le domaine des réseaux maillés sans fil ("Wireless Mesh Network (WMN)" en anglais) suscite un grand intérêt auprès de la communauté des chercheurs en télécommunications. Ceci est dû aux nombreux avantages que la technologie WMN offre, telles que l'installation facile et peu coûteuse, la connectivité fiable et l'interopérabilité flexible avec d'autres réseaux existants (réseaux Wi-Fi, réseaux WiMax, réseaux cellulaires, réseaux de capteurs, etc.). Cependant, plusieurs problèmes restent encore à résoudre comme le passage à l'échelle, la sécurité, la qualité de service (QdS), la gestion des ressources, etc. Ces problèmes persistent pour les WMNs, d'autant plus que le nombre des utilisateurs va en se multipliant. Il faut donc penser à améliorer les protocoles existants ou à en concevoir de nouveaux.
L'objectif de notre recherche est de résoudre certaines des limitations rencontrées à l'heure actuelle dans les WMNs et d'améliorer la QdS des applications multimédia temps-réel (par exemple, la voix). Le travail de recherche de cette thèse sera divisé essentiellement en trois principaux volets: le contrôle d‟admission du trafic, la différentiation du trafic et la réaffectation adaptative des canaux lors de la présence du trafic en relève ("handoff" en anglais).
Dans le premier volet, nous proposons un mécanisme distribué de contrôle d'admission se basant sur le concept des cliques (une clique correspond à un sous-ensemble de liens logiques qui interfèrent les uns avec les autres) dans un réseau à multiples-sauts, multiples-radios et multiples-canaux, appelé RCAC. Nous proposons en particulier un modèle analytique qui calcule le ratio approprié d'admission du trafic et qui garantit une probabilité de perte de paquets dans le réseau n'excédant pas un seuil prédéfini. Le mécanisme RCAC permet d‟assurer la QdS requise pour les flux entrants, sans dégrader la QdS des flux existants. Il permet aussi d‟assurer la QdS en termes de longueur du délai de bout en bout pour les divers flux.
Le deuxième volet traite de la différentiation de services dans le protocole IEEE 802.11s afin de permettre une meilleure QdS, notamment pour les applications avec des contraintes temporelles (par exemple, voix, visioconférence). À cet égard, nous proposons un mécanisme d'ajustement de tranches de temps ("time-slots"), selon la classe de service, ED-MDA (Enhanced Differentiated-Mesh Deterministic Access), combiné à un algorithme efficace de contrôle d'admission EAC (Efficient Admission Control), afin de permettre une utilisation élevée et efficace des ressources. Le mécanisme EAC prend en compte le trafic en relève et lui attribue une priorité supérieure par rapport au nouveau trafic pour minimiser les interruptions de communications en cours.
Dans le troisième volet, nous nous intéressons à minimiser le surcoût et le délai de re-routage des utilisateurs mobiles et/ou des applications multimédia en réaffectant les canaux dans les WMNs à Multiples-Radios (MR-WMNs). En premier lieu, nous proposons un modèle d'optimisation qui maximise le débit, améliore l'équité entre utilisateurs et minimise le surcoût dû à la relève des appels. Ce modèle a été résolu par le logiciel CPLEX pour un nombre limité de noeuds. En second lieu, nous élaborons des heuristiques/méta-heuristiques centralisées pour permettre de résoudre ce modèle pour des réseaux de taille réelle. Finalement, nous proposons un algorithme pour réaffecter en temps-réel et de façon prudente les canaux aux interfaces. Cet algorithme a pour objectif de minimiser le surcoût et le délai du re-routage spécialement du trafic dynamique généré par les appels en relève. Ensuite, ce mécanisme est amélioré en prenant en compte l‟équilibrage de la charge entre cliques. / In the last few years, Wireless Mesh Networks (WMNs) area brought a new field of advanced research among network specialized scientists. This is due to the many advantages which WMN technology offers, such as: easy and inexpensive installation, reliable connectivity and flexible interoperability with other existing networks (Wi-Fi, WiMax, Cellular, Sensors, WPAN networks, etc.). However, several problems still remain to be solved such as the scalability, the security, the quality of service (QoS), the resources management, etc. These problems persist for WMNs, therefore the researchers propose to improve the existing protocols or to conceive new protocols for WMNs.
In order to solve some of the current limitations met in the wireless networks and to improve QoS of real time multimedia applications in such networks, our research will be divided primarily into three parts: traffic admission control, traffic differentiation and handoff-aware channel assignment schemes.
In the first part, we propose a distributed admission control scheme for WMNs, namely, Routing on Cliques (a clique is defined as a subset of logical links that interfere with each other) Admission Control (RCAC). Particularly, we propose an analytical model to compute the appropriate acceptance ratio and guarantee that the packet loss probability in the network does not exceed a threshold value. The model also allows computing end-to-end delay to process flow requests with delay constraints.
In the second part, we design an efficient scheduler for Mesh Deterministic Access (MDA) in IEEE 802.11s-based WMNs, called Enhanced Differentiated-MDA (ED-MDA) to support voice and video applications with strict requirements on delay and on blocking/dropping probability. ED-MDA together with Enhanced Admission Control, namely EAC, reserves the minimum amount of necessary resources while maintaining an acceptable handoff call dropping and high resource utilization.
The final section addresses handoff-aware channel assignment (CA) problem in Multiple Radios WMNs (MR-WMNs). In this section, we first propose a multi-objective optimization model that, besides maximizing throughput, improves fairness and handoff experience of mesh clients. In this model, the Jain’s index is used to maximize users’ fairness and to allow same channel assignments to links involved in the same high handoff traffic, thus reducing handoff-triggered re-routing characterized by its high latency. Second, we solved this model to obtain exact solutions by the CPLEX software for a limited number of nodes. We therefore propose to use centralized heuristics/meta-heuristics algorithms as an offline CA process to obtain near-optimal solutions for larger instances (real size network). Moreover, in order to adapt to traffic dynamics caused especially by user handoffs, an online CA scheme is proposed that carefully re-assigns channels to interfaces with the purpose of continuously minimizing the re-routing overhead/latency during user handoffs. This online scheme is improved using load balancing.
|
145 |
Comparaison de réseaux biologiquesMohamed Babou, Hafedh 06 November 2012 (has links) (PDF)
La comparaison de réseaux biologiques est actuellement l'une des approches les plus prometteuses pour aider à la compréhension du fonctionnement des organismes vivants. Elle apparaît comme la suite attendue de la comparaison de séquences biologiques dont l'étude ne représente en réalité que l'aspect génomique des informations manipulées par les biologistes. Dans cette thèse, nous proposons une approche innovante permettant de comparer deux réseaux biologiques modélisés respectivement par un graphe orienté D et un graphe non-orienté G, et dotés d'une fonction f établissant la correspondance entre les sommets des deux graphes. L'approche consiste à extraire automatiquement une structure dans D, biologiquement significative, dont les sommets induisent dans G, par f, une structure qui soit aussi biologiquement significative. Nous réalisons une étude algorithmique du problème issu de notre approche en commençant par sa version dans laquelle D est acyclique (DAG). Nous proposons des algorithmes polynomiaux pour certains cas, et nous montrons que d'autres cas sont algorithmiquement difficiles (NP-complets). Pour résoudre les instances difficiles, nous proposons une bonne heuristique et un algorithme exact basé sur la méthode branch-and-bound. Pour traiter le cas où D est cyclique, nous introduisons une méthode motivée par des hypothèses biologiques et consistant à décomposer D en DAGs tels que les sommets de chaque DAG induisent dans G un sous-graphe connexe. Nous étudions également dans cette thèse, l'inférence des voies de signalisation en combinant les informations sur les causes et sur les effets des événements extra-cellulaires. Nous modélisons ce problème par un problème d'orientation de graphes mixtes et nous effectuons une étude de complexité permettant d'identifier les instances faciles et celles difficiles.
|
146 |
Impairment-aware design and performance evaluation of all-optical wavelength convertible networks / Conception et évaluation des performances des réseaux à conversion de longueur d'onde tout-optique gérant les dégradations du signalChouman, Hussein 22 March 2019 (has links)
La croissance continue du trafic Internet implique une augmentation de la consommation d'énergie en raison des nombreuses conversions optique à électronique(OEO) requises par les routeurs et les commutateurs. L'utilisation de réseaux transparents pourraient freiner cette croissance incontrôlée, mais le maintien des données dans le domaine optique a deux conséquences néfastes: une accumulation du bruit et des non-linéarités de l'amplification qui dégrade fortement les performances au niveau de la couche physique. et la contrainte de continuité de longueur d'onde (WCC) reflétant la conservation de la longueur d'onde du signal optique dans les réseaux optiques multiplexés en longueur d'onde (WDM) qui dégradent les performances du réseau, notamment sa probabilité de blocage. Les convertisseurs de longueur d'onde (WC) peuvent pallier la contrainte WCC, mais les seuls dispositifs suffisamment matures disponibles dans le commerce sont les WC basés sur OEO (OEO-WC). Cependant, leur coût augmente avec les débits binaires. D'autre part, des convertisseurs de longueur d'onde tout optique (AO-WC) ont été démontrés dans des laboratoires de recherche, avec toutefois une plage de conversion limitée et une dégradation du signal converti.Dans cette thèse, nous concevons la couche de transmission en utilisant deux ensembles de formats de modulation différents avec des plages de débits différentes; et par conséquent différents modèles d'estimation de performance. Au niveau du réseau, nos analyses montrent que la contribution des WC dépend des demandes de trafic servant à l’ordre dans un scénario de planification du réseau; qu'en utilisant des algorithmes fixed-alternate-routing (FAR) ou least-loaded-routing (LLR) et un algorithme d'affectation de longueur d'onde first-fit (FF), les AO-WCs offrent les mêmes améliorations de performances que les OEO-WC. De plus, nous identifions une plage de conversion et une cascadabilité optimale d’AO-WC qui montre que le LLR nécessite un nombre de conversions par canal inférieur au FAR. / The continuous growth of Internet traffic implies an increased power consumption due to the many optical-to-electronic (OEO) conversions required by routers and switches. Transparent networks could curb this uncontrolled growth, but keeping the data in the optical domain has two adverse consequences: physical layer impairments accumulation which strongly degrades the performance due to amplication noise and non-linearities; and the wavelength continuity constraint (WCC) to keep the opticalsignal's wavelength unchanged in wavelength-division-multiplexed (WDM) optical networks which degrades network blocking performance. Wavelength converters (WCs) can alleviate the WCC constraint, but the only commercially available devices are the OEO-based WCs (OEO-WCs), however, their cost increases with bit-rates. On the other hand, all-optical wavelength converters (AO-WCs) have been demonstrated in research laboratories albeit with a limited conversion range and a performance that degrades converted signal's quality.In this thesis, we design the transmission layer using two different modulation formats sets with different bit-rates ranges; and consequently different performance estimation models. At the network level, our analyses show that WCs' contribution depends on traffic demands serving ordering in the online traffic assumption; that using xed-alternate routing (FAR) or least-loaded routing (LLR) algorithms and first-fit (FF) wavelength assignment algorithm, AO-WCs give the same performance enhancement as OEO-WCs. Moreover, we identify an optimum AO-WC conversion range and cascadability which shows that LLR requires lower number of conversions per channel compared to FAR.
|
147 |
Comparaisons de séquences biologiques sur architecture massivement multi-cœursTran, Tuan Tu 21 December 2012 (has links) (PDF)
Rechercher les similarités entre séquences est une opération fondamentale en bioinformatique, que cela soit pour étudier des questions biologiques ou bien pour traiter les données issues de séquenceurs haut-débit. Il y a un vrai besoin d'algorithmes capables de traiter des millions de séquences rapidement. Pour trouver des similarités approchées, on peut tout d'abord considérer de petits mots exacts présents dans les deux séquences, les graines, puis essayer d'étendre les similarités aux voisinages de ces graines. Cette thèse se focalise sur la deuxième étape des heuristiques à base de graines : comment récupérer et comparer efficacement ces voisinages des graines, pour ne garder que les bons candidats ? La thèse explore différentes solutions adaptées aux processeurs massivement multicoeurs: aujourd'hui, les GPUs sont en train de démocratiser le calcul parallèle et préparent les processeurs de demain. La thèse propose des approches directes (extension de l'algorithme bit-parallèle de Wu-Manber, publiée à PBC 2011, et recherche dichotomique) ou bien avec un index supplémentaire (utilisation de fonctions de hash parfaites). Chaque solution a été pensée pour tirer le meilleur profit des architectures avec un fort parallélisme à grain fin, en utilisant des calculs intensifs mais homogènes. Toutes les méthodes proposées ont été implémentés en OpenCL, et comparées sur leur temps d'exécution. La thèse se termine par un prototype de read mapper parallèle, MAROSE, utilisant ces concepts. Dans certaines situations, MAROSE est plus rapide que les solutions existantes avec une sensibilité similaire.
|
148 |
Méthodes hybrides parallèles pour la résolution de problèmes d'optimisation combinatoire : application au clustering sous contraintes / Parallel hybrid methods for solving combinatorial optimization problems : application to clustering under constraintsOuali, Abdelkader 03 July 2017 (has links)
Les problèmes d’optimisation combinatoire sont devenus la cible de nombreuses recherches scientifiques pour leur importance dans la résolution de problèmes académiques et de problèmes réels rencontrés dans le domaine de l’ingénierie et dans l’industrie. La résolution de ces problèmes par des méthodes exactes ne peut être envisagée à cause des délais de traitement souvent exorbitants que nécessiteraient ces méthodes pour atteindre la (les) solution(s) optimale(s). Dans cette thèse, nous nous sommes intéressés au contexte algorithmique de résolution des problèmes combinatoires, et au contexte de modélisation de ces problèmes. Au niveau algorithmique, nous avons appréhendé les méthodes hybrides qui excellent par leur capacité à faire coopérer les méthodes exactes et les méthodes approchées afin de produire rapidement des solutions. Au niveau modélisation, nous avons travaillé sur la spécification et la résolution exacte des problématiques complexes de fouille des ensembles de motifs en étudiant tout particulièrement le passage à l’échelle sur des bases de données de grande taille. D'une part, nous avons proposé une première parallélisation de l'algorithme DGVNS, appelée CPDGVNS, qui explore en parallèle les différents clusters fournis par la décomposition arborescente en partageant la meilleure solution trouvée sur un modèle maître-travailleur. Deux autres stratégies, appelées RADGVNS et RSDGVNS, ont été proposées qui améliorent la fréquence d'échange des solutions intermédiaires entre les différents processus. Les expérimentations effectuées sur des problèmes combinatoires difficiles montrent l'adéquation et l'efficacité de nos méthodes parallèles. D'autre part, nous avons proposé une approche hybride combinant à la fois les techniques de programmation linéaire en nombres entiers (PLNE) et la fouille de motifs. Notre approche est complète et tire profit du cadre général de la PLNE (en procurant un haut niveau de flexibilité et d’expressivité) et des heuristiques spécialisées pour l’exploration et l’extraction de données (pour améliorer les temps de calcul). Outre le cadre général de l’extraction des ensembles de motifs, nous avons étudié plus particulièrement deux problèmes : le clustering conceptuel et le problème de tuilage (tiling). Les expérimentations menées ont montré l’apport de notre proposition par rapport aux approches à base de contraintes et aux heuristiques spécialisées. / Combinatorial optimization problems have become the target of many scientific researches for their importance in solving academic problems and real problems encountered in the field of engineering and industry. Solving these problems by exact methods is often intractable because of the exorbitant time processing that these methods would require to reach the optimal solution(s). In this thesis, we were interested in the algorithmic context of solving combinatorial problems, and the modeling context of these problems. At the algorithmic level, we have explored the hybrid methods which excel in their ability to cooperate exact methods and approximate methods in order to produce rapidly solutions of best quality. At the modeling level, we worked on the specification and the exact resolution of complex problems in pattern set mining, in particular, by studying scaling issues in large databases. On the one hand, we proposed a first parallelization of the DGVNS algorithm, called CPDGVNS, which explores in parallel the different clusters of the tree decomposition by sharing the best overall solution on a master-worker model. Two other strategies, called RADGVNS and RSDGVNS, have been proposed which improve the frequency of exchanging intermediate solutions between the different processes. Experiments carried out on difficult combinatorial problems show the effectiveness of our parallel methods. On the other hand, we proposed a hybrid approach combining techniques of both Integer Linear Programming (ILP) and pattern mining. Our approach is comprehensive and takes advantage of the general ILP framework (by providing a high level of flexibility and expressiveness) and specialized heuristics for data mining (to improve computing time). In addition to the general framework for the pattern set mining, two problems were studied: conceptual clustering and the tiling problem. The experiments carried out showed the contribution of our proposition in relation to constraint-based approaches and specialized heuristics.
|
Page generated in 0.5609 seconds