• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 666
  • 315
  • 46
  • 1
  • 1
  • 1
  • 1
  • 1
  • Tagged with
  • 1026
  • 344
  • 215
  • 206
  • 201
  • 166
  • 139
  • 137
  • 116
  • 100
  • 88
  • 81
  • 76
  • 75
  • 73
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
31

Métaheuristiques pour l'optimisation multiobjectif : approches coopératives, prise en compte de l'incertitude et application en logistique / Metaheuristics for multiobjective optimisation : cooperative approaches, uncertainty handling and application in logistics

Liefooghe, Arnaud 08 December 2009 (has links)
De nombreux problèmes d'optimisation issus du monde réel. notamment dans le domaine de la logistique, doivent faire face à beaucoup de difficultés, En effet, ils sont souvent caractérisés par des espaces de recherche vastes et complexes, de multiples fonctions objectif contradictoires, et une foule d'incertitudes qui doivent être prises en compte, Les métaheuristiques sont des candidats naturels pour résoudre ces problèmes, ce qui les rend préférables aux méthodes d'optimisation classiques, Toutefois, le développent de métaheuristiques efficaces résulte en un processus d'ingénierie complexe, Le coeur de ce travail réside en la conception, l'implémentation et l'analyse expérimentale de métaheuristiques pour l'optimisation multiobjectif ainsi que leurs applications à des problèmes logistiques de tournées et d'ordonnancement. Tout d'abord, une vue unifiée de ces approches est présentée, puis intégrée dans une plateforme logicielle dédiée à leur implémentation, ParadisEO-MOEO, Ensuite, plusieurs approches de coopération, combinant des métaheuristiques pour l'optimisation multiobjectif, sont proposées, Enfin, la question de la prise en compte de l'incertitude est abordée dans le context de l'optimisation multiobjectif. / Many real-world optimization problems, especially in the field of logistics, have to face a lot of difficulties, Indeed, they are often characterized by large and complex search'spaces, multiple conflicting objective functions, and a host of uncertainties that have ta be taken into account. Metaheuristics are natural candidates ta solve those problems and make them preferable to classical optimization methods, However, the development of efficient metaheuristics results in a complex engineering process, The core subject of this work lies in the design, implementation and experimental analysis of metaheuristics for multiobjective optimization, together with theu applications to logis tic problems from routing and scheduling, Firstly, a unitïed view of such approaches is presented and then integrated into a software framework for their implementation, ParadisEO-MOEO, Next, sorne cooperative approaches combining metaheuristics for multiobjective optimization are proposed, At last, the issue of uncertainty handling is discussed in the context of multiobjective optimization.
32

Métaheuristiques parallèles sur GPU / Parallel metaheuristics on GPU

