De nos jours, l'intérêt porté à la préservation de l'environnement à travers la réduction des émissions de gaz à effet de serre prend de plus en plus d'ampleur. Depuis 2006,la politique multimodale a évolué vers une politique co-modale qui n'oppose plus la voiture au transport public mais encourage une combinaison de tous les modes de transport sans favorisation dans le but d'une optimisation du service. Placés dans ce cadre, le but de cette thèse est de mettre en œuvre un système de gestion de véhicules partagés qui recouvre tous les services de transports existants tel que le transport public, le covoiturage, les véhicules en libre service et qui capable de satisfaire les demandes des utilisateurs en leur fournissant des itinéraires co-modaux optimisés en terme de temps, coût et émission des gaz à effet de serre tout en respectant leurs préférences et priorités. En recevant plusieurs requêtes simultanées en un court laps de temps, le système doit être capable à la fois de décomposer les solutions en tronçons que nous appelons Routes, en respectant toutes les similarités entre les différentes demandes et de regrouper les informations de manière cohérente pour déterminer les combinaisons de Routes possibles. Vu l'aspect dynamique et distribué du problème, une stratégie de résolution efficace mettant à profit une mixture de concepts ; à savoir les systèmes multi-agents et l'optimisation a été mise en place. Les résultats expérimentaux présentés dans cette thèse justifient l'importance de la co-modalité et la nécessité de mettre à profit la complémentarité entre les véhicules partagés et les autres moyens de transport à travers un système intelligent et global