Luong, Thé Van 01 December 2011 (has links)
Les problèmes d'optimisation issus du monde réel sont souvent complexes et NP-difficiles. Leur modélisation est en constante évolution en termes de contraintes et d'objectifs, et leur résolution est coûteuse en temps de calcul. Bien que des algorithmes approchés telles que les métaheuristiques (heuristiques génériques) permettent de réduire la complexité de leur résolution, ces méthodes restent insuffisantes pour traiter des problèmes de grande taille. Au cours des dernières décennies, le calcul parallèle s'est révélé comme un moyen incontournable pour faire face à de grandes instances de problèmes difficiles d'optimisation. La conception et l'implémentation de métaheuristiques parallèles sont ainsi fortement influencées par l'architecture parallèle considérée. De nos jours, le calcul sur GPU s'est récemment révélé efficace pour traiter des problèmes coûteux en temps de calcul. Cette nouvelle technologie émergente est considérée comme extrêmement utile pour accélérer de nombreux algorithmes complexes. Un des enjeux majeurs pour les métaheuristiques est de repenser les modèles existants et les paradigmes de programmation parallèle pour permettre leurdéploiement sur les accélérateurs GPU. De manière générale, les problèmes qui se posent sont la répartition des tâches entre le CPU et le GPU, la synchronisation des threads, l'optimisation des transferts de données entre les différentes mémoires, les contraintes de capacité mémoire, etc. La contribution de cette thèse est de faire face à ces problèmes pour la reconception des modèles parallèles des métaheuristiques pour permettre la résolution des problèmes d'optimisation à large échelle sur les architectures GPU. Notre objectif est de repenser les modèles parallèles existants et de permettre leur déploiement sur GPU. Ainsi, nous proposons dans ce document une nouvelle ligne directrice pour la construction de métaheuristiques parallèles efficaces sur GPU. Le défi de cette thèse porte sur la conception de toute la hiérarchie des modèles parallèles sur GPU. Pour cela, des approches très efficaces ont été proposées pour l'optimisation des transferts de données entre le CPU et le GPU, le contrôle de threads, l'association entre les solutions et les threads, ou encore la gestion de la mémoire. Les approches proposées ont été expérimentées de façon exhaustive en utilisant cinq problèmes d'optimisation et quatre configurations GPU. En comparaison avec une exécution sur CPU, les accélérations obtenues vont jusqu'à 80 fois plus vite pour des grands problèmes d'optimisation combinatoire et jusqu'à 2000 fois plus vite pour un problème d'optimisation continue. Les différents travaux liés à cette thèse ont fait l'objet d'une douzaine publications comprenant la revue IEEE Transactions on Computers. / Real-world optimization problems are often complex and NP-hard. Their modeling is continuously evolving in terms of constraints and objectives, and their resolution is CPU time-consuming. Although near-optimal algorithms such as metaheuristics (generic heuristics) make it possible to reduce the temporal complexity of their resolution, they fail to tackle large problems satisfactorily. Over the last decades, parallel computing has been revealed as an unavoidable way to deal with large problem instances of difficult optimization problems. The design and implementation of parallel metaheuristics are strongly influenced by the computing platform. Nowadays, GPU computing has recently been revealed effective to deal with time-intensive problems. This new emerging technology is believed to be extremely useful to speed up many complex algorithms. One of the major issues for metaheuristics is to rethink existing parallel models and programming paradigms to allow their deployment on GPU accelerators. Generally speaking, the major issues we have to deal with are: the distribution of data processing between CPU and GPU, the thread synchronization, the optimization of data transfer between the different memories, the memory capacity constraints, etc. The contribution of this thesis is to deal with such issues for the redesign of parallel models of metaheuristics to allow solving of large scale optimization problems on GPU architectures. Our objective is to rethink the existing parallel models and to enable their deployment on GPUs. Thereby, we propose in this document a new generic guideline for building efficient parallel metaheuristics on GPU. Our challenge is to come out with the GPU-based design of the whole hierarchy of parallel models.In this purpose, very efficient approaches are proposed for CPU-GPU data transfer optimization, thread control, mapping of solutions to GPU threadsor memory management. These approaches have been exhaustively experimented using five optimization problems and four GPU configurations. Compared to a CPU-based execution, experiments report up to 80-fold acceleration for large combinatorial problems and up to 2000-fold speed-up for a continuous problem. The different works related to this thesis have been accepted in a dozen of publications, including the IEEE Transactions on Computers journal.
33

Etude de la sécurité des implémentations de couplage / On the security of pairing implementations

Lashermes, Ronan 29 September 2014 (has links)
Les couplages sont des algorithmes cryptographiques qui permettent de nouveaux protocoles de cryptographie à clé publique. Après une décennie de recherches sur des implémentations efficaces, ce qui permet maintenant d’exécuter un couplage en un temps raisonnable, nous nous sommes concentrés sur la sécurité de ces mêmes implémentations.Pour cela nous avons évalué la résistance des algorithmes de couplage contre les attaques en faute. Nous avons envoyé des impulsions électromagnétiques sur la puce calculant le couplage à des moments choisis. Cela nous a permis de remonter au secret cryptographique qu’est censé protéger l’algorithme de couplage. Cette étude fut à la fois théorique et pratique avec la mise en œuvre d’attaques en faute. Finalement, des contremesures ont été proposées pour pouvoir protéger l’algorithme dans le futur / Pairings are cryptographic algorithms allowing new protocols for public-key cryptography. After a decade of research which led to a dramatic improvement of the computation speed of pairings, we focused on the security of pairing implementations.For that purpose, we evaluated the resistance to fault attacks. We have sent electromagnetic pulses in the chip computing a pairing at a precise instant. It allowed us to recover the cryptographic secret which should be protected in the computation. Our study was both theoretical and practical; we did implement actual fault attacks. Finally, we proposed countermeasures in order to protect the algorithm in the future
34

Algorithmes exacts et exponentiels pour les problèmes NP-difficiles : domination, variantes et généralisations / Excat exponential time algorithms for NP-hard problems : domination, variants and generalizations

Liedloff, Mathieu 07 December 2007 (has links)
Les premiers algorithmes exacts exponentiels pour résoudre des problèmes NP-difficiles datent des années soixante. Ces dernières années ont vu un intérêt croissant pour la conception de tels algorithmes tout comme pour l'amélioration de la précision de l'analyse de leur temps d'exécution. Ils sont motivés par les larges applications de problèmes réputés difficiles et qui, sous l'hypothèse P 6= NP, n'admettent pas d'algorithme polynomial en calculant une solution exacte. Dans cette thèse on s'intéresse au problème classique de la domination dans un graphe. On étudie également plusieurs variantes et généralisations de ce problème fondamental. Nous proposons des algorithmes exponentiels pour déterminer un ensemble dominant de taille minimum sur les graphes c-denses, cordaux, 4-cordaux, faiblement cordaux, cercles et bipartis. Puis, nous étudions le problème de la clique dominante qui demande de trouver un ensemble dominant qui soit aussi une clique du graphe. Nous proposons un algorithme Brancher & Réduire qui détermine une clique dominante de taille minimum. L'analyse du temps d'exécution est réalisée en utilisant la technique Mesurer pour Conquérir. Nous donnons ensuite un algorithme général pour énumérer tous les ensembles ( %)-dominants d'un graphe en temps O(cn), avec c < 2, sous certaines conditions sur les ensembles et %, et établissons une borne supérieure combinatoire sur leur nombre. Finalement, nous nous intéressons à un problème de domination partielle et obtenons un algorithme pour le problème de la domination romaine. Grâce à un algorithme basé sur le paradigme de la Programmation Dynamique, nous proposons un algorithme pour le problème de la domination avec des puissances variables / The first exact exponential-time algorithms solving NP-hard problems date back to the sixties. The last years have seen an increasing interest for designing such algorithms as well as analysing their running time. The existence of many applications of well known hard problems is one of the main motivations. Moreover, under the hypothesis P 6= NP, apolynomial time algorithm for these problems does not exist. In this thesis, we deal with the classical domination problem in graphs. We are also interested in some variants and generalizations of this fondamental problem. We give exponential-time algorithms for computing a minimum dominating set on c-dense graphs, chordal graphs, 4-chordal graphs, weakly chordal graphs, circle graphs and bipartite graphs. Then, we study the dominating clique problem requiring to find a minimum dominating set inducing a clique of the graph. We provide a Branch & Reduce algorithm computing a minimum dominating clique. The analysis of the running time is done by using the Measure and Conquer technique. Afterwards, we propose a general algorithm for enumerating all (%)-dominating sets of a graph in time O(cn), with c < 2, under some assumptions on the sets and %. Subsequently, we establish a combinatorial upper bound on the number of such sets in a graph. Finally, we consider a partial dominating set problem and we give an algorithm for solving the Roman domination problem. Using the dynamic programming paradigm, we obtain an algorithm for the domination problem with flexible powers
35

Approches évolutionnaires pour la reconstruction de réseaux de régulation génétique par apprentissage de réseaux bayésiens / Learning bayesian networks with evolutionary approaches for the reverse-engineering of gene regulatory networks