Les travaux de recherche présentés dans cette thèse s'intègrent dans le cadre du projet national VIATIC.MOBILITE du pôle de compétitivité I-TRANS « Le ferroviaire au cœur des systèmes de transports innovants » (http://www.i-trans.org/index.htm). De nos jours, les informations liées au déplacement et à la mobilité dans un réseau de transport représentent sans aucun doute un potentiel important. En effet, on peut imaginer une infinité de services innovants liés à la mobilité, non seulement à destination du grand public, mais également à des entreprises, dans le conseil en mobilité pour leurs plans de déplacement. Le but de cette thèse est donc de fournir un système d'aide à la mobilité qui s'articule autour des motifs de déplacements quotidiens, occasionnels, de tourisme, de culture, etc. avec la possibilité de pouvoir bénéficier d'une information pertinente et exploitable.<br />Ces travaux de recherche visent à mettre en œuvre un Système d'Information de Transport Multimodal (SITM) pour optimiser la gestion de flux des requêtes utilisateurs qui peuvent être nombreuses et simultanées. Dans ce cas, le SITM doit pouvoir procéder par des processus de décomposition des requêtes simultanées en un ensemble de tâches indépendantes. Chaque tâche correspond à un service qui peut être proposé par plusieurs fournisseurs d'information, en concurrence, avec différents couts, formats et temps de réponse. Un fournisseur d'information voulant proposer ses services via le SITM, doit d'abord y enregistrer son système d'information, en assumant la responsabilité des aspects juridiques et qualitatifs de ses données. Le SITM est donc lié à un Réseau informatique Etendu et distribué de Transport Multimodal (RETM) qui comporte plusieurs sources d'information hétérogènes des différents services proposés aux utilisateurs de transport.<br />L'aspect dynamique, distribué et ouvert du problème, nous a conduits à adopter une modélisation multi-agent pour assurer au système une évolution continue et une flexibilité pragmatique. Le système multi-agent proposé s'appuie sur les métaheuristiques pour la recherche et la composition des services; la recherche des services se base sur le paradigme Agent Mobile (AM) utilisant un algorithme d'optimisation dynamique de construction des Plans De Routes (PDR). Cette première étape d'optimisation prépare les parcours des AMs en prenant en considération l'état du RETM. La composition des services utilise les algorithmes évolutionnistes pour optimiser les réponses en termes de coût et de temps, sachant qu'une réponse à une requête utilisateur ne doit pas dépasser un temps maximum autorisé et qu'un utilisateur cherche toujours à avoir le meilleur rapport qualité prix pour les services qu'il demande.<br />Enfin, le SITM prend en considération les éventuelles perturbations sur le RETM (pannes, goulets d'étranglements, etc.) pour satisfaire les requêtes utilisateurs dans tous les cas de figure. Dans ce contexte, nous avons créé un protocole de négociation entre les agents mobiles et les agents responsables des choix des fournisseurs d'information pour les services demandés, ces agents sont appelés agents Ordonnanceurs. Le protocole proposé dépasse les limites d'une communication agent traditionnelle, ce qui nous a incités à associer au système une ontologie flexible qui permet d'automatiser les différents types d'échanges entre les agents grâce à un vocabulaire approprié. <br />Les résultats expérimentaux présentés dans cette thèse justifient l'utilisation du paradigme agent mobile dans notre système qui remplace parfaitement bien les paradigmes classiques telle que l'architecture client/serveur. Les simulations présentées montrent différents scénarios de gestion d'un nombre des requêtes simultanées plus ou moins important. En effet, quelque soit le nombre de requêtes utilisateurs formulées pendant un court laps de temps , le système se charge de leur décomposition, de l'identification des services demandés et des fournisseurs d'information susceptibles d'y répondre.

La dynamique de frappe au clavier est une modalité biométrique comportementale qui permet d'authentifier des individus selon leur façon de taper au clavier. Un tel système est peu coûteux, car il ne nécessite pas de matériel d'acquisition autre que le clavier de l'ordinateur, et est facilement accepté par l'utilisateur. Nous nous sommes principalement intéressé aux systèmes statiques où le texte saisit par l'utilisateur est connu à l'avance par la machine. Malheureusement, les performances de cette modalité sont plutôt médiocres en raison de la forte variabilité de la donnée biométrique. Cette variabilité est due à l'état émotionnel de la personne, l'apprentissage de la façon de taper, \ldots Nous proposons dans cette thèse différentes contributions permettant d'améliorer les performances de reconnaissance de systèmes de dynamique de frappe au clavier (DDF). Nous effectuons également une analyse des bases publiques permettant d'évaluer la performance de nouveaux systèmes de reconnaissance. Une contribution est la mise au point d'un système de DDF par mot de passe partagé. Nous étudions ensuite la fusion multibiométrique avec la dynamique de frappe au clavier et la reconnaissance faciale afin d'augmenter les performances des deux systèmes. Nous montrons, sur deux jeux de données différents, qu'il est possible de reconnaitre le genre d'un individu suivant sa façon de taper au clavier. Enfin, nous présentons une nouvelle méthode de mise à jour de la référence biométrique qui permet de prendre en compte le vieillissement de la donnée biométrique, afin de ne pas avoir une diminution des performances de reconnaissance au cours du temps.

Ma thèse s'inscrit dans le domaine de l'ingénierie de l'interaction homme-machine. Elle traite de la conception d'interfaces hommes machine (IHM). La créativité n'y est souvent considérée que de manière marginale. Pourtant l'effervescence technologique et la diversité résultante des contextes d'usage appellent à de plus en plus de créativité. Ma thèse soutient le principe que l'innovation passe par l'application de processus créatifs. Dès lors, le défi est de savoir explorer largement et efficacement l'espace de conception dès les phases amont du processus. Il convient donc d'intégrer et d'enseigner la créativité dans les processus de conception d'IHM, en particulier pour les concepteurs débutants.Ce positionnement sur le sujet provient d'une double approche : d'une part théorique, avec un état de l'art explorant les dimensions de la créativité et les outils informatiques de support à la créativité ; d'autre part empirique, avec quatre mises en pratique de la créativité dans des domaines de conception différents comme l'architecture, la conception de produit et la conception de systèmes interactifs. Je construis ma contribution sur les principes suivants : (1) la créativité n'est pas réservée à une élite, mais peut être travaillée et renforcée par des outils informatiques ; (2) ces outils doivent soutenir la motivation, la recherche d'inspiration, l'exploration en largeur, et les connaissances relatives au domaine et aux processus de conception. Selon une démarche réflexive, j'applique ces mêmes principes dans ma thèse. Je propose une exploration en largeur du support à la créativité via cinq contributions logicielles complémentaires : Maestro et Bank pour la capitalisation des connaissances ; WebGallery, BrianStorming et Magellan pour l'inspiration et l'exploration de l'espace de conception. Plus précisément, Maestro traite de la capitalisation des processus de conception tandis que BANK assure la structuration et la capitalisation des connaissances en IHM via un graphe de modèles. WebGallery est une galerie de sites web pour inspirer les concepteurs : je conduis une expérimentation sur la perception humaine du style d'un site web. BrianStorming est un assistant au brainstorming : il fournit des suggestions pendant une séance de brainstorming électronique. Magellan est un environnement interactif à base d'algorithmes génétiques qui génèrent et transforment automatiquement des IHM pour un problème de conception donné. Par ce positionnement et ces contributions logicielles, l'ordinateur change de statut : de simple outil, il devient un concepteur assistant, partenaire du processus de créativité. / My PhD thesis contributes to the engineering of Human Computer Interaction (HCI). It deals with the design of User Interfaces (UI). I claim that creative processes should be better considered, and supported by tools especially for novice designers. The challenge is to speed up the exploration of the design space at the early stages of the process. This claim is grounded in both a theoretical state of the art in creativity and creativity support tools, and in practice of the topic with four hands-on experiences of creativity in different areas of design such as architecture, product design and UI design. I build my contribution on the following principles: (1) creativity is not reserved for the elite, but can be tailored and fostered by software tools; (2) the tools must leverage motivation, inspiration, wide exploration, and knowledge in UI and design processes. Through a reflective process, I apply these principles to my thesis. I explore a wide range of creativity support tools through five complementary software contributions: Maestro and Bank for supporting knowledge capitalization; WebGallery, BrianStorming and Magellan for fostering inspiration and exploration of the design space. Maestro addresses the capitalization of design processes whilst BANK gathers knowledge in HCI as a graph of models. WebGallery is a gallery of websites to inspire designers: I report an experiment on human perception of websites styles. BrianStorming is a brainstorming assistant: it provides suggestions in a electronic brainstorming session. Magellan is an interactive environment based on genetic algorithms that automatically generate and transform UIs for a given design problem. This changes the role of the computer: from a simple tool, it becomes a designer's partner in the creative process.

La quantité d'images disponible sur Internet ne fait que croître, engendrant un besoin d'algorithmes permettant de fouiller ces images et retrouver de l'information. Les systèmes de recherche d'images par le contenu ont été développées dans ce but. Mais les bases de données grandissant, de nouveaux défis sont apparus. Dans cette thèse, la classification à grain fin est étudiée en particulier. Elle consiste à séparer des images qui sont relativement semblables visuellement mais représentent différents concepts, et à regrouper des images qui sont différentes visuellement mais représentent le même concept. Il est montré dans un premier temps que les techniques classiques de recherche d'images par le contenu rencontrent des difficultés à effectuer cette tâche. Même les techniques utilisant les machines à vecteur de support (SVM), qui sont très performants pour la classification, n'y parviennent pas complètement. Ces techniques n'explorent souvent pas assez l'espace de recherche pour résoudre ce problème. D'autres méthodes, comme les algorithmes évolutionnaires sont également étudiées pour leur capacité à identifier des zones intéressantes de l'espace de recherche en un temps raisonnable. Toutefois, leurs performances restent encore limitées. Par conséquent, l'apport de la thèse consiste à proposer un système hybride combinant un algorithme évolutionnaire et un SVM a finalement été développé. L'algorithme évolutionnaire est utilisé pour construire itérativement un ensemble d'apprentissage pour le SVM. Ce système est évalué avec succès sur la base de données Caltech-256 contenant envieront 30000 images réparties en 256 catégories / Given the ever growing amount of visual content available on the Internet, the need for systems able to search through this content has grown. Content based image retrieval systems have been developed to address this need. But with the growing size of the databases, new challenges arise. In this thesis, the fine grained classification problem is studied in particular. It is first shown that existing techniques, and in particular the support vector machines which are one of the best image classification technique, have some difficulties in solving this problem. They often lack of exploration in their process. Then, evolutionary algorithms are considered to solve the problem, for their balance between exploration and exploitation. But their performances are not good enough either. Finally, an hybrid system combining an evolutionary algorithm and a support vector machine is proposed. This system uses the evolutionary algorithm to iteratively feed the support vector machine with training samples. The experiments conducted on Caltech-256, a state of the art database containing around 30000 images, show very encouraging results

Il a été observé que l'exécution des heuristiques de recherche aléatoire dépend d'un ou de plusieurs paramètres. Un certain nombre de résultats montrent un avantage des paramètres dynamiques, c'est-à-dire que les paramètres de l'algorithme sont modifiés au cours de son exécution. Dans ce travail, nous montrons que la complexité de la boîte noire sans biais de la classe de fonction de référence OneMax est $n ln(n) - cn pm o(n)$ pour une constante $c$ comprise entre $0.2539$ et $0.2665$. L'exécution peut être réalisé avec un algorithme simple de type-(1+1) utilisant une puissance de mutation fitness dépendant. Une fois traduite dans le cas du budget fixe, notre algorithme trouve des solutions plus proches de l'optimum de 13% que celles des meilleurs algorithmes connus.Basé sur la puissance de mutation optimale analysée pour OneMaX, nous montrons qu'un choix auto-ajusté du nombre de bits à retourner atteint le même temps d'exécution (excepté $o(n)$ termes inférieurs) et le même (asymptotique) 13% amélioration de la fitness-distance par rapport au RLS. Le mécanisme d'ajustement doit apprendre de manière adaptative la puissance de mutation actuellement optimale des itérations précédentes. Cela vise à la fois à exploiter le fait que des problèmes généralement différents peuvent nécessiter des puissances de mutation différentes et que, pour un problème fixe, différentes puissances peuvent devenir optimales à différentes étapes du processus d'optimisation.Nous étendons ensuite notre stratégie d'auto-ajustement aux algorithmes évolutifs basés sur la population dans des espaces discrets de recherche. Grosso modo, il consiste à créer la moitié de la descendance avec un taux de mutation qui est deux fois plus élevé que le taux de mutation actuel et l'autre moitié avec la moitié du taux actuel. Le taux de mutation est ensuite mis à jour au taux utilisé dans cette sous-population qui contient la meilleure descendance. Nous analysons comment l'algorithme d'évolution $(1+lambda)$ avec ce taux de mutation auto-ajustable optimise la fonction de test OneMax. Nous montrons que cette version dynamique de $(1+lambda)$~EA trouve l'optimum dans un temps d'optimisation attendu (nombre d'évaluations de la fitness) de $O(nlambda/loglambda+nlog n)$. Le temps est asymptotiquement plus petit que le temps d'optimisation de l'EA classique $(1+lambda)$. Des travaux antérieurs montrent que cette performance est la meilleure possible parmi tous les algorithmes de boîtes noires sans biais unaire basés sur des mutations $lambda$-parallèles.Nous proposons et analysons également une version auto-réglage de l'algorithme évolutionnaire $(1,lambda)$ dans lequel le taux de mutation actuel fait partie de l'individu et donc également sujet à mutation. Une analyse d'exécution rigoureuse sur la fonction de référence OneMax révèle qu'un simple schéma de mutation pour le taux conduit à un temps d'optimisation attendu du meilleur $O(nlambda/loglambda+nlog n)$. Notre résultat montre que l'auto-réglage dans le calcul évolutif peut trouver automatiquement des paramètres optimaux complexes. En même temps, cela prouve qu'un schéma d'auto-ajustement relativement compliqué pour le taux de mutation peut être remplacé par notre schéma endogène simple. / It has been observed that the runtime of randomized search heuristics depend on one or more parameters. A number of results show an advantage of dynamic parameter settings, that is, the parameters of the algorithm are changed during its execution. In this work, we prove that the unary unbiased black-box complexity of the OneMax benchmark function class is $n ln(n) - cn pm o(n)$ for a constant $c$ which is between $0.2539$ and $0.2665$. This runtime can be achieved with a simple (1+1)-type algorithm using a fitness-dependent mutation strength. When translated into the fixed-budget perspective, our algorithm finds solutions which are roughly 13% closer to the optimum than those of the best previously known algorithms.Based on the analyzed optimal mutation strength for OneMax, we show that a self-adjusting choice of the number of bits to be flipped attains the same runtime (apart from $o(n)$ lower-order terms) and the same (asymptotic) 13% fitness-distance improvement over RLS. The adjusting mechanism is to adaptively learn the currently optimal mutation strength from previous iterations. This aims both at exploiting that generally different problems may need different mutation strengths and that for a fixed problem different strengths may become optimal in different stages of the optimization process.We then extend our self-adjusting strategy to population-based evolutionary algorithms in discrete search spaces. Roughly speaking, it consists of creating half the offspring with a mutation rate that is twice the current mutation rate and the other half with half the current rate. The mutation rate is then updated to the rate used in that subpopulation which contains the best offspring. We analyze how the $(1+lambda)$ evolutionary algorithm with this self-adjusting mutation rate optimizes the OneMax test function. We prove that this dynamic version of the $(1+lambda)$~EA finds the optimum in an expected optimization time (number of fitness evaluations) of $O(nlambda/loglambda+nlog n)$. This time is asymptotically smaller than the optimization time of the classic $(1+lambda)$ EA. Previous work shows that this performance is best-possible among all $lambda$-parallel mutation-based unbiased black-box algorithms.We also propose and analyze a self-adaptive version of the $(1,lambda)$ evolutionary algorithm in which the current mutation rate is part of the individual and thus also subject to mutation. A rigorous runtime analysis on the OneMax benchmark function reveals that a simple local mutation scheme for the rate leads to an expected optimization time of the best possible $O(nlambda/loglambda+nlog n)$. Our result shows that self-adaptation in evolutionary computation can find complex optimal parameter settings on the fly. At the same time, it proves that a relatively complicated self-adjusting scheme for the mutation rate can be replaced by our simple endogenous scheme.

Dans cette thèse, nous cherchons à répondre à une problématique formulée par la DGA Techniques navales pour surveiller une zone stratégique : planifier le déploiement spatial et temporel optimal d’un ensemble de capteurs de façon à maximiser les chances de détecter une cible mobile et intelligente. La cible est dite intelligente car elle est capable de détecter sous certaines conditions les menaces que représentent les capteurs et ainsi de réagir en adaptant son comportement. Les déploiements générés pouvant aussi avoir un coût élevé nous devons tenir compte de ce critère lorsque nous résolvons notre problématique. Il est important de noter que la résolution d’un problème de ce type requiert, selon les besoins, l’application d’une méthode d’optimisation mono-objectif voire multiobjectif. Jusqu’à présent, les travaux existants n’abordent pas la question du coût des déploiements proposés. De plus la plupart d’entre eux ne se concentrent que sur un seul aspect à la fois. Enfin, pour des raisons algorithmiques, les contraintes sont généralement discrétisées.Dans une première partie, nous présentons un algorithme qui permet de déterminer le déploiement spatio-temporel de capteurs le plus efficace sans tenir compte de son coût. Cette méthode est une application à l’optimisation de la méthode multiniveau généralisée.Dans la seconde partie, nous montrons d’abord que l’utilisation de la somme pondérée des deux critères permet d’obtenir des solutions sans augmenter le temps de calcul. Pour notre seconde approche, nous nous inspirons des algorithmes évolutionnaires d’optimisation multiobjectif et adaptons la méthode multiniveau généralisée à l’optimisation multiobjectif. / In this work, we propose a solution to a problem issued by the DGA Techniques navales in order to survey a strategic area: determining the optimal spatio-temporal deployment of sensors that will maximize the detection probability of a mobile and smart target. The target is said to be smart because it is capable of detecting the threat of the sensors under certain conditions and then of adapting its behaviour to avoid it. The cost of a deployment is known to be very expensive and therefore it has to be taken into account. It is important to note that the wide spectrum of applications within this field of research also reflects the need for a highly complex theoretical framework based on stochastic mono or multi-objective optimisation. Until now, none of the existing works have dealt with the cost of the deployments. Moreover, the majority only treat one type of constraint at a time. Current works mostly rely on operational research algorithms which commonly model the constraints in both discrete space and time.In the first part, we present an algorithm which computes the most efficient spatio-temporal deployment of sensors, but without taking its cost into account. This optimisation method is based on an application of the generalised splitting method.In the second part, we first use a linear combination of the two criteria. For our second approach, we use the evolutionary multiobjective optimisation framework to adapt the generalised splitting method to multiobjective optimisation. Finally, we compare our results with the results of the NSGA-II algorithm.

L’évaluation visuelle de lésions cutanées est l’analyse la plus couramment réalisée par les dermatologues. Ce diagnostic s’effectue principalement à l’œil nu et se base sur des critères tels que la taille, la forme, la symétrie mais principalement la couleur. Cependant, cette analyse est subjective car dépendante de l’expérience du praticien et des conditions d’utilisation. Nous proposons dans ce manuscrit (1) le développement d’une caméra multispectrale spécialement conçue pour un usage en dermatologie. Cette caméra multispectrale se base sur la technologie de roue porte-filtres composée de filtres interférentiels et d’un algorithme basé sur les réseaux de neurones générant un cube hyperspectral de données cutanées. Cet ensemble combine l’avantage d’un spectrophotomètre (information spectrale), et celui d’une caméra (information spatiale). Son intérêt est également de délivrer une information reproductible et indépendante des conditions d’acquisition. La mise en place d’un protocole d’acquisition de données de peaux saines issues de cinq des six phototypes existants a permis la validation de notre système en comparant les spectres générés par notre système avec des spectres théoriques acquis par un spectrophotomètre professionnel. (2) La réflectance spectrale de données de peau fournit une information précieuse, car directement liée à sa composition en chromophores. La mesure quantitative des propriétés optiques du tissu cutané peut être basée sur la modélisation de la propagation de la lumière dans la peau. Pour cela, nous nous sommes appuyés sur le modèle de Kubelka-Munk, auquel nous avons associé une méthode d’optimisation basée sur les algorithmes évolutionnaires. Cette dernière apporte une réponse à l’inversion de ce modèle. A partir de cette approche, la quantification de divers paramètres de la peau peut être obtenue, tels que la mélanine et l’hémoglobine. (3) La validation de cette méthodologie est effectuée sur des données pathologiques (vitiligo et melasma) et permet de quantifier une différence de composition entre zone saine et zone affectée sur une même image. / Visual evaluation of cutaneous lesions is the analysis the most commonly performedby dermatologists. This diagnostic is mainly done by naked eye and is based on criterionsuch as the size, shape, symmetry but principally on colour of the lesions. However, thisanalysis is subjective because it depends on the practician experience and the acquisitionconditions. We propose in this dissertation (1) the development of a multispectralcamera specifically dedicated for dermatological use. This device is based on a filterwheel composed of interferential filters and a neural network-based algorithm, generatinga hyperspectral cube of cutaneous data. This setting combines advantage of both spectrophotometer(spectral information) and digital camera (spatial information). Its maininterest is also to provide reproducible information which is independent of the acquisitionconditions. The setting-up of an acquisition protocol of healthy skin data from five of thesix exisiting skin phototypes allows the validation of our system by comparing spectragenerated by our system and theoretical spectra acquired by professional spectrophotometer.(2) Skin spectral reflectance provides precious information because it is directly linkedto the skin chromophore composition. Quantitative measure of cutaneous tissue opticalproperties can be based on the modelisation of light propagation in skin. For this purpose,we based our method on Kubelka-Munk model with which we associated an optimizationmethod based on evolutionary algorithm. This method helps for the model inversion.Using this approach, quantification of diverse parameters of skin can be obtained such asmelanin and haemoglobin. (3) The validation of this model is performed on disease skindata (vitiligo and melasma) and allows to quantify difference between healthy and affectedskin area within a single image.

Une tâche importante qui a été étudiée dans le contexte de données à forte dimensionnalité est la tâche connue sous le nom de subspace clustering. Le subspace clustering est généralement reconnu comme étant plus compliqué que le clustering standard, étant donné que cette tâche vise à détecter des groupes d’objets similaires entre eux (clusters), et qu’en même temps elle vise à trouver les sous-espaces où apparaissent ces similitudes. Le subspace clustering, ainsi que le clustering traditionnel ont été récemment étendus au traitement de flux de données en mettant à jour les modèles de clustering de façon incrémentale. Les différents algorithmes qui ont été proposés dans la littérature, reposent sur des bases algorithmiques très différentes. Parmi ces approches, les algorithmes évolutifs ont été sous-explorés, même si ces techniques se sont avérées très utiles pour traiter d’autres problèmes NP-difficiles. L’objectif de cette thèse a été de tirer parti des nouvelles connaissances issues de l’évolution afin de concevoir des algorithmes évolutifs qui traitent le problème du subspace clustering sur des jeux de données statiques ainsi que sur des flux de données dynamiques. Chameleoclust, le premier algorithme développé au cours de ce projet, tire partie du grand degré de liberté fourni par des éléments bio-inspirés tels qu’un génome de longueur variable, l’existence d’éléments fonctionnels et non fonctionnels et des opérateurs de mutation incluant des réarrangements chromosomiques. KymeroClust, le deuxième algorithme conçu dans cette thèse, est un algorithme de k-medianes qui repose sur un mécanisme évolutif important: la duplication et la divergence des gènes. SubMorphoStream, le dernier algorithme développé ici, aborde le problème du subspace clustering sur des flux de données dynamiques. Cet algorithme repose sur deux mécanismes qui jouent un rôle clef dans l’adaptation rapide des bactéries à des environnements changeants: l’amplification de gènes et l’absorption de matériel génétique externe. Ces algorithmes ont été comparés aux principales techniques de l’état de l’art, et ont obtenu des résultats compétitifs. En outre, deux applications appelées EvoWave et EvoMove ont été développés pour évaluer la capacité de ces algorithmes à résoudre des problèmes réels. EvoWave est une application d’analyse de signaux Wi-Fi pour détecter des contextes différents. EvoMove est un compagnon musical artificiel qui produit des sons basés sur le clustering des mouvements d’un danseur, décrits par des données provenant de capteurs de déplacements. / An important task that has been investigated in the context of high dimensional data is subspace clustering. This data mining task is recognized as more general and complicated than standard clustering, since it aims to detect groups of similar objects called clusters, and at the same time to find the subspaces where these similarities appear. Furthermore, subspace clustering approaches as well as traditional clustering ones have recently been extended to deal with data streams by updating clustering models in an incremental way. The different algorithms that have been proposed in the literature, rely on very different algorithmic foundations. Among these approaches, evolutionary algorithms have been under-explored, even if these techniques have proven to be valuable addressing other NP-hard problems. The aim of this thesis was to take advantage of new knowledge from evolutionary biology in order to conceive evolutionary subspace clustering algorithms for static datasets and dynamic data streams. Chameleoclust, the first algorithm developed in this work, takes advantage of the large degree of freedom provided by bio-like features such as a variable genome length, the existence of functional and non-functional elements and mutation operators including chromosomal rearrangements. KymeroClust, our second algorithm, is a k-medians based approach that relies on the duplication and the divergence of genes, a cornerstone evolutionary mechanism. SubMorphoStream, the last one, tackles the subspace clustering task over dynamic data streams. It relies on two important mechanisms that favor fast adaptation of bacteria to changing environments, namely gene amplification and foreign genetic material uptake. All these algorithms were compared to the main state-of-the-art techniques, obtaining competitive results. Results suggest that these algorithms are useful complementary tools in the analyst toolbox. In addition, two applications called EvoWave and EvoMove have been developed to assess the capacity of these algorithms to address real world problems. EvoWave is an application that handles the analysis of Wi-Fi signals to detect different contexts. EvoMove, the second one, is a musical companion that produces sounds based on the clustering of dancer moves captured using motion sensors.

L’objectif de ce projet de trois ans est de proposer des avancées conceptuelles et technologiques dans la résolution de problèmes d’ordonnancement du personnel. L’atteinte de cet objectif passe par la proposition de nouveaux algorithmes basés sur les métaheuristiques et leur implémentation sur les architectures de calcul haute performance. Ce projet s’inscrit en complémentarité du projet HORUS qui bénéficie d’une subvention ANR et qui réunit les expertises scientifiques de deux laboratoires universitaires spécialisés en optimisation et en calcul parallèle : l’équipe SysCom du laboratoire CReSTIC de l’URCA et l’équipe CaRO du laboratoire PRiSM de l’UVSQ. Les avancées technologiques proposées s’appuient également sur les moyens de calcul haute performance offerts par le Centre de Calcul Régional Champagne-Ardenne. / .Many academic and industrial optimization problems are multi-objective and have been of particular interest to researchers in recent years. These problems usually do not have a single optimal solution but a set of best trade-off solutions which form the so-called Pareto front in the objective space. In order to approximate the Pareto front, multi-objective evolutionary algorithms (MOEAs) have been largely investigated in the fields of continuous and combinatorial optimization. Contrary to some classical algorithms, MOEAs have the ability to provide a number of solutions in one single run and are less sensitive to the shape of the Pareto front.As they often require a high amount of computing resources to explore large portions of the search space and handle complex real-life constraints, MOEAs could greatly benefit from today's high-performance computing architectures. Although significant progress has been made in recent years in the design and improvement of parallel models for evolutionary algorithms, most of these models have limited scalability and ability to solve various problems. In fact, solving multi-objective combinatorial optimization problems efficiently on a large number of processors remains a challenge today.This thesis aims to propose an island model which is based on objective space division. The main features of the proposed model are the following (i) An organizer has a global view of the current search via a global archive (ii) Asynchronous cooperation between islands, especially for the exchange of local archives with the organizer to limit model overheads (iii)Control islands to guide the exploration of the search space and improve diversity (iv) A periodic use of a specific local search procedure to improve convergence. Extensive experiments have been conducted to evaluate the performance of the approach and more particularly of each component in the resolution of two classical combinatorial problems, the travelling salesman problem and quadratic assignment problem. Extensibility and quality of the solutions are analyzed compared to state-of-the-art parallel models.