Auliac, Cédric 24 September 2008 (has links)
De nombreuses fonctions cellulaires sont réalisées grâce à l'interaction coordonnée de plusieurs gènes. Identifier le graphe de ces interactions, appelé réseau de régulation génétique, à partir de données d'expression de gènes est l'un des objectifs majeurs de la biologie des systèmes. Dans cette thèse, nous abordons ce problème en choisissant de modéliser les relations entre gènes par un réseau bayésien. Se pose alors la question de l'apprentissage de la structure de ce type de modèle à partir de données qui sont en général peu nombreuses. Pour résoudre ce problème, nous recherchons parmi tous les modèles possibles le modèle le plus simple, expliquant le mieux les données. Pour cela, nous introduisons et étudions différents types d'algorithmes génétiques permettant d'explorer l'espace des modèles. Nous nous intéressons plus particulièrement aux méthodes de spéciation. ces dernières, en favorisant la diversité des solutions candidates considérées, empêchent l'algorithme de converger trop rapidement vers des optima locaux. Ces algorithmes génétiques sont comparés avec différentes méthodes d'apprentissage de structure de réseaux bayésiens, classiquement utilisées dans la littérature. Nous mettons ainsi en avant la pertinence des approches evolutionnaires pour l'apprentissage de ces graphes d'interactions. Enfin, nous les comparons à une classe alternative d'algorithmes évolutionnaires qui s'avère particulièrement prometteuse : les algorithmes à estimation de distribution. Tous ces algorithmes sont testés et comparés sur un modèle du réseau de régulation de l'insuline de 35 noeuds dont nous tirons des jeux de données synthétiques de taille modeste. / Inferring gene regulatory networks from data requires the development of algorithms devoted to structure extraction. When only static data are available, gene interactions may be modelled by a bayesian network that represents the presence of direct interactions from regulators to regulees by conditional probability distributions. In this work, we used enhanced evolutionary algorithms to stochastically evolve a set of candidate bayesian network structures and found the model that best fits data without prior knowledge. We proposed various evolutionary strategies suitable for the task and tested our choices using simulated data drawn from a given bio-realistic network of 35 nodes, the so-called insulin network, which has been used in the literature for benchmarking. We introduced a niching strategy that reinforces diversity through the population and avoided trapping of the algorithm in one local minimum in the early steps of learning. We compared our best evolutionary approach with various well known learning algorithms (mcmc, k2, greedy search, tpda, mmhc) devoted to bayesian network structure learning. Then, we compared our best genetic algorithm with another class of evolutionary algorithms : estimation of distribution algorithms. We show that an evolutionary approach enhanced by niching outperforms classical structure learning methods in elucidating the original model. Finally, it appears that estimation of distribution algorithms are a promising approach to extend this work. These results were obtained for the learning of a bio-realistic network and, more importantly, on various small datasets.
36

Pistage d'objets multiples dans le cas d'un lidar à faible résolution angulaire

Roy-Labbé, Maude 22 June 2021 (has links)
Ce mémoire présente une analyse des performances d'algorithmes de pistage dans le cas d'un lidar à faible résolution angulaire. Plus particulièrement, on s'intéresse à un système lidar composé de capteurs individuels couvrant chacun une région angulaire distincte. Les capteurs utilisés ont la particularité de mesurer uniquement la distance des objets rencontrés, limitant ainsi la résolution angulaire à leur faisceau. Les algorithmes ont été testés à l'aide de données de simulations basées sur le système lidar. Dans les cas de détections simples, un algorithme de pistage instantané basé sur un filtre de Kalman a été amplement suffisant. Pour des cas plus complexes, l'utilisation de la théorie des hypothèses multiples ( MHT pour multiple hypothesis theory ) a permis d'améliorer les résultats d'associations. Dans cette méthode, lorsqu'il y a une ambiguïté d'associations, les hypothèses probables sont considérées en parallèle jusqu'à ce que l'information reçue aux instants subséquents permette d'identifier l'association la plus probable. Pour le cas à l'étude, les résultats optimaux ont été obtenus pour un MHT considérant au plus 3 hypothèses à chaque instant et en attendant au plus 3 pas de temps pour prendre une décision. Globalement, les algorithmes présentés ont mieux réagi face aux fausses alarmes plutôt que face aux non détections. Une méthode permettant d'optimiser les temps de calcul des algorithmes a également été développée. Cette méthode se base sur l'algorithme de Murty et permet de passer d'une méthode d'association simple et rapide (ici l'algorithme d'associations par plus proches voisins)à une méthode d'associations plus complexe (ici par filtre de Kalman) seulement lorsqu'une ambiguïté est détectée dans l'association. Dans le cas d'une situation simple à deux cibles, des performances comparables à celle d'une association par filtre de Kalman ont été obtenues avec un temps de calcul de moins de 10% de celui nécessaire habituellement. / This thesis presents an analysis of the performance of tracking algorithms in the case of a lidar with low angular resolution. More particularly, we are interested in a lidar system composed of individual sensors each covering a distinct angular region. The sensors used have the particularity of measuring only the distance of the objects encountered, thus limiting the angular resolution to their beam. The algorithms were tested using simulation data based on the lidar system. In the case of simple detections, an instant tracking algorithm based on a Kalman filter was more than sufficient. For more complex cases, the use of multiple hypothesis theory (MHT) made it possible to improve tracking results. In this method, when there is an ambiguity in the tracking, the possible hypotheses are considered simultaneously until the information received at subsequent times makes it possible to identify the correct one. For the case under study, optimal results were obtained for an MHT considering at most 3 hypotheses at any time and waiting at most 3 time steps to make a decision. Overall, the algorithms presented reacted better to false alarms rather than to non-detections. A method for optimizing the calculation times of the algorithms has also been developed. This method is based on Murty's algorithm goes from a simple and fast tracking method (here by nearest neighbors) to a more complex association method (here using a Kalman lter) only when an ambiguity is detected. In the case of a simple situation with two targets, performances comparable to that of an association by Kalman filter were obtained with a calculation time of less than 10% of that usually required.
37

Priors PAC-Bayes avec covariance pleine qui dépendent de la distribution source

Alain, Mathieu 09 November 2022 (has links)
L'ambition du présent mémoire est la présentation d'un ensemble de principes appelés la théorie PAC-Bayes. L'approche offre des garanties de type PAC aux algorithmes d'apprentissage bayésiens généralisés. Le mémoire traite essentiellement des cas où la distribution prior dépend des données. Le mémoire est divisé en trois chapitres. Le premier chapitre détaille les notions de base en apprentissage automatique. Il s'agit d'idées nécessaires à la bonne compréhension des deux chapitres subséquents. Le deuxième chapitre présente et discute de la théorie PAC-Bayes. Finalement, le troisième chapitre aborde l'idée d'une garantie PAC-Bayes où le prior dépend des données. Il y a deux contributions principales. La première contribution est une formulation analytique du risque empirique espéré pour les distributions elliptiques. La seconde contribution est une extension du travail de Parrado-Hernández et al. (34). En effet, il s'agit du développement d'une garantie PAC-Bayes avec un prior espérance non sphérique. / The ambition of this thesis is to present a set of principles called the PAC-Bayes theory. The approach provides PAC-like guarantees for generalised Bayesian learning algorithms. This thesis deals essentially with cases where the prior distribution is data dependent. The paper is divided into three chapters. The first chapter details the core concepts of machine learning. These are ideas that are necessary for a good understanding of the two subsequent chapters. The second chapter presents and discusses the PAC-Bayes theory. Finally, the third chapter addresses the idea of a PAC-Bayes guarantee where the prior depend on the data. There are two main contributions. The first contribution is an analytical formulation of the empirical expected risk for elliptical distributions. The second contribution is an extension of the work of Parrado-Hernández et al. (34). Indeed, it is the development of a PAC-Bayes guarantee with a non-spherical prior expectation.
38

Priors PAC-Bayes avec covariance pleine qui dépendent de la distribution source

Alain, Mathieu 09 November 2022 (has links)
L'ambition du présent mémoire est la présentation d'un ensemble de principes appelés la théorie PAC-Bayes. L'approche offre des garanties de type PAC aux algorithmes d'apprentissage bayésiens généralisés. Le mémoire traite essentiellement des cas où la distribution prior dépend des données. Le mémoire est divisé en trois chapitres. Le premier chapitre détaille les notions de base en apprentissage automatique. Il s'agit d'idées nécessaires à la bonne compréhension des deux chapitres subséquents. Le deuxième chapitre présente et discute de la théorie PAC-Bayes. Finalement, le troisième chapitre aborde l'idée d'une garantie PAC-Bayes où le prior dépend des données. Il y a deux contributions principales. La première contribution est une formulation analytique du risque empirique espéré pour les distributions elliptiques. La seconde contribution est une extension du travail de Parrado-Hernández et al. (34). En effet, il s'agit du développement d'une garantie PAC-Bayes avec un prior espérance non sphérique. / The ambition of this thesis is to present a set of principles called the PAC-Bayes theory. The approach provides PAC-like guarantees for generalised Bayesian learning algorithms. This thesis deals essentially with cases where the prior distribution is data dependent. The paper is divided into three chapters. The first chapter details the core concepts of machine learning. These are ideas that are necessary for a good understanding of the two subsequent chapters. The second chapter presents and discusses the PAC-Bayes theory. Finally, the third chapter addresses the idea of a PAC-Bayes guarantee where the prior depend on the data. There are two main contributions. The first contribution is an analytical formulation of the empirical expected risk for elliptical distributions. The second contribution is an extension of the work of Parrado-Hernández et al. (34). Indeed, it is the development of a PAC-Bayes guarantee with a non-spherical prior expectation.
39

Pistage d'objets multiples dans le cas d'un lidar à faible résolution angulaire

Roy-Labbé, Maude 22 June 2021 (has links)
Ce mémoire présente une analyse des performances d'algorithmes de pistage dans le cas d'un lidar à faible résolution angulaire. Plus particulièrement, on s'intéresse à un système lidar composé de capteurs individuels couvrant chacun une région angulaire distincte. Les capteurs utilisés ont la particularité de mesurer uniquement la distance des objets rencontrés, limitant ainsi la résolution angulaire à leur faisceau. Les algorithmes ont été testés à l'aide de données de simulations basées sur le système lidar. Dans les cas de détections simples, un algorithme de pistage instantané basé sur un filtre de Kalman a été amplement suffisant. Pour des cas plus complexes, l'utilisation de la théorie des hypothèses multiples ( MHT pour multiple hypothesis theory ) a permis d'améliorer les résultats d'associations. Dans cette méthode, lorsqu'il y a une ambiguïté d'associations, les hypothèses probables sont considérées en parallèle jusqu'à ce que l'information reçue aux instants subséquents permette d'identifier l'association la plus probable. Pour le cas à l'étude, les résultats optimaux ont été obtenus pour un MHT considérant au plus 3 hypothèses à chaque instant et en attendant au plus 3 pas de temps pour prendre une décision. Globalement, les algorithmes présentés ont mieux réagi face aux fausses alarmes plutôt que face aux non détections. Une méthode permettant d'optimiser les temps de calcul des algorithmes a également été développée. Cette méthode se base sur l'algorithme de Murty et permet de passer d'une méthode d'association simple et rapide (ici l'algorithme d'associations par plus proches voisins)à une méthode d'associations plus complexe (ici par filtre de Kalman) seulement lorsqu'une ambiguïté est détectée dans l'association. Dans le cas d'une situation simple à deux cibles, des performances comparables à celle d'une association par filtre de Kalman ont été obtenues avec un temps de calcul de moins de 10% de celui nécessaire habituellement. / This thesis presents an analysis of the performance of tracking algorithms in the case of a lidar with low angular resolution. More particularly, we are interested in a lidar system composed of individual sensors each covering a distinct angular region. The sensors used have the particularity of measuring only the distance of the objects encountered, thus limiting the angular resolution to their beam. The algorithms were tested using simulation data based on the lidar system. In the case of simple detections, an instant tracking algorithm based on a Kalman filter was more than sufficient. For more complex cases, the use of multiple hypothesis theory (MHT) made it possible to improve tracking results. In this method, when there is an ambiguity in the tracking, the possible hypotheses are considered simultaneously until the information received at subsequent times makes it possible to identify the correct one. For the case under study, optimal results were obtained for an MHT considering at most 3 hypotheses at any time and waiting at most 3 time steps to make a decision. Overall, the algorithms presented reacted better to false alarms rather than to non-detections. A method for optimizing the calculation times of the algorithms has also been developed. This method is based on Murty's algorithm goes from a simple and fast tracking method (here by nearest neighbors) to a more complex association method (here using a Kalman lter) only when an ambiguity is detected. In the case of a simple situation with two targets, performances comparable to that of an association by Kalman filter were obtained with a calculation time of less than 10% of that usually required.
40

Contribution à l'étude de grands systèmes non linéaires : comportement d'algorithmes itératifs, stabilité de systèmes continus.

Spiteri, Pierre, January 1900 (has links)
Th.--Sci. math.--Besançon, 1984. N°: 183.

Page generated in 0.1128 seconds